# How to treat ϵ-productions in table-driven predictive parsing?

Here:
https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html
in chapter Driver Procedure, it's shown how table-drive predictive parsing works.

The predict table however can involve $\epsilon$-productions (which leads to including a production in the symbols of $FOLLOW(w)$, where $w$ is a non-terminal/row, in addition to $FIRST(w)$) and I cannot find how these should be treated. I.e. how should the parser decide whether it predicts for an $\epsilon$-production or non- $\epsilon$-production. I.e. e.g. how should the end of the string be handled by the Driver.

Case example:

Such production involving the $\epsilon$ could be e.g.

$$A \rightarrow \text{B | c | \epsilon}$$ where c is a terminal and B is a non-terminal.

The remaining input could be "".

So how should the driver decide to match with the $\epsilon$ and not e.g. something that the non-terminal $B$ leads to.

A guess would be that it tries all of the symbols between the $|$s but fails in other than the $\epsilon$.

It will predict $A\rightarrow B$ if the look-ahead is in $FIRST(B)$, it will predict $A\rightarrow c$ if the look-ahead is $c$, it will predict $A\rightarrow\epsilon$ is the look-ahead is in $FOLLOW(A)$.
• Also, how should the "inferring" of different options (between $|$s) be done? By querying whether in $a_1|a_2|a_3$ some $a_i$ is a terminal, non-terminal or epsilon (and these are the only options that every $a_i$ may belong to)? Jan 15, 2016 at 4:23
• @mavavilj, For the table driven predictive parsers I've written, the tables were sufficient. Again, the table gives for a given non-terminal and a given look-ahead the production to use, which may be a $\epsilon$ one. Jan 15, 2016 at 9:12