CS 410: Homework 3
Fall 2006 [Bono]
Due: Friday, Oct. 27, 2006,
by 2pm to receptionist in Sal 300
Problem 1
Consider the following grammar to describe grammars that use bison
syntax. For more details on the language generated by this grammar,
see problem 6 on this semester's midterm exam. Note: '|' is a
terminal symbol in the grammar, so we'll avoid using it as a
meta-symbol in the grammar below. The complete set of terminals is: {
':', ';', '|', t, nt }. Note:
<eps> denotes the empty string.
gmr --> prod
gmr --> gmr prod
prod --> nt ':' RHS opt ';'
RHS --> symbol RHS
RHS --> <eps>
symbol --> t
symbol --> nt
opt --> '|' RHS opt
opt --> <eps>
Create the table for a table-driven LL(1) parser for this grammar.
Show your work. In particular, show:
- transformed grammar without left recursion (if necessary). For
this and the next step, show the whole grammar (if it changed), and
clearly label what transformation was made. If the grammar did not
need to be changed, then say so.
- left-factored grammar (starting with the grammar from the first
part) (if necessary)
- FIRST sets of all non-terminals
- FOLLOW sets of all non-terminals
- the table itself
Problem 2
The following is a version of an expression grammar. Do the steps to
make an LL(1) parse table (shown above for problem 1). If there are
conflicts, show all the values that can go in a spot in the table.
E --> E + E
| E - E
| id
The University of Southern California does not screen or control the content on this website and thus does not guarantee the accuracy, integrity, or quality of such content. All content on this website is provided by and is the sole responsibility of the person from which such content originated, and such content does not necessarily reflect the opinions of the University administration or the Board of Trustees