User Tools

Site Tools


cc17:assignment_1

This is an old revision of the document!


Interpreter for While-Language

Introduction

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

While Language Syntax

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.

Program::=Statement* <EOF>
Statement::=SingleStatement ;
if ( Expression ) Statement
if ( Expression ) Statement else Statement
while ( Expression ) Statement
for ( SingleStatement ; Expression ; SingleStatement ) Statement
{ Statement* }
SingleStatement::=ɛ
println ( " <STRING_LITERAL> " , Identifier )
Identifier = Expression
Expression::=Expression ( && | || | < | == | > | + | - | * | / | % ) Expression
! Expression
- Expression
( Expression )
Identifier
<INTEGER_LITERAL>
Identifier::=<IDENTIFIER>
  • <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.

Implementation Skeleton

We provide a stub for your implementation ( here). 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

Tasks

1) 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).

2) Desugaring

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.

Visitor Pattern

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.

Deadline and Deliverables

The deadline of this project is February 10th at 11:59. Please upload only the java files in the interp package: Interpreter.java and TreeSimplifier.java.

cc17/assignment_1.1485732998.txt.gz · Last modified: 2017/01/29 18:36 by hossein