COP 4555 - Homework 1

Due Wednesday, January 26

1. Recall the unambiguous grammar for arithmetic expressions discussed in class:

     E -> E+T | E-T | T
     T -> T*F | T/F | F
     F -> (E) | a | b | c
   

   Modify this grammar to allow an exponentiation operator, ^, so that we can write expressions like a+b^c*a. Of course, your modified grammar should be unambiguous. Give exponentiation higher precedence than the other binary operators and (unlike the other binary operators) make it associate to the right.

2. Recall the grammar for the tiny language used in our discussion of recursive-descent parsing. Let us extend the grammar to allow both if-then and if-then-else statements:

     S -> if E then S | if E then S else S | begin S L | print E
     L -> end | ; S L
     E -> a | b | c
   

   Show that the grammar is now ambiguous.

3. Following the approach described in class, write a complete (pseudo-code) recursive-descent parser for the grammar in question 2, including functions S(), L(), and E(). Try to improve on the code given in class by returning helpful error messages.

   [You may wonder how a recursive-descent parser can be written, given the ambiguity that you found in question 2. This ambiguity, known as the dangling else ambiguity, is found in many programming languages, including C and Java. However, you should see that the parser can resolve that ambiguity in a natural way that corresponds to a rule that you should have learned in your study of C or Java.]

• COP 4555 home page
• Geoffrey Smith's home page