LL

An LL parser is a top-down parser for a subset of context-free grammars that parses the input from left to right and constructs a leftmost derivation. The name "LL" is mnemonic: the first L indicates left-to-right scanning of the input; the second L indicates that the parser produces a leftmost derivation. LL parsers are table-driven or recursive descent implementations of predictive parsing, in which the parser decides which grammar production to apply based on a fixed number of lookahead tokens.

An LL(k) parser uses k tokens of lookahead. In practice, almost all LL parsers are LL(1) — they use a single token of lookahead — because LL(1) grammars are simple to parse and sufficient for most programming language constructs. The parsing table for an LL(1) grammar has one row for each non-terminal and one column for each terminal, and each cell contains at most one production. If any cell would contain more than one production, the grammar is not LL(1).

LL(1) Parsing Algorithm

The LL(1) parser maintains an explicit stack of symbols and a pointer to the current input token. Initially, the stack contains the start symbol of the grammar and a bottom-of-stack marker. On each step:

1. If the top of the stack is a non-terminal, the parser consults the parsing table at (non-terminal, current token). If the table entry is a production A → α, the parser pops A and pushes α in reverse order. If the table entry is empty, the parser reports a syntax error.

2. If the top of the stack is a terminal, the parser compares it to the current input token. If they match, both are consumed. If they do not match, the parser reports a syntax error.

3. If the top of the stack is the bottom marker and the input is exhausted, parsing succeeds.

This algorithm is linear in the length of the input and requires no backtracking. The entire parse is determined by the parsing table, which is computed from the grammar before parsing begins.

FIRST and FOLLOW Sets

The construction of an LL(1) parsing table depends on two functions computed from the grammar:

FIRST(α) is the set of terminals that can appear as the first symbol of some string derived from α. If α can derive the empty string, ε is in FIRST(α).

FOLLOW(A) is the set of terminals that can appear immediately after A in some sentential form.

For a production A → α, the parser applies this production when the current token is in FIRST(α). If α can derive ε, the production is also applied when the current token is in FOLLOW(A). A grammar is LL(1) if and only if, for every non-terminal A and every pair of distinct productions A → α and A → β:

FIRST(α) and FIRST(β) are disjoint.
If ε is in FIRST(β), then FIRST(α) and FOLLOW(A) are disjoint (and vice versa).

These conditions ensure that the parsing table has at most one production in each cell.

Limitations of LL Parsing

LL parsers cannot handle left-recursive grammars. A left-recursive production A → A α causes FIRST(A α) to include FIRST(A), creating a circular dependency in the FIRST sets and making table construction impossible. Left recursion must be eliminated by grammar transformation before an LL parser can be constructed.

LL parsers also struggle with ambiguous constructs. The classic example is the dangling else: in a grammar with productions Statement → if Condition then Statement and Statement → if Condition then Statement else Statement, an input of the form "if C1 then if C2 then S1 else S2" is ambiguous. The else could attach to the inner if or the outer if. An LL parser cannot resolve this ambiguity without modifying the grammar or adding semantic rules.

Because of these limitations, LL parsing is less powerful than LR parsing. Every LL(1) grammar is also LR(1), but the converse is not true. However, LL parsers have compensating advantages: they are easier to understand, easier to debug, and typically produce better error messages than LR parsers.

Recursive Descent as LL Parsing

A recursive descent parser in which each function examines the next token to decide which alternative to pursue is essentially an LL parser implemented with the program call stack rather than an explicit stack. The correspondence is direct: each non-terminal function corresponds to a row in the LL parsing table, and each if-statement or switch-statement on the lookahead token corresponds to a column.

This equivalence means that the theoretical properties of LL parsers apply to recursive descent parsers as well. A recursive descent parser that uses lookahead without backtracking can only parse LL(k) grammars. If the grammar is not LL(k), the parser will either fail to compile (if the ambiguity is detected statically) or exhibit incorrect behavior (if the ambiguity is resolved arbitrarily by the order of if-statements).

LL parsing occupies a sweet spot in the design space: simple enough to implement by hand, fast enough for production use, and powerful enough for most language syntaxes. Its limitations are real but not crippling. The languages that cannot be parsed by LL(1) — C, C++, Ruby — are exceptions, not the rule. For the majority of language designers, LL parsing is the right choice, and the fact that it is taught in every compiler course is not academic inertia but practical wisdom.