Interpreting LL Parsing Table

This is the top-down parser:

var stack : Stack[GrammarSymbol]
lex = new Lexer(inputFile)
while (true) {
* X = stack.pop
  t = lex.curent
  if isTerminal(X)
    if (t==X) 
      if (X==EOF) return success
      else // eat token t
      parseError("Expected " + X)
  else // non-terminal
    cs = choice(X)(t)
    cs match {
    case {i} => // exactly one choice
      rhs = p(X,i) // choose correct right-hand side
*     stack.push(reverse(rhs))
    case {} => parseError("Parser expected an element of " + unionOfAll(choice(X)))
    case _ => crash("wrong parse table, not LL(1)")

The lines marked with * give us the essence of this parser: it pops non-terminals from stack and replaces them with the right-hand side of a production rule.

When we write recursive descent procedures by hand, the stack is implicit in the use of recursive procedures.

Note: the program above corresponds to a deterministic push-down automaton that parses the LL(1) grammar

  • non-deterministic push down automata correspond to all grammars
  • determinization of push down automata in general is not possible, non-deterministic ones are more expressive