Top-Down Parsing and LL(1)

• FIRST and FOLLOW Sets: definitions and computation; the expression grammar and its sets are reused here.
• The grammar must first be free of left recursion and left-factored (see the note Grammar Transformations for Parsing).

The LL(1) conditions

1. $\text{FIRST}(\alpha) \cap \text{FIRST}(\beta) = \emptyset$ (no terminal begins strings of both; this includes $\varepsilon$, so at most one of them is nullable);
2. if $\beta \Rightarrow^{*} \varepsilon$, then $\text{FIRST}(\alpha) \cap \text{FOLLOW}(A) = \emptyset$ (and symmetrically when $\alpha$ is nullable).

Building the table

BUILD-LL1-TABLE(G)
    for each production A -> alpha
        for each terminal a in FIRST(alpha) - {eps}
            add A -> alpha to M[A, a]
        if eps in FIRST(alpha)
            for each b in FOLLOW(A)          (b may be $)
                add A -> alpha to M[A, b]
    every entry still empty is an error entry

The table-driven parser

LL1-PARSE(M, S, input)
    push $; push S
    a <- first token of input$
    loop
        X <- top of stack
        if X = $ and a = $ then accept
        else if X is a terminal
            if X = a then pop; a <- next token
            else error
        else if M[X, a] = X -> Y1 Y2 ... Yk
            pop; push Yk, ..., Y2, Y1        (Y1 ends on top)
        else error

Recursive descent for the same grammar

PROC-E():   PROC-T(); PROC-E1()
PROC-E1():  if a = '+' then MATCH('+'); PROC-T(); PROC-E1()
            else if a in { ')', '$' } then return          (E' -> eps)
            else error
PROC-T():   PROC-F(); PROC-T1()
PROC-T1():  if a = '*' then MATCH('*'); PROC-F(); PROC-T1()
            else if a in { '+', ')', '$' } then return     (T' -> eps)
            else error
PROC-F():   if a = '(' then MATCH('('); PROC-E(); MATCH(')')
            else if a = 'id' then MATCH('id')
            else error

The table for the expression grammar

Parsing id + id * id

Detecting an error: id + * id

Is the grammar LL(1)?

• LL(1) implies unambiguous. Each string has at most one leftmost derivation, because every step is forced. Hence an ambiguous grammar is never LL(1).
• LL(1) implies not left-recursive (for grammars without useless symbols). A left-recursive alternative shares FIRST with the alternative that ends the recursion.
• Language versus grammar. "LL(1)" is a property of a grammar. A language is called LL(1) if some LL(1) grammar generates it. Rewriting can turn a non-LL(1) grammar into an LL(1) one for the same language, but not always: some deterministic context-free languages have no LL($k$) grammar for any $k$.
• Relation to LR. Every LL(1) grammar is LR(1). It need not be SLR(1): S -> A a A b | B b B a, A -> eps, B -> eps is LL(1) but its SLR(1) table has a reduce-reduce conflict, because FOLLOW($A$) $=$ FOLLOW($B$) $= \{a, b\}$. See the note CLR(1) and LALR(1) Parsing for the full picture.
• Every regular language has an LL(1) grammar: the right-linear grammar read off a DFA has one production per state and symbol, so the next token always decides.
• Error recovery. In panic mode the parser skips input until a token in a synchronising set, typically FOLLOW of the nonterminal on top of the stack, then pops that nonterminal and continues.

• "A grammar with $\varepsilon$-productions cannot be LL(1)." It can; the expression grammar above has two.
• "Left factoring and left-recursion removal always give LL(1)." They are necessary steps, not a guarantee; the dangling-else grammar stays non-LL(1).
• "The number of parsing steps equals the number of tokens." It equals expansions plus matches; expansions include every $\varepsilon$-production applied.
• "An unambiguous grammar without left recursion is LL(1)." S -> a S a | b S b | eps is both, and still has two conflicts: the parser cannot tell where the middle of the string is.
• "An empty table entry means the grammar is not LL(1)." Empty entries are error entries; only an entry with two productions is a conflict.

• Fill a table entry. $M[A, a]$ contains $A \to \alpha$ if $a \in \text{FIRST}(\alpha)$, or if $\alpha$ is nullable and $a \in \text{FOLLOW}(A)$. Questions ask for the entries of one row or for which entries hold $\varepsilon$-productions.
• Decide LL(1). Check both conditions for every pair of alternatives. A conflict through FOLLOW (condition 2) is the classic trap.
• Count moves or the stack contents. At a given step of the trace; keep the top of the stack at a consistent end and push bodies in reverse.
• Grammar classes. LL(1) grammars are unambiguous, not left-recursive, and LR(1). Not every LL(1) grammar is SLR(1) or LR(0).
• Recursive descent. Questions may show recursive procedures and ask which grammar they parse, or which input causes an infinite loop (left recursion).
• Where is the error detected? Trace until an empty entry or a terminal mismatch; by the valid-prefix property, the offending token is the first one that cannot extend a valid prefix.
• Nullable alternatives check against FOLLOW of the head. For $S \to a S a \mid \varepsilon$, the test uses FOLLOW($S$), which contains a because of the inner $S$ in $aSa$.

• FIRST and FOLLOW Sets: prerequisite. The sets that fill the table.
• Syntax-Directed Definitions: dependent. L-attributed definitions are evaluated naturally during a top-down parse.