ToolSphere
Back to all articles
student

Compiler Bootstrapping and Error Recovery

2026-11-059 min read

Try it: free Phases of a Compiler

Follow an assignment through each stage of compilation

Open →

A compiler is a program, so something must run the compiler before it can translate another program. Bootstrapping explains how a compiler becomes available on a machine. Error recovery answers a different practical question: how can that compiler keep checking a source file after it finds a mistake?

This compiler foundations guide connects those ideas to the compiler phases tool, then uses the site's LL(1) parser and LR parser to show exactly where invalid expressions stop. The parser examples below were generated with their calculation libraries. These teaching parsers report the first syntax error; they do not implement the recovery algorithms described later.

Read a T-diagram without mixing up the languages

A T-diagram records the source language, target language and implementation language of a translator. Read the top from left to right; read the stem as the language in which this version of the compiler is represented.

source language L ───── target language M
                   │
          implementation language I

For compiler source written in C, the stem is C. Once an existing compiler translates that source into host machine code H, the resulting executable version has H at the stem. The top still says L → M: compiling the compiler changes its representation, not the language translation it implements. The University of Colorado's bootstrapping notes use this source/target/implementation distinction.

The stem is therefore not automatically the target at the top right. An executable that runs on an x86 host can emit code for an ARM target. It cannot necessarily run the ARM output on that x86 machine.

Native compiler, cross-compiler and build machine

A native compiler runs on the kind of system for which it generates code. A cross-compiler runs on one host and generates code for another target. When building a compiler, distinguish its build machine from both.

Term Meaning for a compiler build
Build System performing the build
Host System that will run the resulting compiler
Target System for which that compiler will emit code

For example, building an x86-hosted ARM compiler on x86 has build = host = x86 and target = ARM. A compiler built on x86 to run on ARM and emit ARM code has build = x86 and host = target = ARM. Architecture names alone are shorthand: real toolchains also depend on the operating system and ABI. These roles follow the GCC configuration terminology.

Bootstrapping: use an available translator as the seed

Suppose the new language is L and the host machine is H. An available C-to-H compiler can compile an L-to-H compiler written in C. That produces an executable L compiler running on H.

Next, write a newer L-to-H compiler in the supported subset of L. Compile its source with the available L compiler. The result can compile that source again. A compiler whose own implementation uses the language it compiles is called self-hosting. The first usable compiler still needs an available translator or interpreter; self-hosting does not remove that starting dependency. This is the pattern illustrated in the University of Northern Iowa's bootstrapping lesson.

An L-to-M compiler can similarly be built on H and used to compile a native compiler for M, provided the necessary language support and target tools exist. Cross-compilation is useful here because the compiler produced for M may not execute on H.

Real compiler builds also need compatible assemblers, linkers, libraries and target headers. Rebuilding a compiler with itself and comparing later outputs can detect inconsistencies; equal outputs do not prove that every generated program is correct. GCC's build documentation describes its bootstrap comparison and the different setup used for cross-compilers.

Error detection and recovery are separate jobs

Detection identifies a point at which the implementation cannot proceed normally. Recovery decides how to continue. The detected location may follow the original mistake, so a useful diagnostic should show the unexpected token and enough context to correct it.

A lexer can report an invalid character or an unterminated string. A parser can reject a token arrangement even when its individual tokens are valid. Later semantic checks can reject a type mismatch or an undeclared name. A logically wrong but otherwise valid program may pass all of them. Use the lexical analyzer for token classification, rather than expecting a grammar-only parser to check a complete C program.

Worked LL(1) failure: an empty table cell

Load the expression example in the LL(1) parser, then enter id + * id.

E  -> T E'
E' -> + T E' | ε
T  -> F T'
T' -> * F T' | ε
F  -> ( E ) | id

The computed trace contains 8 rows, including the error row. The stack is written bottom to top, with the active symbol on the right. The end marker is shown as “end” in this guide; the tool displays a dollar sign.

Stack Remaining input Action
end E id + * id end Output E → T E'
end E' T id + * id end Output T → F T'
end E' T' F id + * id end Output F → id
end E' T' id id + * id end Match id
end E' T' + * id end Output T' → ε
end E' + * id end Output E' → + T E'
end E' T + + * id end Match +
end E' T * id end Error: M[T, *] is empty, so "*" can't appear here

After the plus, the parser needs a term. No production in the T row begins a term with *, so it stops without consuming that token. Its full diagnostic is M[T, *] is empty, so "*" can't appear here. Deleting the extra star and trying id + id gives an accepted trace with 13 rows. That edit is your correction, not an automatic parser repair.

For the input ( id + id, the same library stops after 17 rows with a terminal mismatch: it expects the closing parenthesis but reaches the end marker. A missing delimiter and an empty prediction-table cell are different detection cases.

Worked SLR(1) failure: an empty ACTION cell

The LR page's default expression grammar is left-recursive:

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

Select SLR(1) and enter id + * id. The generated automaton has 12 states. Its trace has 6 rows, including the error:

Stack Remaining input Action
0 id + * id end Shift id, go to state 5
0 id 5 + * id end Reduce by F → id (r6)
0 F 3 + * id end Reduce by T → F (r4)
0 T 2 + * id end Reduce by E → T (r2)
0 E 1 + * id end Shift +, go to state 6
0 E 1 + 6 * id end Error: no action in state 6 for "*"

The state number describes this implementation's construction order; another correct parser can number states differently. For ( id + id, this parser reaches state 8 and reports no action for the end marker. Correcting the input to id + id gives an accepted 10-row trace. Neither parser silently skips to another statement.

Compare syntax-error recovery strategies

These approaches summarize the classification in NYU's compiler lecture on error handling.

Strategy Recovery idea Main trade-off
Panic mode Discard input until a chosen synchronization token, such as a statement delimiter Easy to bound, but may skip useful context
Phrase-level recovery Make a local repair, such as inserting a missing delimiter A plausible repair can misread the programmer's intent
Error productions Add grammar cases for recognizable common mistakes Requires designed diagnostic/recovery rules
Global correction Find a valid input minimizing a defined edit cost More expensive; a minimum-cost repair may still be unintended

Synchronization tokens depend on the language and parsing context. A semicolon may be useful at a statement boundary, but it is not a universal reset button. Local repairs must make progress so the parser cannot repeatedly “fix” the same position.

Error productions also differ from merely adding a normal terminal named error. In Bison, error is a special recovery symbol. A rule such as the following can allow processing to resume after a statement delimiter:

statement: error ';'

Bison can pop parser states until it can shift that recovery symbol, then discard input until the continuation is usable. This is an illustration of Bison's mechanism, not syntax that enables recovery in the site's LR tool. Recovery can cause follow-on diagnostics when its guess is wrong; the Bison error-recovery manual explains this limitation and the handling of discarded values.

Check your exam answer against the actual behaviour

For a bootstrapping question, label the compiler's input, output and representation before combining diagrams. For a recovery question, state what is discarded or repaired, where parsing resumes and what context may be lost.

To reproduce the traces, load the exact grammar, select the stated parser mode and enter the invalid input. Compare the final stack and remaining tokens before editing. Continue with the FIRST/FOLLOW worked guide, SLR table example or the CS Theory Lab's syllabus units.

Looking for other tools?

Explore ToolSphere Homepage →