How Does Typed Text Become Something a Chip Can Run? Translation in Stages
By the BrainSnail editorial team. How these articles are written and checked, and how to tell us when one is wrong.
Source code written for people is converted into instructions a processor executes, and the conversion happens in a sequence of distinct stages. Each stage solves one problem and hands a cleaner representation to the next.
What the translation has to bridge
Source code is written in a notation designed for humans, with names, structure, nesting and abstractions that exist to make intentions clear. A processor executes a stream of numeric instructions that move values between registers and memory, perform arithmetic, and jump to addresses, with no notion of a name, a type or a loop. The gap between those two is enormous, and closing it in one step would be unmanageable, so the work is divided into stages that each perform one transformation. That division is what makes it possible to support many source languages and many processors without writing a separate translator for every combination, since the front and back of the sequence can be mixed.
The stages
The conventional division has held for decades:
- •Lexical analysis breaks the text into tokens such as names, numbers and symbols
- •Parsing arranges those tokens into a tree reflecting the structure of the language
- •Semantic analysis checks types, resolves names and rejects what is meaningless
- •An intermediate representation is generated, independent of any particular processor
- •Optimisation rewrites that representation into a faster or smaller equivalent
- •Code generation emits actual instructions for the target processor and allocates registers
What optimisation actually does
The rewriting stage is where most of the sophistication lives and the transformations are individually simple. Computations whose result is known in advance are performed once during translation rather than every time the code runs. Values recomputed identically are computed once and reused. Work that does not change inside a loop is moved outside it. Small routines are copied into the place that calls them, removing the cost of the call and exposing further opportunities. Code that can never execute is deleted. Instructions are reordered to suit how the processor overlaps work internally. Each transformation must preserve the meaning exactly, which is the hard constraint, and proving that in the presence of concurrency and arithmetic edge cases is where the real difficulty lies.
Why the errors are so unhelpful
Anybody who has used one of these tools has met a message that identifies the wrong line, and the reason is structural. The checking stage discovers a problem when the input stops making sense, which is frequently several tokens after the actual mistake, since a missing bracket or semicolon leaves the text valid until something later cannot be reconciled. Recovering after an error is also difficult, because the tool must guess what the author meant in order to continue and report further problems, and a wrong guess produces a cascade of spurious complaints after the real one. Type errors in languages with elaborate type systems generate messages describing deeply nested constructions that the author never wrote. Modern implementations put substantial effort into this, tracking positions carefully, suggesting corrections and truncating cascades, and it remains one of the clearest differences between tools.
The alternatives to translating everything first
Translating the whole source before running any of it is one strategy among several. An interpreter reads and executes the source directly, which starts instantly and runs more slowly, and which makes interactive use and rapid editing far more pleasant. A just in time approach translates while the software runs, which allows decisions based on what is actually happening, such as specialising a routine for the types it turns out to receive, and it can beat ahead of time translation on code whose behaviour is not predictable in advance. Bytecode systems translate to instructions for an abstract machine, which is then interpreted or translated further. Most substantial systems now mix these, interpreting at first and translating the parts that run often.
The takeaway
Source code and machine instructions are far apart, so the translation is split into stages that each do one job and hand on a cleaner form. Tokenising, parsing, checking, generating an intermediate form, rewriting it and emitting instructions is the conventional sequence. Splitting it that way is what allows many languages and many processors to be supported without a separate translator for every pair.