1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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)$.

If the prediction is ambiguous, the construction of the tables should either have failed or used another way to resolve the conflict (for instance you could get a generator which allow ambiguity in the productions and resolve them using precedence -- using associativity to solve conflicts in a predictive parser is harder).

$\endgroup$
  • $\begingroup$ Hmm, so I need a way to query FIRST and FOLLOW symbol sets separately. $\endgroup$ – mavavilj Jan 13 '16 at 10:47
  • $\begingroup$ @mavavilj, I expect the table to be bidimensional, one being the non-terminals, the other the terminals, and the content being the production (with the possibility to have a special value for error cases). When the generator generate the table, yes, it has to know the FIRST and FOLLOW sets. $\endgroup$ – AProgrammer Jan 13 '16 at 12:06
  • $\begingroup$ What I was referring to that one'd need to query the FIRST and FOLLOW sets IN ADDITION TO the parsing table. Some references have only spoken about querying the parsing table (but not the FIRST and FOLLOW sets). $\endgroup$ – mavavilj Jan 15 '16 at 3:24
  • $\begingroup$ 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)? $\endgroup$ – mavavilj Jan 15 '16 at 4:23
  • $\begingroup$ @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. $\endgroup$ – AProgrammer Jan 15 '16 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.