CcCompilers · Lesson 3 of 7

Parsing — Tokens to Trees

Flat token lists become a tree that captures structure: what belongs to what, what happens first. The AST — abstract syntax tree — is the data structure every language tool lives on.

Text
3 * (cost + 12)   parses to:

        (*)
       /   \
     (3)   (+)
          /   \
      (cost)  (12)

The tree IS the precedence: to evaluate (*) you need
(+) first. '3 * cost + 12' builds a different tree —
(+) on top — same tokens, different meaning.
Parentheses exist only to shape the tree; the tree
itself has no parentheses.
Python
# Recursive descent — the technique real compilers use
# (Clang, V8, TypeScript are all hand-written this way).
# One function per grammar rule; precedence via layering:

def parse_expr(toks):        # expr := term (('+'|'-') term)*
    node = parse_term(toks)
    while toks and toks[0] == ("OP", "+"):
        toks.pop(0)
        node = ("add", node, parse_term(toks))
    return node

def parse_term(toks):        # term := factor (('*') factor)*
    node = parse_factor(toks)
    while toks and toks[0] == ("OP", "*"):
        toks.pop(0)
        node = ("mul", node, parse_factor(toks))
    return node

def parse_factor(toks):      # factor := NUMBER | '(' expr ')'
    kind, val = toks.pop(0)
    if kind == "NUMBER":
        return ("num", val)
    if (kind, val) == ("OP", "("):
        node = parse_expr(toks)
        toks.pop(0)          # the ')'
        return node
    raise SyntaxError(f"unexpected {val}")

print(parse_expr(lex("3 * (4 + 12)")))
# ('mul', ('num', 3), ('add', ('num', 4), ('num', 12)))

Notice the layering does the precedence: parse_expr calls parse_term which calls parse_factor, so * binds tighter than + automatically. Grammars are written down formally (BNF notation), and parser generators can produce parsers from them — though production compilers mostly hand-write for better error messages.

◆ Note
Once you have an AST, an interpreter is trivial: walk the tree, evaluating children before parents. def eval(n): return n[1] if n[0]=='num' else eval(n[1]) + eval(n[2]) if n[0]=='add' else eval(n[1]) * eval(n[2]). Congratulations — lexer, parser, evaluator is a complete language implementation, and you've now seen all three.