LL parser

For a given context-free grammar, the parser attempts to find the leftmost derivation. Given an example grammar ${\displaystyle G}$:

1. ${\displaystyle S\to E}$
2. ${\displaystyle E\to (E+E)}$
3. ${\displaystyle E\to i}$

the leftmost derivation for ${\displaystyle w=((i+i)+i)}$ is:

${\displaystyle 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:

${\displaystyle 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 ${\displaystyle (}$ , the only correct rule that can be used is 2.

Generally, an ${\displaystyle LL(k)}$ parser can look ahead at ${\displaystyle k}$ symbols. However, given a grammar, the problem of determining if there exists a ${\displaystyle LL(k)}$ parser for some ${\displaystyle k}$ that recognizes it is undecidable. For each ${\displaystyle k}$, there is a language that cannot be recognized by an ${\displaystyle LL(k)}$ parser, but can be by an ${\displaystyle LL(k+1)}$.

We can use the above analysis to give the following formal definition:

Let ${\displaystyle G}$ be a context-free grammar and ${\displaystyle k\geq 1}$. We say that ${\displaystyle G}$ is ${\displaystyle LL(k)}$, if and only if for any two leftmost derivations:

1. ${\displaystyle S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\beta \alpha \ \Rightarrow \ \cdots \ \Rightarrow \ wu}$
2. ${\displaystyle 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 ${\displaystyle u}$ of length ${\displaystyle k}$ equals the prefix of the string ${\displaystyle v}$ of length ${\displaystyle k}$ implies ${\displaystyle \beta \ =\ \gamma }$.

In this definition, ${\displaystyle S}$ is the start symbol and ${\displaystyle A}$ any non-terminal. The already derived input ${\displaystyle w}$, and yet unread ${\displaystyle u}$ and ${\displaystyle v}$ are strings of terminals. The Greek letters ${\displaystyle \alpha }$, ${\displaystyle \beta }$ and ${\displaystyle \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 ${\displaystyle LL(k)}$ parser is a deterministic pushdown automaton with the ability to peek on the next ${\displaystyle k}$ input symbols without reading. This peek capability can be emulated by storing the lookahead buffer contents in the finite state space, since both buffer and input alphabet are finite in size. As a result, this does not make the automaton more powerful, but is a convenient abstraction.

The stack alphabet is ${\displaystyle \Gamma =N\cup \Sigma }$, where:

• ${\displaystyle N}$ is the set of non-terminals;
• ${\displaystyle \Sigma }$ the set of terminal (input) symbols with a special end-of-input (EOI) symbol ${\displaystyle \$}$.

The parser stack initially contains the starting symbol above the EOI: ${\displaystyle [\ S\ \$\ ]}$. During operation, the parser repeatedly replaces the symbol ${\displaystyle X}$ on top of the stack:

• with some ${\displaystyle \alpha }$, if ${\displaystyle X\in N}$ and there is a rule ${\displaystyle X\to \alpha }$;
• with ${\displaystyle \epsilon }$ (in some notations ${\displaystyle \lambda }$), i.e. ${\displaystyle X}$ is popped off the stack, if ${\displaystyle X\in \Sigma }$. In this case, an input symbol ${\displaystyle x}$ is read and if ${\displaystyle 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 ${\displaystyle X}$
• column: ${\displaystyle |w|\leq k}$ lookahead buffer contents
• cell: rule number for ${\displaystyle X\to \alpha }$ or ${\displaystyle \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.

[ (, S, +, F, ), $ ]

[ S, +, F, ), $ ]

[ F, +, F, ), $ ]

[ a, +, F, ), $ ]

[ F, ), $ ]

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:

#include <iostream>
#include <map>
#include <stack>

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 < 2)
	{
		cout << "usage:\n\tll '(a+a)'" << endl;
		return 0;
	}

	// LL parser table, maps < non-terminal, terminal> pair to action
	map< Symbols, map<Symbols, int> > table;
	stack<Symbols>	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 << "Matched symbols: " << lexer(*p) << endl;
			p++;
			ss.pop();
		}
		else
		{
			cout << "Rule " << table[ss.top()][lexer(*p)] << endl;
			switch (table[ss.top()][lexer(*p)])
			{
				case 1:	// 1. S → F
					ss.pop();
					ss.push(NTS_F);	// F
					break;

				case 2:	// 2. S → ( S + F )
					ss.pop();
					ss.push(TS_R_PARENS);	// )
					ss.push(NTS_F);		// F
					ss.push(TS_PLUS);	// +
					ss.push(NTS_S);		// S
					ss.push(TS_L_PARENS);	// (
					break;

				case 3:	// 3. F → a
					ss.pop();
					ss.push(TS_A);	// a
					break;

				default:
					cout << "parsing table defaulted" << endl;
					return 0;
			}
		}
	}

	cout << "finished parsing" << endl;

	return 0;
}

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 $:

• If the top is a nonterminal then the parser looks up in the parsing table, on the basis of this nonterminal and the symbol on the input stream, which rule of the grammar it should use to replace nonterminal on the stack. The number of the rule is written to the output stream. If the parsing table indicates that there is no such rule then the parser reports an error and stops.
• If the top is a terminal then the parser compares it to the symbol on the input stream and if they are equal they are both removed. If they are not equal the parser reports an error and stops.
• If the top is $ and on the input stream there is also a $ then the parser reports that it has successfully parsed the input, otherwise it reports an error. In both cases the parser will stop.

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 A₁ → w₁, …, A_n → w_n, we can compute the Fi(w_i) and Fi(A_i) for every rule as follows:

1. initialize every Fi(A_i) with the empty set
2. add Fi(w_i) to Fi(A_i) for every rule A_i → w_i, where Fi is defined as follows:
   • Fi(aw') = { a } for every terminal a
   • Fi(Aw') = Fi(A) for every nonterminal A with ε not in Fi(A)
   • Fi(Aw' ) = (Fi(A) \ { ε }) ∪ Fi(w' ) for every nonterminal A with ε in Fi(A)
   • Fi(ε) = { ε }
3. add Fi(w_i) to Fi(A_i) for every rule A_i → w_i
4. do steps 2 and 3 until all Fi sets stay the same.

The result is the least fixed point solution to the following system:

• Fi(A) ⊇ Fi(w) for each rule A → w
• Fi(a) ⊇ { a }, for each terminal a
• Fi(w₀ w₁) ⊇ Fi(w₀)·Fi(w₁), for all words w₀ and w₁
• Fi(ε) ⊇ {ε}

where, for sets of words U and V, the truncated product is defined by ${\displaystyle 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:

1. initialize Fo(S) with { $ } and every other Fo(A_i) with the empty set
2. if there is a rule of the form A_j → wA_iw' , then
   • if the terminal a is in Fi(w' ), then add a to Fo(A_i)
   • if ε is in Fi(w' ), then add Fo(A_j) to Fo(A_i)
   • if w' has length 0, then add Fo(A_j) to Fo(A_i)
3. repeat step 2 until all Fo sets stay the same.

This provides the least fixed point solution to the following system:

• Fo(S) ⊇ {$}
• Fo(A) ⊇ Fi(w)·Fo(B) for each rule of the form B → ... A w

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:

• the truncated product is defined ${\displaystyle 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(α)${\displaystyle \cdot }$Fi(β) also in step 2 of the Fi construction given for LL(1).
• In step 2 of the Fo construction, for A_j → wA_iw' simply add Fi(w')${\displaystyle \cdot }$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 LL(k) parsing (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.

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.

S -> E | E 'a'
E -> 'b' | ε

E -> E '+' term | alt1 | alt2

S -> A 'a' 'b'
A -> 'a' | ε

A -> X | X Y Z

A -> X B
B -> Y Z | ε

S -> E | E 'a'
E -> 'b' | ε

S -> 'b' | ε | 'b' 'a' | 'a'

S -> 'b' E | E
E -> 'a' | ε

E -> E '+' T
E -> T

E -> T Z
Z -> '+' T Z
Z -> ε

S -> A | B
A -> 'a' A 'b' | ε
B -> 'a' B 'b' 'b' | ε

• Comparison of parser generators
• Parse tree
• Top-down parsing
• Bottom-up parsing

• A tutorial on implementing LL(1) parsers in C# (archived)
• Parsing Simulator This simulator is used to generate parsing tables LL(1) and to resolve the exercises of the book.
• LL(1) DSL PEG parser (toolkit framework)
• Language theoretic comparison of LL and LR grammars
• LL(k) Parsing Theory