Homework # 2
due Monday, February 9, 11:00 AM

Ambiguous Grammars

Some programming languages have ``if'' expressions:

<expr> ::= <expr> + <expr> | <expr> = <expr> | <expr> * <expr>
        |  if <expr> then <expr> else <expr> 
        |  <INTEGER> | <ID> | ( <expr> )

Thus one can write:

(if x = 0 then 1 else 10 * x ) + y

However the grammar above is ambiguous.

• Show three parse trees for the string ``if 1 = 2 then 3 else 4 * 5 + 6''
• Rewrite the grammar to be unambiguous, where: if has lowest precedence, then =, then + and then *, with highest precedence. Both + and * should have left associativity, and = should be non-associative (x = y = z should be a syntax error).

Book Exercises

Please do exercises 4 and 5 (all four parts of each) in Chapter 4.

First Experience with ML

I assume you have a computer you can install software on. Install SML on your own computer. Start up a session and evaluate the following two expressions:

Time.now();
if 1 = 2 then 3 else 4 * 5 + 6;

Print out the window with the contents of this session. Indicate which of the three parse trees SML/NJ chose for the second expression.

Submitting Your Work

If you do not have your own computer, see me, and I will give you you an alternate assignment.

Turn in your answers on paper.

About this document