Due date Feb. 26, 2004.
1. Consider the following context-free grammar:
S ::= ( L ) | id
L ::= L ',' S | S
Non-terminals and S and L, terminals are parentheses, comma, and id.
a) Remove left-recursion from this grammar.
b) Compute the First and Follow set for the new grammar (it will have some
additional non-terminals). You can use the algorithms in the text, p.99,
or the description given in class, which should be sufficient for this
c) Build the LL (1) table for the grammar, using the result obtained in b).
Number the productions in the grammar. The table is indexed by non-terminal
symbol n and terminal symbol t. The entry in the table Tab (n, t) is the production number
that is to be used when n is on top of the stack, and t is the next token in
d) Consider the sentence (id, (id, id)) generated by this grammar. Using
the algorithm given in p. 106 of the text, trace the parsing of this
sentence, by showing the contents of the stack and the position of the token
being examined at each step. Initially the stack contains the sentence symbol S,
and the token being examined is the left parenthesis. At the end the stack
is empty and the next token is the end of file.