Homework: Context-Free Grammars

For this homework, you do not have to type and print your answers given that it includes drawings of derivation trees. However, your homework should still be done in a professional manner and your answers should be clear and readable.

1. Using the grammar for real-number constants discussed in class, write a set of rewrite rules for signed real-number constants that allow an optional sign at the front of the constants. Use signed-real-const as the new start symbol. You can reuse as much or as little of the real-number constant grammar rules as you deem appropriate. Examples of valid signed real-number constants are:

   -3.56, +17.E09, 4.95

2. Using the following rewrite rules for Boolean expressions, give a derivation for the Boolean expression (NOT((F AND T)) OR F). Also draw a derivation tree corresponding to the derivation.

   bool-exp	→ T |
   	→ F |
   	→ NOT ( bool-exp ) |
   	→ ( bool-exp AND bool-exp ) |
   	→ ( bool-exp OR bool-exp )

3. Using the following rewrite rules for Boolean expressions, find two different derivation trees for the Boolean expression NOT(T OR T AND F).

   bool-exp	→ T |
   	→ F |
   	→ NOT ( bool-exp ) |
   	→ bool-exp AND bool-exp |
   	→ bool-exp OR bool-exp

4. Using the following rewrite rules for arithmetic expressions, draw a derivation tree for the expression 5*3+1+4.

   expr	→ expr add-op term | term
   term	→ term mult-op factor | factor
   factor	→ ( expr ) | digit-seq
   add-op	→ + | -
   mult-op	→ * | DIV | MOD
   digit-seq	→ digit digit-seq | digit
   digit	→ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

5. Using the following rewrite rules for arithmetic expressions, draw a derivation tree for the expression 5*3+1+4.

   expr	→ term { add-op term }
   term	→ factor { mult-op factor }
   factor	→ ( expr ) | digit-seq
   add-op	→ + | -
   mult-op	→ * | DIV | MOD
   digit-seq	→ digit digit-seq | digit
   digit	→ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

   Note: A pair of new special symbols ('{' and '}') is used in the rewrite rules above. The meaning of {...} is that the string of nonterminal and terminal symbols appearing between { and } can be repeated 0 or more times. For instance, the first rewrite rule:

   expr	→ term { add-op term }

   is equivalent to the following (infinite) set of rewrite rules:

   expr	→ term |
   	→ term add-op term |
   	→ term add-op term add-op term |
   	→ term add-op term add-op term add-op term |
   	→ ...