MCS-388 Homework 2 (Spring 2009)

Due: February 27, 2009

1. Eliminate all left recursion (direct and indirect) from the following grammar:

   S → S a | B c | d
   B → S e | f
   

2. For the following grammar

   S → ( L ) | a
   L → S T
   T → ε | , L
   

   1. Construct the FIRST and FOLLOW sets.
   2. Construct the predictive parsing table.
   3. Show (in the style of Figure 4.21, p. 228) the actions of the predictive parser on input ((a,a),a).

3. Is the following grammar LL(1)? Explain how you know. Also, if the grammar is not LL(1), write an LL(1) grammar for the same language.

   S → a | b C
   C → S | a d
   

4. Using the grammar of Exercise 4.2.2(e) on p. 207 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 using a table in the form of Figure 4.28 on page 237. Number the rows in your table consecutively, starting with 1, for reference in the next part of this problem.

   3. Show the parse tree. Label each terminal in the parse tree with the row number of the corresponding shift step in your shift-reduce parse. Label each nonterminal with the row number of the corresponding reduce step.