MCS388 Homework 1 (Spring 2001)
Due: February 12, 2001

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.

For the grammar of problem 2.2b on page 78, prove the following:

The excess of
a
's over operators (+
's and

's) in any S (i.e., any string derivable from
S) is 1.

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 nonempty prefixes isn't needed here, since the excess
in an empty prefix is of course 0.)

The grammar is unambiguous.

Do problem 2.5 on page 79.
Course web site: http://www.gac.edu/~max/courses/S2001/MCS388/
Instructor: Max Hailperin <max@gac.edu>