Syntax: grammars, parsing and abstract syntax

Before a language implementation can do anything with a program, it must recognize which strings are programs at all and recover their structure. That is the job of syntax. This lesson covers the two levels at which syntax is described, lexical structure (the words) and phrase structure (the sentences), the notations used to write grammars, the danger of ambiguity, and the technique of recursive-descent parsing, which turns a grammar directly into code. We finish with abstract syntax trees, the data structure every later lesson builds on.

CMPUT-415 studies parsing algorithms in depth, including the LR parser generators used in industrial compilers, and CMPUT-474 proves what grammars can and cannot describe. Our aim is narrower and practical: to read and write grammars confidently and to build a correct hand-written parser for a small language, which is how the front ends of GCC, Clang, Go and Rust are actually written today.

Two levels: tokens and phrases

Lexical analysis, or scanning, breaks a stream of characters into tokens such as identifiers, numbers, keywords, operators and punctuation, discarding white space and comments. Each token kind is usually described by a regular expression: an identifier is a letter or underscore followed by letters, digits or underscores; an integer is one or more digits. Regular expressions are enough for tokens because tokens do not nest. Phrase structure, by contrast, does nest: parentheses inside parentheses, blocks inside blocks. Nesting needs a more powerful notation, the context-free grammar.

# A tokenizer (lexer) built from regular expressions, one pattern per token kind.
import re
TOKEN_SPEC = [
    ("NUM",   r"\d+(?:\.\d+)?"),
    ("ID",    r"[A-Za-z_]\w*"),
    ("OP",    r"[-+*/^()=]"),
    ("SKIP",  r"[ \t]+"),
    ("ERROR", r"."),
]
MASTER = re.compile("|".join(f"(?P<{k}>{p})" for k, p in TOKEN_SPEC))

def tokens(src):
    for m in MASTER.finditer(src):
        kind, text = m.lastgroup, m.group()
        if kind == "SKIP":
            continue
        if kind == "ERROR":
            raise SyntaxError(f"unexpected character {text!r} at column {m.start() + 1}")
        yield kind, text

print(list(tokens("rate = 2.5 * (hours + 40)")))
try:
    list(tokens("x = 3 # 4"))
except SyntaxError as e:
    print("lexical error:", e)

[('ID', 'rate'), ('OP', '='), ('NUM', '2.5'), ('OP', '*'), ('OP', '('), ('ID', 'hours'), ('OP', '+'), ('NUM', '40'), ('OP', ')')]
lexical error: unexpected character '#' at column 7

Two rules settle most tokenizing questions. The longest-match rule says the scanner takes the longest prefix that forms a token, so 'counter' is one identifier rather than 'count' followed by 'er', and '>=' is one operator rather than '>' then '='. The priority rule says that when two patterns match the same longest prefix, the earlier one wins, which is how keywords such as 'if' beat the identifier pattern. Some languages complicate scanning: Python's indentation is turned into INDENT and DEDENT tokens by keeping a stack of indentation levels, and C++ templates once made '>>' ambiguous between a shift operator and two closing angle brackets.

Context-free grammars and BNF

A context-free grammar has four parts: a set of terminal symbols (the tokens), a set of nonterminal symbols (syntactic categories such as expression or statement), a start symbol, and a set of productions, each of which says that a nonterminal can be replaced by a sequence of terminals and nonterminals. John Backus and Peter Naur used this notation to define ALGOL 60, and it has been called Backus–Naur form, or BNF, ever since. Here is a small grammar for arithmetic expressions in BNF:

E ::= E + T | T, T ::= T * F | F, F ::= ( E ) | n. Each line reads 'an E is either an E followed by + and a T, or just a T'. The vertical bar separates alternatives. Terminals here are +, *, (, ) and n (a number token); E, T and F are nonterminals standing for expression, term and factor.

Extended BNF, or EBNF, adds conveniences: braces { } for zero or more repetitions, square brackets [ ] for an optional part, and parentheses for grouping. With EBNF the same grammar becomes E ::= T { + T } and T ::= F { * F }. The ISO standardized one EBNF variant in 1996, but in practice every language reference uses its own dialect. Python's reference manual, for example, uses a PEG-style notation since Python 3.9 switched to a parsing expression grammar parser.

Derivations and parse trees

A grammar generates strings by derivation: start from the start symbol and repeatedly replace a nonterminal with the right-hand side of one of its productions until only terminals remain. A leftmost derivation always replaces the leftmost nonterminal. The sequence of replacements can be drawn as a parse tree, whose root is the start symbol, whose interior nodes are nonterminals and whose leaves, read left to right, spell out the string.

# A leftmost derivation printed step by step for the grammar
#   E ::= E + T | T     T ::= T * F | F     F ::= ( E ) | n
# We record which rule we expand at each step to derive  n + n * n.
steps = [
    ("E",          "E -> E + T"),
    ("E + T",      "E -> T"),
    ("T + T",      "T -> F"),
    ("F + T",      "F -> n"),
    ("n + T",      "T -> T * F"),
    ("n + T * F",  "T -> F"),
    ("n + F * F",  "F -> n"),
    ("n + n * F",  "F -> n"),
    ("n + n * n",  "done"),
]
for i, (form, rule) in enumerate(steps):
    print(f"{i}: {form:12}  ({rule})")

0: E             (E -> E + T)
1: E + T         (E -> T)
2: T + T         (T -> F)
3: F + T         (F -> n)
4: n + T         (T -> T * F)
5: n + T * F     (T -> F)
6: n + F * F     (F -> n)
7: n + n * F     (F -> n)
8: n + n * n     (done)

The derivation and the tree show that * binds more tightly than +: the multiplication sits lower in the tree, so it is computed first. That shape is not an accident of how we happened to derive the string; this grammar allows only one parse tree for n + n * n, because multiplication can only appear inside a T. Writing a grammar so that its trees always reflect the intended precedence is one of the main skills of language design.

Ambiguity

A grammar is ambiguous if some string has two or more different parse trees. Ambiguity is a serious problem, because different trees usually mean different things. The grammar E ::= E - E | n is ambiguous: 10 - 4 - 3 can be read as (10 - 4) - 3 = 3 or as 10 - (4 - 3) = 9. As the program below shows, the number of trees grows quickly with the length of the expression; it follows the Catalan numbers, so a chain of six subtractions already has 132 readings.

# How many parse trees does an ambiguous grammar give?
# Grammar:  E ::= E "-" E | NUM      (no precedence, no associativity)
# Count the trees for a chain of n subtractions by brute force.
from functools import lru_cache

def trees(tokens):
    """Return every parse tree (as a nested tuple) for a token list under E ::= E - E | NUM."""
    if len(tokens) == 1:
        return [tokens[0]]
    result = []
    for i, t in enumerate(tokens):
        if t == "-":
            for left in trees(tokens[:i]):
                for right in trees(tokens[i + 1:]):
                    result.append(("-", left, right))
    return result

def ev(t):
    return t if isinstance(t, int) else ev(t[1]) - ev(t[2])

expr = [10, "-", 4, "-", 3]
for t in trees(expr):
    print(t, "=", ev(t))

for n in range(1, 7):
    toks = [1] + ["-", 1] * n
    print(f"{n} minus signs: {len(trees(toks))} parse trees")

('-', 10, ('-', 4, 3)) = 9
('-', ('-', 10, 4), 3) = 3
1 minus signs: 1 parse trees
2 minus signs: 2 parse trees
3 minus signs: 5 parse trees
4 minus signs: 14 parse trees
5 minus signs: 42 parse trees
6 minus signs: 132 parse trees

There are two ways to remove ambiguity. The first is to rewrite the grammar so that only one tree is possible, by layering nonterminals for each precedence level and choosing left or right recursion for associativity, as in the E, T, F grammar. Left recursion (E ::= E + T) makes an operator left-associative, so 10 - 4 - 3 means (10 - 4) - 3. Right recursion (F ::= P ^ F) makes it right-associative, which is the convention for exponentiation, so 2 ^ 3 ^ 2 means 2 ^ 9. The second way is to keep a simple ambiguous grammar and add separate precedence and associativity declarations, as parser generators such as Bison allow.

The most famous ambiguity in real languages is the dangling else. In C, Java and many others, if (a) if (b) s1; else s2; could attach the else to either if. Every such language resolves it with an extra rule that the else belongs to the nearest unmatched if, and programmers are encouraged to use braces. Python avoids the problem with indentation, and languages such as Ada and Rust avoid it by requiring an explicit end or braces for every if.

Recursive-descent parsing

A recursive-descent parser has one function for each nonterminal. Each function looks at the next token to decide which alternative to use, calls the functions for the nonterminals on that alternative's right-hand side, and consumes terminals as it matches them. The EBNF form of a grammar maps to code almost line by line: a repetition { ... } becomes a while loop and an optional [ ... ] becomes an if.

One rule needs care. A left-recursive production such as E ::= E + T cannot be coded directly, because the function for E would call itself first without consuming anything and loop forever. The standard fix is to rewrite left recursion as repetition, E ::= T { + T }, and build the tree from left to right inside the loop, which preserves left associativity. Right-recursive productions such as exponentiation can be coded directly as recursion on the right operand.

# A recursive-descent parser for arithmetic with the usual precedence and associativity.
# Grammar (EBNF):
#   expr   ::= term   { ("+" | "-") term }        left-associative
#   term   ::= factor { ("*" | "/") factor }      left-associative
#   factor ::= unary [ "^" factor ]               right-associative
#   unary  ::= "-" unary | atom
#   atom   ::= NUM | ID | "(" expr ")"
import re
TOK = re.compile(r"\s*(?:(\d+)|([A-Za-z_]\w*)|(.))")

class Parser:
    def __init__(self, src):
        self.toks = []
        for num, name, op in TOK.findall(src):
            if num: self.toks.append(("num", int(num)))
            elif name: self.toks.append(("id", name))
            elif op.strip(): self.toks.append(("op", op))
        self.toks.append(("eof", None)); self.i = 0
    def peek(self): return self.toks[self.i]
    def take(self, val=None):
        tok = self.toks[self.i]
        if val is not None and tok[1] != val:
            raise SyntaxError(f"expected {val!r} but found {tok[1]!r} at token {self.i}")
        self.i += 1; return tok
    def expr(self):
        node = self.term()
        while self.peek()[1] in ("+", "-"):
            op = self.take()[1]; node = (op, node, self.term())
        return node
    def term(self):
        node = self.factor()
        while self.peek()[1] in ("*", "/"):
            op = self.take()[1]; node = (op, node, self.factor())
        return node
    def factor(self):
        base = self.unary()
        if self.peek()[1] == "^":
            self.take(); return ("^", base, self.factor())   # recursion on the right
        return base
    def unary(self):
        if self.peek()[1] == "-":
            self.take(); return ("neg", self.unary())
        return self.atom()
    def atom(self):
        kind, val = self.take()
        if kind in ("num", "id"): return val
        if val == "(":
            node = self.expr(); self.take(")"); return node
        raise SyntaxError(f"unexpected {val!r}")

def parse(src):
    p = Parser(src); tree = p.expr(); p.take(None) if p.peek()[0] == "eof" else p.take("<end>")
    return tree

for s in ["1 + 2 * 3", "10 - 4 - 3", "2 ^ 3 ^ 2", "-(a + b) * c"]:
    print(f"{s:14} -> {parse(s)}")
try:
    parse("2 * (3 + 4")
except SyntaxError as e:
    print("syntax error:", e)

1 + 2 * 3      -> ('+', 1, ('*', 2, 3))
10 - 4 - 3     -> ('-', ('-', 10, 4), 3)
2 ^ 3 ^ 2      -> ('^', 2, ('^', 3, 2))
-(a + b) * c   -> ('*', ('neg', ('+', 'a', 'b')), 'c')
syntax error: expected ')' but found None at token 6

Look at how each case in the output matches the table above. 1 + 2 * 3 parses as ('+', 1, ('*', 2, 3)), so multiplication happens first. 10 - 4 - 3 parses with the left subtraction nested inside, giving left associativity. 2 ^ 3 ^ 2 nests on the right. The parser also reports a useful error for the unclosed parenthesis, naming what it expected and where. Good error messages are much easier to produce in a hand-written parser than with a generated one, which is one reason so many production compilers use recursive descent.

A related technique, Pratt parsing or precedence climbing, handles many precedence levels with a single loop driven by a table of binding powers instead of one function per level. It is popular for expression-heavy languages and is used in the parsers of several JavaScript tools and in many tutorials on writing interpreters. Parser generators such as Yacc, Bison and ANTLR, and parsing expression grammar tools, take a grammar file and produce a parser automatically; tree-sitter, used by many code editors, generates incremental parsers that can re-parse a file as you type. CMPUT-415 compares these approaches in detail.

Abstract syntax

A parse tree contains everything about how the string was derived, including nodes for every precedence level and for parentheses. Later stages do not need that detail. An abstract syntax tree (AST) keeps only what matters for meaning: operators with their operands, statements with their parts, declarations with their names and types. Parentheses disappear because the tree shape already records grouping. Two different concrete programs, such as (a + b) and a+b, have the same abstract syntax.

# Once we have an abstract syntax tree, evaluation is a short recursive function.
def ev(t, env):
    if isinstance(t, int): return t
    if isinstance(t, str): return env[t]
    op = t[0]
    if op == "neg": return -ev(t[1], env)
    a, b = ev(t[1], env), ev(t[2], env)
    return {"+": a + b, "-": a - b, "*": a * b, "/": a / b, "^": a ** b}[op]

tree = ("*", ("neg", ("+", "a", "b")), "c")      # -(a + b) * c
print(ev(tree, {"a": 2, "b": 3, "c": 4}))
print(ev(("^", 2, ("^", 3, 2)), {}))              # 2 ^ (3 ^ 2) = 2 ^ 9
print(ev(("-", ("-", 10, 4), 3), {}))             # (10 - 4) - 3

-20
512
3

Every interpreter, type checker and compiler in the rest of this course works on abstract syntax, not on text. In Python you can see the real thing: the ast module exposes the trees CPython builds, and tools such as linters, formatters and refactoring tools work by reading and transforming them. Lesson 9 returns to this when we use Python's ast module for metaprogramming.

# Python's own parser produces an abstract syntax tree we can inspect.
import ast
tree = ast.parse("total = price * (1 + rate)", mode="exec")
print(ast.dump(tree.body[0], indent=2))

Assign(
  targets=[
    Name(id='total', ctx=Store())],
  value=BinOp(
    left=Name(id='price', ctx=Load()),
    op=Mult(),
    right=BinOp(
      left=Constant(value=1),
      op=Add(),
      right=Name(id='rate', ctx=Load()))))

Worked examples