Lesson 3 of 7

Parsing — Tokens to Trees

The parser turns a flat of tokens into a tree that shows structure and order of operations. This tree, the abstract syntax tree (AST), is what most language tools work with.

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.
# 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)))
Python (loads on first run)Ctrl+Enter runs

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 can produce parsers from them — though production mostly hand-write for better messages.

Finished reading?Mark it done to track your progress.

Tip: use the ← and → keys to move between lessons.