{
  "id": "enwiki-001378825386",
  "slug": "ll-parser",
  "title": "LL parser",
  "qid": "",
  "lead": "In computer science, an LL parser is a top-down parser for a restricted context-free language. It parses the input from Left to right, performing Leftmost derivation of the sentence. An LL parser is called an LL(k) parser if it uses k tokens of lookahead when parsing a sentence. A grammar is called an LL(k) grammar if an LL(k) parser can be constructed from it. A formal language is called an LL(k) language if it has an LL(k) grammar. The set of LL(k) languages is properly contained in that of LL(k+1) languages, for each k ≥ 0. A corollary of this is that not all context-free languages can be recognized by an LL(k) parser. An LL parser is called LL-regular (LLR) if it parses an LL-regular language. The class of LLR grammars contains every LL(k) grammar for every k. For every LLR grammar there exists an LLR parser that parses the grammar in linear time. Two nomenclative outlier parser types are LL(*) and LL(finite). A parser is called LL(*)/LL(finite) if it uses the LL(*)/LL(finite) parsing strategy. LL(*) and LL(finite) parsers are functionally closer to PEG parsers. An LL(finite) parser can parse an arbitrary LL(k) grammar optimally in the amount of lookahead and lookahead comparisons. The class of grammars parsable by the LL(*) strategy encompasses some context-sensitive languages due to the use of syntactic and semantic predicates and has not been identified.…",
  "body": "In computer science, an LL parser is a top-down parser for a restricted context-free language. It parses the input from Left to right, performing Leftmost derivation of the sentence. An LL parser is called an LL(k) parser if it uses k tokens of lookahead when parsing a sentence. A grammar is called an LL(k) grammar if an LL(k) parser can be constructed from it. A formal language is called an LL(k) language if it has an LL(k) grammar. The set of LL(k) languages is properly contained in that of LL(k+1) languages, for each k&nbsp;≥&nbsp;0. A corollary of this is that not all context-free languages can be recognized by an LL(k) parser. An LL parser is called LL-regular (LLR) if it parses an LL-regular language. The class of LLR grammars contains every LL(k) grammar for every k. For every LLR grammar there exists an LLR parser that parses the grammar in linear time. Two nomenclative outlier parser types are LL(*) and LL(finite). A parser is called LL(*)/LL(finite) if it uses the LL(*)/LL(finite) parsing strategy. LL(*) and LL(finite) parsers are functionally closer to PEG parsers. An LL(finite) parser can parse an arbitrary LL(k) grammar optimally in the amount of lookahead and lookahead comparisons. The class of grammars parsable by the LL(*) strategy encompasses some context-sensitive languages due to the use of syntactic and semantic predicates and has not been identified. It has been suggested that LL(*) parsers are better thought of as TDPL parsers. Against the popular misconception, LL(*) parsers are not LLR in general, and are guaranteed by construction to perform worse on average (super-linear against linear time) and far worse in the worst-case (exponential against linear time). LL grammars, particularly LL(1) grammars, are of great practical interest, as parsers for these grammars are easy to construct, and many computer languages are designed to be LL(1) for this reason. LL parsers may be table-based, i.e. similar to LR parsers, but LL grammars can also be parsed by recursive descent parsers. According to Waite and Goos (1984), LL(k) grammars were introduced by Stearns and Lewis (1969). the leftmost derivation for w = ((i+i)+i) is: S\\ \\overset{(1)}{\\Rightarrow}\\ E\\ \\overset{(2)}{\\Rightarrow}\\ (E+E)\\ \\overset{(2)}{\\Rightarrow}\\ ((E+E)+E)\\ \\overset{(3)}{\\Rightarrow}\\ ((i+E)+E)\\ \\overset{(3)}{\\Rightarrow}\\ ((i+i)+E)\\ \\overset{(3)}{\\Rightarrow}\\ ((i+i)+i) Generally, there are multiple possibilities when selecting a rule to expand the leftmost non-terminal. In step 2 of the previous example, the parser must choose whether to apply rule 2 or rule 3: S\\ \\overset{(1)}{\\Rightarrow}\\ E\\ \\overset{(?)}{\\Rightarrow}\\ ? To be efficient, the parser must be able to make this choice deterministically when possible, without backtracking. For some grammars, it can do this by peeking on the unread input (without reading). In our example, if the parser knows that the next unread symbol is (, the only correct rule that can be used is 2. Generally, an LL(k) parser can look ahead at k symbols. However, given a grammar, the problem of determining if there exists a LL(k) parser for some k that recognizes it is undecidable. For each k, there is a language that cannot be recognized by an LL(k) parser, but can be by an parser. We can use the above analysis to give the following formal definition: Let G be a context-free grammar and . We say that G is LL(k), if for any two leftmost derivations: S\\ \\Rightarrow\\ \\cdots\\ \\Rightarrow\\ wA\\alpha\\ \\Rightarrow\\ \\cdots\\ \\Rightarrow\\ w\\beta\\alpha\\ \\Rightarrow\\ \\cdots\\ \\Rightarrow\\ wu S\\ \\Rightarrow\\ \\cdots\\ \\Rightarrow\\ wA\\alpha\\ \\Rightarrow\\ \\cdots\\ \\Rightarrow\\ w\\gamma\\alpha\\ \\Rightarrow\\ \\cdots\\ \\Rightarrow\\ wv the following condition holds: the prefix of the string u of length k equals the prefix of the string v of length k implies \\beta = \\gamma . In this definition, S is the start symbol and A any non-terminal. The already derived input w , and yet unread u and v are strings of terminals. The Greek letters \\alpha , \\beta and \\gamma represent any string of both terminals and non-terminals (possibly empty). The prefix length corresponds to the lookahead buffer size, and the definition says that this buffer is enough to distinguish between any two derivations of different words. The stack alphabet is \\Gamma = N \\cup \\Sigma , where: N is the set of non-terminals; \\Sigma the set of terminal (input) symbols with a special end-of-input (EOI) symbol $. The parser stack initially contains the starting symbol above the EOI: . During operation, the parser repeatedly replaces the symbol X on top of the stack: with some \\alpha , if X \\in N and there is a rule X \\to \\alpha ; with \\epsilon (in some notations \\lambda ), i.e. X is popped off the stack, if X \\in \\Sigma . In this case, an input symbol x is read and if x \\neq X , the parser rejects the input. If the last symbol to be removed from the stack is the EOI, the parsing is successful; the automaton accepts via an empty stack. The states and the transition function are not explicitly given; they are specified (generated) using a more convenient parse table instead. The table provides the following mapping: row: top-of-stack symbol X column: ≤ k lookahead buffer contents cell: rule number for X \\to \\alpha or \\epsilon If the parser cannot perform a valid transition, the input is rejected (empty cells). To make the table more compact, only the non-terminal rows are commonly displayed, since the action is the same for terminals. include include include enum Symbols { // the symbols: // Terminal symbols: TS_L_PARENS, // ( TS_R_PARENS, // ) TS_A, // a TS_PLUS, // + TS_EOS, // $, in this case corresponds to '\\0' TS_INVALID, // invalid token // Non-terminal symbols: NTS_S, // S NTS_F // F }; /* Converts a valid token to the corresponding terminal symbol / Symbols lexer(char c) { switch (c) { case '(': return TS_L_PARENS; case ')': return TS_R_PARENS; case 'a': return TS_A; case '+': return TS_PLUS; case '\\0': return TS_EOS; // end of stack: the $ terminal symbol default: return TS_INVALID; } } int main(int argc, char **argv) { using namespace std; if (argc pair to action map > table; stack ss; // symbol stack char *p; // input buffer // initialize the symbols stack ss.push(TS_EOS); // terminal, $ ss.push(NTS_S); // non-terminal, S // initialize the symbol stream cursor p = &argv[1][0]; // set up the parsing table table[NTS_S][TS_L_PARENS] = 2; table[NTS_S][TS_A] = 1; table[NTS_F][TS_A] = 3; while (ss.size() > 0) { if (lexer(*p) == ss.top()) { cout from enum import Enum from collections.abc import Generator class Term(Enum): pass class Rule(Enum): pass All constants are indexed from 0 class Terminal(Term): LPAR = 0 RPAR = 1 A = 2 PLUS = 3 END = 4 INVALID = 5 def __str__(self): return f\"T_{self.name}\" class NonTerminal(Rule): S = 0 F = 1 def __str__(self): return f\"N_{self.name}\" Parse table table = [[1, -1, 0, -1, -1, -1], [-1, -1, 2, -1, -1, -1 RULES = [ [NonTerminal.F], [ Terminal.LPAR, NonTerminal.S, Terminal.PLUS, NonTerminal.F, Terminal.RPAR, ], [Terminal.A], ] stack = [Terminal.END, NonTerminal.S] def lexical_analysis(input_string: str) -> Generator[Terminal]: print(\"Lexical analysis\") for c in input_string: match c: case \"a\": yield Terminal.A case \"+\": yield Terminal.PLUS case \"(\": yield Terminal.LPAR case \")\": yield Terminal.RPAR case _: yield Terminal.INVALID yield Terminal.END def syntactic_analysis(tokens: list[Terminal]) -> None: print(\"tokens:\", end=\" \") print(*tokens, sep=\", \") print(\"Syntactic analysis\") position = 0 while stack: svalue = stack.pop() token = tokens[position] if isinstance(svalue, Term): if svalue == token: position += 1 print(\"pop\", svalue) if token == Terminal.END: print(\"input accepted\") else: raise ValueError(\"bad term on input:\", str(token)) elif isinstance(svalue, Rule): print(f\"{svalue = !s}, {token = !s}\") rule = table[svalue.value][token.value] print(f\"{rule = }\") for r in reversed(RULES[rule]): stack.append(r) print(\"stacks:\", end=\" \") print(*stack, sep=\", \") if __name__ == \"__main__\": inputstring = \"(a+a)\" syntactic_analysis(list(lexical_analysis(inputstring))) Outputs: Fi(ε) = { ε } add Fi(w i ) to Fi(A i ) for every rule A i → w i do steps 2 and 3 until all Fi sets stay the same. The result is the least fixed point solution to the following system: for each rule A → w for each terminal a for all words w 0 and w 1 where, for sets of words U and V, the truncated product is defined by U \\cdot V = \\{ (uv):1 \\mid u \\in U, v \\in V \\} , and w:1 denotes the initial length-1 prefix of words w of length 2 or more, or w, itself, if w has length 0 or 1. Unfortunately, the First-sets are not sufficient to compute the parsing table. This is because a right-hand side w of a rule might ultimately be rewritten to the empty string. So the parser should also use the rule A → w if ε is in Fi(w) and it sees on the input stream a symbol that could follow A. Therefore, we also need the Follow-set of A, written as Fo(A) here, which is defined as the set of terminals a such that there is a string of symbols αAaβ that can be derived from the start symbol. We use $ as a special terminal indicating end of input stream, and S as start symbol. Computing the Follow-sets for the nonterminals in a grammar can be done as follows: initialize Fo(S) with { $ } and every other Fo(A i ) with the empty set if there is a rule of the form A j → wA i , then if the terminal a is in Fi( ), then add a to Fo(A i ) if ε is in Fi( ), then add Fo(A j ) to Fo(A i ) if w' has length 0, then add Fo(A j ) to Fo(A i ) repeat step 2 until all Fo sets stay the same. This provides the least fixed point solution to the following system: for each rule of the form Now we can define exactly which rules will appear where in the parsing table. If T[A, a] denotes the entry in the table for nonterminal A and terminal a, then T[A,a] contains the rule A → w if and only if a is in Fi(w) or ε is in Fi(w) and a is in Fo(A). Equivalently: T[A, a] contains the rule A → w for each If the table contains at most one rule in every one of its cells, then the parser will always know which rule it has to use and can therefore parse strings without backtracking. It is in precisely this case that the grammar is called an LL(1) grammar. the truncated product is defined U \\cdot V = \\{ (uv):k \\mid u \\in U, v \\in V \\} , where w:k denotes the initial length-k prefix of words of length > k, or w, itself, if w has length k or less, Fo(S) = {$ k } Apply Fi(αβ) = Fi(α) ⋅ Fi(β) also in step 2 of the Fi construction given for LL(1). In step 2 of the Fo construction, for A j → wA i w simply add Fi( )·Fo(A j ) to Fo(A i ). where an input is suffixed by k end-markers $, to fully account for the k lookahead context. This approach eliminates special cases for ε, and can be applied equally well in the LL(1) case. Until the mid-1990s, it was widely believed that (for k > 1) was impractical, since the parser table would have exponential size in k in the worst case. This perception changed gradually after the release of the Purdue Compiler Construction Tool Set around 1992, when it was demonstrated that many programming languages can be parsed efficiently by an LL(k) parser without triggering the worst-case behavior of the parser. Moreover, in certain cases LL parsing is feasible even with unlimited lookahead. By contrast, traditional parser generators like yacc use LALR(1) parser tables to construct a restricted LR parser with a fixed one-token lookahead. FIRST(E) = {b, ε} and FIRST(E a) = , so when the table is drawn, there is conflict under terminal b of production rule S.",
  "categories": [
    "22904498",
    "22911470",
    "22929053",
    "23118434",
    "23603337",
    "24745122",
    "25257581",
    "27395026",
    "27954162",
    "37160764",
    "61223478",
    "68384674"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1378825386",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1791272129.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001378825386",
    "type": "webpage",
    "title": "LL parser",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/ll-parser",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001378825386",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1378825386",
    "note": "Immutable snapshot enwiki-001378825386"
  }
}