An Introduction to Formal Languages and Automata, 7th Edition

16.3 LL(1) PARSING ALGORITHM

We present the following algorithm for LL(1) parsing that uses the LL(1) Parse Table and a stack to parse strings instead of using an npda. For this stack we do not use a stack start symbol, but instead assume this stack can determine whether it is empty or not. We first define several functions for the algorithm.

1. push(w) pushes w on the stack. If w = x₁x₂ … x_n, where x_i is a symbol either from V or T, then x_n is pushed on the stack first, and x₁ is pushed on the stack last.
2. top() returns a copy of the top symbol on the stack.
3. pop() removes and returns the top symbol on the stack.
4. get() returns the next lookahead symbol in the input string. If there is no such symbol, it returns the end of string marker $.

LL ...