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

Lessons

  1. 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. 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. 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

Module quiz

1. Where are brackets kept in an abstract syntax tree?
2. Nested scopes are searched in which order?
3. An inner block declares x when an outer x exists. What is that called?
4. What is the type of (if c 1 2) when c is bool?
5. In which order does a type checker handle an operator node?
6. Why does a compiler store each name's type in the symbol table?

‹ ParsingIntermediate code and optimization ›