MCS-388 Homework 1 (Spring 2005)

Due: February 15, 2005

1. Using the grammar for expr on page 32, show the parse tree for 3*(5-4*7/2), where each of the digits (3, 5, 4, 7, 2) is a digit.
2. Answer each of the following questions about the grammar

   S -> S a S b S | epsilon
   

   where epsilon represents the empty string:
   1. Is this grammar ambiguous? Justify your answer.
   2. Prove by induction on the number of nodes in a parse tree that any string generated by the grammar has an equal number of a's and b's.
   3. Can the grammar generate all strings of a's and b's that have an equal number of a's and b's? Justify your answer.
3. Consider the grammars of exercises 2.1 and 2.2b on page 78. For each of these two grammars, answer the following two questions and justify your answers. Is the grammar suitable for predictive parsing? Is it ambiguous?