MCS-388 Homework 3 (Spring 2005)

Due: March 8, 2005

1. Using the grammar of Exercise 4.1 (p. 267) and the input string ((a,a),a)
   1. Show a rightmost derivation, with the handle underlined in each right-sentential form (including the final sentence, but excluding the initial start symbol).
   2. Show the steps of a shift-reduce parse, in the form of Figure 4.22 on page 199.
   3. Show the parse tree, and label each terminal in the parse tree with the line number of the corresponding shift step in your shift-reduce parse, and each nonterminal with the line number of the corresponding reduce step.

2. (This is based on Appel's exercise 3.12.) For the grammar

   E -> id | id ( E ) | E + id
   

   build an SLR parser by drawing the state machine and then constructing the parsing tables.

3. Consider the following two grammars

      R -> a R | a
   

   and

      L -> L a | a
   

   Suppose we construct an LR(1) parser for each and in each case parse an input consisting of n tokens, each of which is an a. What is the maximum depth of the parser stack in each case? Justify your answer.