User Tools

Site Tools


cc18:assignment_1

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cc18:assignment_1 [2018/01/20 23:24] (current)
hossein created
Line 1: Line 1:
 +====== Interpreter for While-Language ======
  
 +==== Introduction ====
 +
 +You will write an interpreter for the while language (introduced in [[cc18:​lecture_2|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. 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
 +
 +==== 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. 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.
 +
 +
 +==== Deadline and Deliverables ====
 +
 +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.
cc18/assignment_1.txt · Last modified: 2018/01/20 23:24 by hossein