Mini-Project 1: You First Interpreter

One-Week Check-in

To verify you're making progressing the mini-projects, you will be required to submit part of the mini-project, along with some written problems, by Thursday 10/30 8:00PM Monday 11/3 8:00PM.

This time around, you must submit:

• (20%) An implementation of parse, as detailed in the mini-project specification. You should be able to leave your implementations of the other functions partial or empty as long as your code builds.
• (20%) Solutions to the written problems below.

Note. We will not re-test parts of the mini-project from the one-week check-in. To recieve full credit on the mini-project, you must successfully submit both the one-week check-in and the complete mini-project.

Written Problems

Both of the problems below will consider the following grammar.

<expr>  ::= let <var> = <expr> in <expr>
          | <expr> + <expr1>
          | <expr1>
<expr1> ::= <num> | <var> | ( <expr> )
<num>   ::= 1 | 2 | 3
<var>   ::= x | y | z

Parse Tree

Draw a parse tree in the above grammar for the following sentence.

1 + (let x = let y = 2 in y in x)

Ambiguity

Demonstrate that the above grammar is ambiguous. That is, give a sentence that has multiple parse trees in the above grammar. Also draw both parse trees.