You will write an interpreter for the while language (introduced in Lecture 2).

Since you have not yet implemented the lexer and parser of you compiler, you will work directly on the Abstract Syntax Tree (AST) of while programs. The grammar of the while language is the following.

• <IDENTIFIER> represents a sequence of letters, digits and underscores, starting with a letter and which is not a keyword. Identifiers are case-sensitive.
• <INTEGER_LITERAL> represents a sequence of digits, with no leading zeros
• <STRING_LITERAL> represents a sequence of arbitrary characters, except new lines and ".
• <EOF> represents the special end-of-file character

The variables in the while-language are always of type integer. The operators that return truth values (such as <, ==, &&, etc.) always return 0 or 1. When an expression is used as a boolean (for example in the condition of a while statement), any non-zero value evaluates to true and zero evaluates to false.

We provide a stub for your implementation. You can download the stub from the following folder. This folder is accessible from the CS Department Linux systems (e.g., queeg.cs.rit.edu and ICLs 1,2, and 3).

/usr/local/pub/hh/cc18/interp

This code defines Java classes for the AST node structure (names of nodes match the names of the non-terminals in grammar), a pretty-printer for program AST, as well as some example ASTs of different programs. We also give you a minimal skeleton that you must use for the interpreter. This code contains the following files:

• src/whilelang/ast contains all the class definitions related to AST. It also includes the Tree Printer that pretty prints the AST.
• src/whilelang/progs/Programs.java contains three examples of ASTs for simple programs (squares, collatz, sums)
• src/whilelang/interp/TreeSimplifier contains a stub for for-loop elimination (details later)
• src/whilelang/interp/Interpreter.java contains a skeleton for the interpreter
• src/whilelang/interp/Main.java contains the main method which runs the interpreter

Implement the methods in the Interpreter class so that it executes the programs passed to it. Print the output from println straight to the console. Add as many helper methods and fields as you need in the same file. Remember that your interpreter should run each test case independently from the others (ie. when running test A then test B, test A should have no influence on the output for test B).

The AST class hierarchy we give you can represent both while and for loops, and your interpreter should work on both. However it is sometimes desirable in a compiler to reduce the number of different tree node types by merging constructs that are semantically equivalent, while their concrete syntax is different. This can reduce the amount of work for later phases (for example, it could be simpler to write code to optimize only one type of loops). Implement TreeSimplifier so that it replaces all for loops by equivalent subtrees using while loops. Again, add as many methods and members as you wish, but keep them in the same file. Your interpreter should of course produce the same result whether the programs are simplified or not.

The code stub (and your final interpreter) use the visitor pattern from object oriented programming. Read section 1.3 of Tiger book to learn about how to define trees in Java. To learn about visitor pattern read section 4.3. One of the main advantages of the visitor pattern is that it helps the programmer to avoid using instanceof which is a bad programming practice. You are not allowed to use instanceof in this assignment.

The deadline of this project is January 30th at 11:59pm (https://mycourses.rit.edu). Please upload only the java files in the interp package: Interpreter.java and TreeSimplifier.java. You do not need to change the rest of files.