MCS-388 Homework 1 (Spring 2001)

Due: February 12, 2001

  1. Using the grammar for expr on page 32, show the parse tree for 5+2*(3+4), where each of the digits (5, 2, 3, 4) is a digit.
  2. For the grammar of problem 2.2b on page 78, prove the following:
    1. The excess of a's over operators (+'s and -'s) in any S (i.e., any string derivable from S) is 1.
    2. The excess of a's over operators in any proper prefix of an S is less than 1. (If there are more operators than a's, the excess is negative. A proper prefix means a prefix that is not empty and is not the entire string. The restriction to non-empty prefixes isn't needed here, since the excess in an empty prefix is of course 0.)
    3. The grammar is unambiguous.
  3. Do problem 2.5 on page 79.

Course web site:
Instructor: Max Hailperin <>