2
$\begingroup$

How to treat $\epsilon$ and '\$' in top-down parser using predict table?

The construction of the predict table

Given a product $X \rightarrow w$, row $X$ and column $t$
-Mark $X \rightarrow w$ for each $t \in FIRST(w)$
-If $NULLABLE(w)$, then mark $X \rightarrow w$ for each $t \in FOLLOW(w)$ as well

says to create columns for all terminal symbols. $\epsilon$ is a terminal symbol so it's naturally added as a column.

However, I've somehow interpreted that I could/should add '\$' as a terminal symbol as well. Basically because '\$' is used in the FOLLOW sets (and the FOLLOW sets don't contain $\epsilon$).

But does this create redundancy since then the table would hold basically the same predict rules for '\$' and $\epsilon$ (at least in the implementation I have here)?

The rules given here also treat '\$' and $\epsilon$ as if they were separate:
http://www.jambe.co.nz/UNI/FirstAndFollowSets.html

The FOLLOW sets basically use '\$' in place of $\epsilon$, but the predict table uses $\epsilon$, because it's a terminal symbol.

$\endgroup$
3
$\begingroup$

$\epsilon$ is a terminal symbol

No. $\epsilon$ is the empty string, i.e. no symbols at all.

However, I've somehow interpreted that I could/should add '$' as a terminal symbol as well.

Yes, $ is the special symbol that marks the end of input, and you may have to do things at that place and when you want to go past it, you are done (or in situation of error for LR parsing if the stack is not empty).

The rules given here also treat '$' and ϵ as if they were separate: http://www.jambe.co.nz/UNI/FirstAndFollowSets.html

Considering $\epsilon$ as a symbol to be put in $FIRST$ could be an worthwhile implementation trick instead of computing $NULLABLE$ separately (I haven't tried it, at first sight it seems to break useful properties and to add as much complexity as it removes, see the point 4 in the computation of $FIRST$), but it is nothing more than an implementation trick.

$\endgroup$

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.