LL(1) Parse

LL(1) Parsing Algorithm

Assume that the current top of the stack is X and the current input symbol is a:

• If X=a=end symbol, parser halts and announces accept.

• If X is a terminal:
  • If X=a pop X off the stack and advance to the next input symbol.

  • Otherwise the parser halts and announces error.

• If X is a nonterminal and table(X,a) is:
  • A production number p. Pop X off the stack and replace it with the reverse of the right-hand side of production p. As a semantic action, output the production number.

  • Error. The parser halts and announces error.