Parsing table

The parsing table tells us for a given non-terminal $\mathcal{X}$ and a given terminal $a$, which production rule to use to re-write $\mathcal{X}$.

If multiple entries appear in a table location, the grammar cannot be parsed by an LL(1) parser, i.e., it’s not an LL(1) grammar.

Construction

Basic idea: for a production in the form $\mathcal{X}\to \alpha$, add $\mathcal{X}\to \alpha$ to the table entry at row $\mathcal{X}$ and column $a$, for each $a\in \mathcal{F}irst(\alpha )$. Then when $ϵ\in \mathcal{F}irst(\alpha )$, we use $\mathcal{F}ollow(\alpha )$.

We follow the algorithm:

• For each production $\mathcal{X}\to \alpha$, repeat the following:
  • Add $\mathcal{X}\to \alpha$ to row $\mathcal{X}$ and column $a$ for each $a\in \mathcal{F}irst(\alpha )$.
  • If $ϵ$ in $\mathcal{F}irst(\alpha )$, add $\mathcal{X}\to \alpha$ to row $\mathcal{X}$ and column $a$ for each $a\in \mathcal{F}ollow(\mathcal{X})$.
• Each undefined entry in the table is an error.

To construct the parsing table, we must understand: what are the parser states, how do we determine the transitions, and how do we determine the actions (shift, reduce, goto, accept, error)?

Usage

We have states, actions, and goto. Elements in a parsing table are:

• si — shift and move to state i.
• ri — reduce by production i.
• gi — go to state i.
• a — accept.
• Blank — error.

We maintain a stack of elements, and a state stack. We always start with state 0. Each time we push/pop from the element stack, we do the same with the state stack.

Reduction doesn’t advance the pointer. This only happens when we shift.

Parser states represent the set of productions the parser may currently use, and how far the parser is in each production.

Say we run into a non-terminal, we look for other productions that can still satisfy the transition, i.e., we transitively add items (see slides)¹

Footnotes

1. related by necessity, see dictionary definition ↩