JLOX: A Recursive Descent Interpreter using an abstract syntax tree (AST)

Introduction

JLOX is a lightweight, dynamically-typed programming language based on Lox, designed with simplicity and flexibility in mind. It is implemented using recursive descent parsing and runs on the Java Virtual Machine (JVM). This document details the grammar, evaluation model, and execution workflow of JLOX.

---

Features

• Dynamic Typing: Variables can hold any type at runtime.
• Garbage Collection: Managed by the JVM.
• Lexical Scoping: Variables are scoped within blocks.
• Functions as First-Class Citizens: Functions can be assigned to variables, passed as arguments, and returned.
• Interpreter Execution: Runs code line by line without prior compilation.
• Native Interoperability: Java functions can be called using Foreign Function Interface (FFI).
• Nox Mechanism: A unique value influencing control flow in unconventional ways.

---

Very Simple Explaination for How the Language Works

JLOX follows a structured execution model that includes lexical analysis, parsing, semantic analysis, and interpretation.

Execution Model

1. Lexical Analysis (Scanning)

The Scanner converts source code into tokens.

var x = 10;

Produces tokens:

VAR IDENTIFIER( x ) EQUAL NUMBER( 10 ) SEMICOLON

2. Parsing (Abstract Syntax Tree)

The Parser constructs an AST from tokens. Example AST for var x = 10;:

VarDecl(
  name = "x",
  initializer = Literal(10)
)

3. Semantic Analysis

• Resolves variable scope
• Validates function calls

4. Interpretation (Execution)

The Interpreter walks the AST and executes code.

print x;

Would produce output:

10

---

Syntax

Variables

var x = 10;
var name = "Alice";

Control Flow

If-Else

if (x > 5) {
    print "Greater than 5";
} else {
    print "Not greater than 5";
}

Loops

while (x < 20) {
    print x;
    x = x + 1;
}

Functions

fun greet(name) {
    print "Hello, " + name;
}
greet("Alice");

The nox Literal

if (nox) {
    print "This runs";
} else {
    print "This also runs";
}

---

Language Explanation

Recursive Descent

JLOX's parser processes the source code from the top-level program rule down to primary expressions by recursively calling functions corresponding to each production rule. This method ensures clarity and modularity in parsing.

Post-Order Traversal

The Abstract Syntax Tree (AST) generated by the parser is traversed in post-order, meaning child nodes are evaluated before their parent nodes. This guarantees correct evaluation of nested expressions and operations.

Panic Mode

If a syntax error is encountered, JLOX's parser enters panic mode, skipping tokens until it reaches a synchronization point (such as a semicolon). This prevents the entire parsing process from halting due to a single error.

Visitor Pattern

JLOX utilizes the Visitor Pattern to decouple the AST structure from operations performed on its nodes. This makes it easy to extend and maintain language features without modifying the core AST structure.

nox Propagation

The nox literal propagates through expressions, affecting control flow. If an operation involves nox, the result is typically nox, allowing for controlled execution paths in conditional statements.

Example:

var x = 5 / nox; // This will result in 'nox' being propagated, affecting subsequent evaluation.

---

File Organization & Flow of Work

Project Structure and Components

├── src/                    # Source code
│   ├── lox/                # Main interpreter source files
│   │   ├── AstPrinter.java   # Prints AST representation of expressions
│   │   ├── Environment.java  # Stores variables and their scopes
│   │   ├── Expr.java         # Defines expression nodes for AST
│   │   ├── Interpreter.java  # Evaluates AST; handles dynamic typing, nox propagation
│   │   ├── Lox.java          # Entry point; bootstraps REPL and file execution
│   │   ├── LoxCallable.java  # Interface for callable objects like functions
│   │   ├── LoxFunction.java  # Implements LoxCallable for function execution
│   │   ├── Nox.java          # Handles special nox literal behavior
│   │   ├── Parser.java       # Recursive descent parser that generates AST
│   │   ├── Return.java       # Represents function return statements
│   │   ├── RuntimeError.java # Handles runtime errors in interpreter
│   │   ├── Scanner.java      # Lexical analyzer that tokenizes source code
│   │   ├── Stmt.java         # Defines statement nodes for AST
│   │   ├── Token.java        # Represents individual tokens produced by the scanner
│   │   └── TokenType.java    # Enum defining all token types
│   ├── tool/               # Tools for Jlox
│   └── └── GenerateAst.java # Generates AST classes from grammar definitions
│
├── grammar/                # Jlox grammar definitions
│   └── grammar.txt         # Contains full recursive descent grammar
│
└── tests/                  # Test files
    ├── all_test.jlox       # general testing
    ├── issue_test.jlox     # Tests for known issues
    ├── nox_test.jlox       # Tests specific to nox behavior
    └── test.jlox           # simplified testing

---

Grammar

JLOX's syntax is defined using a recursive descent grammar, expressed in an EBNF-like notation:

program     → declaration* EOF ;
declaration → varDecl | statement ;
varDecl     → "var" IDENTIFIER ( "=" expression )? ";" ;
statement   → exprStmt | printStmt | block | ifStmt | whileStmt | returnStmt ;
exprStmt    → expression ";" ;
printStmt   → "print" expression ";" ;
block       → "{" declaration* "}" ;
ifStmt      → "if" "(" expression ")" statement ( "else" statement )? ;
whileStmt   → "while" "(" expression ")" statement ;
returnStmt  → "return" expression? ";" ;
expression  → assignment ;
assignment  → IDENTIFIER "=" assignment | logic_or ;
logic_or    → logic_and ( "or" logic_and )* ;
logic_and   → equality ( "and" equality )* ;
equality    → comparison ( ( "!=" | "==" ) comparison )* ;
comparison  → term ( ( ">" | ">=" | "<" | "<=" ) term )* ;
term        → factor ( ( "-" | "+" ) factor )* ;
factor      → unary ( ( "/" | "*" ) unary )* ;
unary       → ( "!" | "-" ) unary | primary ;
primary     → NUMBER | STRING | "true" | "false" | "nox" | "(" expression ")" ;

---

Foreign Function Interface (FFI) and Native Extensions

JLOX supports FFI, enabling Java interoperability.

Implementation

• Calling Java Methods: JLOX can invoke Java methods.
• Binding Native Functions: Java functions are wrapped in LoxCallable.
• JVM Interoperability: JLOX functions interact with Java at runtime.

Example of FFI in JLOX

Defining a Native Function in Java

class NativeTimeFunction implements LoxCallable {
    @Override
    public Object call(Interpreter interpreter, List<Object> arguments) {
        return (double) System.currentTimeMillis() / 1000.0;
    }
    @Override
    public int arity() { return 0; }
}

Registering the Function

environment.define("clock", new NativeTimeFunction());

Using in JLOX

print clock(); // Prints current time in seconds

---

How to Build and Run

0. Prerequisites

• Java Development Kit (JDK) 8 or higher
• Makefile

1. Clone the repository and build using Make:

git clone https://github.com/Ahmad-Faraj/JLOX-Interpreter.git
cd jlox

2. Compile the JLOX Source Code

javac -d bin src/lox/*.java

3. Running JLOX Tests

java -cp bin lox.Lox tests/test.jlox
java -cp bin lox.Lox tests/all_test.jlox
java -cp bin lox.Lox tests/issue_test.jlox
java -cp bin lox.Lox tests/nox_test.jlox

4. How to use the tools

Generate the AST Classes

JLOX uses a tool to generate AST classes from grammar definitions.

javac -d bin src/tool/GenerateAst.java
java -cp bin tool.GenerateAst src/lox

Simplified method

Compile the project

make

Run JLOX (REPL mode)

make run

Generate AST classes

make tool

Clean compiled files

make clean

---

Contributing

Contributions are welcome! Feel free to fork the repository and submit pull requests.

Star the Repository ⭐

If you find JLOX useful, please consider starring the repository!

---

Acknowledgements

• Crafting Interpreters: Inspired by Crafting Interpreters by Robert Nystrom.