MCS-388 Homework 3 (Spring 2008)

Due: March 10, 2008

  1. 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.

  2. Each of the following two grammars generates the language of all strings of as with positive even lengths. Grammar 1 is

    S -> a S a
    S -> a a

    and Grammar 2 is

    S -> a a S
    S -> a a

    Of these two grammars, one of them is suitable for shift-reduce parsing, and in fact you can successfully use any of the SLR(1), LR(1), or LALR(1) parser construction techniques. The other will not work using any of the three techniques or any other technique that uses limited lookahead.

    1. First, determine which of the two grammars can be parsed with just one symbol of lookahead. Consider an input that is a long, even-length string of as, such as aaaaaaaa or aaaaaaaaaa. With each of the two grammars, there will be some point at which a reduction by the production S -> a a needs to occur. At what point in the string will this need to happen using grammar 1? At what point when using grammar 2? This should tell you which grammar is suitable for use with one symbol of lookahead. (If not, you can try creating canonical LR(1) parsers for each and see which you get stuck on.)

    2. Now, for the workable grammar, construct a parser using whichever of SLR(1), LR(1), or LALR(1) you prefer. Augment the grammar, draw the state machine, and then construct the parsing tables.

Course web site:
Instructor: Max Hailperin <>