In computer science, an LL parser (Left-to-right, leftmost derivation) 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.[1] 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.[2] [3] [4] 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.[5] [6] 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.[7] 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.[8] 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),[9] LL(k) grammars were introduced by Stearns and Lewis (1969).[10]
For a given context-free grammar, the parser attempts to find the leftmost derivation.Given an example grammar
G
S\toE
E\to(E+E)
E\toi
the leftmost derivation for
w=((i+i)+i)
S \overset{(1)}{ ⇒ } E \overset{(2)}{ ⇒ } (E+E) \overset{(2)}{ ⇒ } ((E+E)+E) \overset{(3)}{ ⇒ } ((i+E)+E) \overset{(3)}{ ⇒ } ((i+i)+E) \overset{(3)}{ ⇒ } ((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)}{ ⇒ } E \overset{(?)}{ ⇒ } ?
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
(
Generally, an
LL(k)
k
LL(k)
k
k
LL(k)
LL(k+1)
We can use the above analysis to give the following formal definition:
Let
G
k\ge1
G
LL(k)
S ⇒ … ⇒ wA\alpha ⇒ … ⇒ w\beta\alpha ⇒ … ⇒ wu
S ⇒ … ⇒ wA\alpha ⇒ … ⇒ w\gamma\alpha ⇒ … ⇒ wv
the following condition holds: the prefix of the string
u
k
v
k
\beta = \gamma
In this definition,
S
A
w
u
v
\alpha
\beta
\gamma
The
LL(k)
k
The stack alphabet is
\Gamma=N\cup\Sigma
N
\Sigma
\$
[ S \$ ]
X
\alpha
X\inN
X\to\alpha
\epsilon
λ
X
X\in\Sigma
x
x ≠ X
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:
X
|w|\lek
X\to\alpha
\epsilon
To explain an LL(1) parser's workings we will consider the following small LL(1) grammar:
and parse the following input:
(a + a)
An LL(1) parsing table for a grammar has a row for each of the non-terminals and a column for each terminal (including the special terminal, represented here as $, that is used to indicate the end of the input stream).
Each cell of the table may point to at most one rule of the grammar (identified by its number). For example, in the parsing table for the above grammar, the cell for the non-terminal 'S' and terminal '(' points to the rule number 2:
| ( | ) | a | + | $ | ||
|---|---|---|---|---|---|---|
| S | 2 | 1 | ||||
| F | 3 |
The algorithm to construct a parsing table is described in a later section, but first let's see how the parser uses the parsing table to process its input.
In each step, the parser reads the next-available symbol from the input stream, and the top-most symbol from the stack. If the input symbol and the stack-top symbol match, the parser discards them both, leaving only the unmatched symbols in the input stream and on the stack.
Thus, in its first step, the parser reads the input symbol '(
['''(''', S, '''+''', F, ''')''', '''$''' ]
In the second step, the parser removes the '(
[S, '''+''', F, ''')''', '''$''' ]
Now the parser has an 'a' on its input stream and an 'S' as its stack top. The parsing table instructs it to apply rule (1) from the grammar and write the rule number 1 to the output stream. The stack becomes:
[F, '''+''', F, ''')''', '''$''' ]
The parser now has an 'a' on its input stream and an 'F' as its stack top. The parsing table instructs it to apply rule (3) from the grammar and write the rule number 3 to the output stream. The stack becomes:
['''a''', '''+''', F, ''')''', '''$''' ]
The parser now has an '
[F, ''')''', '''$''' ]
In the next three steps the parser will replace 'F' on the stack by 'a', write the rule number 3 to the output stream and remove the 'a' and ')' from both the stack and the input stream. The parser thus ends with '$' on both its stack and its input stream.
In this case the parser will report that it has accepted the input string and write the following list of rule numbers to the output stream:
[2, 1, 3, 3 ]
This is indeed a list of rules for a leftmost derivation of the input string, which is:
S → ( S + F ) → ( F + F ) → (a + F ) → (a + a)
Below follows a C++ implementation of a table-based LL parser for the example language:
enum Symbols ;
/*Converts a valid token to the corresponding terminal symbol
Symbols lexer(char c)
int main(int argc, char **argv)
TERM = 0RULE = 1
T_LPAR = 0T_RPAR = 1T_A = 2T_PLUS = 3T_END = 4T_INVALID = 5
N_S = 0N_F = 1
table = 1, -1, 0, -1, -1, -1, [-1, -1, 2, -1, -1, -1]]
RULES = (RULE, N_F), [(TERM, T_LPAR), (RULE, N_S), (TERM, T_PLUS), (RULE, N_F), (TERM, T_RPAR)], [(TERM, T_A)]]
stack = [(TERM, T_END), (RULE, N_S)]
def lexical_analysis(inputstring: str) -> list: print("Lexical analysis") tokens = [] for c in inputstring: if c
"(": tokens.append(T_LPAR) elif c
"a": tokens.append(T_A) else: tokens.append(T_INVALID) tokens.append(T_END) print(tokens) return tokens
def syntactic_analysis(tokens: list) -> None: print("Syntactic analysis") position = 0 while len(stack) > 0: (stype, svalue) = stack.pop token = tokens[position] if stype
token: position += 1 print("pop", svalue) if token
RULE: print("svalue", svalue, "token", token) rule = table[svalue][token] print("rule", rule) for r in reversed(RULES[rule]): stack.append(r) print("stack", stack)
inputstring = "(a+a)"syntactic_analysis(lexical_analysis(inputstring))
As can be seen from the example, the parser performs three types of steps depending on whether the top of the stack is a nonterminal, a terminal or the special symbol $:
These steps are repeated until the parser stops, and then it will have either completely parsed the input and written a leftmost derivation to the output stream or it will have reported an error.
In order to fill the parsing table, we have to establish what grammar rule the parser should choose if it sees a nonterminal A on the top of its stack and a symbol a on its input stream.It is easy to see that such a rule should be of the form A → w and that the language corresponding to w should have at least one string starting with a.For this purpose we define the First-set of w, written here as Fi(w), as the set of terminals that can be found at the start of some string in w, plus ε if the empty string also belongs to w.Given a grammar with the rules A1 → w1, …, An → wn, we can compute the Fi(wi) and Fi(Ai) for every rule as follows:
The result is the least fixed point solution to the following system:
where, for sets of words U and V, the truncated product is defined by
U ⋅ V=\{(uv):1\midu\inU,v\inV\}
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:
This provides the least fixed point solution to the following system:
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 a ∈ Fi(w)·Fo(A).
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 construction for LL(1) parsers can be adapted to LL(k) for k > 1 with the following modifications:
U ⋅ V=\{(uv):k\midu\inU,v\inV\}
⋅
⋅
Until the mid-1990s, it was widely believed that (for k > 1) was impractical,[11] 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.
As described in the introduction, LL(1) parsers recognize languages that have LL(1) grammars, which are a special case of context-free grammars; LL(1) parsers cannot recognize all context-free languages. The LL(1) languages are a proper subset of the LR(1) languages, which in turn are a proper subset of all context-free languages. In order for a context-free grammar to be an LL(1) grammar, certain conflicts must not arise, which we describe in this section.
Let A be a non-terminal. FIRST(A) is (defined to be) the set of terminals that can appear in the first position of any string derived from A. FOLLOW(A) is the union over:[12]
There are two main types of LL(1) conflicts:
The FIRST sets of two different grammar rules for the same non-terminal intersect.An example of an LL(1) FIRST/FIRST conflict: S -> E | E 'a' E -> 'b' | εFIRST(E) = and FIRST(E a) =, so when the table is drawn, there is conflict under terminal b of production rule S.
Left recursion will cause a FIRST/FIRST conflict with all alternatives. E -> E '+' term | alt1 | alt2
The FIRST and FOLLOW set of a grammar rule overlap. With an empty string (ε) in the FIRST set, it is unknown which alternative to select.An example of an LL(1) conflict: S -> A 'a' 'b' A -> 'a' | εThe FIRST set of A is, and the FOLLOW set is .
A common left-factor is "factored out". A -> X | X Y Zbecomes A -> X B B -> Y Z | εCan be applied when two alternatives start with the same symbol like a FIRST/FIRST conflict.
Another example (more complex) using above FIRST/FIRST conflict example: S -> E | E 'a' E -> 'b' | εbecomes (merging into a single non-terminal) S -> 'b' | ε | 'b' 'a' | 'a'then through left-factoring, becomes S -> 'b' E | E E -> 'a' | ε
Substituting a rule into another rule to remove indirect or FIRST/FOLLOW conflicts.Note that this may cause a FIRST/FIRST conflict.
See.[13]
For a general method, see removing left recursion.A simple example for left recursion removal:The following production rule has left recursion on E E -> E '+' T E -> TThis rule is nothing but list of Ts separated by '+'. In a regular expression form T ('+' T)*.So the rule could be rewritten as E -> T Z Z -> '+' T Z Z -> εNow there is no left recursion and no conflicts on either of the rules.
However, not all context-free grammars have an equivalent LL(k)-grammar, e.g.: S -> A | B A -> 'a' A 'b' | ε B -> 'a' B 'b' 'b' | εIt can be shown that there does not exist any LL(k)-grammar accepting the language generated by this grammar.