Abstract syntax trees and semantic analysis · CMPUT-415 Lesson 5

A program can be grammatically perfect and still meaningless. The Tern statement x = y + 1; parses, but if x was never declared, or y is an array, or the statement appears in a function whose other paths return nothing, the program is wrong. Semantic analysis is the part of the front end that checks these context-dependent rules and gathers the information later phases need: what each name refers to, what type each expression has, how much storage each variable requires. It works on the abstract syntax tree, so this lesson begins by designing Tern's AST and its parser, then builds symbol tables and name resolution. Lesson 6 adds type checking and type inference.

Designing an abstract syntax tree

An AST has one kind of node for each kind of construct: literals, names, binary and unary operations, calls, array indexing, and statements such as variable declarations, assignments, if, while and return. Each node stores its children and the attributes that distinguish it, such as the operator of a binary node or the name of a variable, together with its source position so that errors can be reported precisely. Good AST design keeps the tree close to the source language, without committing to how it will be executed: an if statement is an If node with a condition, a then-block and an optional else-block, not a pattern of jumps. Many compilers distinguish expressions, which produce values, from statements, which do not, because the type checker and code generator treat them differently.

The node types of Tern's abstract syntax tree
Tern construct	AST node	Children and attributes
42, true	Num, Bool	value
x	Name	identifier; later, a link to its declaration
a + b, x < y, p && q	Bin	operator, left, right
-x, !p	Unary	operator, operand
f(a, b)	Call	function name, argument list
a[i]	Index	array expression, index expression
var x: int = e;	Var	name, optional declared type, initializer
x = e; a[i] = e;	Assign	target (Name or Index), value
if c { ... } else { ... }	If	condition, then-block, optional else-block
while c { ... }	While	condition, body
return e;	Return	value
fn f(p: T) -> R { ... }	Func	name, typed parameters, return type, body

The parser below combines the techniques of lessons 2 and 3: a regular-expression scanner, recursive-descent procedures for functions, blocks and statements, and a Pratt loop for expressions. Each statement procedure begins by examining the next token, var, if, while or return, to decide which construct follows, which is predictive LL(1) parsing written by hand. Assignment needs a little care, because x = e and a call statement f(x); both begin with an expression; the parser parses an expression first and then checks for =, and rejects targets such as 3 that cannot be assigned. Nodes are Python dataclasses, a convenient way to declare record types; in C++ or Rust compilers, ASTs are usually class hierarchies or enums with variants.

Tern's parser: recursive descent for statements and Pratt parsing for expressions, producing a typed AST

# Tern's parser: recursive descent for declarations and statements, Pratt
# parsing for expressions, producing an AST of dataclasses with positions.
import re
from dataclasses import dataclass, field
@dataclass
class Node: line: int = field(default=0, repr=False, compare=False)
@dataclass
class Num(Node): value: int = 0
@dataclass
class Bool(Node): value: bool = False
@dataclass
class Name(Node): id: str = ""
@dataclass
class Bin(Node): op: str = ""; left: Node = None; right: Node = None
@dataclass
class Unary(Node): op: str = ""; operand: Node = None
@dataclass
class Call(Node): func: str = ""; args: list = None
@dataclass
class Index(Node): array: Node = None; index: Node = None
@dataclass
class Var(Node): name: str = ""; type: str = None; init: Node = None
@dataclass
class Assign(Node): target: Node = None; value: Node = None
@dataclass
class If(Node): cond: Node = None; then: list = None; orelse: list = None
@dataclass
class While(Node): cond: Node = None; body: list = None
@dataclass
class Return(Node): value: Node = None
@dataclass
class ExprStmt(Node): expr: Node = None
@dataclass
class Func(Node): name: str = ""; params: list = None; ret: str = ""; body: list = None

TOKEN = re.compile(r"(?P<ws>[ \t]+|//[^\n]*)|(?P<nl>\n)|(?P<num>\d+)|(?P<id>[A-Za-z_]\w*)"
                   r"|(?P<op>==|!=|<=|>=|&&|\|\||->|[-+*/%<>=!(){}\[\],;:])")
KW = {"fn", "var", "if", "else", "while", "return", "true", "false"}
def lex(src):
    out, line = [], 1
    for m in TOKEN.finditer(src):
        k, t = m.lastgroup, m.group()
        if k == "nl": line += 1
        elif k != "ws": out.append((t if (k == "op" or t in KW) else k, t, line))
    return out + [("EOF", "", line)]
LB, RB = "{", "}"
BP = {"||": 1, "&&": 2, "==": 3, "!=": 3, "<": 4, "<=": 4, ">": 4, ">=": 4, "+": 5, "-": 5, "*": 6, "/": 6, "%": 6}

class Parser:
    def __init__(p, src): p.t, p.i = lex(src), 0
    def peek(p, k=0): return p.t[p.i + k][0]
    def eat(p, kind):
        tok = p.t[p.i]
        if tok[0] != kind: raise SyntaxError(f"line {tok[2]}: expected {kind!r}, found {tok[1] or 'end of file'!r}")
        p.i += 1; return tok
    def program(p):
        fns = []
        while p.peek() != "EOF": fns.append(p.func())
        return fns
    def type_(p):
        if p.peek() == "[": p.eat("["); t = p.eat("id")[1]; p.eat("]"); return f"[{t}]"
        return p.eat("id")[1]
    def func(p):
        line = p.eat("fn")[2]; name = p.eat("id")[1]; p.eat("("); params = []
        while p.peek() != ")":
            pn = p.eat("id")[1]; p.eat(":"); params.append((pn, p.type_()))
            if p.peek() == ",": p.eat(",")
        p.eat(")"); p.eat("->"); ret = p.type_()
        return Func(line, name, params, ret, p.block())
    def block(p):
        p.eat(LB); body = []
        while p.peek() != RB: body.append(p.stmt())
        p.eat(RB); return body
    def stmt(p):
        line = p.t[p.i][2]; k = p.peek()
        if k == "var":
            p.eat("var"); name = p.eat("id")[1]; ty = None
            if p.peek() == ":": p.eat(":"); ty = p.type_()
            p.eat("="); init = p.expr(); p.eat(";"); return Var(line, name, ty, init)
        if k == "if":
            p.eat("if"); c = p.expr(); th = p.block(); el = None
            if p.peek() == "else":
                p.eat("else"); el = [p.stmt()] if p.peek() == "if" else p.block()
            return If(line, c, th, el)
        if k == "while": p.eat("while"); c = p.expr(); return While(line, c, p.block())
        if k == "return": p.eat("return"); e = p.expr(); p.eat(";"); return Return(line, e)
        e = p.expr()
        if p.peek() == "=":
            p.eat("="); v = p.expr(); p.eat(";")
            if not isinstance(e, (Name, Index)): raise SyntaxError(f"line {line}: cannot assign to this expression")
            return Assign(line, e, v)
        p.eat(";"); return ExprStmt(line, e)
    def expr(p, min_bp=0):
        left = p.prefix()
        while True:
            k = p.peek(); line = p.t[p.i][2]
            if k == "[": p.eat("["); ix = p.expr(); p.eat("]"); left = Index(line, left, ix); continue
            bp = BP.get(k)
            if bp is None or bp <= min_bp: return left
            p.i += 1; left = Bin(line, k, left, p.expr(bp))
    def prefix(p):
        kind, text, line = p.t[p.i]; p.i += 1
        if kind == "num": return Num(line, int(text))
        if kind in ("true", "false"): return Bool(line, kind == "true")
        if kind == "(": e = p.expr(); p.eat(")"); return e
        if kind in ("-", "!"): return Unary(line, kind, p.expr(7))
        if kind == "id":
            if p.peek() == "(":
                p.eat("("); args = []
                while p.peek() != ")":
                    args.append(p.expr())
                    if p.peek() == ",": p.eat(",")
                p.eat(")"); return Call(line, text, args)
            return Name(line, text)
        raise SyntaxError(f"line {line}: unexpected {text or 'end of file'!r}")

def show(n, ind=0):                                  # compact indented AST dump
    pad = "  " * ind
    if isinstance(n, list):
        for s in n: show(s, ind)
        return
    fields = {k: v for k, v in vars(n).items() if k != "line"}
    kids = {k: v for k, v in fields.items() if isinstance(v, (Node, list)) and k != "params"}
    leaf = ", ".join(f"{k}={v!r}" for k, v in fields.items() if k not in kids)
    print(f"{pad}{type(n).__name__}({leaf})")
    for k, v in kids.items():
        if v is None: continue
        print(f"{pad}  .{k}:"); show(v, ind + 2)

SRC = """fn gcd(a: int, b: int) -> int {
    while b != 0 {
        var t = a % b;
        a = b;
        b = t;
    }
    return a;
}"""
show(Parser(SRC).program())
for bad in ["fn f() -> int { return 1 + ; }", "fn f() -> int { 3 = x; }"]:
    try: Parser(bad).program()
    except SyntaxError as e: print("syntax error:", e)

Output

Func(name='gcd', params=[('a', 'int'), ('b', 'int')], ret='int')
  .body:
    While()
      .cond:
        Bin(op='!=')
          .left:
            Name(id='b')
          .right:
            Num(value=0)
      .body:
        Var(name='t', type=None)
          .init:
            Bin(op='%')
              .left:
                Name(id='a')
              .right:
                Name(id='b')
        Assign()
          .target:
            Name(id='a')
          .value:
            Name(id='b')
        Assign()
          .target:
            Name(id='b')
          .value:
            Name(id='t')
    Return()
      .value:
        Name(id='a')
syntax error: line 1: unexpected ';'
syntax error: line 1: cannot assign to this expression

The dump shows the shape of the tree for Euclid's algorithm: the function's body is a list of a While and a Return; the loop's condition is a Bin node; its body declares t and performs two assignments. Each node also carries a line number, hidden in the dump. The two syntax errors show the parser's messages, which name the offending token or construct and give the line.

What semantic analysis checks

Language rules that depend on context fall into a few groups. Scope rules say which declaration each use of a name refers to and forbid using undeclared names. Type rules say which operations are allowed on which values: you cannot add a boolean to an integer or index an integer in Tern. Declaration rules forbid declaring the same name twice in one scope and require functions to be called with the right number of arguments. Control-flow rules require, for example, that every path through a function with a non-void return type returns a value and that break appears only inside a loop. Other checks are language-specific: definite assignment in Java and C# (a variable must be assigned before it is read on every path), exhaustiveness of match expressions in Rust and Swift, borrow checking in Rust. Some of these rules could in principle be written into a grammar, but the grammar would be enormous; context-sensitive rules are much more naturally checked by walking the tree.

Symbol tables and scopes

A symbol table maps names to information about their declarations: kind (variable, parameter, function, type), type, location, and anything else the compiler needs. Most languages use static, also called lexical, scoping: the declaration a name refers to is determined by the program's text, by the nesting of blocks, rather than by the order of calls at run time. CMPUT-325 (lesson 4) compares static and dynamic scoping; compilers for almost every modern language implement static scoping with a stack of scopes. Entering a block pushes a new, empty scope; a declaration adds a name to the innermost scope; looking up a name searches from the innermost scope outward; leaving the block pops its scope. An inner declaration with the same name as an outer one shadows it for the rest of the inner block.

Nested scopes for the function sum: lookups search outward from the innermost scope

Two implementation strategies are common. The scope-stack approach keeps a separate hash table per scope, linked to its parent, exactly as drawn. The alternative keeps a single hash table mapping each name to a stack of declarations, pushing on declaration and popping when a scope ends, with a list per scope recording which names to pop; this makes lookups a single hash access, which matters in compilers for languages like C++ where name lookup is a significant cost. Either way, the result of name resolution is usually recorded in the AST itself: each Name node gets a pointer to the declaration it refers to, so later phases never look names up again.

Name resolution with nested scopes: bindings, shadowing, and errors for undeclared and duplicate names

# Name resolution with a stack of scopes. The resolver walks an AST (nested
# tuples here, to keep the program short), binds each use of a name to its
# declaration, and reports undeclared and duplicate names with line numbers.
class Scope:
    def __init__(s, kind, parent=None):
        s.kind, s.parent, s.names = kind, parent, {}
        s.depth = 0 if parent is None else parent.depth + 1
    def declare(s, name, info, line, errors):
        if name in s.names:
            errors.append(f"line {line}: {name!r} already declared in this {s.kind} scope "
                          f"(line {s.names[name]['line']})")
        else: s.names[name] = dict(info, line=line, depth=s.depth)
    def lookup(s, name):
        sc = s
        while sc:
            if name in sc.names: return sc.names[name]
            sc = sc.parent
        return None
# AST: ("fn", line, name, params, body); statements ("var", line, name, expr),
# ("assign", line, name, expr), ("while"/"if", line, cond, block), ("return", line, expr)
# expressions: ("name", line, id), ("num", value), ("bin", op, l, r), ("call", line, f, args)
PROG = [
 ("fn", 1, "sum", [("n", "int")], [
    ("var", 2, "total", ("num", 0)),
    ("var", 3, "i", ("num", 1)),
    ("while", 4, ("bin", "<=", ("name", 4, "i"), ("name", 4, "n")), [
        ("var", 5, "sq", ("bin", "*", ("name", 5, "i"), ("name", 5, "i"))),
        ("assign", 6, "total", ("bin", "+", ("name", 6, "total"), ("name", 6, "sq"))),
        ("var", 7, "i", ("bin", "+", ("name", 7, "i"), ("num", 1)))]),   # shadows outer i
    ("assign", 9, "totl", ("name", 9, "sq")),                             # two mistakes
    ("var", 10, "total", ("num", 0)),                                     # duplicate
    ("return", 11, ("call", 11, "helper", [("name", 11, "total")]))]),
]
errors, uses = [], []
globals_ = Scope("global")
for item in PROG: globals_.declare(item[2], {"kind": "function"}, item[1], errors)
for builtin in ("print", "len", "array"): globals_.names[builtin] = {"kind": "builtin", "line": 0, "depth": 0}
def expr(e, sc):
    tag = e[0]
    if tag == "name":
        d = sc.lookup(e[2])
        if d is None: errors.append(f"line {e[1]}: use of undeclared name {e[2]!r}")
        else: uses.append((e[1], e[2], d["line"], d["depth"]))
    elif tag == "bin": expr(e[2], sc); expr(e[3], sc)
    elif tag == "call":
        if sc.lookup(e[2]) is None: errors.append(f"line {e[1]}: call to undeclared function {e[2]!r}")
        for a in e[3]: expr(a, sc)
def block(stmts, sc):
    for s in stmts:
        tag = s[0]
        if tag == "var":
            expr(s[3], sc)                       # initializer sees the OUTER binding
            sc.declare(s[2], {"kind": "variable"}, s[1], errors)
        elif tag == "assign":
            if sc.lookup(s[2]) is None: errors.append(f"line {s[1]}: assignment to undeclared {s[2]!r}")
            expr(s[3], sc)
        elif tag in ("while", "if"):
            expr(s[2], sc); block(s[3], Scope("block", sc))
        elif tag == "return": expr(s[2], sc)
for _, line, name, params, body in PROG:
    fsc = Scope("function", globals_)
    for p, t in params: fsc.declare(p, {"kind": "parameter", "type": t}, line, errors)
    block(body, Scope("block", fsc))
for line, name, decl, depth in uses:
    print(f"line {line:2}: {name:5} -> declared on line {decl:2} (scope depth {depth})")
for e in errors: print("error:", e)

Output

line  4: i     -> declared on line  3 (scope depth 2)
line  4: n     -> declared on line  1 (scope depth 1)
line  5: i     -> declared on line  3 (scope depth 2)
line  5: i     -> declared on line  3 (scope depth 2)
line  6: total -> declared on line  2 (scope depth 2)
line  6: sq    -> declared on line  5 (scope depth 3)
line  7: i     -> declared on line  3 (scope depth 2)
line 11: total -> declared on line  2 (scope depth 2)
error: line 9: assignment to undeclared 'totl'
error: line 9: use of undeclared name 'sq'
error: line 10: 'total' already declared in this block scope (line 2)
error: line 11: call to undeclared function 'helper'

The output repays close reading. On line 7, var i = i + 1 inside the loop shadows the outer i, but its initializer still refers to the outer i declared on line 3, because a new name comes into scope only after its declaration is complete; languages differ on this point, and Rust and Tern choose this rule. After the loop, the assignment on line 9 has two mistakes, a misspelled target and a use of sq, which was declared inside the loop body and is out of scope after it. Line 10 redeclares total in the same scope, and the call on line 11 names a function that does not exist. A good resolver reports all of these rather than stopping at the first.

Attribute grammars and syntax-directed definitions

Semantic analysis can be described formally with attribute grammars, introduced by Donald Knuth in 1968. Each grammar symbol has attributes, such as a type or a value, and each production has rules that compute attributes from those of related symbols. Synthesized attributes flow up the tree, computed from children: the type of a + b is computed from the types of a and b. Inherited attributes flow down or sideways, computed from the parent or siblings: the scope in which a statement is checked, or the expected type of an initializer, is inherited. An attribute grammar is well defined if attributes can be evaluated in some order without circular dependencies. S-attributed grammars use only synthesized attributes and can be evaluated during an LR parse, in the semantic actions of lesson 4; L-attributed grammars allow inherited attributes that depend only on the parent and on siblings to the left, and can be evaluated during a single top-down, left-to-right pass, such as a recursive-descent parse. In practice, compilers rarely use attribute grammar tools, but the vocabulary is useful, and the passes we write are hand-implemented attribute evaluators: the resolver passes the current scope down (inherited) and the type checker passes types up (synthesized).

\[\begin{array}{ll} \text{Production} & \text{Semantic rule} \\ E \to E_1 + T & E.\mathit{type} = \mathit{int} \text{ if } E_1.\mathit{type} = T.\mathit{type} = \mathit{int}, \text{ else error} \\ E \to \mathbf{num} & E.\mathit{type} = \mathit{int} \\ E \to \mathbf{id} & E.\mathit{type} = \mathit{lookup}(\mathbf{id}.\mathit{name}, E.\mathit{scope}) \end{array}\]

In these rules, type is synthesized and scope is inherited. A tree-walking pass computes them in one traversal: it passes the scope down as an argument and returns the type as a result.

Organizing semantic analysis into passes

Some rules cannot be checked in a single left-to-right walk. Tern allows a function to call a function defined later in the file, as do Java, Rust and Go, so the analyser first collects all function signatures into the global scope, then checks function bodies; our resolver does this by declaring every function before walking any body. C requires declarations before use, partly because the earliest compilers had to work in a single pass with little memory. Languages with classes, modules and generics need more elaborate ordering: Java resolves class hierarchies before member types, and C++ templates are checked partly at definition and partly at instantiation. Modern compilers are organized as a series of passes over the AST, each adding information: collecting declarations, resolving names, checking types, checking control flow and definite assignment, lowering high-level constructs to simpler ones. Increasingly, as in rustc and Swift, these computations are organized as demand-driven queries with caching, so that an IDE can re-check just what an edit affected.

Reporting semantic errors well

Semantic errors are where users spend most of their debugging time, so their quality matters. A good message names the construct and the rule, gives the position of both the offending use and the relevant declaration (as our resolver does for duplicates), and suggests a fix when one is likely. Misspelled names are common, and compilers such as Clang and rustc suggest the closest declared name using edit distance: our line 9 would earn the hint did you mean total?. Error cascades are a hazard here too: after reporting an undeclared name, the analyser should declare it with an error type that is silently compatible with everything, so that one mistake does not produce a dozen messages about each later use.

Worked examples

Worked problem

Resolving a shadowed name

In fn f(x: int) -> int { var y = x; if y > 0 { var x = y * 2; y = x; } return x; }, which declaration does each x refer to?

Show solution

In var y = x, x is the parameter; no inner x exists yet.
Inside the if block, var x = y * 2 declares a new x that shadows the parameter; y = x then uses the inner x.
After the block ends, its scope is popped, so return x uses the parameter again.

Answer: The first and last uses refer to the parameter; the use in y = x refers to the inner x.

Worked problem

Synthesized and inherited attributes

In checking var z: int = a + 1; which information is inherited and which synthesized?

Show solution

The scope used to look up a is inherited from the enclosing block.
The types of a and 1 are synthesized at the leaves and combined into the type of a + 1.
The declared type int could be passed down to the initializer as an expected type, an inherited attribute, or compared after the initializer's type is synthesized.

Answer: Scope (and possibly the expected type) is inherited; the expression's type is synthesized.

Worked problem

Why two passes?

Tern's main calls helper, which is defined later in the file. What goes wrong with a single-pass analyser, and how is it fixed?

Show solution

A single pass reaches the call in main before helper's declaration, so lookup fails.
A first pass over the top-level declarations enters every function's name and signature into the global scope.
A second pass checks bodies, when all functions are known.

Answer: Collect signatures first, then check bodies; mutually recursive functions then work too.

Common mistakes

MistakeLook names up again in every later phase.
InsteadResolve each name once and link the AST node to its declaration.
MistakeLet an inner declaration's initializer see the new name.
InsteadFollow the language rule; in Tern and Rust, var x = x + 1 reads the outer x.
MistakeStop at the first undeclared name.
InsteadReport it, give the name an error type and continue, avoiding cascades.
MistakeCheck functions in file order when the language allows forward references.
InsteadCollect all signatures in a first pass.
MistakeKeep source positions only in tokens.
InsteadStore positions in AST nodes too, so semantic errors can point at the right place.

Summary and key terms

The AST represents the program's structure with one node type per construct and records source positions.
Tern's parser uses recursive descent for statements and Pratt parsing for expressions.
Semantic analysis checks context-dependent rules: scopes, types, declarations and control flow.
Symbol tables map names to declarations; a stack of scopes implements static scoping and shadowing.
Attribute grammars describe semantic analysis with synthesized and inherited attributes.
Analysis is organized into passes; collecting declarations first permits forward references.
Good semantic diagnostics locate the use and the declaration, suggest fixes and avoid cascades.

Abstract syntax tree: A tree representing a program's essential structure without grammar details.
Semantic analysis: Checking the context-dependent rules of a language and gathering information about the program.
Symbol table: A data structure mapping names to information about their declarations.
Static scoping: Determining the declaration a name refers to from the program text.
Shadowing: An inner declaration hiding an outer one with the same name.
Name resolution: Binding each use of a name to its declaration.
Attribute grammar: A grammar with attributes on symbols and rules for computing them.
Synthesized attribute: An attribute computed from a node's children.
Inherited attribute: An attribute computed from a node's parent or siblings.
Forward reference: A use of a name that appears before its declaration in the source.

Practice problems

Work each problem on paper first, then reveal the answer to check.

What AST node does Tern's parser build for a[i] = 0;?
Show answer
An Assign whose target is an Index node.
Why does the parser parse an expression before deciding a statement is an assignment?
Show answer
Both assignments and call statements begin with an expression.
What happens to the scope of a block when the block ends?
Show answer
It is popped, so its names are no longer visible.
Give an example of a rule that semantic analysis checks but the grammar does not.
Show answer
Any of: names declared before use, type compatibility, argument counts, no duplicate declarations.
In the resolver output, why is sq undeclared on line 9?
Show answer
It was declared inside the loop body, whose scope ended.
Is the type of an expression usually a synthesized or an inherited attribute?
Show answer
Synthesized.
What is an advantage of the single-table, stack-per-name implementation of scopes?
Show answer
Each lookup is a single hash access.
What is an error type used for?
Show answer
To give an erroneous expression a type compatible with everything, avoiding cascading errors.
Which kind of attribute grammar can be evaluated during an LR parse?
Show answer
An S-attributed grammar, using only synthesized attributes.
How could a compiler suggest a fix for an undeclared name?
Show answer
By finding the declared name with the smallest edit distance.