Re: The $ in predictive parsing tables

Andreas Ravnestad <andreas.ravnestad@gmail.com> writes:


> In predictive parsing tables there is often a column designated '$'. I
> can't find any explanations for this column in my notes. Can someone
> shed a light on what this means?


You should find an explanation in most compiler textbooks. '$' is the
end-of-input marker. To the original grammar, you add a new
production S' -> S $, where S is the original start symbol. S' is the
new start symbol and will recognize w$ whenever the original grammar
recognizes w.


Using '$' reduces the number of conflicts in the table and simplifies
end-of-input treatment. If you use LL(2) parsing, you will use two
end-of-input markers, and so on.


'$' is also used in LR parsing.


Torben

Return to the comp.compilers page.
Search the comp.compilers archives again.