Content

1. Overview
2. Predictive Grammars & Parsers
   1. LL(1)
   2. Recursive Descent
      1. First() & Follow()
      2. First+()
      3. First & Follow Sets Calculation
   3. Table-Driven Parsing

Overview

• Lookahead
• Backtracking: excessive is grammar complex

Predictive Grammars & Parsers

LL(1)

• Scanned from left to right (L)
• Leftmost derivation (L)
• 1 symbol lookahead (1)
• No left recursions (not the other way round)
• No left factors (not the other way round)

Recursive Descent

A predictive parser based on LL(1). Another is table-driven parser.
Using recursive function, top-down starting from root.

A -> aAb | c

# each non-terminal has a routine
ParseA() {
    if (nextSym() == 'a') {
        ParseA();
        if (nextSym() == 'b') OK else ERROR;
    } else if (nextSym() == 'c') OK;
    else ERROR;
}

Must be no left recursion.

# left recursion:
P -> E

E -> E + T | E - T | T 
T -> T * S | T / S | S 
S -> F ^ S | F
F -> ( E ) | char

# transform to EBNF:
P -> E

E -> T {(+|-)T} 
T -> S {(*|/)S} 
S -> F^S | F        # left factor!
F -> ( E ) | char

Must also get rid of left factors.

First() & Follow()

First(u) is the set of terminals that starts the sequences of symbols derivable from u.
Follow(A) is the set of terminals that immediately follows A.

A -> u1 | u2 | ..., if First(ui) are disjoint, then a RD routine can be easily written. Since A may be ε, Follow(A) is needed.

void ParseA() {
    switch (lookahead)
 {
        case First(u1):
            /* code to recognize u1 */
            return;
        ...
        case Follow(A): 
            // predict production A -> ε if A is nullable

            /* usually do nothing here */
        default:
            ...
    }
}

First+()

If A -> α and A -> β, then need to make sure First(α) ∩ First(β) = ∅. But if α can be ε, then also Follow(α) ∩ First(β) = ∅.

First+(α) = First(α) ∪ Follow(α) if ε ∈ First(α)
          = First(α) otherwise

A grammar is LL(1) if A -> α and A -> β implies:

First+(α) ∩ First+(β) = ∅

First & Follow Sets Calculation

• First(u): u = X1X2...Xn

  • If X1 is terminal, add X1 and finish
  • Else, add First(X1) - ε
    • If X1 is nullable, add First(X2) - ε, and keep going
      • If X2...XN are nullable, add ε
    • Else, finish

• Follow()

  • Add $ to Follow(S)
  • For A -> uBv, add First(v) - ε to Follow(B)
    • If v is nullable, add Follow(A) to Follow(B)
  • For A -> uB, add Follow(A) to Follow(B)

Table-Driven Parsing

1. For A -> u, do 2. & 3.
2. For each terminal a in First(u), add A -> u to M[A,a]
3. If A nullable, then for each terminal b in Follow(A), add A -> u to M[A,b]
4. Undefined entries are errors