Compiler Front End for a Small Language
A C++ lexer and recursive-descent parser for a small language with if, while, begin…end and integer expressions. It records the leftmost derivation, prints the syntax tree and generates three-address code with back-patched jumps.
- Period
- Spring 2026
- Context
- Compiler Principles course labs
- Team
- Individual project
- My role
- Sole author of the lab programs
- Status
- Lab programs completed; two versions kept (Project1 and Project2)
Demo & artifacts
- Open demoWeb adaptation
The walkthrough runs a TypeScript port of the lab program in your browser. Type a program or pick an example, then replay the compilation step by step with the original C++ highlighted. For every example, the page also shows the output of the compiled C++ program and checks that the two match.

My contribution
- Wrote the lexer by hand. It recognises identifiers, the seven keywords and decimal, octal and hexadecimal integers, gives illegal octal (
09) and hexadecimal (0x1G) numbers their own token kinds, and records the line and column of each token for error messages. - Removed left recursion from the expression grammar (23 productions) and wrote one parsing function per non-terminal. The parser records every production in leftmost-derivation order and builds a syntax tree, printed as an indented tree.
- Generated three-address code in the same pass: a temporary for each operator, true and false labels for
ifandwhile, and placeholder jumps that are back-patched once their targets are known. Each nested statement receives the label it should continue at, so a false condition inside a loop body jumps straight back to the loop head. - Collected syntax errors with line and column and kept parsing after an error, so one run reports more than the first mistake.
- Kept two versions: Project1 stops at the first error and expects
;after every statement; Project2 adds the pre-scan, the syntax tree, the production record, the error list andbegin … endblocks.
The language
Programs are assignments, if … then … else, while … do and begin … end blocks over integer expressions, with statements separated by ;. The lab handout’s example shows most of it:
while (a3+15)>0xa do if x2 = 07 then while y<z do y = x * y / z;
c=b*c+d
How it works
Each non-terminal of the grammar has one C++ function, and the function chooses a production by looking at the next token. Expressions are built from Term and Factor, with the primed rules (Expr', Term') replacing left recursion, so a - b - c is still evaluated left to right: each primed function receives the value computed so far and passes the new temporary on.
Back-patching, by example
A while has to jump past its body when the condition is false, but the address after the body is not known when the condition is compiled. The parser emits goto __PLACEHOLDER__, remembers its position, and overwrites it once the body is done. For the handout example above:
L0:
t1 = a3 + 15
if t1 > 10 goto L1
goto L4 ← written as a placeholder, patched after the loop body
L1:
if x2 = 7 goto L2
goto L0 ← false branch of the if: straight back to the loop head
L2:
if y < z goto L3
goto L0
L3:
t2 = x * y
t3 = t2 / z
y = t3
goto L2
goto L0
L4:
t4 = b * c
t5 = t4 + d
c = t5
The if inside the loop gets L0 as the label to continue at, so its false branch needs no label of its own. The inner while reuses the if’s true label L2 as its loop head.
What porting it showed
To replay the compiler in a browser I rewrote it in TypeScript function by function and compared the two on thousands of inputs. Matching the output exactly was the easy part. Writing test inputs turned up behaviour the lab tests never reached. The most important is the missing end-of-input check: the parser stops at the first token that cannot start or continue a statement and reports success. The walkthrough marks these examples with ⚑ and strikes through the tokens that were never parsed.
Results & validation
- For this page I ported Project2 to TypeScript. I compiled the C++ with g++ and gave both versions the same 4,020 inputs: 1,946 generated valid programs, 1,452 with random edits, 602 random strings and 20 hand-picked edge cases. The outputs matched byte for byte.
- A small interpreter runs the generated code. On 1,903 random valid programs it gave the same variable values as evaluating the source directly. Programs that divided by zero or ran past a loop budget were left out.
- The walkthrough replays any input step by step, with tokens, the call stack, productions, the growing tree, and code as it is emitted and back-patched.
The port and both checks were run for this website in November 2026, against the g++ 13 build of the original 23.cpp (Project2). The lab's own test inputs were not part of the material I had.
Limitations & next steps
- No end-of-input check: the parser returns from
Programwithout checking that every token was read.x = 1 y = 2compiles onlyx = 1, andif a < b then x = 1; else x = 2(Project1's syntax) loses the else branch. An unknown character such as@also ends parsing early. None of these produces an error. Fix: report an error when the lookahead afterProgramis not end of input. - Temporaries can clash with variables: temporaries are named
t1,t2, … like ordinary identifiers, sot1 = 5; x = a + b; y = t1leavesyequal to a + b. Fix: a prefix the lexer cannot produce, such as$t1. - Silent overflow: integer literals are accumulated in a 32-bit
int, so99999999999becomes 1215752191. Signed overflow is undefined behaviour in C++. - Fixed buffers: names and numbers are copied into 256-byte arrays without a length check, so a name longer than 255 characters writes past the buffer.
- Minimal error recovery: after an error the parser skips one token. The tree then contains error nodes and the code contains
?operands, so it cannot be run. - No optimisation: the generated code keeps some unreachable jumps and extra labels.
Run / reproduce
Environment
- A C++ compiler. The original is a Visual Studio 2022 (v143) solution; g++ 13 also builds it.
Steps
- Download
23.cppfrom the walkthrough and compile it:g++ -std=c++17 -o lab 23.cpp. - Pipe a program into it:
echo 'while a <> b do if a > b then a = a - b else b = b - a' | ./lab. - Compare the console output with section 3 of the walkthrough for the same input.
The original Visual Studio solution has no public repository; the full source is shown and downloadable in the walkthrough.