Skip to content
Tutorials Center
My learning

Topics

Lesson 52 of 61 ยท Projects

Project: A Complete Toy Language

Finish the Tiny language in Python: a lexer with positions, a recursive descent parser, a scope and type checker, a closure-aware interpreter and friendly errors.

In the first project you compiled arithmetic. Now you will build a real programming language from end to end: the Tiny language introduced in Meet Our Toy Language, with variables, if and while, functions, recursion, closures and strings. You will not stop at a program that merely works. A good language implementation also refuses bad programs politely, so this project adds a static checker for scopes and types and shows every error with the source line and a caret under the guilty spot.

The finished system has four stages: a lexer, a parser, a checker and a tree-walking interpreter. Each is short because you already know the ideas: lexing, recursive descent, symbol tables and type checking. The next project compiles the same language to bytecode.

The plan

flowchart LR
    S["Source text"] --> L["Lexer"]
    L -->|"tokens with line and column"| P["Parser"]
    P -->|"AST with positions"| C["Checker"]
    C -->|"checked AST"| I["Interpreter"]
    I --> O["Program output"]
    L -.->|"LangError"| E["Error report with caret"]
    P -.->|"LangError"| E
    C -.->|"LangError"| E
    I -.->|"LangError"| E

Every stage can raise the same LangError, which carries a message and a position. One function turns it into a readable report.

The key design decision is that every token and every AST node knows its position (line and column). Because of that, the parser, the checker and the interpreter can all report an error at the exact place, using one shared LangError class and one report function.

Step 1: the lexer

The lexer is a single regular expression with named groups. The order of the alternatives matters: whitespace and comments are matched first and thrown away, numbers and strings come next, then identifiers, then operators. The operator alternative lists the two-character operators (<=, >=, ==, !=) before the one-character ones, so <= is never split in two (the longest-match rule from regular expressions for lexers).

To track positions, the lexer counts newlines inside every whitespace match and remembers where the current line started. The column of a token is then its offset minus the start of its line, plus one. Keywords are identifiers that appear in a fixed set. Two special alternatives catch mistakes: a lone " becomes an unterminated string error, and any other unmatched character becomes an unexpected character error.

Python Step 1: a lexer with line and column

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first three lines of output show how positions work: let is at column 1, total at column 5, and = at column 11, because the spaces count. The comment disappears entirely, and the loop on the second line starts again at column 1. The three error reports show the caret idea: the report prints the source line behind a gutter such as 1 | and then places ^ under the column of the problem, so the caret lines up with the offending character.

Step 2: the parser

The parser is a recursive descent parser with one method per grammar rule, directly following the EBNF in the language definition. Three things deserve a closer look.

Precedence by levels. The lesson on ambiguity and precedence layered one grammar rule per precedence level. Writing six nearly identical methods would be tedious, so a single method expr(level) does the same job from a table of operator groups: or, then and, then equality, comparison, addition and multiplication. At each level it parses the next tighter level on both sides of the operator and loops, which makes every operator left-associative. Below the table sit unary (- and not) and call expressions, whose arguments are parsed with the full expr.

Positions in the tree. Every node is a named tuple whose last field is pos. A binary node takes the position of its operator, so a type error such as "+ needs int operands" points at the +. A call node takes the position of the callee. This costs nothing during parsing and pays off in every later stage.

Where syntax errors point. When the parser expects a token and sees something else, the natural position is the unexpected token. For a missing token, however, a better place is just after the last token that was fine. In let x = 3 followed by print x; on the next line, the real mistake is the missing semicolon after 3, not the word print on the following line. The expect method therefore reports the end of the previous token. A missing operand (let x = 3 +;) is reported on the ; itself, because that is where an expression should have started.

The parser tells assignments from other statements with one token of lookahead: an identifier followed by = is an assignment. Everything else that is not a keyword statement is an expression statement.

Step 3: the checker

The checker walks the AST before anything runs and reports problems that a grammar cannot express. It does two jobs at once.

Scopes. The checker keeps a stack of dictionaries. Entering a { ... } block pushes a new scope; leaving pops it. let declares a name in the innermost scope and rejects a second declaration of the same name in that scope (shadowing in an inner scope is allowed). Reading or assigning a name searches the stack from the inside out and reports an undeclared variable if nothing is found. Function names are hoisted: before checking a block, the checker declares all fun names in it, so functions can call each other, as in the mutual recursion example. A variable, however, must be declared before the text that uses it.

Types. Tiny has no type annotations, so the checker infers just enough. A literal has an obvious type, a let gives a variable the type of its initializer, and operators demand operand types: arithmetic needs int, and/or/not need bool, a condition needs bool, and == needs two values of the same type. Function parameters have the special type any ("unknown") and anything is accepted where any appears, which keeps the checker simple without rejecting valid programs. Each function also gets a return type, inferred from its return statements: int if they all return an int, none if the function never returns a value (so let v = hello(); is reported as "produces no value"), and any when they disagree or while the function is still being checked, which is why recursion works.

This is a deliberately modest design: sound for the facts it knows, quiet about the rest. The lesson on type inference shows how to push the idea much further.

Step 4: the interpreter

The interpreter evaluates the checked tree directly. Its ideas are the ones from runtime environments:

  • An environment is a dictionary of variables plus a link to its parent. Each block gets a fresh child, so an inner let x shadows without overwriting. Lookups walk up the chain.
  • A function value stores its parameters, its body and the environment where it was defined. That captured environment is what makes closures work: the counter function can still see and change count after make_counter has returned.
  • return is implemented with an exception, ReturnSignal, which unwinds the Python stack to the call that is waiting for the value.
  • and and or evaluate the right-hand side only when needed (short-circuiting).
  • Runtime errors, such as division by zero, raise LangError with the position of the operator.
  • A step counter stops runaway programs, and Python's RecursionError is turned into a "stack overflow" message, so a buggy Tiny program cannot hang or crash the page.

Step 5: the whole language

Here is everything together, followed by a set of Tiny programs and a gallery of deliberate mistakes. Run it, then edit the programs or add your own. Try breaking things: remove a semicolon, compare a number with a string, call a function with too many arguments.

Python The complete Tiny language

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first five programs run correctly and agree with the reference interpreter from the earlier lesson: factorial prints 1, 2, 6, 24, 120, the prime counter finds 10 primes below 30, the shadowing program prints 99 and then 10, and the mutually recursive functions both answer true. The counter example shows two independent closures: a() is called twice and prints 1 and 2, while b(), which has its own count, prints 1.

Now read the mistakes. Each one is caught at a different stage, and each message says where:

  • The lexical error and the unterminated string come from the lexer, before any parsing.
  • The missing operand and the missing semicolon come from the parser. The caret for the missing semicolon sits right after the 3.
  • The undeclared variable, the redeclaration, the non-boolean condition, the bad operands, the changed type, the wrong argument count and the value-less call all come from the checker, before the program runs. No output from such a program appears at all.
  • Division by zero, the infinite loop and the runaway recursion can only be found while running, so they come from the interpreter.

That split is the main lesson of the project. The earlier an error is found, the cheaper it is for the programmer, and a program that passes the checker cannot fail with a type error at run time.

Ideas for extending the language

  • Strings. Add concatenation with + for two strings, and update the type rules so that + accepts int and int or string and string.
  • A better checker. Report all errors instead of stopping at the first one, using the recovery ideas from syntax errors and error recovery.
  • Arrays and for loops, with new AST nodes and new type rules.
  • Line comments in error messages, showing two lines of context around the error.
  • A formal test suite. Store each sample program with its expected output and run them all after every change, as the later lesson on testing and debugging a compiler recommends.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does the parser report a missing semicolon just after the previous token instead of at the next token?

    When a statement ends without a semicolon, the next token usually starts on the following line. Pointing there would blame the wrong line, so the report points at the end of the last good token.
  2. 2. What does the checker gain by hoisting function names before checking a block?

    Without hoisting, is_even would not know is_odd exists yet. Declaring all function names first lets each body refer to the others.
  3. 3. How can a counter function still change its variable after make_counter has returned?

    A closure is a function plus the environment of its definition. The inner function's lookups walk up into that captured environment.
  4. 4. Which error can only be detected while the program runs?

    Whether the divisor is zero depends on values that exist only at run time. The other three follow from the program text, so the checker finds them before running.

Summary

  • Tiny is implemented with a lexer, a recursive descent parser, a checker and a tree-walking interpreter that share one position-carrying error type.
  • Every token and AST node stores its line and column, so any stage can print the source line with a caret.
  • One table-driven method handles all binary precedence levels; missing tokens are reported after the last good token.
  • The checker keeps a scope stack, hoists function names, infers simple types with an any escape hatch, and infers function return types.
  • The interpreter uses environment chains for scopes, captures the defining environment for closures, and uses an exception for return.
  • Errors found before running are cheaper than errors found while running; step and recursion limits protect against the rest.

Next: Project: Compiler and VM for the Toy Language