compiler-front-end

2023

C++Lexical AnalysisRecursive-Descent ParsingStatic Type Checking

── case study ────────────────────────────────────────────────────────────

What it is

A compiler front-end for a small C-like language (typed variable declarations, if/while/switch control flow, boolean/int/real types, public/private visibility) written for ASU's CSE340 compilers course. A hand-written lexer (lexer.cc/.h) tokenizes raw source into a typed token stream. A recursive-descent parser (parser.cc/.h, ~1,170 lines) consumes it, builds a syntax tree, and checks types as it goes: operand type agreement on binary/unary ops, boolean-only loop/if conditions, matching return types. Verified against 29 test cases, each with a paired expected-output file, run via a shell test harness.

The problem

A lexer only tokenizes. Nothing enforces that the token stream forms a grammatically valid program, or that types agree, so an invalid program that is shaped like valid syntax (e.g. 1 + true, an if given an int condition) would otherwise pass through untouched.

Approach

One recursive function per grammar nonterminal. A symbol table is built up during parsing so type checks can resolve a variable's declared type mid-parse instead of needing a separate pass. Types are computed bottom-up per expression and checked immediately against what the enclosing grammar rule expects, interleaved with parsing rather than run as a separate semantic-analysis pass.