MCS-388 Homework 1 (Spring 2000)

Due: February 14, 2000

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.