DEV Community: Lahari Tenneti

LLVM #2 — Optimiser Support & JIT Compilation

Lahari Tenneti — Tue, 17 Mar 2026 06:48:33 +0000

Having understood what compiler optimisations are and how they work in theory, we now actually wire them into Kaleidoscope, and then take things one step further by adding a JIT compiler so our REPL can evaluate expressions on the spot.

What I built: Commit 91267d2

What I understood:

1) Adding Optimisation Passes:

So far, our codegen was correct but not efficient. The IR we produced was merely a pretty-print of the AST. LLVM provides a FunctionPassManager to change that.
A pass is simply one "go" over the IR that looks for a specific pattern and rewrites it. The FunctionPassManager contains a sequence of passes and runs them over each function in that order, passing the output of one as input to the next.
The key change is in InitialiseModuleAndManagers(). After creating the module and the IR builder, we now also have a whole suite of analysis and pass managers:

TheFPM = std::make_unique<FunctionPassManager>();
TheLAM = std::make_unique<LoopAnalysisManager>();
TheFAM = std::make_unique<FunctionAnalysisManager>();
TheCGAM = std::make_unique<CGSCCAnalysisManager>();
TheMAM = std::make_unique<ModuleAnalysisManager>();

The four AnalysisManagers each correspond to a level of LLVM's IR hierarchy — loops, functions, call-graph SCCs, and whole modules.
They're required so transform passes can look up analysis results when they need them.
Side note: A call graph is one with functions for nodes, with every edge representing a call. So an edge from A to B means A calls B.
SCCs (Strongly Connected Components) in a call graph represent a group of functions where each function can reach/call the other. (Mutual recursion of sorts)

Then we create four transform passes:

TheFPM->addPass(InstCombinePass());    // peephole optimisations
TheFPM->addPass(ReassociatePass());    // reorder expressions
TheFPM->addPass(GVNPass());            // eliminate redundant computations
TheFPM->addPass(SimplifyCFGPass());    // clean up unreachable blocks

A) InstCombinePass:

Handles "peephole" optimisations (small/local rewrites).
1+2 becoming 3.0 before the program ever runs is constant folding at play, and this pass is what catches it in the generated IR.

B) ReassociatePass:

Reorders expressions to enable more opportunities for other passes.
(x+1)+2 becomes x+3. Small change, but it means GVN can now recognise that (x+1)+2 and 1+(x+2) are the same thing.

C) GVNPass (Global Value Numbering):

Assigns a symbolic identity to each new/unique computation and replaces duplicates.
Ex: if we write (1+2+x)*(x+(1+2)), both sides of the multiplication are x+3.
Without GVN, the IR computes x+3 twice. With it, the result is computed once and reused.

So before GVN:

%addtmp = fadd double 3.000000e+00, %x
%addtmp1 = fadd double %x, 3.000000e+00
%multmp = fmul double %addtmp, %addtmp1

After GVN:

%addtmp = fadd double %x, 3.000000e+00
%multmp = fmul double %addtmp, %addtmp

D) SimplifyCFGPass:

Cleans up the control flow graph. If a branch can never be entered into, or a block has no predecessors, this pass removes it.
It's more like keeping the IR tidy after the other passes have finished their work.

Finally, we run the pass manager after every function is constructed, just before returning it:

TheFPM->run(*TheFunction, *TheFAM);

The FunctionPassManager updates the function in-place. The IR going in is the naive transcription; the IR coming out is the cleaned-up, optimised version.

2) JIT Compilation:

Now that we have nice IR coming out of the optimiser, we want to execute it — not just pretty-print it. That's where the JIT comes in.
JIT (Just-In-Time) compilation means converting LLVM IR to native machine code at runtime, in memory, right as the user types. The result is a pointer to executable code we can call directly, as if it were a C function.
Setting it up requires initialising the native target first:

InitializeNativeTarget();
InitializeNativeTargetAsmPrinter();
InitializeNativeTargetAsmParser();
TheJIT = ExitOnErr(KaleidoscopeJIT::Create());

// Side note: LLVM is cross-platform by design. These initialisation calls are what tell
// the JIT to look at the hardware the user is on and prepare to speak its specific language.
// Ex: Even if we're on Apple Silicon (arm64), LLVM could generate x86 code if we told it to.

And setting the module's data layout to match the JIT's:

TheModule->setDataLayout(TheJIT->getDataLayout());

This is important as it ensures that the memory layout of structs, function arguments, and return values matches what the host machine expects.
When the user types a top-level expression like 4+5;, we wrap it in an anonymous function (__anon_expr), add the module to the JIT, look up the symbol, and call it:

auto ExprSymbol = ExitOnErr(TheJIT->lookup("__anon_expr"));
double (*FP)() = ExprSymbol.toPtr<double (*)()>();
fprintf(stderr, "Evaluated to %f\n", FP());

The JIT compiles the LLVM IR to machine code, returns its address, we cast it to a function pointer, and call it like any other native function.
There's no difference at the hardware level between JIT-compiled code and statically linked machine code (i.e., they live in the same address space).

After calling it, we clean it up:

ExitOnErr(RT->remove());

The ResourceTracker (RT) is responsible for the JIT'd memory allocated to that anonymous expression. Removing it frees that memory.

3) The module lifetime problem:

The issue in the REPL:

ready> def testfunc(x y) x + y*2;
ready> testfunc(4, 10);
Evaluated to 24.000000

ready> testfunc(5, 10);
LLVM ERROR: Program used external function 'testfunc' which could not be resolved!

testfunc was defined in the same module as the anonymous expression for testfunc(4, 10).
When we removed that module from the JIT to free the memory for the anonymous expression, we inadvertently deleted testfunc along with it.
The solution: Every function definition gets its own module. The JIT can resolve calls across module boundaries, so testfunc lives in its own module indefinitely.
Each new anonymous expression gets a fresh module, which we remove after execution. Function definitions stay.
But this creates a new problem: when the codegen for a new anonymous expression tries to emit a call to testfunc, that function doesn't exist in the current module.
The IR emitter needs at least a declaration of testfunc to generate a valid call instruction.
The solution is getFunction(), a helper that first checks the current module for a declaration, and if it doesn't find one, regenerates it from FunctionProtos (a map of the most recent prototype for every function we've seen):

Function *getFunction(std::string Name) {
  if (auto *F = TheModule->getFunction(Name))
    return F;

  auto FI = FunctionProtos.find(Name);
  if (FI != FunctionProtos.end())
    return FI->second->codegen();

  return nullptr;
}

So the function "body" lives in its own module in the JIT.
The function "declaration" gets re-emitted into each new module that needs to call it.
The JIT links them at call time.

What's next: Control flow (if/then/else and loops).

Musings:
Learning the piano taught me something about passes. When you're learning a new piece, you don't play the whole thing perfectly on the first try. You play it slowly, fix the wrong notes, correct the timing, then fix the phrasing, then the dynamics. Each run is a pass, and each one builds on the last until what comes out sounds nothing like the stumbling first attempt, but means exactly the same thing. The optimiser does the same thing. The IR that enters is technically correct and the IR that exits is still correct; only better.

Compiler Optimisations

Lahari Tenneti — Tue, 24 Feb 2026 11:03:40 +0000

Before we perform compiler optimisations, we must know what they are, why they're needed, and how we do them.

What:
Compiler Optimisations are systematic transformations that rewrite our source code into faster, smaller machine code without changing its meaning.

Why:
They're needed because programs are full of inefficiencies—redundant calculations, impossible branches, or operations the CPU could do cheaper. Raw code from the parser is readable but slow, so optimisations squeeze out every drop of performance.

Importantly, many impactful optimisations aren't fully hardware-agnostic. Universal ones like "this expression is always 0, delete it" work anywhere, but the big wins (like using SIMD registers, scheduling for a chip's pipeline, or picking specific CPU instructions) are often hardware-specific.

Without a shared layer like LLVM's IR, every backend duplicates this effort. LLVM lets you write optimisations once against the IR, with backends handling hardware translation later.

How:
Compilers apply optimisations in structured passes over the code. First local (within basic blocks, like folding constants), then global (across the function, like dead code elimination), often in multiple rounds. Each pass analyses data flow, rewrites IR, and repeats until no more gains are possible.

As I'd mentioned in the previous post, LLVM uses SSA for this. In action, it's the %addtmp or %multmp1 variables we keep seeing in Kaleidoscope's output. While it looks redundant (mostly because we're used to seeing the output directly), it's what optimisation ultimately depends on.

In most programming languages, we can change/reassign a variable's value whenever we want.

x = 5
x = x + 2
x = 10

In SSA form, every variable is assigned exactly once. If we wish to change the value of x, the compiler creates a new version of it. (Remember persistent data structures and the blockchain example from the Lox resolver?) Hence, the code above looks like this:

%x1 = 5
%x2 = %x1 + 2
%x3 = 10

In fact, through dead-code elimination (see below), it would become more like:

%x3 = 10 #because %x2 isn't used anywhere and %x3 comes immediately after

This is to address the issue of Data Flow Analysis — where did a value come from?

In non-SSA code, if you see a variable on a certain line, you'll have to look at every line before it to figure out which assignment currently "owns" that variable.

But in SSA, the name of the variable is its definition. We know exactly where %x2 was born and what value it holds.

How SSA is used in Compiler Optimisations:

1) Constant Propagation and Folding:

It took me a while to understand that these were two different things. But it's only that they both feed into each other.

Propagation is simply fetching values. If I know the value of a constant used in certain expressions, I'll just replace that variable with its value directly.

r = 5
area = 3.14 * r * r
#becomes
area = 3.14 * 5 * 5

Folding is merely precomputing known values — the actual math is performed at compile-time instead of runtime. It's like saying, "I know the answer to this. Why do I make the CPU calculate it later?"

area = 3.14 * 5 * 5
#becomes
area = 78.5

2) Value Range Propagation:

Tracking the possible range of values a variable can hold, so the compiler can make smarter decisions later in the program.

if (x > 0 && x < 10):
    y = x * 2

The compiler now knows y must be in the range (0, 20). If a later condition asks something like if (y > 100), the compiler can eliminate that branch entirely because it's impossible.
SSA makes it easy to track a variable's range through the program since each definition has a single, known origin.

3) Sparse Conditional Constant Propagation:

Constant propagation + branch awareness; only propagating values along branches that are actually reachable.

x = 5
if (x > 10):
    y = x * 2   #dead; compiler knows x = 5 can never satisfy x > 10
else:
    y = x + 1   #compiler propagates: y = 6

SSA names are unique per definition, so once the compiler knows a branch is dead, every variable inside it is unreachable too. This avoids wastage of effort.

4) Dead Code Elimination:

Removing code that will never execute or whose result is never used.

x = 10
y = x + 5    #y is never used again
return x

becomes:

x = 10
return x

Every SSA variable has a list of uses. If that list is empty, the variable (and the code that produced it) is eliminated.

5) Global Value Numbering:

Assigning a symbolic "number" to each unique computation, then replacing duplicates that produce the same result with a single reference.

a = x + y
b = x + y

Both expressions get the same value number. The compiler replaces b with a, computing x + y only once, even if a and b are in different parts of the function. Again, SSA at play.

6) Partial Redundancy Elimination:

Removing calculations that are redundant on some paths through the program, by hoisting them to a point where they cover all paths.
In the following example, in case of heavy_traffic = true, The CPU calculates distance/speed inside the if block, then calculates it again at the end. That’s unnecessary.
For else, The CPU skips the first calculation and only does it once at the end.
Compiler optimisation's goal is to make the work uniform so the final result is always "pre-calculated."

if (heavy_traffic):
    time = distance/speed
else:
    pass

total_time = distance/speed #why calculate the same thing a second time?

The compiler "hoists" the missing calculation into the else block:

if (heavy_traffic):
    tmp = distance/speed
    time = tmp
else:
    tmp = distance/speed

#Now the final result just uses the 'tmp' already in the register
total_time = tmp

It might look like we're adding code, but we’re actually ensuring that no matter which path the CPU takes, it only performs the heavy division exactly once.
SSA tracks exactly where every value was computed. So the compiler can see at a glance, "this path did the work, that one didn't."

7) Strength Reduction:

Swapping out a costly operation for a cheaper one that produces the same result.

y = x * 8
# becomes
y = x << 3

Multiplying by 8 is multiplying by 2³. In binary, multiplying by 2 is a left shift by one bit, so multiplying by 8 is simply a left shift by three bits.
The CPU performs this using a barrel shifter, which shifts bits in a single clock cycle. It’s basically a network of wires and switches that reroutes bits to new positions simultaneously; more like rearranging than computing.
General multiplication is more complex. The hardware must perform multiple additions and shifts internally, requiring more circuitry and cycles.

8) Register Allocation:

Mapping the potentially unlimited SSA virtual variables down to the finite number of physical CPU registers available at runtime.
Ex: If the function produces %tmp1 through %tmp20 but the CPU only has 6 registers, the compiler figures out which temporaries work at the same time and assigns them registers accordingly, spilling the rest to the stack. Good allocation means fewer memory round-trips and faster code.

What's next: Having established some context to compiler-optimisations, we can proceed with adding support for them and JIT, for Kaleidoscope.

Musings:
Optimisation, at its core, is about simplicity. There's an incredible story from the Mahabharata about this. Dronacharya, the renowned guru, gathered his students—already among the world's finest—to find the greatest archer. The goal was the eye of a wooden bird perched high in a tree. Pointing to it, he asked each student what they saw. They described the tree, the bird’s feathers, and the sky. He dismissed them. When he asked Arjuna, the latter replied, “I only see the eye of the bird.” He shot, and the arrow struck the centre instantly. By treating everything except the target as “noise,” we focus all resources on the singular point of impact. Compiler optimisations do the same, ensuring the CPU never looks at anything but the essential logic. After all, Neti Neti-ing eventually led those ancient minds to the Ultimate Answer.

LLVM #1 - Lexer, Parser, Codegen

Lahari Tenneti — Fri, 13 Feb 2026 06:14:09 +0000

The Lexer/Scanner and Parser aren’t very different from what we’ve done earlier. Both are initial/front-end phases of compilation, after which the code is converted into LLVM IR.

What I built: Commits 15710fe, 2562e61

What I understood:

1) The Lexer:

Reads raw text input one character at a time and groups them into meaningful chunks of code called Tokens.
enum Token defines the kinds of words the language can process. gettok() loops through characters, skips whitespaces, recognises keywords/numbers, and handles comments too (by skipping text after #)

2) AST:

Once the tokens are ready, we need to understand how they relate to each other. A tree is the best way to do the same.
ExprAST is the base/parent class for all the nodes.
public: virtual ~ExprAST() = default;: Here, Expr objects will later be manipulated through pointers to the base (ExprAST) class.
Without virtual, if we wish to delete a subclass node, only the base class' destructor will be called, not the subclass' destructor. Any data stored in the subclass won't be deleted and can affect other areas through leaks.
Thus, we use virtual to delete/release all memory/resources used by the derived (sub)class.
Similarly, NumberExprAST' represents a number,VariableExprASTrepresents a variable,BinaryExprASTrepresents an operator with two operands,CallExprASTrepresents a function call,PrototypeASTrepresents a function signature (not the body), andFunctionAST` represents a full function (prototype + body)

3) The Parser:

Uses operator-precedence parsing for building AST objects for binary expressions and recursive descent parsing for everything else.
Ex: On seeing a number token, it creates a NumberExprAST

4) Code Generation:

This is LLVM specific. We traverse through the AST we've built and ask each node to codegen()
Ex: In NumberExprAST, we use ConstantFP::get to create a floating-point constant in LLVM's internal format.
NamedValues is a symbol table/dictionary for remembering where (in which specific memory location/register) a variable is stored.
Note: LLVM uses Static Single Assignment (SSA), meaning its "virtual registers" can only be assigned once. It's why we see names like %multmp and %multmp1 in our results.
BinaryExprAST::codegen is for generating code for the left and right sides recursively.
Then, we use Builder to create the math instruction (like Builder->CreateFAdd for float addition)
For <, it converts the result to a float (0.0 or 1.0) as Kaleidoscope only uses doubles.
Similarly, FunctionAST::codegen creates a new function in the LLVM Module
Module here is like a project folder; a container that holds all our functions together so they can see and call each other.
It creates a block called entry. LLVM code lives inside such basic blocks (chunks of instructions)
It tells the Builder to start writing instructions into this new block.
It adds the function arguments to NamedValues so the body can use them.
Finally, it creates a ret instruction to finish the function.

5) Driver Code:

The MainLoop is an infinite loop printing ready> waiting for the user to type.
It switches based on what is typed (def, `extern, or just math) and calls the appropriate handler.
HandleDefinition parses the code, generates the LLVM IR, and prints it to the screen.
It also sets up the operator precedence so the math logic works correctly, initialises the module, and starts the loop.

Let’s understand this through an example:

def foo(x) x + 1 is converted by the Lexer into [tok_def] [tok_identifier “foo”] [ ( ] [tok_identifier “x”] [ ) ] [tok_identifier “x”] [ + ] [tok_number1]
The Parser turns it into a FunctionAST object.
The codegen turns that object into LLVM IR define double @foo(double %x) { … }

Results:

What's next: Optimising and Just-in-time (JIT) compilation!

Musings:
The one thing that calms me the most is playing the piano. You see, mindfulness and being focused is a rather difficult thing, especially in the attention economy. So it feels particularly wonderful and refreshing when an activity demands our time, patience, and full focus, lest we compromise on the quality of its outcome. “Right hand first, left hand next, and then do it together.” I feel like every single inch of my brain is dedicated to getting that one bar right. And nothing feels more rewarding than seeing (or maybe hearing?) the fruits of our labour. Whenever I’ve felt bored, lost, confused, overwhelmed, or even happy—the piano has helped me move on feeling better. My mom wanted us to learn some or the other instrument. I was merely “okay” with the idea of learning the piano, but never could I have fathomed how important it would become to me. Life’s little surprises are often like that, with some of the most beautiful experiences coming to us when we least expect it. So it doesn’t hurt to try and be a little open.

LLVM — Introduction and Setup

Lahari Tenneti — Wed, 11 Feb 2026 12:37:50 +0000

Helloo! Welcome to my next project—The LLVM framework (the Kaleidoscope tutorial, to be precise). I decided to try this out as soon as I finished the jlox Interpreter in Robert Nystrom’s Crafting Interpreters.

What’s LLVM?
The ‘Low Level Virtual Machine’ (LLVM) is a full compiler infrastructure that can take various programming languages, generate LLVM Intermediate Representation (IR), optimise it, and finally convert it into hardware-specific machine level code. This low level code is then run on the CPU.

Why am I doing this?
The Abstract Syntax Trees (ASTs) borne out of interpreting any code are specific to its language. When we use LLVM’s IR, which is aware of hardware concepts like registers, memory, arithmetic operations, etc., our language becomes more universal.

As against assembly language, which is very platform/hardware dependent, LLVM (whose IR almost resembles assembly language) supports various machines like Intel x86, ARM, RISC-V, etc. I find heterogenous hardware very fascinating, especially the prospect of hardware-agnostic compilation. That’s pretty much what drew me LLVM.

How I set it up:
While there are many tutorials to familiarise oneself with the platform, I (surprisingly) found the documentation wonderful. Some of it I skipped, but the set-up and introduction were quite helpful. I still haven’t figured out a lot, so I’m taking things slowly. For anyone wanting to start out with LLVM, I’d recommend these:

Getting the source code and building LLVM
An example for using the LLVM tool chain
Disclaimer: Most of what I did below is adapted from these tutorials.

1) Getting LLVM running on macOS (especially Apple Silicon) is very straightforward with Homebrew.

brew install llvm
export PATH="/opt/homebrew/opt/llvm/bin:$PATH"
export CMAKE_PREFIX_PATH="/opt/homebrew/opt/llvm"
source ~/.zshrc

2) Managing Dependencies: I used CMake.

llvm -config —version
cd ~
mkdir toy-compiler
cd toy-compiler
mkdir src build
nano CMakeLists.txt

Here's the CMakeLists.txt (configuration) for the toy-compiler/Kaleidoscope project I'll be doing. It serves as a project manager, telling the compiler where the LLVM "brains" are and which specific libraries (like JIT, native codegen) we want to use.
It doesn't compile the code itself, and instead gathers all the ingredients (libraries, headers, compiler settings) so the build tool (Ninja, in my case) knows what to do.

cmake_minimum_required(VERSION 3.13)
project(ToyCompiler LANGUAGES C CXX)

set(CMAKE_CXX_STANDARD 17)
set(CMAKE_CXX_STANDARD_REQUIRED ON)

find_package(LLVM REQUIRED CONFIG)
message(STATUS "Found LLVM ${LLVM_PACKAGE_VERSION}")

add_definitions(${LLVM_DEFINITIONS})
include_directories(${LLVM_INCLUDE_DIRS})
link_directories(${LLVM_LIBRARY_DIRS})

add_executable(toy src/main.cpp)

# For JIT and native codegen
llvm_map_components_to_libnames(llvm_libs core orcjit native)
target_link_libraries(toy ${llvm_libs})

3) Verifying the build system:

To ensure the libraries are linking correctly, I wrote a simple sanity check in src/main.cpp using LLVM's output stream, llvm::outs()

#include "llvm/Support/raw_ostream.h"
int main() {
    llvm::outs() << "LLVM setup works!\n";
    return 0;
}

To actually compile the project, I used Ninja. It's a small build system focused on speed.

brew install ninja
cd ~/toy-compiler/build
cmake -G Ninja ..
ninja
./toy -> LLVM setup works!

4) An example: To truly understand how compilation happens at lower levels, it helps to follow a program through the entire pipeline, from high level code to bit code, and finally to a native binary.
test1.c

#include <stdio.h>
int main() {
    printf("First go at LLVM!");
    return 0;
}

clang -O3 -emit-llvm test1.c -c -o test1.bc (Clang is the C compiler macOS uses as a front-end; emit-llvm creates the bitcode.)
lli test1.bc (lli directly executes the bytecode.)
llvm-dis < test1.bc | less (This is for looking at the human-readable LLVM assembly code.)
llc test1.bc -o test1.s (llc converts bitcode to native assembly.)
gcc test1.s -o test1.native (This assembles the native file into a program.)
Running ./test1.native → First go at LLVM!

What's next:
The lexer and parser for Kaleidoscope!

Musings:
Sometimes, I get these sudden, intense urges to just... be somewhere. I often find myself wishing for Doraemon’s "Anywhere Door" so I could instantly step into a completely different world. It’s not that I don’t enjoy where I am, but there’s an incomparable high that comes from being somewhere totally foreign.

Travel has always been my ultimate meditation. I once read that our memories of new places are so vivid because we become hyper-sensitive to our surroundings. In our daily lives—the same commute, the same routine—we stop truly "seeing" the world. We stop noticing the colour of the sky, the old man reading the newspaper by the shopfront, or the little puppy prancing around with an aluminium foil. But in a new place, with your senses wide open, you notice everything.

A few years ago, I visited Sikkim (an absolutely stunning state in our North-East), and I’ve never felt more alive. Even now, I can recall every sound, smell, and sight from that trip with perfect clarity. That level of observation taught me how to be more attentive to the daily moments in my life. Ever since, I've tried to carry that traveler’s spirit with me, finding joy in the small details—in the "normal" and the everyday.

Extensions - Lists and for-in loops

Lahari Tenneti — Mon, 09 Feb 2026 07:18:03 +0000

Well, here we are. Here’s my interpreter. I want to get philosophical already, but I’ll save it for the musings section. Anyway, I’ve extended Robert’s jlox interpreter by adding support for lists and for-in loops.

What I built: Commits 8409dee, 1f4f09d, 380a16d, 72972f6, 64fdc5f

What I understood:

I. Lists

1) The basics:

We start by adding the tokens/keywords in the TokenType.java file. Because lists use square brackets, we add them (LEFT_BRACKET, RIGHT_BRACKET)
We then update the scanToken() function in the Scanner to handle the newly added tokens.

case '[': addToken(LEFT_BRACKET); break;
case ']': addToken(RIGHT_BRACKET); break;

We then create two types of expressions through GenerateAst, one for creating a list (Array) and another for accessing or modifying it (Subscript)

2) Parsing for lists:

We update the primary() method to catch a LEFT_BRACKET, create a new list, and check for comma-separated elements until the RIGHT_BRACKET is caught.
We also use chaining to check for sub indices, which if found, are made into a new subscript.

else if (match(LEFT_BRACKET)) {
    Expr index = expression();
    Token bracket = consume(RIGHT_BRACKET, "Expect ']' after index.");
    expr = new Expr.Subscript(expr, bracket, index);
}

3) Visitor methods in the Resolver:

Because we’ve added new AST nodes (Array, Subscript)

4) Actual List Logic: 

We use a java list to represent a lox list, with every expression/element inside evaluated and stored in the lox list. The SubscriptExpr’s job is to check whether the variable we’re trying to index is actually a list, if the index is a number and within the list size.

5) List functions:

Finally, we implement global native functions that act as an interface between the user and the Java ArrayList
push(list, item) calls add() on the java list to append an item to the array.
pop(list) finds the size() - 1th element and uses java’s remove() method to delete it (the last item) from the list and return it.
Likewise, len(list) uses java’s size() function to fetch the array’s length.

II. For-in loops

1) The basics:

Add the IN token to the enum in TokenType.java and in to the keywords map in the Scanner.
checkNext() is a helper function we use to look ahead for an in keyword when we encounter for (var i …. If found, the Parser will build a list-iterator. If in is not found, it is considered a normal for-loop.
Next, update the forStatement() function in the Parser with a check for in.

2) Desugaring:

We then desugar for the parser to break down the complex and user-friendly syntax into simpler pieces the interpreter can handle (primitives).
Side note: Desugaring is also a life-lesson. Breaking down complex problems into smaller and simpler ideas always improves the possibility of solving them. Richard Feynman all the way!
It creates two hidden variables - _list and _i to store the collection and counter (starting at 0.0) respectively.
The Parser then creates an AST that resembles a while loop.
Ex: for (var item in myList) { print item; } effectively becomes:

{
    var _list = myList; 
    var _i = 0;
    while (_i < len(_list)) {
        {
            var item = _list[_i]; // The "item" variable is created here
            print item;           // The original body
        }
    _i = _i + 1;            // The increment
    }
}

listVar and itemVar in the forStatement() are initialisers, which occur once before the loop begins.
The forStatement() creates a variable meant for the user (like item) and uses Expr.Subscript to fetch its value from _list at index _i
The next block increments by adding 1 to _i
The condition block calls the native len() function to check if the index _i is still less than the list size.
We use curly braces for scope, to ensure that the hidden variables _list and _i are destroyed as soon as the loop ends. Else, trying to use _list later in the program might confuse the interpreter as it was never previously defined.

Musings:
That brings the interpreter to an end. Not “The End,” (because I’m going to keep extending it) but you could say all that I’d intended to do for this project has been accomplished. I took on something that puzzled me, sat and reasoned with it, learnt from it, and finally overcame my hesitation towards it. I now want to get into the “proper” backend of compilation.

The first step is always the hardest one. But we must take it anyway. Mistakes will happen and failing is certain. But rarely will we regret it, if we learn how to learn from our experiences. I’ve taken risks that didn’t yield what I hoped for. It was a little disappointing, but they’ve 100% made me a better person—well informed and sensitive to issues that matter.
This project coincided with such a phase in life. Amidst confusion and uncertainty, it gave me something I could keep coming back to consistently; something I could see tangible progress in; something that gave me the satisfaction of “creating.” We see programming languages all the time, but know so little of all the thought and effort going into them. Every design choice is intended to make programming easier and more intuitive; more accessible too! If I had to sum up in a sentence what I learnt from this—“God is in the details.” I will always be grateful for having done this.

Dear reader, if you’ve followed this project thus far, thank you for your time! Until next time, for the next adventure!

Classes and Inheritance

Lahari Tenneti — Wed, 04 Feb 2026 11:02:31 +0000

We now move on to complete the interpreter by adding support for classes. They will also be able to inherit from other classes (i.e., reuse their properties and methods) while also customising them through modifications and additions.

What I built: Commits bac3f3c, bfa82b9, 03b3af3, 6c70087

What I understood: 

1) Class Declarations:

The parser creates a Stmt.Class node for each class declaration, containing the name and list of methods.
The resolver declares the class name in the current scope to allow the class to refer to itself (inside its own methods), for recursion.
When the interpreter visits Stmt.Class, it converts the AST node into a LoxClass object, which stores a map of methods (which are in turn converted into LoxFunction objects).

2) Class Instances/Objects:

Lox doesn’t use any new keyword.
Instead, LoxClass implements the LoxCallable interface such that a class is instantiated whenever called.
When the class is “called,” a new LoxInstance object is instantiated and returned.
This new object stores a reference to its class (LoxClass) so it can access methods later.

3) Properties:

Fields aren’t declared in the class, but are created on assignment through instances.
When the interpreter evaluates that an object is a LoxInstance, it first calls get(), which checks the instance’s field map.
If the field exists, the value is returned. Else, it looks for a method. If neither are found, it throws a runtime error.
Also, the parser can’t easily distinguish between a set and get expression until it encounters a = sign. Thus, it parses the left-hand side as a regular expression (a get), and on encountering the = it converts that node into a set node.
If set() is invoked, the fields map is updated to overwrite any existing key.

4) Methods:

Lox methods don’t have the fun keyword preceding them and are accessed through instances.
If we extract a method (assign it to a variable) and call it later, this must still refer to the instance the method was accessed/extracted from, and not where it was called.
To achieve this, when a method is accessed, LoxClass instead of returning the raw LoxFunction, calls bind(instance) on it.
bind() creates a new environment nested inside the method’s original closure, defines this in that new environment, and uses it to return a new LoxFunction
If this is used outside a class, the resolver (which tracks if it’s currently inside a class) reports an error. Else, it resolves this as a local variable.
The interpreter looks up this in the environment like any other variable. Because of the binding step, the correct instance is found.

5) Constructors:

We implement support for user-defined constructors called init, which if found (by LoxClass.call), is called immediately to set up the new instance. Also, arity is checked here to ensure the class’ argument count matches the initialiser’s.
init always returns this (even if the user tries to return any value from inside the function). The resolver ensures this by tracking through an isInitialiser flag in LoxFunction.

6) Inheritance:

Allows a subclass to inherit methods from a superclass through a reference to the latter (stored by the subclass’ LoxClass) and a method lookup walking up the chain.
The parser creates a Stmt.Class node that now includes a superclass variable (of type Expr.Variable)
The resolver checks if a class tries to inherit from itself and reports an error if yes.
If a superclass exists, the resolver creates a new scope and defines super in it, ensuring super is available to all methods in the subclass.
While creating a subclass, the interpreter creates a new environment, defines super to point to the superclass, and then creates the methods.
The parser recursively looks up a method by first checking the instance’s fields, then the class’ methods, and then the superclass, which if null, causes the lookup to fail.

7) Super:

This keyword allows subclasses to override (their own version of) a method and access the original implementation in a parent class.
It ensures that even if a chain of subclasses overrides a method, super will always point to the correct parent class definition.
It is followed by a dot and an identifier (super.method) and is parsed as an Expr.Super node.
It looks up a method on the superclass but binds it to the current instance (this), with both belonging to different environments.
The resolver treats super as a local variable and calculates its distance (number of hops) from the environment in which super is defined.

What's next: Some extensions to Lox. Support for lists and for-in loops.

Musings:
Blogging this project has been really good for me. It probably is because despite doing other projects at the moment, trying to explain it to myself by writing encourages me to remember what I did (months ago!) and why. In a way, the insights I gained earlier continue to influence how I approach my current work. I absolutely love documenting things I do, even if it's for the most mundane of activities. In Indian philosophy, work is among the highest acts of devotion. Whatever we do, if we do it with intent, it leads us to competence and mastery. Because it's the process of learning and doing something that helps us become our best versions. Tagore put it well — "Where tireless striving stretches its arms towards perfection..."
In pursuit of that perfection, I remind myself of all that I've learnt.

Functions

Lahari Tenneti — Mon, 05 Jan 2026 07:04:47 +0000

Well, It's been a minute. I'd finished the interpreter a long time ago, but had put off blogging it because a thousand different things came up these past few months. Anyhow, it now takes on the ability to handle functions - user defined, native, and nested - and even deal with shadowing, wherein a variable in a local scope "eclipses" the same (existing) variable in an outer scope. We'll also enter proper compiler territory by creating a "resolver" phase.

What I built: Commits 3da669d, 930014e, 5adb148, and 9d534f3

What I understood:

1) Updating the Grammar:

The function call takes the highest precedence here, above the unary rule.
We also create an object (class) called Callable that helps resolve whether or not something can be used as a function.
Ex: A string isn't callable, while classes and functions (user-defined and native) are. Python does something really cool by allowing all its datatypes to be callable, because they're really objects that're being called.
If the "callee" (entity calling the function) doesn't belong to LoxCallable, Lox raises an error.
The parser also allows for currying or chained function calls through (( "(" arguments? ")" )*, allowing for function(arg)(arg)(arg)

2) Arguments:

We also check for arity, wherein the number of parameters in the function definition must equal the number of arguments passed in the call.

3) Native Functions:

We create clock() in Java, which Lox can access.
This is an anonymous class implementing LoxCallable, instantiated and bound to a variable "clock" in the interpreter's globals environment.
It returns the system time in seconds, for us to perform benchmarks.

4) Function Declaration:

Every time the interpreter encounters fun, it creates a callable object out of it (through LoxCallable) and binds it to the function's name in a new environment created.
In this local environment, the function's arguments are bound to the parameters mentioned in the declaration.
Every time the interpreter encounters a function call, a new environment is created. This is to allow for recursion, which wouldn't be possible if an environment existed only for declarations.
Once the function's body is completed, this local environment is destroyed and the execution environment returns to the state before the call.

5) Return:

The interpreter looks for a return statement followed by an optional expression.
If no return is mentioned, nil is implicitly returned.
When return is encountered, the interpreter must immediately jump out of all its (current) environments and revert to the original function call site.
Instead of a complex stack to do so, we use a simple exception class called Return, which evaluates the return value (if given) and wraps it, finally returning it as the function's result.
This is kept inside a try-catch block, that looks for the return "exception", which if not found, causes the full function to be parsed and nil returned implicitly.

6) Scoping:

So far, Lox was able to support dynamic scoping wherein a called function's scope was always set to the global environment, and not the environment it was defined in.
This hindered the called function's access to variables in the environment it was defined in, once the environment ended (when the function finished executing).
Basically, a live reference to a mutable scope was being captured, when it should have captured the lexical environment it was defined in, instead of deferring name resolution to the call site.
To explain this with an example:

fun getName(name) {
     var person = name;
     fun greet() {
          print “Hello, “ + person + “!”;
     }
     return greet;
}
var momo = getName("Momo”);
var chutney = getName("Chutney”);

momo(); //Should give “Hello, Momo!” ; Instead, it gives an error: “Undefined variable!”
chutney(); //Should give “Hello, Chutney!”

This is because once getName("Momo") finishes, the variableperson` is destroyed, as the function's scope ended.
When momo() is called, it tries to find person in its parent scope, which has now become the global scope (which doesn't contain the variable person) → So error!
We deal with this issue of dynamic scoping, by using lexical scoping.
Here, when a function is first declared, we close over and capture the environment surrounding the function (inner function holds a live reference to the outer one, which the garbage collector can't destroy despite the completion of the function's execution).
When the function is called, this captured environment becomes the call's parent instead of globals.

7) Resolver:

Implementing closures through lexical scoping gave rise to another issue.
Because a closure holds a live reference to a "mutable" map representing the current scope, its captured view of the current scope can change based on code that runs later in the same block.
This shouldn't be the case. Because Lox has lexical/static scope, a variable's usage must always "resolve" to the same declaration throughout the program's execution.
Even a redeclaration/redefinition of the variable later in the code shouldn't influence behaviour written with the original/declared value in mind.
Let's understand this through an example:

var a = "one"; { fun showA() { print a; } showA(); var a = "two"; showA(); }

In this code, the variable a belongs to the global scope, with its value being "one."
The function showA creates a closure that captures the block/environment it is declared in.
When showA() is called, a is first searched for in the block, and when not found, is searched for in the environment above (i.e., global). Hence, the output for print a is "one."
But, a is redeclared to have the value "two" in the same block (i.e., in the same environment captured by showA())
So, when showA() is called after the redeclaration, because the scope was mutable, the output is "two" when it should've been "one" again.
The resolver, added after the parser and before the interpreter, thus uses a concept called "Persistent Data Structures" wherein the original data structure can't be tampered with directly.
Any change to an existing structure creates a newer structure that contains the original information along with the modification.
To give a parallel, this is how blockchain works. If you're familiar with it, you must know that every time a block is modified in a ledger, a new block is created referencing the older one's hash, while also containing the change.
When the resolver enters a block and sees a variable being "used" (after its declaration), it searches upward from the function's scope.

Scope 0 (the function's scope):ais not found Scope 1 (block scope):ais not found (asvar a = "two"hasn't been defined yet in the resolver's static pass) Scope 2 (global scope):ais found

Because the variable is found 2 hops away from the innermost scope (of its use), the resolver annotates that "use" or node with the number 2.
When the interpreter encounters print a, instead of searching for the variable, it just uses the given number of hops to jump to the declaration.

What's next: We're going to keep it Classy! 💅
(Hehe, classes and inheritance, in case you didn't get it)

Musings:
I’ve had the opportunity to witness some of the most wonderful and bewildering of things these past few months. Feels like I saw the full spectrum of life, much like Shakespeare’s seven ages of man. In a way, it really humbled me. For the longest time, I was afraid of letting go… of my beliefs, interests, and even some dreams, because I thought I’d lose my very identity. Now, I’ve learnt that much like functions, it’s okay to have a template of non-negotiables, upon which we can let life keep adding her own “implementations.” (I absolutely HAD to use that analogy, pleeease excuse me). Change and unpredictability don’t seem so daunting anymore, and maybe (like 0.05%) are good too. I suppose c’est la vie.

Logical Operators & Control Flow

Lahari Tenneti — Fri, 10 Oct 2025 09:36:25 +0000

After statements, we will now be adding support for logical operators and control flow statements - conditional (if-else) and looping (while, for).

What I built: Commit 089ad4d

What I understood:

1) If Statements

We extend the statement rule to accomodate ifStmt, which leads to expression(). The thenBranch calls statement() again.
Also, we avoid the dangling-else problem, wherein nesting-if conditions cause uncertainty about which if statement an else clause belongs to - inner or outer?
This is by checking for the existence of an else branch which is assumed to belong to the innermost if statement.

2) Logical Operators

We modify the grammar to have assignment() call or() (which calls and()) instead of equality(). equality() is called by and()
We use short-circuiting while using logical-operators, which makes decisions basis the state of the left-operand.
Ex: In OR, if the left operand is truthy (evaluates to true), the interpreter skips the right operand, and returns the left operand itself.
But if the left-operand is false, it has to check the right operand and compute the result based on it.

var greet = greeting or "Hello";
//defaults to Hello if greeting is null/false.

In AND, if the left-operand is false, the entire expression results in false, and thus the second operand needn't be evaluated.

//LOGIC  
public Object visitLogicalExpr(Expr.Logical expr) {
    Object left = evaluate(expr.left);

    if (expr.operator.type == TokenType.OR) {
      if (isTruthy(left)) return left;
    } else {
      if (!isTruthy(left)) return left;
    }

    return evaluate(expr.right);
  }

3) While Loops

The statement rule is further extended to call whileStmt, which basically executes the body of statements if the given condition evaluates to ‘true’

//LOGIC
public Void visitWhileStmt(Stmt.While stmt) {
    while (isTruthy(evaluate(stmt.condition))) {
      execute(stmt.body);
    }
    return null;
  }

4) For Loops

forStmt is added to the statement rule. A for condition is supposed to have three parts - initialiser, the condition, and the action (increment/decrement). Variables are created to hold these three parts.
Interestingly, we don’t evaluate a for loop as a for loop, and actually convert it into a while loop
We first check for the initialiser by looking for VAR and call varDeclaration() if it’s present.
Then, the interpreter looks for a ;, after which it calls expression(). Finally, we call expression() again on encountering an increment/decrement.
The statements are wrapped inside a block, as a list.
We also append the increment condition to the body of statements.
When then wrap this body into a while loop, that is executed after the initialiser statement runs exactly once.

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

is converted to

var i = 0; // Initialiser runs once 
while (i < 10) {
// the parser here groups the original body of statements and the
increment into a single unit for the while loop’s body
    {
        print i;
        i = i + 1; 
    }
}

What's next:
Functions! This takes the interpreter ahead significantly by introducing concepts like lexical scope, closures, call stack management, and a return mechanism.

Musings:
Coffee Cold is a song I deeply love. For some reason, it feels like both a dig at and a celebration of life’s strangeness. Like it’s trying to tell me that at the end of the day, there are things way beyond my control that shape my world. I can either choose to get upset due to them or smile and walk on, towards my next adventure. “Life is neither a Tempest, nor a Midsummer Night’s Dream. It’s more like a Comedy of Errors and you take it As You Like It.” As the Tao Te Ching says, it's alllll about the flow. 😉

Evaluating Statements

Lahari Tenneti — Thu, 02 Oct 2025 17:32:13 +0000

So far, we evaluated expressions. Now, we'll be interpreting statements and adding support for variables, assignment, and blocks.

What I built: Commit e04ea1d

What I understood:

1) Summary:

Without any "memory," an interpreter is merely a glorified calculator. To really work, it should be able to remember variables and their values - basically storing them somewhere.
As against expressions - which evaluate to something - statements can execute an action, and can change the state of the world outside them.
We extend our grammar to now begin with declaration as the top-level rule, which refers to the rules varDecl or statement
statement follows two other rules, exprStmt or printStmt to add support for print (which isn't a function in lox) and other kinds of statements.
Like Expr, we create a Stmt class using GenerateAst, which has the subclasses Block, Expression, Print, and Var - each with their own visitSubclass() methods to be overridden by the Interpreter class.

2) Flow:

run() calls parse(), which repeatedly calls declaration() to process the Lox script line by line.
The parser starts building the AST as it consumes tokens and first creates List<Stmt> (list of statements in the program)
It first looks for a VAR token, which if not found, causes it to call statement()
When it encounters a block, it enters and starts parsing the block’s contents as well.
Similar to the contents within () being treated as one entity, the entire contents of a block (within {}) are treated as a statement.
It also uses peek(), when a = is encountered, to check whether it is an expression or assignment.
Also, it checks whether or not the left-side of the = is an assignable target.
Ex: a + b = 5 is not an assignment; it is an expression
REPL:
The Interpreter uses a hash-map called Environment to keep track of the declared variables.
There are two methods, namely define() and assign() for dealing with variables.
When we’re defining/declaring/creating a variable, Stmt’s Var subclass operates on the current environment.
Whenever we update a variable, assign() searches up the enclosing chain recursively, until it finds the mentioned variable; In that scope, it updates the variable. Expr’s Assign subclass uses this method.
Whenever a local variable is created (i.e., a new environment), it also keeps track of its parent environment.
For print statements, it performs concatenation if more than one (string) token is involved.

Let's understand this through an example:

var name = "World";
{
  var greeting = "Hello, ";
  print greeting + name;
  name = "Lox";
}
print name;

The parser creates a list of statements, in which each item is further parsed for tokens.
In Line 1, var is encountered, leading to the rule varDecl, and hence a new environment E0 is created for name to be stored in, with its value as "World".
In Line 2, the parser sees a block through {, due to which visitBlockStmt() calls executeBlock(), passing the list of statements in the block, while creating a new environment E1, which has E0 as its parent.
Again, var in Line 3 (in the block), creates a new environment in E1, with greeting as the name and "Hello, " as its value.
When print is encountered in Line 4, evaluate(expr) is triggered, which finds that the print statement has a binary expression - greeting + name
While Line 5 is being parsed, visitAssignExpr() is called, which further calls evaluate(expr), after which the Environment class' assign() function is called. This checks for the presence of the variable (name), first in its own environment E1, and then recursively in parent environments until the name is found.
name is found in E0, following which put() updates its value in that environment: "World" → "Lox"
Once the block ends in Line 6 (when } is encountered), its environment E1 is destroyed.
Finally, in Line 7, when print name; is encountered, name's (changed) value "Lox" is printed.

What's next: Support for logical operators, while, and for loops.

Musings:
I felt very, very, very happy when the code started working. Passing a .lox file felt almost magical. Except, I now know what went behind it. I still find myself most fascinated by the Scanner. Strings (and by extension, characters) never seemed very important to me, so I was pleasantly surprised to find out that they’re critical to interpreters/compilers. All it takes is a switch-case! I’m loving how much this project has taught me to appreciate all parts of programming.

The Interpreter ✨

Lahari Tenneti — Sat, 20 Sep 2025 19:22:32 +0000

Finally, I created the Interpreter class that implements the visitor interface! From where all the function calls begin...
We can now evaluate various kinds of expressions - Literal, Binary, Unary, and Grouping (wherein we use accept() to recursively evaluate the subexpression within the ()).
I also created the RuntimeError class to handle errors in Lox.

What I built: Commits 6c14a8e & b49dfbc

What I understood:

1) The Interpreter class

Like I'd previously mentioned, the visitor interface needs a separate class that implements it. This is how we "extend" behaviour.
The class in question is Interpret, that begins with the interpret() method for evaluating and printing an expression, or reporting a runtime error.
Also, all the visitSubclass() methods we wrote in the Expr class are overridden here to behave/act basis the type of expression parsed.
These visitSubclass() functions have not much to do - they merely extract the "values" from the "nodes" the Parser created and return them or the result of the expression they're in.

@Override
    public Object visitBinaryExpr(Expr.Binary expr) {
        Object left = evaluate(expr.left);
        Object right = evaluate(expr.right);

        switch (expr.operator.type) {
            //comparison
            case GREATER:
                checkNumberOperands(expr.operator, left, right);
                return (double)left > (double)right;
            case GREATER_EQUAL:
                checkNumberOperands(expr.operator, left, right);
                return (double)left >= (double)right;
            case LESS:
                checkNumberOperands(expr.operator, left, right);
                return (double)left < (double)right;
            case LESS_EQUAL:
                checkNumberOperands(expr.operator, left, right);
                return (double)left <= (double)right;
            //arithmetic
            case MINUS:
                checkNumberOperands(expr.operator, left, right);
                return (double)left - (double)right;
            case PLUS:
                if (left instanceof Double && right instanceof Double) {
                    return (double)left + (double)right;
                }
                if (left instanceof String && right instanceof String) {
                    return (String)left + (String)right;
                }
                throw new RuntimeError(expr.operator, "Operands must be two numbers or two strings.");
            case STAR:
                checkNumberOperands(expr.operator, left, right);
                return (double)left * (double)right;
            case SLASH:
                checkNumberOperands(expr.operator, left, right);
                return (double)left / (double)right;
            //equality
            case BANG_EQUAL: return !isEqual(left, right);
            case EQUAL_EQUAL: return isEqual(left, right);
        }
        //Unreachable
        return null;
    }

We also use helper functions like checkNumberOperands(), checkNumberOperand(), isTruthy(), isEqual(), and evaluate() to simplify each visitSubclass() function.

2) Runtime Errors

Instead of having Lox's errors reported in Java, we needed to create a mechanism to display those errors in Lox itself.
The underlying class we extend for this remains Java's RuntimeException though.
We create a runtimeError() method in Lox that uses the RuntimeError class we created, to print the error message and line number.

What's next: Evaluating and working with statements (and not just expressions)!

Musings:
K-dramas are simply brilliant. I'm just using this platform to express my heartfelt gratitude for the gems that they are. And to the awesome people who make them. It's amusing how I'd scoff at their very mention just 3-4 years back. And I did so because I thought they were too unrealistic. Now I love them precisely because they're so unrealistic! I often look to them for inspiration on how not to take anything too seriously. When code or something else doesn't seem to work, I find it very helpful to watch yet another show revolving around a girl (a guy?) who suddenly finds herself in a Joseon-era royal kitchen. And lo! I return brimming with positivity, ideas, and the ability to understand just where in my code I erred. Sometimes, all we need to do is step back and take a chill-pill.

The Parser!

Lahari Tenneti — Thu, 18 Sep 2025 12:23:49 +0000

Aaaand she's here! Last time, we created the rules/grammar basis which the parser converts tokens into syntax-tree. Now, we create association rules, i.e. we define the order in which expressions must be parsed to generate the tree.

Recursive descent parsing is used here, wherein the parser starts from the outermost/top-level rule with lowest precedence and traverses through subexpressions to make it to the tree's bottom, where it finds literals (which happen to have the highest precedence).

What I built: Commit 5750470

What I understood:
1) Association Rules

The rules we create must be defined as functions which call other functions of higher precedence, until we reach literals.
We create a Parser class with a list of tokens and a current pointer for noting the position.
We also use a match() function to look for certain tokens after the current one. This is the parser anticipating code based on the function it's currently in.

private boolean match(TokenType... types) {
     for (TokenType type : types) {
          if (check(type)) {
               advance();
               return true;
          }
     }
     return false;
}

A ParseError class (extending Java's RuntimeError class) is created to handle errors.
parse() is defined to call expression()
expression() calls equality(), which calls comparison(), which calls term(), which calls factor(), which further calls unary(), which ultimately calls either itself or primary()
primary() checks for LITERAL, TRUE, FALSE, and LEFT-PAREN
When we encounter LEFT-PAREN, we use consume() to advance() when the RIGHT-PAREN is found. Else, a custom error is reported: "Expect ')' after expression."

2) Error Handling

We use a method called 'Panic Mode Error Recovery,' which uses a concept called synchronisation to find the nearest acceptable token to restart parsing from, whenever the parser encounters an unanticipated/wrong token.
Ex: Tokens like CLASS, VAR, FUN, FOR, IF, and WHILE are good tokens to restart parsing from, because they mark the beginning of a new statement.
This is the parser "panicking" and looking for a safe and graceful exit from the error line.
It also prevents the parser from reporting a cascade of errors associated with the initial error.
Ex: If the parser sees:

var a = 1 + ;
var b = 2;

It notes that after +, we have a ;, when we should have another operand. This is an error.
Without panic-mode error recovery, it would report a cascading errors like:

Error on line 1: Expected an expression after '+'.
Error on line 2: Unexpected token 'Var'
Error on line 2: Missing expression.
Error on line 2: Unexpected semicolon.

With panic-mode, var in the second line, is according to synchronisation(), a safe place to resume parsing from. So error reporting looks like:

Error on line 1: Expected an expression after '+'.

What I didn't understand: How the hierarchy of association rules works. This is fundamentally based on the rules of precedence and association we define, and uses match() to look for tokens, and then call the next appropriate rule (function).

Let's say we have the expression: 5-3*2

First, parse() is called, which calls expression(), which calls equality(), and so on until we reach primary()
Now, primary() recognises that the first character 5 is a Literal and hence creates an object for it.
primary() returns Literal(5) to unary(), which returns it to factor(), which returns it to term()
Now that the pointer is currently with the second character, term() finds a match when it sees -. Now that we have an operator, the right-operand must be found.
Hence, term() calls factor() again, and so on, until primary() finds and returns 3 as another Literal object.
This object now reaches factor(), which finds a match in *, and decides that 3* needs a right-operand.
Again, factor() calls unary(), which calls primary(), which finds and returns 2 as a Literal object.
This object reaches factor(), which now has a full binary expression. It then creates a Binary object like Binary(3*2), and returns it to term()
Now, term() has its right-operand for 5-, and finally constructs a full binary expression, i.e. Binary(5-(3*2))
In this endeavour, by giving factor() higher precedence over term(), we ended up preserving the BODMAS rule.
And lo! The binary expression is returned all the way to the top of the stack until parse() returns it too. It is from this expression/object that we create a syntax tree.

What's next:
We’re going to evaluate the expressions we constructed the tree for! We're also going to extend the parser to handle not just expressions, but also statements - which is what actual code looks like.

Musings:
In my opinion, concepts are best understood through examples and metaphors. Unless we really engage with the subject at hand, we cannot internalise what's being taught. And we do this best by trying to use the pool of knowledge we have through our own experiences in life.
I once read in the Upanishads that the best process to learn anything is by shravana (listening to or reading from a credible guru or text), manana (contemplating through deep thought, analysis, questioning, and even explaining it to another), and finally nididhyasana (meditating upon the knowledge gained from the previous two stages, to transform it from a concept into a lived reality).
While I’m not as thorough with this process as I’d like to be, I do try my best to understand a concept through various perspectives. It also gives me the opportunity to apply these learnt formulae to problems beyond computer-science.

Grammar for the Parser

Lahari Tenneti — Sun, 14 Sep 2025 19:07:21 +0000

Well, it's been a while. Hyderabad's weather has been erratic lately and for a brief, brief time - so has my consistency towards this project. But I'm back!

Anyhoo, the second stage of the Interpreter is the Parser, which accepts the tokens generated by the Scanner and creates a syntax-tree out of them. This tree is based on certain specified rules - the Context Free Grammar.

As against regular language, which groups similar language into tokens but cannot adequately deal with deeply nested expressions, CFG allows for infinite possibilities of string/code (called derivations, because they’re “derived” from rules).

But before we create the Parser itself, we need to create and define these rules, basis which trees can be constructed.

What I built: Commit 3264f2b

What I understood:

1) Introducing Trees and Grammar

Trees are made of terminals and non-terminals (references to other rules).
The Scanner emits Tokens which are consumed by the Parser, and grouped based on the grammar's rules, to produce nodes for the tree.
Literals (string/numeric) are often leaf or end nodes, and operators - the internal nodes.
Rules are also capable of referring to themselves, allowing for recursion and hence infinite possibilities.
Based on Robert's breakfast example to explain how rules are defined, I created my own example as well.

Terminals are enclosed in double-quotes and are in blue, while non-terminals are in black. Grouping/OR/repetitions are in purple.
We can pick any of the options for a rule.
Ex: I choose the first rule in chilling: chilling → do activity;
I now go to the non-terminal do and choose any of its rules. Let's say: do → "watch";
Because watch is a terminal, I have no other rule to refer to through it. So in chilling, I replace do with watch, making it: chilling → "watch" activity;
I now go to the nonterminal activity and choose a rule.
I decide to pick music (movie would have been a more appropriate choice for "watch", but I want to demonstrate the flexibility CFG offers). activity → music;
In music, which is a non-terminal, I choose: music → "piano";
Because there's nowhere to go beyond "piano," I have: activity → "piano";
Finally, going back to the first rule we started out with, we have a full-fledged instruction ready, based only on a few grammar rules: chilling → "watch piano";

2) Lox's actual grammar

We create a base class (or rule) called Expr (expression), that refers to other subclasses (also rules), which can again refer to Expr. This recursion is important because expressions generally consist of other expressions, which ultimately contain operators and operands.
Because Expr and its subclasses will have a similar, repetitive template, we metaprogram to have code write code for us.
We do so by creating a general template that takes from a description and creates the relevant subclass using a for-loop.

defineAst(outputDir, "Expr", Arrays.asList(
     "Binary: Expr left, Token operator, Expr right",
     "Grouping: Expr expression",
     "Literal: Object value",
     "Unary: Token operator, Expr right"
));

...

for (String type : types) {
     String className = type.split(":")[0].trim();
     String fields = type.split(":")[1].trim();
     defineType(writer, baseName, className, fields);
}

3) The Expression Problem

This is a huge issue programmers face when they wish to have multiple (sub)classes with similar behaviour (methods).
In our situation, we deal with various subclasses like Binary, Unary, Literal, etc. There are some common methods necessary for them all.
Ex: Printing or computing the expression
One way to deal with this would be by adding a print method for each subclass, i.e. printBinary(), printUnary(), computeBinary(), computeUnary(), etc.
The issue with this approach is when we'd like to add a new method - say typeCheck() - we'll have to update every subclass to implement its version of this new method, making the entire code bulky.
Another way to resolve this is by using a common method that checks which subclass it must operate on, through if-else. But that is also problematic. What if we decide to add a new type/subclass? We'll have to update every (common) method to accommodate this new type.

4) Classes' Behaviour - What should it be like?

The Expr class and its subclasses are merely data structures that must be passed between phases of the Interpreter.
They must not have any "behaviour" (methods) of their own, lest we violate the 'Separation of Concerns' principle, which says that each part of the program must focus on one responsibility only.
Because if we start mixing multiple responsibilities into one class, that class becomes harder to maintain, reuse, and extend without drastically altering it.

5) Solution: The Visitor-Design Pattern

This is a standard approach for solving the Expression Problem in object-oriented languages like Java.
I see this as a bidirectional communication method, that overcomes the issues of the unidirectional approaches mentioned earlier.
Here, we can extend the behaviour of (sub)classes while preserving their inherent structure, by simply creating a new visitor.
We create a Visitor 'interface' with a list of visitSubclass() methods, which aren't yet defined.
The main/base class has an accept() method that's extended and overridden by each of its subclasses.
We then create a new class for a new behaviour. This class implements the Visitor interface, and is therefore the Visitor class.
When I say "implements" the visitor interface, we just override the interface's undefined methods and give them specific behaviour.
When this new class' object is created, it accepts an expression from the parser. This is the Visitor object.
Depending on the expression's type (subclass), the accept() method relevant to the type is called, with the class' object passed as an argument.
The subclass' accept() now receives the Visitor object and goes on to call the visitSubclass() method associated with it, while also passing the subclass object as an argument. This is for giving visitSubclass() access to the subclass' fields.
Remember when I said we overrode the interface's visitSubclass() method in the new class and gave it specific behaviour? That behaviour (method) gets implemented here.

What I didn't understand: The Visitor-Design Pattern

If the previous section completely went over your head, don't worry. It did for me too. I took two days to figure this out. 😁

Let's understand this through an example. Assume that the behaviour we wish to implement here is of printing the expression. And assume that we need to print a binary expression.
In our Expr class, we create the Visitor interface, with methods like visitBinary(), visitUnary(), visitLiteral(), visitGrouping(), etc. Note that these methods are undefined here.
We create an accept() method for Expr that is also undefined.
In each subclass extending Expr, we override Expr’s accept(), such that it calls the visitSubclass() method associated with it. For example, the Binary subclass’s accept() will call visitBinaryExpr(this).

abstract class Expr {
  abstract <R> R accept(Visitor<R> visitor);

  interface Visitor<R> {
    R visitBinaryExpr(Binary expr);
    R visitGroupingExpr(Grouping expr);
    R visitLiteralExpr(Literal expr);
    R visitUnaryExpr(Unary expr);
  }

  static class Binary extends Expr {
    Binary(Expr left, Token operator, Expr right) {
      this.left = left;
      this.operator = operator;
      this.right = right;
    }
    @Override
    <R> R accept(Visitor<R> visitor) {
      return visitor.visitBinaryExpr(this);
    }
    final Expr left;
    final Token operator;
    final Expr right;
  }
}

this is passed as an argument because the subclass is giving the visitor object full access to itself, and therefore all its fields.
We now create a new class called PrintExpr that implements Expr's Visitor interface.
It then overrides all the visitSubclass() methods to print the expression associated with each subclass.
visitBinaryExpr() will be overridden to return/print the whole binary expression.
We can create as many behaviours as we like without changing a single thing about the subclasses.

class PrintExpr implements Expr.Visitor<String> {
    String print(Expr expr) {
        return expr.accept(this);
    }

    @Override
    public String visitBinaryExpr(Expr.Binary expr) {
        return expr.left.accept(this) + " " + expr.operator.lexeme + " " + expr.right.accept(this);
    }

    public static void main(String[] args) {
        Expr expression = new Expr.Binary(
            new Expr.Unary(
                new Token(TokenType.MINUS, "-", null, 1),
                new Expr.Literal(123)
            ),
            new Token(TokenType.STAR, "*", null, 1),
            new Expr.Grouping(
                new Expr.Literal(45.67)
            )
        );

        System.out.println(new PrintExpr().print(expression));
    }
}

If I had to explain it in a very crude way: Let's say there's a census being conducted, for which an officer must visit your house. They are supposed to count members of your house, and cannot visit without an invitation. Maybe they'll also issue certain ID cards. (Both these - counting and issuing cards - are behaviours)
The Census Office creates an interface that sends out mails informing families of the census. (This is the Visitor Interface and families/houses are subclasses)
When this mail is received by a house (liken this to the visitor object passing itself), it is supposed to accept the visitor (accept()).
The house is also supposed to send a mail back to the Census office saying "Yes, we agree to allow the officer inside." (This is the subclass giving the visitor object access to itself through this while calling visitSubclass())
The officer then arrives and either counts or issues an ID card (depending on the class we've created to implement the behaviour).

What's next: For real, the Parser. Like "Parser" Parser. Proper Parser.

Musings:
Nothing interpreter related, honestly. But I had a really good time today. Spent about 15-20 minutes in the balcony looking at the city. I really, really love balconies. There's no such thing as a bad balcony, I guess?
You see, they show us a world beyond the comfort of wherever we are. They offer us a phenomenal vantage point from where we can watch countless little dramas unfold; from where we can both appreciate man's incredible skill in creating these chaotically beautiful structures, and also find ourselves amused at how it's the lone, calm green tree breaking through the maze of streets, that we find ourselves most in awe of.