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)
  • C++
  • Recursive descent parsing
  • Three-address code
  • Visual Studio 2022

Demo & artifacts

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.

The compiler walkthrough part-way through Euclid's algorithm, showing the input with the lookahead token, the call stack, the productions so far and the C++ source with one line highlighted.
Screenshot Part-way through compiling Euclid's algorithm, just after the parser emitted t1 = a - b. Left, the input with the lookahead token, the call stack with the jump labels passed down, and the productions so far; right, the original C++ with the running line highlighted. This is the TypeScript port in a browser, not the original console program.

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 if and while, 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 and begin … end blocks.

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

Compiler front-end pipelineThe source program goes to the lexer, which produces a token list with line and column numbers. The parser reads the token list by recursive descent, one function per non-terminal, and produces four outputs together: the production sequence of the leftmost derivation, the syntax tree, three-address code with back-patched jumps, and a list of syntax errors.Sourceprogram textLexerlexical_analyze()keeps line, columnToken listprescan()Parserrecursive descent,one function pernon-terminal;jump labels passeddown to nested codeProductionsSyntax tree3-address codeSyntax errors
The two passes of the Project2 program. The lexer turns the whole input into a token list first; one recursive-descent pass over that list then records the derivation, builds the tree and emits the code at the same time.

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 Program without checking that every token was read. x = 1 y = 2 compiles only x = 1, and if 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 after Program is not end of input.
  • Temporaries can clash with variables: temporaries are named t1, t2, … like ordinary identifiers, so t1 = 5; x = a + b; y = t1 leaves y equal to a + b. Fix: a prefix the lexer cannot produce, such as $t1.
  • Silent overflow: integer literals are accumulated in a 32-bit int, so 99999999999 becomes 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

  1. Download 23.cpp from the walkthrough and compile it: g++ -std=c++17 -o lab 23.cpp.
  2. Pipe a program into it: echo 'while a <> b do if a > b then a = a - b else b = b - a' | ./lab.
  3. 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.