Trees, scopes and types
The program as a tree: abstract syntax trees and tree walks, symbol tables with nested scopes, and type checking with type rules.
About 5 hours of study
Learning objectives
- Build abstract syntax trees and walk them recursively
- Resolve names through a stack of scopes
- Type-check expressions and statements and report clear errors
Lessons
- 1
Abstract syntax trees Intermediate
Represent a program as a tree of nodes that keeps its meaning and drops the punctuation. Build the tree in the parser, then walk it with recursive functions to print, evaluate or check it.
- 2
Symbol tables and scopes Intermediate
A compiler must know what each name refers to. Keep a symbol table as a stack of scopes, declare names in the innermost scope, look them up from the inside out, and report undeclared and duplicate names.
- 3
Type checking Advanced
Give every expression a type and reject programs that combine types wrongly, before they run. Write type rules, check a tree bottom-up with an environment of declared types, and report clear type errors.
Module practice
- Compilers: Measure a treeEasy
- Compilers: Draw the treeMedium
- Compilers: Back to source with the fewest bracketsHard
- Compilers: Undeclared and duplicate namesEasy
- Compilers: Resolve names in nested scopesMedium
- Compilers: Unused and shadowing warningsHard
- Compilers: The type of one operationEasy
- Compilers: Type-check expression treesMedium
- Compilers: Type-check a small programHard