Design note

Ambiguity in Parsing
When parsing expressions, ambiguity arises when a single sequence of tokens can be interpreted in multiple ways. The parser’s role is not only to validate syntax but also to determine how different parts of the input relate to the grammar. Without clear rules, the parser may construct different syntax trees for the same expression, leading to different evaluation results.

Operator Precedence
Precedence defines the order in which different operators are evaluated. Operators with higher precedence are evaluated before those with lower precedence—they “bind tighter” to their operands. For example, in an expression combining division and subtraction, division is evaluated first due to its higher precedence.

Associativity
Associativity determines evaluation order when multiple operators of the same type appear in sequence.

• Left-associative: evaluation proceeds from left to right
• Right-associative: evaluation proceeds from right to left

For instance:

5 - 3 - 1

is interpreted as:

(5 - 3) - 1

Without well-defined precedence and associativity rules, expressions become ambiguous and unreliable.

Operator Hierarchy

Name	Operators	Associativity
Equality	== !=	Left
Comparison	> >= < <=	Left
Term	- +	Left
Factor	/ *	Left
Unary	! -	Right

Design note

There are many parsing techniques—such as LL, LR, LALR, parser combinators, and others—but for this interpreter, a simpler and highly effective approach is used: recursive descent parsing.

Recursive descent is a top-down parsing technique. It starts from the highest-level grammar rule (typically expression) and progressively breaks it down into smaller sub-expressions until reaching the most basic elements of the syntax tree.

This method relies on straightforward, handwritten code instead of parser generators like Yacc, Bison, or ANTLR. Despite its simplicity, recursive descent is:

• Efficient and fast
• Easy to understand and maintain
• Capable of handling complex grammar structures
• Well-suited for detailed error reporting

The parser’s control flow naturally mirrors the structure of the grammar, making the implementation intuitive and closely aligned with the language design.

Design note

Role of the Parser
A parser has two primary responsibilities:

• Generate a syntax tree for valid input
• Detect and report errors for invalid input

In real-world development environments, parsers frequently process incomplete or incorrect code. Therefore, robust error handling is essential for a good user experience.

Error Handling Requirements
A well-designed parser should:

• Detect and clearly report syntax errors
• Avoid crashing or entering infinite loops
• Continue parsing after encountering errors when possible
• Report multiple errors in a single pass
• Minimize cascading errors caused by earlier failures

Error Recovery
Error recovery is the mechanism that allows the parser to continue processing after encountering an error.

Panic Mode Recovery
In panic mode, the parser immediately stops processing the current construct when an error is detected. It then skips tokens until it reaches a point where parsing can safely resume. This process is called synchronization.

Entering Panic Mode
For example, while parsing a parenthesized expression, if the parser fails to find the expected closing ), it triggers an error and enters panic mode.

Synchronization in Recursive Descent
In recursive descent parsing, the parser’s state is implicitly stored in the call stack. Each active grammar rule corresponds to a function call. To recover from an error:

• The parser unwinds the call stack
• Skips tokens until a safe synchronization point is found
• Resumes parsing from a stable state

This strategy allows the parser to recover gracefully while continuing to provide useful feedback to the user.

Design note

Expression Statements
An expression statement allows an expression to appear where a statement is expected. These are primarily used when evaluating expressions that produce side effects, such as function calls.

someFunction();

Print Statements
A print statement evaluates an expression and displays its result to the user.

print 2 + 1;

Grammar

program   → statement* EOF ;

statement → exprStmt
          | printStmt ;

exprStmt  → expression ";" ;
printStmt → "print" expression ";" ;
      

Expressions vs Statements

• Expressions produce values and can be nested.
• Statements perform actions and control execution.

This separation ensures a clean and predictable structure in both parsing and execution.

Design note

Expressions and statements are represented using separate class hierarchies in the AST.

• Expr → represents expressions (value-producing)
• Stmt → represents statements (execution-oriented)

This separation improves:

• Type safety (compile-time validation)
• Code clarity and maintainability
• Clear separation of responsibilities

Base Class

abstract class Stmt {}

The AST generator is extended to include statements, producing specific subclasses such as print and expression statements.

Design note

Variable Declaration
A variable declaration introduces a new binding between a name and a value.

var beverage = "espresso";

Variable Access
A variable expression retrieves the value associated with a name.

print beverage;

Grammar

program      → declaration* EOF ;

declaration  → varDecl
             | statement ;

varDecl      → "var" IDENTIFIER ( "=" expression )? ";" ;

primary      → IDENTIFIER | ... ;
      

If no initializer is provided, the variable is assigned a default value (nil). Accessing a variable before it is defined results in a runtime error.

Design note

Variable bindings are stored in a structure called an environment. Internally, this behaves like a map:

• Keys → variable names
• Values → runtime values

The interpreter maintains an environment instance to store variables during execution.

private Environment environment = new Environment();
      

Operations supported:

• Define a variable
• Retrieve a variable’s value
• Update an existing variable

This structure allows variables to persist throughout program execution.

Design note

Assignment allows updating the value of an existing variable.

a = 2;

In this language, assignment is an expression, not a statement. It has the lowest precedence and is right-associative.

expression → assignment ;

assignment → IDENTIFIER "=" assignment
           | equality ;
      

Key Concept

• l-value: location being assigned to
• r-value: value being assigned

Only valid assignment targets (like variables) are allowed. Invalid targets result in a syntax error. Assignment expressions return the assigned value, allowing chaining:

print a = 2; // prints 2

Design note

A scope defines where a variable is accessible. This language uses lexical scope, meaning variable resolution is determined by the structure of the code.

Block Scope

{
  var a = "inside";
}
print a; // Error
      

Variables declared inside a block are only accessible within that block.

Nested Scope & Shadowing

var a = "global";
{
  var a = "local";
  print a; // local
}
print a; // global
      

Inner variables can shadow outer variables without modifying them.

Environment Chaining
Each block creates a new environment linked to its enclosing one. Variable lookup proceeds from:

• Current (innermost) scope
• Outward through enclosing scopes

This ensures correct resolution of both local and global variables.

Block Grammar

statement → exprStmt
          | printStmt
          | block ;

block     → "{" declaration* "}" ;
      

Design note

Any sufficiently expressive programming language is capable of performing arbitrary computation. This idea is formalized through models like Turing machines and lambda calculus.

In practice, control flow determines how a program executes. It can be broadly divided into:

• Conditional flow: executes code selectively
• Looping flow: repeats execution of code

These constructs allow programs to make decisions and perform repeated computations. :contentReference[oaicite:0]{index=0}

Design note

The if statement enables conditional execution based on a boolean expression.

statement → exprStmt
          | ifStmt
          | printStmt
          | block ;

ifStmt    → "if" "(" expression ")" statement
           ( "else" statement )? ;
      

Behavior

• If the condition is truthy → execute the first statement
• If falsey and else exists → execute the alternative statement

Dangling Else Problem
When nested if statements omit braces, it can be unclear which if an else belongs to. This ambiguity is resolved by associating the else with the nearest preceding if.

Design note

Logical operators and and or are also control flow constructs, as they determine whether expressions are evaluated.

expression → assignment ;
assignment → IDENTIFIER "=" assignment
           | logic_or ;

logic_or   → logic_and ( "or" logic_and )* ;
logic_and  → equality ( "and" equality )* ;
      

These operators typically use short-circuit evaluation:

• or stops when a truthy value is found
• and stops when a falsey value is found

Design note

The while loop repeatedly executes a statement as long as its condition remains truthy.

statement  → exprStmt
           | ifStmt
           | printStmt
           | whileStmt
           | block ;

whileStmt  → "while" "(" expression ")" statement ;
      

Behavior

• Evaluate condition
• If truthy → execute body
• Repeat until condition becomes false

Design note

The for loop provides a compact way to write iteration logic.

forStmt → "for" "(" ( varDecl | exprStmt | ";" )
          expression? ";"
          expression? ")" statement ;
      

A for loop consists of three parts:

• Initializer: runs once before the loop starts
• Condition: checked before each iteration
• Increment: executed after each iteration

Example:

for (var i = 0; i < 10; i = i + 1) print i;

Internally, a for loop can be transformed into an equivalent while loop, making it a higher-level construct built on top of simpler control flow.

Design note

A function call evaluates a callee expression and invokes it with arguments.

callee(arguments);

The callee is not limited to identifiers—it can be any expression that evaluates to a callable object.

Grammar

unary → ( "!" | "-" ) unary | call ;
call  → primary ( "(" arguments? ")" )* ;
      

This allows chained calls such as:

fn(1)(2)(3);

Evaluation Process

• Evaluate the callee expression
• Evaluate each argument (left to right)
• Invoke the callable with evaluated arguments

Callable objects implement a common interface (e.g., SunCallable) which defines how calls are executed. :contentReference[oaicite:0]{index=0}

Design note

Function calls must be validated before execution.

Invalid Call Targets
If the callee is not callable, a runtime error is raised:

"not a function"();

Arity Checking
Each function defines an arity (number of expected arguments).

fun add(a, b, c) {
  print a + b + c;
}
      

Calling with incorrect argument count results in an error:

add(1, 2);       // too few
add(1, 2, 3, 4); // too many
      

The interpreter validates argument count before invocation to ensure correctness.

Design note

Native functions are implemented in the host language but exposed to user programs. They are useful for:

• Accessing system features (time, IO, etc.)
• Providing built-in functionality

Example:

clock();

This function returns the current time, allowing programs to measure execution duration.

Native functions are part of the runtime and are typically registered in the global environment.

Design note

Functions are declared using the fun keyword.

declaration → funDecl
            | varDecl
            | statement ;

funDecl     → "fun" function ;
function    → IDENTIFIER "(" parameters? ")" block ;
      

A function declaration:

• Binds a name to a callable object
• Defines parameters and a body

Design note

A return statement exits a function and optionally provides a value.

return expression;

If no value is provided, the function returns nil.

Execution Behavior
Return statements may appear inside nested constructs, but they must immediately exit the entire function. To implement this, the interpreter uses a controlled mechanism (such as exceptions) to unwind execution until the function boundary is reached.

This ensures:

• Immediate function exit
• Correct value propagation
• Consistent execution behavior