JLox - Interpreter Implementation in Java

This is a slightly modified version of interpreter based on the book "Crafting Interpreters".

Sample Code for Lexer at the moment

class Breakfast {
    init(jam, bread) {
        this.jam = jam;
        this.bread = bread;
    }
}
var b = Breakfast("Peanut Butter", "Brown Bread");
var num1 = 5;
var num2 = 6;
var num3 = 4;
num3 = num3 * 5;
var num4 = (num1 - num3) * num2 + num3 * num1;
print "Hello Hello!";

Grammar implemented so far

program ::= declaration* EOF;
declaration ::= var_decl | fun_decl | statement;
statement ::= print_stmt | expr_stmt | readInto_stmt | block_stmt | if_stmt | while_stmt | break_stmt;
print_stmt ::= "print" expression ";";
expr_stmt ::= expression ";";
var_decl ::= "var" var_lvalue ("=" expression)? ";";
readInto_stmt ::= "readInto" IDENTIFIER ";";
block_stmt ::= "{" declaration* "}" ";";
if_stmt    ::= "if" "(" expression ")" statement ("else" statement )?;
while_stmt ::= "while" "(" expression ")" statement;
break_stmt ::= "break" ";";
fun_decl ::= "fun" IDENTIFIER (" parameters? ")" block_stmt;
return_stmt ::= "return" expression ";";

expression ::= assign | logical_expr | literal | unary | binary | expr_group | var_value;
expr_group ::= "(" expression ")";
boolean ::= "true" | "false" ;
literal ::= NUMBER | STRING | boolean | "nil";
unary  ::= ( "-" | "!" ) primary | call;
primary ::= literal | var_value | fun_expr;

call_expr ::= expression "(" arguments? ")";
arguments ::= expression ("," expression)*;
fun_expr ::= "fun" "(" parameters? ")" block_stmt;
parameters ::= IDENTIFIER ("," IDENTIFIER )*;

var_value ::= IDENTIFIER;
binary ::= expression binop expression;
binop ::= "<" | ">" | "==" | "<=" | ">=" | "+" | "-" | "*" | "/";
assign::= lvalue "=" expression;
logical_expr ::= or_expr | and_expr;
or_expr ::= expression ("or" | ||) expression;
and_expr ::= expression ("and" | &&) expression;

lvalue ::= var_lvalue;
var_lvalue ::= IDENTIFIER; 
#To be precise, var_lvalue is any variable used in lhs of assign expr or var_decl.

Sample Code for Interpretation

var x = 5;
var y = 9;
var z = (x * x) + 2 * x * y + y * y;
print z;
var quoteOfTheDay;
print "Enter quote of the day: ";
readInto quoteOfTheDay;
print quoteOfTheDay;

Block Scoping

The language support shadowing of variables and re-declaration of the existing variables like we have in JS with var based variable declaration. While var in JS is function-scoped, our language has block-level scoping.

{
var a = 5;
print a;
    {
    var a = 10;
    print a;
    }
print a;
}

Here the output will be: 5 10 5

Logical Construct (AND / OR)

Like JS, the logical operation gets short-circuited which means:

For OR operation, right expression is only evaluated if left expression evaluates to false. For AND operation, right expression is only evaluated if left expression evaluates to true.

var x = 5;
var y = 6;
print x == 5 && y == 6; //→ true
print x > 5 and z == 5; //→ false (Notice, how variable z (undefined at this point) doesn't throw any Runtime error.)

If-Else

var x = 5;
var y = 3;
if ( x >= 1 && y >= 2 ) {
    print "True that";
} else {
    print "You are wrong!";
}

While and Break Statement

Sample code to print from 1 to 10.

Wait: It's actually 1 to 5 due to break.

var i = 1;
while ( i <= 10 ) {
    print i;
    if ( i == 5) {
        break;
    }
    i = i + 1;
}

NOTE: A ParseError will be thrown by parser if you try to use break outside loop.

Functions

fun hello() {
    print "Welcome!!!";
}
hello(); //→ Welcome!!!
hello(); //→ Welcome!!!
hello(); //→ Welcome!!!

fun factorial(a) {
    if (a == 1) return 1;
    else return a * factorial(a - 1);
}
print factorial(10); //→ 3628800

Inner Function

fun makeCounter() {
var count = 0;
fun counter() {
   count = count + 1;
   return count;
}
return counter;
}
var counter = makeCounter();
print counter(); // 1
print counter(); // 2
print counter(); // 3

var c2 = makeCounter();
print c2(); // 1
print c2(); // 2
print c2(); // 3

Function Expression / Anonymous function

var hello = fun() {
    print "Hello from here!";
    print "Are you sure?";
};
var factorial = fun(n) {
    if (n == 1) return 1;
    return n * factorial(n-1);
};
hello();
//→ Hello from here!
//→ Are your sure?

print fib(5); //→ 120

var multiply = fun (a, b, c, d, e, f, g, h, i, j, k) {
    return a * b * c * d * e * f * g * h * i * j * k;
};
print multiply(1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 3); //→ 10368
print multiply(1, 2); //→ Expected 11 arguments but got exactly 2 [line X]

Native Function

It's a way to write function implementation in the host programming language. With this, we can bring forth possibly everything that Java currently provides as a function declaration.

For educational purpose, we have implemented two native functions:

clock() → return number of second elapsed after Jan 1, 1970 till this function is called.

pause(x) -> pauses the program for x seconds.

Globals and Locals : Scoping Rules, Resolution and Variable Bindings

Scopes

Programs operate with a chain of scopes.

• Local : All variables declared within that block.
• Enclosing : Variables from outer blocks are accessible via an environment chain.
• Global : Variables outside any scoping rules. (Also, includes built-in variables and functions.).

Resolution

Internally, the resolver maintains a stack of scopes, where each block introduces a new table of variables and their resolution states. The Resolver and Interpreter are tightly coupled in the sense that for every variable that’s resolved, the interpreter records how far its declaration is from its point of use. Anything declared outside blocks or functions lives in the global environment (interpreter.globals) and is not tracked by the resolver’s scope stack.

Variable Bindings

For each block or function call, a new environment is created which stores variables declared within that scope. Bind names to scopes statically via Resolver & bind names (optionally, to values) during runtime via Environment.

var globalVar = 5;
fun outerFunction() {
  var outerVar = 55;
  fun innerFunction() {
    var localVar = 555;
    print globalVar;
    print outerVar;
    print innerVar;
  }
  return innerFunction;
}
var innerFunction = outerFunction(); 
innerFunction();
//→ 5
//→ 55
//→ 555

Resolution

-- Variable must be used somewhere if it is already declared, it throws a static resolution error if it is not true.