Project: Interpreter Solution

Background




For this project, you will write an interpreter for a small fragment of JavaScript. To write an interpreter, you need a parser to turn JavaScript’s concrete syntax into an abstract syntax tree (as explained in class). However, you don’t need to write the parser yourself. We have provided it for you.







Concrete Syntax




The following grammar describes the concrete syntax of the fragment of JavaScript that you will be working with.

Numbers
n ::= …


Variables
x ::=
…


Expressions
e ::= n
numeric constant


|
true
boolean value true


|
false
boolean value false


|
x
variable reference


|
e 1 + e 2
addition


|
e 1 - e 2
subtraction


|
e 1 * e 2
multiplication


|
e 1 / e 2
division


|
e 1 && e 2
logical and


|
e 1 || e 2
logical or


|
e 1 e 2
less than


|
e 1 < e 2
greater than


|
e 1 === e 2
equal to
Statements
s ::= let x = e ;
variable declaration


|
x = e ;
assignment


|
if ( e ) b 1 else b 2
conditional


|
while ( e ) b
loop


|
print( e );
display to console
Blocks
b ::=
{ s 1 … s n }


Programs
p ::= s 1 … s n








Parser




We have provided two parsing functions. The function parser.parseExpression parses expressions ( e ) and the function parse.parseProgram parses programs ( p ). Note that functions produce results with a kind field that is either "ok" or "error" .For example:







parser.parseExpression("1")



{




value: {




kind: "number",




value: 1 },




kind: "ok"




}




Programming Task




Your task is to implement the following functions:







Input: The AST of an expression and a state object.



Output: The result of the expression (number or boolean). function interpExpression(state, e) {



...




}




Input: The AST of a statement and a state object.



Output: Return nothing;



function interpStatement(state, p) {




...




}




Input: The AST of a program.



Output: The final state of the program function interpProgram(p) {



let state = { }; // Use at input to interpStatement




...




return state; // Do not change this line




}

Note that the inputs of these functions are abstract syntax trees, not concrete syntax .Therefore, you can run your code by using the parser, or by directly constructing ASTs by hand. E.g.:




interpProgram(parser.parseProgram("let x = 10; x = x * 2;").value) { x: 20 }




interpProgram([




{ kind: "let", name: "x", expression: { kind: "number", value: 10 } },




{ kind: "assignment", name: "x",







expression: {




kind: "operator", op: "*", e1: { kind: "variable", name: "x" },




e2: { kind: "number", value: 2 } } } ]);




{ x: 20 }




Suggested Approach




We suggest taking the following approach:




Implement interpExpression ,following the template shown in class. You can use an empty object ( { } ) for the state if you do not have any variables, or you can set the values of variable by hand. For example



test("multiplication with a variable", function() {




let r = interpExpression({ x: 10 }, parser.parseExpression("x * 2").value); assert(r === 20);




});

Implement interpStatement and interpProgram ,following the template shown in class. You should be able to test that assignment updates variables. For example: test("assignment", function() {



let st = interpProgram(parser.parseProgram("let x = 10; x = 20;").value); assert(st.x === 20);




});




Finally, test your interpreter, you should try writing some simple programs. For example, you should be able to write an iterative factorial or fibonacci with your interpreter.