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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Hmm, so I need a way to query FIRST and FOLLOW symbol sets separately. $\endgroup$
    – mavavilj
    Jan 13, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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