Skip to content
Tutorials Center
My learning

Topics

Lesson 56 of 61 ยท Projects

Project: A Transpiler to Python

Build a source-to-source compiler in Python that translates the Tiny language into Python code, handles scopes and closures, and maps errors back to source lines.

A transpiler (source-to-source compiler) translates a program from one high-level language into another instead of into machine code. TypeScript becomes JavaScript, Sass becomes CSS, and early C++ compilers produced C. The target language already has a fast runtime and a mature toolchain, so the transpiler author only has to get the meaning across. That is also why transpilers are an excellent project: the back end is a text printer, and all the interesting work is in making the semantics match.

In this project you translate the Tiny language from Meet Our Toy Language into Python source code, run the result with exec, and map runtime errors in the generated code back to the line of Tiny that caused them. You will meet three problems that every transpiler faces: operators that look alike but behave differently, scopes that do not line up, and error messages that mention code the user never wrote.

The plan

The front end is the one you already know: a lexer and a recursive descent parser that turn Tiny text into an AST (the code is the same as the reference interpreter's, except that every token and statement also remembers its line number). The new part is the generator, which walks the AST and prints Python.

flowchart LR
    S["Tiny source"] --> L["Lexer"]
    L --> P["Parser"]
    P --> A["AST with line numbers"]
    A --> G["Generator<br/>resolves names, prints Python"]
    G --> Y["Python text"]
    G --> M["Source map<br/>Python line to Tiny line"]
    Y --> X["compile and exec"]
    X -. "traceback" .-> M
    M -. "Tiny line" .-> U["Error message"]

The generator produces two things at once: the Python text and a line table that lets runtime errors be reported in Tiny terms.

Problem 1: similar operators, different meaning

The easy part first. Most Tiny expressions translate token by token: +, -, *, %, the comparisons and and, or, not all exist in Python with the same spelling. The single spelling change is /, which is floor division in Tiny and so becomes //.

The hard part is grouping. If the generator only copies tokens, the parentheses in the source disappear, and Python's own precedence rules take over. Those rules differ from Tiny's in two ways: Python's not is looser than comparison (Tiny's is tighter), and Python treats a > b > c as a chain meaning a > b and b > c, while Tiny reads it as (a > b) > c.

The cure is to generate from the tree and put parentheses around every operator application. The tree already knows the correct grouping, so the printed text never depends on precedence at all. The result has more parentheses than a human would write, and that is fine: generated code is for the machine.

The run below compares both strategies on a handful of expressions. It computes what each expression means in Tiny by walking the tree, then evaluates both generated Python strings and checks them against that meaning.

Python Naive copying versus tree-based translation

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 naive column goes wrong in five of eight rows. 10 - (4 - 3) loses its parentheses and gives 3 instead of 9; 3 > 2 > 1 becomes a Python chain and turns False into True; not 1 < 2 flips because of the different not precedence. The safe column is right every time. Note that the safe translation of -7 / 2 is ((-7) // 2), which is -4: Tiny's floor division and Python's agree, but a language that truncated toward zero, such as C, would need extra code for /.

Never decide "this operator spelling is the same, so the semantics match" without testing the awkward cases: negative numbers, division and remainder, comparison chains, short-circuiting, and integer overflow. Most real transpiler bugs hide there.

Problem 2: scopes do not line up

Tiny is block scoped: every { } opens a new scope, and an inner let x shadows an outer x until the block ends. Python has only function scope. A variable assigned inside an if is visible in the whole function, and there is no way to declare a second x for the inner block. The usual solution is renaming: give every Tiny declaration its own unique Python name.

The generator keeps a stack of dictionaries, one per Tiny block, mapping Tiny names to Python names. A let creates an entry with a fresh name. The first x becomes x, a shadowing x in an inner block becomes x_1, and a later use of x inside that block looks up the innermost entry. This is the resolver from Symbol Tables and Scopes doing real work. It also gives us two compile-time checks for free: using an undefined name, and return outside a function.

The same trick avoids clashes with Python itself. Tiny allows class or list as variable names, but in Python the first is a keyword and the second shadows a built-in. The generator treats every Python keyword and built-in as already taken, so Tiny's list becomes list_1.

Two more details need care:

  • let order. In let x = x + 1; the right side must refer to the old x. The generator translates the expression first and declares the new name afterwards.
  • Assignment from inner functions. In Tiny, n = n + 1 inside a nested function changes the captured variable. In Python the same assignment would create a new local, so the generated function needs a nonlocal n line. The generator records which outer names each function assigns to and inserts the declaration at the top of the function. To make this work for top-level variables too, the whole program is wrapped in a function called tiny_main.

Problem 3: errors that point at generated code

When Python raises an exception inside generated code, the traceback shows a line of code the user never wrote, such as result = (total // count) on line 9 of something they have not seen. A good transpiler reports the original line.

The simplest source map is what this generator builds: every emitted Python line is stored together with the Tiny line that produced it. After a failure, the runner walks the traceback, finds the deepest frame whose file name is the generated code's (<tiny>), and looks up that Python line number in the table.

This gives line-level accuracy. A finer map could store columns as well, recording for each output token the span of the source token it came from. JavaScript tooling does exactly that.

JSON
{
  "version": 3,
  "file": "app.js",
  "sources": ["app.ts"],
  "names": ["greet"],
  "mappings": "AAAA,SAASA,MAAM"
}

A real source map file (read-only). The mappings string is a compact encoding of (generated column, source file, source line, source column, name) tuples; browsers use it to show TypeScript where the JavaScript failed.

The complete transpiler

Now put everything together. The program below contains the whole front end, the generator and the runner, followed by eight demonstrations. For the first four it prints the generated Python next to the Tiny line each line came from, then the output of running it. The last four show compile-time errors and a runtime error that is reported against Tiny.

Python Tiny to Python transpiler

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.

Read the generated code carefully. In the closure example the inner function next became next_1, because next is a Python built-in. It also received a line nonlocal n, which is why two counters made by make_counter() count independently, exactly as the Tiny semantics require. The shadowing program printed 11 and then 10, because the inner x turned into x_1. Lines marked "Tiny line 0" belong to the tiny_main wrapper, which has no Tiny counterpart.

In the last demonstration average(5, 0) divides by zero. Python raises a ZeroDivisionError; the runner adds Tiny line 2, the line of the let result = ... statement in the user's program. The user never sees the generated code.

What this transpiler gets wrong

Being honest about fidelity is part of the job. Compare with the reference interpreter and you will find differences:

  • Stricter name rules. The transpiler requires a name to be declared textually before it is used, even inside a function body. The interpreter only requires it to exist when the code runs, so mutually recursive functions need a forward declaration here.
  • Closures in loops. Tiny creates a fresh variable for every iteration of a loop body; Python reuses one. A closure created inside a loop and called after it would see different values. A fix would be to generate a factory function per iteration.
  • Runtime errors differ. A call with the wrong number of arguments raises Python's TypeError, with Python's wording.
  • Deep recursion. Python's recursion limit applies to the generated code, not to Tiny.
  • Security. exec on generated code is only safe because the generator controls everything it prints: identifiers passed through the lexer's pattern and string literals are produced by repr. Never splice raw user text into generated code.

For a language that must behave exactly like its specification, the answer is a test suite that runs every program through both the reference interpreter and the transpiler and compares the outputs. Testing and Debugging a Compiler shows how.

Exercises

  • Remove the redundant parentheses around if and while conditions and around the outermost expression of each statement, keeping only the ones that are necessary.
  • Add a for-style loop to Tiny and translate it to while.
  • Translate Tiny to JavaScript instead. Which problems disappear (block scope with let) and which new ones appear (the / operator produces floats, so you need Math.floor)?
  • Add column numbers to the source map and print a caret under the failing expression.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the generator put parentheses around every operator application?

    Python's not and comparison chaining work differently from Tiny's. With full parentheses the generated text means exactly what the AST means.
  2. 2. What problem does renaming x to x_1 solve?

    A second let x in an inner block must not overwrite the outer x. Giving each declaration its own Python name keeps them separate.
  3. 3. Why does the generated function need a nonlocal declaration?

    In Python any assignment inside a function makes the name local unless nonlocal or global says otherwise. Tiny's assignment changes the captured variable.
  4. 4. How does the runner report a runtime error in Tiny terms?

    The source map is a list parallel to the generated lines. The traceback gives the Python line number, which indexes the list.
  5. 5. Which Tiny feature does the transpiler translate with a different operator spelling?

    Tiny's / is floor division, which Python spells //. Everything else keeps its spelling, but grouping still needs care.

Summary

  • A transpiler keeps the front end of a compiler and replaces the back end with a printer for another high-level language.
  • Generate from the tree with full parentheses; copying tokens loses grouping and runs into different precedence rules.
  • Block scope is simulated by giving every declaration a unique target name; keywords and built-ins count as taken.
  • Closures that assign to captured variables need nonlocal in Python; wrapping the program in a function makes top-level variables work too.
  • A source map ties each generated line to its source line, so errors are reported in the language the user wrote.
  • Know where the translation is not exact, and test against a reference implementation.

Next: Practice Exercises with Solutions