Skip to content

Lecture No. 16

Dated: 08-04-2025

Expression: 2 + 4 * 6
Output trace:

>> Expr::isPresent()
    >> Term::isPresent()
        >> Factor::isPresent() token: 2 (257) 
        << Factor::isPresent() return true
        >> Tprime::isPresent() token: + (267)
        << Tprime::isPresent() return false
    << Term::isPresent() return true
    >> Eprime::isPresent() token: + (267) 
        >> Term::isPresent()
            >> Factor::isPresent() token: 4 (257) 
            << Factor::isPresent() return true 
            >> Tprime::isPresent() token: * (269) 
                >> Factor::isPresent() token: 6 (257) 
                << Factor::isPresent() return true
                >> Tprime::isPresent() token: (0)
                << Tprime::isPresent() return false
            << Tprime::isPresent() return true
        << Term::isPresent() return true
        >> Eprime::isPresent() token: (0)
        << Eprime::isPresent() return false
    << Eprime::isPresent() return true
<< Expr::isPresent() return true

2 + 4 * 6

cs606_e_16_1.svg

Non Recursive Predictive Parsing

This is done by maintaining an explicit stack and using a table.
Such a parser1 is called table driven parser.
The LL(1) table has one dimension for current non-terminal to expand and another dimension for next token.2 Each table cell contains one production.

Example

Expression Grammar

1. E  ?   T E'
2. E' ? + T E'
3.    |   e
4. T  ?   F T'
5. T' ? * F T'
6.    | e
7. F  ? (E)
8.    | id

Predictive Parsing Table

id + * ( ) $
E E → TE' E → TE'
E' E' → +TE' E' → ε E' → ε
T T → FT' T → FT'
T' T' → ε T' → *FT' T' → ε T' → ε
F F → id F → (E)

The predictive parser uses an explicit stack to keep track of pending non-terminals. It can thus be implemented without recursion.

\(LL(1)\) Parsing Algorithm

Input string3 ($ denoting the end of it), is contained inside an input buffer.
Initially, the stack contains the starting symbol.

Functionality

Consider

  • Symbol at top of stack be X
  • Current input symbol be a

There are 3 possibilities.

  1. \(X = a = \$\), the parser1 halts and announces successful completion.
  2. \(X = a \ne \$\), the parser1 pops \(X\) and advances the input pointer to next input symbol.
  3. If \(X\) is non terminal then we consult \(M[X, a]\) entry of the \(M\) table.
    • If \(M[X, a] = \{X ? UVW\}\) (a production), the parser1 replaces \(X\) by \(WVU\) (\(U\) being at the top).
    • If \(M[X, a] = \text{error}\) then the parser1 calls an error recovery routine.

Example

Input string3

\[\text{id} + \text{id} \, \text{id}\]
Stack Input Output
$E id+idid$ E → TE'
$E' T id+idid$ T → FT'
$E' T' F id+idid$ F → id
$E' T' +idid$
$E' +idid$ T' → ε
$E' +idid$ E' → +TE'
$E' T + idid$
$E' T' F idid$ T → FT'
$E' T' id$
$E' id$ T' → ε
$E' id$ E' → +TE'
$E' T + id$
$E' T' F id$ T → FT'
$E' T' $
$E' $ T' → ε
$ $ E' → ε

References

  1. Read more about parsers. ↩↩↩↩↩

  2. Read more about tokens. ↩

  3. Read more about strings. ↩↩