Compilers & Interpreters

Python pathway

Programming Foundations / Practice rooms / Track curriculum and enrollment

1. Scanning

   Every compiler starts by reading raw source text and chopping it into tokens, the words and symbols the rest of the pipeline works with. This project builds a scanner (also called a lexer) from the ground up: classifying characters, walking the source with a cursor, recognizing number literals, the one- and two-character operators, and the identifiers and keywords, then skipping the whitespace and comments that carry no meaning. By the end you will have a full tokenize() that turns a line of source into a clean list of tokens, each a simple (TYPE, value) tuple the parser can consume.

   • Characters & the Cursor: 5 lessons
   • Number Literals: 5 lessons
   • Operators & Punctuation: 5 lessons
   • Identifiers & Keywords: 5 lessons
   • The Full Scanner: 5 lessons

2. A Calculator

   With a stream of tokens in hand, the next job is to understand their structure. This project builds an arithmetic calculator the way a real parser does: a cursor that walks the token list, a recursive-descent grammar that encodes precedence (multiplication binds tighter than addition) and left-associativity, the elegant Pratt technique that drives the same result from a table of binding powers, parentheses that override the defaults, and finally a tree-walking evaluator that turns the syntax tree into a number. The result is a working calculator you can read source into and get the right answer out of, the smallest complete language pipeline.

   • The Token Stream: 5 lessons
   • Recursive Descent: 5 lessons
   • Pratt Parsing: 5 lessons
   • Grouping: 5 lessons
   • Evaluating the Tree: 5 lessons

3. Parsing Expressions

   Extend the arithmetic parser with strings, Booleans, nil and variable names, plus comparison, equality and logical operators. Build tagged AST nodes, use binding powers to preserve precedence, distinguish logical nodes for later short-circuit evaluation, and print tree structure as s-expressions. This project's parser covers literals, names, grouping, unary operators and the taught infix operators; assignment and function-call parsing arrive in later projects.

   • Literal Nodes: 5 lessons
   • Operator Nodes: 5 lessons
   • Parsing Primaries: 5 lessons
   • Full Precedence: 5 lessons
   • Printing the Tree: 5 lessons

4. Evaluating Expressions

   A parse tree is only a description; to run a program you must walk that tree and compute what it means. This project builds the tree-walking evaluator at the heart of every interpreter. Literals evaluate to their own values, arithmetic combines numbers while `+` does double duty as string concatenation, comparison and equality produce booleans, and the logical `and`/`or` short-circuit according to the language's own definition of truth (only `nil` and `false` are falsey). Finally you handle the operations that cannot work, dividing by zero or adding a number to a string, by raising clear runtime errors instead of crashing. The result evaluates any expression the parser can build.

   • Evaluating Literals: 5 lessons
   • Arithmetic: 5 lessons
   • Comparison & Equality: 5 lessons
   • Truthiness & Logic: 5 lessons
   • Runtime Errors: 5 lessons

5. Statements & State

   An expression produces a value; a statement makes something happen. This project turns the evaluator into an interpreter of programs. You build statement nodes (print and bare expressions), the environment that stores variables as a chain of scopes, variable declaration and assignment that read and write it, and the block scoping that lets an inner variable shadow an outer one and vanish when its block ends. The environment is modeled as a list of dictionaries, innermost scope first, so looking up a name walks outward until it is found. With state, the language can finally remember things between statements.

   • Statements: 5 lessons
   • The Environment: 5 lessons
   • Variable Declaration: 5 lessons
   • Assignment: 5 lessons
   • Block Scope: 5 lessons

6. Control Flow

   A language that can only run statements top to bottom is barely a language. Control flow gives it branches and loops. This project builds if/else that chooses a path by the condition's truthiness, while loops that repeat until their condition fails, and for loops, which you implement not as a new construct but by desugaring them into an initializer, a while, and an increment. You wire the logical operators into conditions, and finally add break and continue, which jump out of or skip ahead in a loop using control-flow signals (Python exceptions used as a clean non-local jump). With these, the interpreter can express any algorithm.

   • If / Else: 5 lessons
   • While Loops: 5 lessons
   • For Loops: 5 lessons
   • Conditions: 5 lessons
   • Break & Continue: 5 lessons

7. Functions & Closures

   Functions turn a script into a language you can build with. This project adds them in full. A call expression names a callee and its arguments and checks the arity; native functions let the interpreter reach into the host language for primitives like clock and sqrt; a function declaration binds a function VALUE that remembers its parameters, body, and the environment it was born in. The return statement unwinds the call with a control-flow signal, defaulting to nil when omitted. Finally closures fall out for free: because a function captures its defining environment, it can read variables from where it was created, which makes recursion and counter-makers just work.

   • Call Expressions: 5 lessons
   • Native Functions: 5 lessons
   • Declaring Functions: 5 lessons
   • Return: 5 lessons
   • Closures: 5 lessons

8. Resolving, Scope & Errors

   A robust interpreter does two extra jobs around evaluation. First, a static resolution pass walks the program before it runs and pins each variable reference to the exact scope it refers to, measured as a depth; this is what makes closures capture the right variable and fixes a famous bug where a loop variable leaks into every closure. Second, it reports errors well: static errors like redeclaring a variable or returning outside a function are caught before running, runtime errors carry a line number and a clear message, and when the parser hits a syntax error it enters panic mode and synchronizes to the next statement boundary so it can keep going and report more than one problem at a time.

   • Resolving Variables: 5 lessons
   • Scope Rules: 5 lessons
   • Static Errors: 5 lessons
   • Runtime Errors: 5 lessons
   • Panic-Mode Recovery: 5 lessons

9. A Bytecode VM

   Tree-walking is simple but slow; production interpreters compile to bytecode and run it on a virtual machine. This project builds that second backend. A chunk bundles a flat list of instructions with a pool of constants; instructions are tiny tuples like ('CONST', 0) or ('ADD',). You build the value stack the VM computes on, the dispatch loop that executes each opcode (constants push, arithmetic pops two and pushes one, negate flips the top), the compiler that walks the AST in post-order so operands are on the stack before their operator runs, and finally jumps, the instructions that move the instruction pointer to implement branches and loops. The numeric arithmetic subset from the tree walker now runs on a stack machine. Separate jump exercises introduce branching; this backend does not compile the full statement, function or closure language.

   • The Chunk: 5 lessons
   • The Value Stack: 5 lessons
   • Executing Opcodes: 5 lessons
   • Compiling to Bytecode: 5 lessons
   • Jumps & Control Flow: 5 lessons

10. Capstone: A Complete Mini-Language

    Nine projects of parts, one language. This capstone wires the scanner, parser, and evaluator into a single working interpreter and exposes one function, run(source), that takes a program as text and returns the list of values it printed. The language has numbers, strings, booleans and nil, variables and assignment, arithmetic and logic, if/else and while, and functions with parameters, return, recursion, and closures. You assemble it from everything you built, then run real little programs, a counter, a summation loop, a recursive factorial, through your own machine and watch the right answers come out. The interpreter is small, but it is complete, and it is yours.

    • The Pipeline: 5 lessons
    • Running Programs: 5 lessons
    • Functions: 5 lessons
    • Built-ins & Errors: 5 lessons
    • The Finale: 5 lessons