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 ([([])]).