5.2 LL(1) Grammars and Predictive Parsing Tables

An LL(1) parser reads its input from Left to right, produces a Leftmost derivation, and uses 1 token of lookahead to select each production. The label describes a disciplined parsing strategy, not a badge that every grammar can earn. Its strength is transparency: a grammar, a table, a stack, and the next token fully explain the parser's decision.

Use this expression grammar, whose recursion has been made right-recursive so a top-down parser can consume it:

Expr     -> Term ExprTail
ExprTail -> + Term ExprTail | epsilon
Term     -> Factor TermTail
TermTail -> * Factor TermTail | epsilon
Factor   -> NUMBER | IDENT | ( Expr )

The transformed grammar still represents left-associative source expressions, but its parse tree is now convenient for prediction. When building an AST, the parser can fold the Tail sequence left to restore the source language's intended associativity.

The LL(1) Selection Test

For two alternatives of the same nonterminal, a one-token parser must be able to distinguish them. Define SELECT(A -> alpha) as:

FIRST(alpha) - { epsilon }

and, when epsilon is in FIRST(alpha), also include FOLLOW(A). The grammar is LL(1) when the SELECT sets of competing alternatives are disjoint.

For ExprTail:

FIRST(+ Term ExprTail) = { + }
FIRST(epsilon)         = { epsilon }
FOLLOW(ExprTail)       = { ), EOF }

SELECT(ExprTail -> + Term ExprTail) = { + }
SELECT(ExprTail -> epsilon)          = { ), EOF }

The current token + selects the first alternative; ) or EOF selects the empty alternative. No cell needs to guess. In contrast, this grammar is not LL(1):

Stmt -> IDENT = Expr ; | IDENT ( Args ) ;

Both productions begin with IDENT. A parser cannot choose from one token. Left-factor it into Stmt -> IDENT StmtRest and defer the decision until = or ( is visible.

Building and Reading the Table

A predictive table has one row per nonterminal and one column per terminal plus EOF. For every production A -> alpha:

1. Put the production in M[A, a] for every a in FIRST(alpha) - { epsilon }.

2. If epsilon is in FIRST(alpha), put it in M[A, b] for every b in FOLLOW(A).

3. If a cell receives two distinct productions, report a conflict rather than silently keeping one.

The key rows for the expression grammar look like this:

              NUMBER  IDENT  (   +   *   )   EOF
Expr          E->TE'  E->TE' E->TE'
ExprTail                         E'->+TE'  E'->eps E'->eps
Term          T->FT'  T->FT' T->FT'
TermTail                               T'->*FT' T'->eps T'->eps
Factor        F->num  F->id  F->(E)

Blank cells mean the indicated lookahead cannot begin the requested nonterminal. They are parser errors, not missing defaults. An epsilon production appears only in columns licensed by FOLLOW, which is why FOLLOW is essential rather than merely academic.

The Table-Driven Machine

The machine maintains a stack initially containing EOF Program and an input cursor ending in an EOF token.

• If the top of the stack is a terminal equal to lookahead, pop it and advance input.

• If it is a terminal that differs, signal an error.

• If it is a nonterminal A, consult M[A, lookahead]. Replace A by the selected right-hand side pushed in reverse order.

• Accept only when both stack and input are at EOF.

For NUMBER + NUMBER EOF, the stack evolves from EOF Expr to EOF ExprTail Term, then to EOF ExprTail TermTail Factor, and so on. Every expansion is a table lookup; every terminal match is visible. The downside is that a bare table-driven parser does not naturally mirror your AST node constructors. Many production compilers instead encode the same LL(1) choices directly as recursive-descent functions.

Conflicts Are Design Feedback

An LL(1) conflict tells you exactly what the parser cannot decide with one lookahead token. It does not necessarily mean the language is flawed. Common repairs are:

• Remove left recursion.

• Left-factor alternatives with common prefixes.

• Make optional syntax explicit with a delimiter.

• Move a context-sensitive distinction into a later semantic phase.

• Choose a more powerful parser strategy when the language needs one.

Do not “solve” a conflict by assigning an arbitrary production priority in the table. That creates a parser whose behavior depends on file order and whose rejected programs are hard to explain. Print the competing productions, their SELECT sets, and the conflicting table cell. That turns an abstract proof failure into a concrete language-design conversation.

Watch an Epsilon Decision Happen

At ExprTail in the input id ), the lookahead ) cannot start + Term ExprTail. It can, however, follow a completed ExprTail, so the epsilon alternative is selected. The parser pops ExprTail without consuming ); its caller will match that delimiter. Consuming ) during an epsilon choice would break the stack/input contract.

Blank table cells are useful: they name the exact nonterminal and lookahead that cannot coexist. Keep that pair in a diagnostic rather than reducing every failure to a generic “syntax error.”