Assignment III

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 small example.

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 the input.

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.