MCS-388 Homework 2 (Spring 2005)

Due: March 1, 2005

  1. Do problem 3.6, parts a-d only, on page 147. Your descriptions should be simple, which may require you to do more than just a literal one-to-one translation of the regular expression notation into English.

  2. Write a regular expression for the language consisting of all strings over the alphabet {a, b, c} in which no a is immediately followed by a b.

  3. Eliminate left recursion from the following grammar:

    E -> E+T | E-T | T
    T -> T*F | T/F | F
    F -> (E) | id | F!
  4. For the following grammar (in which epsilon represents the empty string)

    S -> (T) | epsilon
    T -> [S] | a
    1. Construct the FIRST and FOLLOW sets.
    2. Construct the predictive parsing table.
    3. Show (in the style of Figure 4.16, p. 188) the actions of the predictive parser on input ([([])]).

Course web site:
Instructor: Max Hailperin <>