Re: The $ in predictive parsing tables (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=)
11 Oct 2006 23:19:08 -0400

          From comp.compilers

Related articles
The $ in predictive parsing tables (Andreas Ravnestad) (2006-10-10)
Re: The $ in predictive parsing tables (2006-10-11)
Re: The $ in predictive parsing tables (Ivan Boldyrev) (2006-10-11)
| List of all articles for this month |

From: (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=)
Newsgroups: comp.compilers
Date: 11 Oct 2006 23:19:08 -0400
Organization: Department of Computer Science, University of Copenhagen
References: 06-10-035
Keywords: parse
Posted-Date: 11 Oct 2006 23:19:08 EDT

Andreas Ravnestad <> 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.


Post a followup to this message

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