Implementing a Parser

The rules we developed above do not change during a parse. Hence, instead of writing them into our parsing program, we can store them in a two-dimensional array, called a parse table. This parse table tells us the rule to apply for the current non-terminal in the sentential form and the current input symbol. Any blank entries in the parse table denote ``error''.

For any non-terminal $X$ and terminal z, the fact that some production $X\, \rightarrow\, \alpha$ is in the parse table entry for [$X$,z] means that we have worked out that this is the production most likely to lead to a derivation of z from $X$.

Thus, to put entry $X\, \rightarrow\, \alpha$ into the parse table entry [$X$,z] we must have either:

1. z is in $FIRST(\alpha)$, or
2. $\varepsilon$ is in $FIRST(\alpha)$ and z is in $FOLLOW(X)$
   

Using these rules we can systematically construct a parse table for any grammar.

The most common way to implement this type of parser is using a stack. At any stage during the parse, the leftmost non-terminal in the sentential form is on top of the stack, with the rest of the symbols (to the right) underneath it. Applying a production rule involves popping the non-terminal off the stack and pushing on the r.h.s. of the rule (with the symbols in reverse order) back on.