Top-down parsing and LL(1)

Why it exists

The simplest way to see whether a program fits the grammar is to try to build the parse tree from the top: start from the start symbol and keep expanding the leftmost nonterminal, matching terminals against the input. If, at every expansion, one token of lookahead is enough to know which production to use, no guessing and no backtracking is needed. Such grammars are LL(1), and the parser is fast, tiny, easy to write by hand (recursive descent) or to drive by a table, and gives good error messages.

Prerequisites

You need FIRST and FOLLOW (FIRST and FOLLOW) and a grammar without left recursion or common prefixes (transformations). The parser uses a stack (stack ADT).

Precise definitions

Top-down parsing. Constructing the parse tree from the root to the leaves, equivalently finding a leftmost derivation of the input. The tree grows by expanding the leftmost nonterminal.

LL(1). The first L: the input is read Left to right. The second L: the parser produces a Leftmost derivation. The 1: it uses one token of lookahead. An LL(1) grammar is one for which such a parser works without backtracking. An LL($k$) grammar uses $k$ tokens of lookahead; every LL($k$) grammar is unambiguous.

LL(1) condition. A grammar is LL(1) if and only if for every nonterminal $A$ with productions $A \to \alpha_1 \mid \dots \mid \alpha_n$ the sets $\text{SELECT}(A \to \alpha_i)$ are pairwise disjoint, where for a production $A \to \alpha$

$\text{SELECT} = \text{FIRST}(\alpha) \setminus \{\varepsilon\} \ \ \cup \ \ \big(\text{FOLLOW}(A) \text{ if } \varepsilon \in \text{FIRST}(\alpha)\big).$

Necessary conditions (not sufficient): not ambiguous, not left recursive, left factored. A grammar can pass all three and still fail LL(1), as the examples show.

The LL(1) parsing table $M[A, a]$. Rows are nonterminals, columns are terminals and $\mathdollar$. For every production $A \to \alpha$ and every $a \in \text{SELECT}(A \to \alpha)$, put $A \to \alpha$ in $M[A, a]$. An empty cell means a syntax error. A cell with more than one production is a conflict: the grammar is not LL(1).

The parser (nonrecursive predictive parser). A stack of grammar symbols (with $\mathdollar$ at the bottom and the start symbol on top) and the input followed by $\mathdollar$. Repeat with $X$ = top of stack and $a$ = next input token:

1. $X = a = \mathdollar$: accept.
2. $X$ a terminal: if $X = a$, match: pop $X$ and advance the input; otherwise error.
3. $X$ a nonterminal: if $M[X, a]$ holds $X \to Y_1 \cdots Y_k$, output the production, pop $X$ and push $Y_k, \dots, Y_1$ so that $Y_1$ is on top (push nothing for $\varepsilon$); if $M[X, a]$ is empty, error.

The sequence of productions output is the leftmost derivation. The tree is built by creating children for $X$ when it is expanded.

Error handling. The parser detects an error as soon as a terminal does not match or a table cell is empty; LL(1) parsers have the viable prefix property (they never shift a token that cannot continue a valid program), so the error is reported at the earliest possible token. Panic-mode recovery: when $M[A, a]$ is empty, skip input tokens until one is found that is in a synchronising set of $A$, typically FOLLOW($A$) (then pop $A$ and carry on) or FIRST($A$) (then expand $A$ as usual); the table cells for FOLLOW($A$) are filled with "synch". When a terminal on the stack does not match, pop it and issue a message (as if it had been inserted).

Recursive descent is the same method written as a procedure per nonterminal; it is a separate page. Power. LL(1) grammars are a proper subset of the LR(1) grammars (comparison of parsers); there are deterministic context-free languages with no LL($k$) grammar for any $k$, for example $\{a^n b^n\} \cup \{a^n c^n\}$ (the choice between the two forms depends on a symbol after an unbounded number of $a$'s).

How it works

Step through the parse of $\text{id} + \text{id} * \text{id}$ with the expression grammar. The top of the stack is at the left. The table at the right shows the entry consulted each time (outlined); the tree grows at the left (new nodes shaded, nodes still on the stack dashed). Notice the pattern: a nonterminal on top is expanded using the table, a terminal on top is matched against the input, and the empty productions are chosen when the lookahead is something that may follow ($+$, ) or $\mathdollar$).

The table itself is built production by production from FIRST and FOLLOW:

When two productions land in the same cell the grammar is not LL(1). The dangling-else grammar (after left factoring) is the standard example: the lookahead e selects both $S' \to e S$ (by FIRST) and $S' \to \varepsilon$ (because e can follow $S'$).

Finally an error. For the input $\text{id} + * \text{id}$ the parser expands $T$ after the plus and finds the cell $M[T, *]$ empty: no production for $T$ can start with $*$, and the error is reported at that token.

Worked examples

stack        input    move
S $          aabb$    output S → a S b
a S b $      aabb$    match a
S b $        abb$     output S → a S b
a S b b $    abb$     match a
S b b $      bb$      output S → ε
b b $        bb$      match b
b $          b$       match b
$            $        accept

Cheat box

Traps and GATE patterns

Connections

The table needs FIRST and FOLLOW and a grammar prepared by the transformations. Writing the parser as procedures gives recursive descent. The bottom-up alternative is shift-reduce parsing and LR; the two families are compared in the parser hierarchy. The semantic actions that compute values during parsing are in syntax-directed definitions.

PYQs

Which of the following statements is/are true?

Consider two grammars G1 and G2 with the
production rules given below:

G1: S → if E then S | if E then S else S | a

       E → b

G2: S → if E then S | M

       M → if E then M else S | c

       E → b

where if, then, else, a, b, c are the terminals.

Which of the following option(s) is/are CORRECT?

Which of the following is/are Bottom-Up Parser(s)

Consider the following context-free grammar where
the set of terminals is {a,b,c,d,f}.
S→daT|Rf
T→aS|baT|ε
R→caTR|ε

          The following is a partially-filled LL(1) parsing table.

a
b
c
d
f
$
S

(1)
S →da T
(2)

T
T →a S
 T →ba T
(3)

T →ε
(4)
R

R →caTR

R →ε

Which one of the following choices represents the
correct combination for the numbered cells in the
parsing table ("blank" denotes that the corresponding
cell is empty)?

COMPILER DESIGN

Consider the following grammar G.

S → F | H

F → p | c

H →d | c

Where S, F and H are non-terminal symbols, p, d
and c are terminal symbols. Which of the following
statement(s) is/are correct?

S1: LL(1) can parse all strings that are generated
using grammar G.

S2: LR(1) can parse all strings that are generated
using grammar.

For the grammar below, a partial LL(1) parsing table
is also presented along with the grammar. Entries that
need to be filled are indicated as E1, E2 and E3. ε is
the empty string, $ indicates end of input, and |
separates alternate right hand sides of productions.

S → a A b B | b A a B | ε

A → S

B → S

      a
b
$
S
E 1
E 2
 S →ε
A
 A → S
 A → S
error
B
B →S
B →S
E3

The FIRST and FOLLOW sets for the non-terminals
A and B are:-

FIRST(A) = {a, b, ε} = FIRST(B)

For the grammar below, a partial LL(1) parsing
table is also presented along with the grammar.
Entries that need to be filled are indicated as E1,
E2, and E3.  epsilon is the empty string, $ indicates
end of input, and, | separates alternate right hand
sides of productions.

S →a A b B | b A a B | ε

A →S

B → S

      a
b
$
S
E 1
E 2
 S →ε
A
 A → S
 A → S
error
B
B →S
B →S
E3

The appropriate entries for E1 , E2, E3 are:-

The grammar : S → aSa|bS|c is:-

Self-check

Revision card

References