Skip to content

L23 Parsing and code generation

24 minSuggested first: L22 Caches and storage

Outcome

Identify parser, transformation, and output generation from the representation each stage consumes and produces.

Learn

A parser reads input text and builds structure. An abstract syntax tree (AST) represents the meaningful parts of the input. A transform changes the tree. A generator turns the result into output text or another representation.

A compiler can have other stages too, and needn't produce machine code.

The toy folder below has one rule: it replaces Add(Number(a), Number(b)) with Number(a + b), and leaves every other node as it is.

Worked example

Follow 2 + 3 through the three stages. What question does each stage answer?

A toy constant folderText
Text:        "2 + 3"
Parsed AST:  Add(Number(2), Number(3))
Transformed: Number(5)
Output text: "5"
Predict first, then show the worked explanation

Parsing builds an Add node with two Number children. The constant-folding transform replaces it with a Number node for 5. The generator prints 5. In order: what is the structure, what simplification is valid, and what text should be emitted?

Practice and check

Guided practice

Practice, not scored

In this example, where does the Add node first become a Number node?

Choose one answer

Exit check

Counts toward completion

The input is x + 3, and nothing is known about x. What does the toy folding rule do?

Choose one answer

Common mistake

Calling all syntax processing "parsing". Identify the representation at each function boundary before naming the stage.

Practice on a real repository

Try the first puzzle below to investigate a pipeline, or the second to connect compilation with caching.

Related topics: Compilers and code generation

Practice is optional. Solving a puzzle doesn't complete a lesson, and lessons never change a puzzle's points.

References