Pumping Trees, Real Parsers

Two weeks ago, the table at the end of Notes 06 had one row with "no" in both columns: equal a's, b's, and c's, in that order, like aabbcc or aaabbbccc. Grammars handled matching a's and b's with two tiny rules. This week we prove that no grammar at all, however clever, can do the same for three letters.

First, see why the obvious attempts fail. The grammar S → aSb | ε works because each use of the first rule adds an a on the left and a b on the right at the same moment. Try to add a c the same way: S → aSbc | ε. Each step does add one of each letter, so the counts stay equal. But look where they land: S ⇒ aSbc ⇒ aaSbcbc ⇒ aabcbc. The b's and c's come out mixed together, not in two neat blocks.

The problem is where a variable sits. The S in the middle of a rule is in one spot. Anything a rule adds around it goes in two places: to its left and to its right. Two places that grow together is exactly what "a's then the same number of b's" needs. Three places that grow together is what a's, b's, and c's need, and one spot in the middle only has two sides.

That's an intuition, not a proof. "I tried and couldn't find a grammar" never proves there isn't one. Last time we pumped, in Notes 05, the tool worked for finite machines: any long enough input forces the machine to repeat itself, and the repeated part can be pumped. This week we find the same kind of repetition inside parse trees.

A finite machine repeats a state. A grammar repeats a variable. Either way, a repeat can be pumped.

Every grammar has a fixed list of variables. S → aSb | ε has just one, S. The arithmetic grammar from Notes 06 has three: E, T, and F. That list never grows, no matter how long the strings get.

Every rule also has a fixed length. In S → aSb, the longest right side has three symbols, so a node in the parse tree never has more than three children. That puts a limit on how much a short tree can hold. A tree one level deep has at most 3 leaves. Two levels, at most 9. Three levels, at most 27. So a long enough string can't fit in a short tree. Long strings need tall trees.

Now walk down a tall tree along its longest path, from the top to a leaf. Every node you pass on the way, except the leaf at the end, is a variable. If the path passes more variables than the grammar has, some variable must show up twice. It's the same reason that a long walk through a finite machine must visit some state twice: there are only so many to go around.

Look at the figure. The upper S (ringed) builds aabb. The lower S (ringed) builds ab, in the middle of that. Between the two copies there's a wedge of tree, drawn with thick edges, that adds one a on the left and one b on the right. That wedge is the thing we're going to pump.

Here's the key move. The upper S and the lower S are both S. And in a context-free grammar, any S can be built in any way an S can be built. Where it sits doesn't matter. That's the "context-free" part from Notes 06. So we're allowed to swap one S-subtree for another, and the result is still a correct parse tree.

That gives two things we can do:

• Cut it out. Replace the upper S's subtree with the lower S's subtree. The wedge disappears.
• Copy it in. Replace the lower S's subtree with a fresh copy of the whole upper S subtree. Now there are two wedges stacked up. Do it again, and there are three.

Every one of these is a real parse tree, so every string they spell out is in the language. Let's name the pieces of the string so we can see what happens. Reading left to right, the string splits into five chunks:

• x (indigo) is what the lower S builds.
• v and y (amber) are what the wedge adds, one on each side of x.
• u and z are everything outside the upper S, left and right.

Cutting the wedge out removes v and y together: a · ab · b = aabb. Copying it in once more adds another v and another y together: a · aa · ab · bb · b = aaaabbbb. The two amber pieces always grow or shrink in step, because one wedge holds both of them.

The same tree pumped 0, 1, and 2 times. Thick edges are wedges. Cutting gives aabb, copying gives aaaabbbb, and every one of them is in the language.

Two details need a word. Why are the pieces close together? Because we pick the repeat near the bottom of the tree. Below that point the tree is short, and a short tree can only build a short string. So v, x, and y, which all come from the upper copy, add up to a short stretch. Why can't v and y both be empty? If they were, cutting the wedge out would give a smaller tree for the very same string. So start from the smallest tree for the string, and this can't happen.

Now try it. Pick a grammar and a string. The lab finds the parse tree, lists every repeated variable on a path (the first one listed is the one nearest the bottom), colors the five chunks, and lets you pump with the slider. After every pump it checks the new string separately, by searching for a parse tree from scratch, so you can see that pumping never leaves the language.

Things to try: aaabbb with each of its repeats. A palindrome like abaaba, where v and y are mirror letters. The arithmetic grammar on (a), where the repeat is a variable inside its own parentheses (F inside F, say), so pumping adds parentheses in matching pairs: ((a)), (((a))). Then a+a, where the repeat is E inside E + T. There v is empty and y is "+a", so pumping just adds more "+a" on the end. That's allowed: only one of the two pieces has to be real.

The lemma says something every context-free language must do. To show a language is not context-free, show that it can't do it. The cleanest way to think about this is as a game against an opponent who claims to have a grammar for the language.

1. The opponent names the reach, p. You don't get to choose it. It comes from their grammar.
2. You pick a string in the language that's at least p long. Pick it carefully; this is your one smart move.
3. The opponent cuts it into u, v, x, y, z, following the lemma's rules: v and y not both empty, and v x y at most p long. They can cut anywhere those rules allow.
4. You pump, choosing how many copies. If the pumped string is outside the language, you win.

If you can win no matter how the opponent cuts, their grammar can't exist. Because a real grammar would give a cut that survives every pump.

Playing it for equal a's, b's, and c's

Pick the string with p a's, then p b's, then p c's. For p = 4 that's aaaabbbbcccc. Now think about where the opponent can put the pumped pieces. v, x, and y fit in a window of at most p letters. The block of b's in the middle is p letters long all by itself. So the window can't reach from the a's all the way over to the c's. It can touch the a's, or the a's and b's, or the b's, or the b's and c's, or the c's. It never touches all three letters.

Now pump down: remove v and y. They contain at least one letter, so at least one of the counts goes down. But at least one letter isn't in the window at all, so its count stays at p. The counts are out of step, and the string is out of the language. You win, whatever the cut was.

Pumping up wins too, sometimes in a second way. If v happens to hold both a's and b's, say v = ab, then pumping gives ...aababb..., with an a after a b. The letters are out of order, which also leaves the language.

Play the opponent's side in the lab. Choose the reach, then cut however you like within the rules, and see if any cut survives. When you're convinced, press Try every cut. It checks every legal cut for that reach.

Notice what pump count 1 does: nothing. It's the original string, which is always in the language. The opponent needs a cut that survives every pump count, so you only need one count that breaks. Here, pump count 0 breaks every cut, and so does 2.

A string written twice

Take the language of strings written twice in a row: abab, aa, abbabb, and so on, every string w followed by an exact copy of w. Compare it with palindromes, which are w followed by w backwards. Palindromes have a grammar (Notes 06) and a stack machine (Notes 07). The stack reverses for free: the last letter in is the first one out. A copy needs the opposite, the first letter in coming out first. That's a queue, not a stack, and a stack can't fake it.

The pumping argument confirms it. Pick p a's, p b's, p a's, p b's. Any window of p letters touches at most two neighbouring blocks. Pumping down shrinks one or two blocks and leaves the others alone. Either the length becomes odd, or the two halves no longer match. The details take a few more lines than the a, b, c case, but it's the same game: the pumped pieces are close together, and the language needs changes in places far apart.

This one shows up in real programming languages. "Every variable is declared before it's used" is a copy-like condition: the name in let total has to appear again, letter for letter, in print(total), possibly far away. No grammar can check that. That's why compilers check it in a separate step after parsing, using a table of declared names. The grammar handles the shape of the program; the table handles the names.

One piece, or two pieces in step

The regular lemma pumps one piece, so it can't keep two counts in step. The grammar lemma pumps two pieces together, so it can keep two counts in step, but not three.

Combining languages, carefully

In Notes 04, regular languages were safe to combine every way you liked. Grammars are only partly safe. "Or," "then," and "repeat" still work: to get "A or B," add the rule S → S_A | S_B, where S_A and S_B start the two grammars. But "and" breaks. Here are two languages with easy grammars:

• Same number of a's and b's, then any number of c's: aabbc, abccc. (S → TC, T → aTb | ε, C → cC | ε.)
• Any number of a's, then the same number of b's and c's: aabc, abbcc. (The same idea, mirrored.)

A string in both has a's equal to b's, and b's equal to c's, in order. That's exactly the language we just proved has no grammar. So "and" of two context-free languages can fall out of the family. "Not" breaks too, and here's the chain: Notes 04 gave the family "or." Say "not" stayed in the family as well. Then "A and B" would too, because asking for both is the same as refusing to miss either: "A and B" is exactly "not (not A or not B)" — read it slowly, it's just the two refusals glued by an or. So if "not" were safe, "and" would be safe. We just saw "and" fail — so "not" can't be safe either.

One combination stays safe, and it's handy: a context-free language "and" a regular one is still context-free. Run the stack machine and the finite machine side by side on the same input, the same way the product construction ran two DFAs. There's still only one stack, so it's still a PDA.

The ladder, updated

The last column is next week's teaser. A ten-line Python function checks both of the "no, no, no" languages. So there's a more powerful kind of machine still to come, one that can do what any program can. That's the Turing machine, in Notes 09.

That's the theory. Now the second half of the week: how real parsers, the ones inside Python and your browser, actually read code. The first thing to know is that they don't work on characters. They work on tokens.

Look at total = price * 12. As characters, that's sixteen symbols, including four spaces. As tokens, it's five: the name total, the operator =, the name price, the operator *, the number 12. The spaces are gone, and each word is one unit. The grammar is written in terms of tokens ("an assignment is a name, then =, then an expression"), so it never has to talk about single letters or spaces.

Splitting the characters into tokens is called lexing or tokenizing. And here's the nice part: each kind of token is a regular language. A number is [0-9]+. A name is a letter followed by letters and digits. So the lexer is built from the regular expressions of Notes 04, which means it's a DFA under the hood, fast and simple. Each tool does the job it's good at: patterns for the flat pieces, a grammar for the nesting.

import re

TOKEN_KINDS = [                          # order matters: earlier kinds win
    ("NUM",  r"\d+"),
    ("NAME", r"[A-Za-z_]\w*"),
    ("OP",   r"==|[=+*()]"),                # == before =, so == is one token
    ("SKIP", r"\s+"),
]
LEXER = re.compile("|".join(f"(?P<{kind}>{pattern})" for kind, pattern in TOKEN_KINDS))

def tokenize(text):
    tokens, pos = [], 0
    while pos < len(text):
        m = LEXER.match(text, pos)           # try to match a token right here
        if not m:
            raise SyntaxError(f"unexpected character {text[pos]!r} at position {pos}")
        if m.lastgroup != "SKIP":
            tokens.append((m.lastgroup, m.group()))
        pos = m.end()
    return tokens

print(tokenize("total = price * 12"))
# [('NAME', 'total'), ('OP', '='), ('NAME', 'price'), ('OP', '*'), ('NUM', '12')]

Each token kind becomes a named group, (?P<NUM>\d+), and all of them are joined with "or." m.lastgroup says which kind matched. Keywords like while come out as names; the parser then checks whether a name's text is one of the reserved words.

One rule real lexers follow is longest match: at each point, take the longest token that fits. That's why == is one token and not two, and why while2 is a name and not the keyword while followed by 2. Python's re tries the choices in order rather than looking for the longest, so in the list above, the longer operator is listed first.

Notes 07 ended on a problem. A stack machine for a grammar has to guess which rule to use, and a computer that guesses has to try many worlds or back up when it's wrong. Real parsers avoid that. The most common way is the one you already wrote in Notes 06: recursive descent.

Recursive descent works top-down. It starts at the start variable, the top of the tree, and works down toward the tokens, one function per variable. It's the expand-and-match machine from Notes 07 with two changes. The stack is Python's own call stack: each function call that hasn't returned yet is a variable that hasn't been finished. And instead of guessing a rule, the parser peeks at the next token and lets it decide.

Here's what that looks like for statements in a small language. Each kind of statement starts with a different token, so one peek picks the rule:

def statement(tokens, pos):
    kind, text = tokens[pos]
    if text == "while":                     # statement -> while_loop
        return while_loop(tokens, pos)
    if text == "print":                     # statement -> print_call
        return print_call(tokens, pos)
    if kind == "NAME":                      # statement -> assignment
        return assignment(tokens, pos)
    raise SyntaxError(f"a statement can't start with {text!r}")

(A sketch: the three functions it calls are written the same way, one per rule.) A grammar where one token of lookahead is always enough to choose the rule is called LL(1). The name just says how it reads: Left to right, building the Leftmost derivation, with 1 token of lookahead. In plain words, the condition is: for each variable, its rules must start with different tokens.

Two things that break it

Two rules that start the same way. Suppose a statement can be name = expr or name ( args ), an assignment or a function call. Both start with a name, so one peek can't choose. The fix is to read the name first, then look at the token after it: = means assignment, ( means call. Pull the shared start out, then decide. This is called left factoring.

Left recursion. A rule like E → E + T starts with E itself. The function for E would call itself first thing, before reading anything, and never stop. Notes 06 already met this and fixed it with a loop: an E is a T, then any number of "+ T". The tree's grouping stays the same, left to right.

Operators the practical way

With many operators, one layer per precedence level (E, T, F, and so on) gets long. Real hand-written parsers often use precedence climbing instead, also called a Pratt parser. Give each operator a number, higher for tighter binding. Then one function handles every level:

PREC = {"+": 1, "-": 1, "*": 2, "/": 2}    # higher number = binds tighter

def parse(tokens):
    pos = 0

    def peek():
        return tokens[pos] if pos < len(tokens) else None

    def take():
        nonlocal pos
        pos += 1
        return tokens[pos - 1]

    def atom():                              # a number, or ( expression )
        tok = peek()
        if tok == "(":
            take()
            node = expr(1)
            if peek() != ")":
                raise SyntaxError(f"expected ')' at token {pos}")
            take()
            return node
        if tok is None or not tok.isdigit():
            raise SyntaxError(f"expected a number at token {pos}")
        return int(take())

    def expr(min_prec):                      # only operators at least this tight
        left = atom()
        while peek() in PREC and PREC[peek()] >= min_prec:
            op = take()
            right = expr(PREC[op] + 1)       # +1 makes 8-3-2 group left to right
            left = (op, left, right)
        return left

    tree = expr(1)
    if pos != len(tokens):
        raise SyntaxError(f"unexpected {tokens[pos]!r} at token {pos}")
    return tree

print(parse(["2", "+", "3", "*", "4"]))      # ('+', 2, ('*', 3, 4))
print(parse(["8", "-", "3", "-", "2"]))      # ('-', ('-', 8, 3), 2)

Read expr(min_prec) as "parse an expression, but stop at any operator weaker than min_prec." After the 3 in 2 + 3 * 4, the parser is inside expr(2), working on the right side of the +. The * has strength 2, which is strong enough, so it keeps going and 3 * 4 becomes one piece. In 8 - 3 - 2, the right side of the first - is parsed with expr(2), and the second - (strength 1) is too weak, so the first subtraction finishes first. Adding a new operator is one new entry in PREC.

The other big family of parsers works the opposite way: bottom-up. Instead of starting at the top of the tree and predicting, it starts with the tokens, the leaves, and glues them into bigger and bigger pieces until the whole input is one piece. It keeps the pieces on a stack, and it has just two moves:

A reduce is a rule used backwards. In a derivation, E → E + T replaces E by E + T. Here, E + T on top of the stack gets replaced by E. Every reduce builds one node of the parse tree, with the popped pieces as its children. So the tree grows from the leaves up, which is where the name comes from.

The hard part is deciding when to reduce. Take the E/T/F grammar from Notes 06 and the input a + a * a. After reading a + a, the top of the stack is E + T. That's a complete right side, so should the parser reduce it to E? Not yet! The next token is *, and * binds tighter, so the last a belongs with what comes after it. The parser shifts the * instead. That's the whole trick: the decision depends on what's on top of the stack and the next token, never on a guess. In this grammar the rules of thumb are:

• a on top: it's a finished factor. Reduce F → a.
• T * F on top: a finished product. Reduce T → T * F. Plain F on top: reduce T → F.
• T on top and the next token is *: the product isn't finished. Shift.
• T on top and the next token is anything else: the term is finished. Reduce E → E + T if there's an E + below it, otherwise E → T.
• ( E ) on top: a finished group. Reduce F → ( E ).
• Otherwise, shift the next token.

The stepper below follows exactly these decisions. The stack runs left to right, bottom to top. Each step shows the action and the reason, and the trees underneath are the pieces on the stack: watch small trees get glued into bigger ones until one tree is left.

Try a+a*a and watch the moment the parser shifts * instead of reducing. Then (a+a)*a, where the parentheses force the sum to be finished first. Then a+a+a, where the first sum is reduced before the second + is shifted: that's left-to-right grouping. Then broken inputs, like a+*a or (a+a, and read where the parser stops.

This is a pushdown automaton from Notes 07, running without guessing. It reads left to right, it touches only the top of its stack, and at every step exactly one move fits. Real bottom-up parsers, called LR parsers, keep a little more on the stack than our stepper shows: next to each symbol they store a state number that summarizes everything below it, so the "is there an E + below it?" check is one table lookup. Those tables are big and tedious to build by hand, which is why nobody does. A program builds them.

Parser generators

A parser generator takes a grammar and writes the parser for you. You write rules in a BNF-like notation; it produces the code or tables. Three you'll hear about:

• yacc and bison ("yet another compiler compiler" and its GNU successor) build bottom-up LR tables from your grammar. They are the classic tools: for decades many compilers, including early versions of GCC, were built with them.
• ANTLR builds top-down parsers, in the recursive-descent family, with smarter lookahead than one token. It is widely used for building language tools, and it can write the parser in Java, Python, and several other languages.
• Lark is a Python library. Hand it a grammar as a string and you get a parser object back. By default it uses a general algorithm (Earley) that handles any grammar, even ambiguous ones; it can also build a fast LR parser.

from lark import Lark                      # pip install lark

calc = Lark(r"""
    ?expr: expr "+" term | term
    ?term: term "*" factor | factor
    ?factor: "(" expr ")" | NUMBER
    %import common.NUMBER
    %ignore " "
""", start="expr", parser="lalr")           # the E / T / F grammar, as text

print(calc.parse("2 + 3 * 4").pretty())     # the tree, with 3 * 4 grouped first

The grammar is the one from Notes 06, nearly word for word, left recursion and all, which is fine for an LR parser. (The ? tells Lark to skip tree nodes that have only one child, so the tree isn't full of E-over-T-over-F chains.) The generator does one more useful thing: it checks your grammar. If some point in the grammar would force the parser to guess, an LR generator reports a conflict, such as "shift/reduce conflict." Feed it the ambiguous E → E + E | E * E grammar and it complains right away. A conflict is the generator telling you, at build time, exactly where the guessing machine of Notes 07 would have had to guess.

Languages are designed to be easy to parse

Notes 07 said that languages are deliberately designed so that a parser never has to guess. Now you can see how: keywords like while and def announce what's coming, so one peek picks the rule. Brackets and colons mark where pieces begin and end, like the c in the middle of abcba. Designers check their grammar with a parser generator, and a conflict usually means the language itself is confusing, to people as well as to the parser.

The classic leftover is the dangling else: in if a then if b then x else y, which if does the else belong to? The grammar is ambiguous there. Most languages settle it by a rule, "an else goes with the nearest if," which an LR parser implements simply by choosing shift over reduce at that conflict. Python dodges the question completely: indentation shows which if you mean.

Errors, and carrying on after them

A parser's error message comes from the moment no move fits, just like the stuck PDA in Notes 07. The parser knows what it was expecting and what it found, so it can say "expected ')' but found end of input." It can't always say where you made the mistake, only where it noticed. A missing ) is often noticed many lines later, when something arrives that can't possibly be inside the parentheses. That's why the error line in a traceback is sometimes after the real bug.

A compiler that stops at the first error is annoying, so many parsers try to recover. The simplest way is called panic mode: on an error, skip tokens until one that clearly starts or ends something, like a semicolon or a closing brace, then pretend things are fine and keep going. You get a list of errors instead of one, at the cost of an occasional silly follow-up error caused by the first.

How Python parses Python

Python itself goes through every stage of these notes. First the tokenizer turns your file into tokens. It also handles indentation, using a stack (of course): it keeps a stack of indentation levels, and when a line is indented further it pushes the new level and emits an INDENT token; when a line goes back out, it pops levels and emits a DEDENT for each. So for the parser, indentation looks just like opening and closing brackets.

Then the parser builds a tree. Up to Python 3.8, CPython used an LL(1) parser, the one-token-lookahead kind. Since Python 3.9, it uses a new parser based on a PEG, a parsing expression grammar, and the old parser was removed in 3.10. A PEG looks like a grammar, but its "or" is ordered: try the first choice, and only if it fails, back up and try the next. The first choice that works wins, so a PEG can never be ambiguous; the order of the choices settles everything. Backing up can be slow, so the parser remembers some results it has already worked out, so it never has to redo them (the idea behind packrat parsing). The change made it easier to add new syntax, such as the match statement of Python 3.10. You can see the tree Python builds with the ast module:

import ast
print(ast.dump(ast.parse("2 + 3 * 4", mode="eval")))
# Expression(body=BinOp(left=Constant(value=2), op=Add(),
#            right=BinOp(left=Constant(value=3), op=Mult(), right=Constant(value=4))))

(The output is one long line; it's wrapped here.) That's the same tree your Notes 06 parser built, ('+', 2, ('*', 3, 4)), with longer names.

Suppose you wanted to push your invented language the way a professional would. Here's the drill, using everything from Notes 06–08:

And if you want to test a pumping hunch with code instead of on paper: this brute force tries every legal cut of the a, b, c string for small reaches, and confirms that pumping 0 or 2 times always breaks it. It isn't a proof (a proof covers every p), but if it finds a cut that survives, your hunch has a hole.

def in_abc(s):
    n = len(s) // 3
    return s == "a" * n + "b" * n + "c" * n

def every_cut_breaks(p):
    s = "a" * p + "b" * p + "c" * p
    for start in range(len(s)):
        for lv in range(p + 1):
            for lx in range(p + 1 - lv):
                for ly in range(p + 1 - lv - lx):
                    if lv + ly == 0 or start + lv + lx + ly > len(s):
                        continue                 # not a legal cut
                    u = s[:start]
                    v = s[start:start + lv]
                    x = s[start + lv:start + lv + lx]
                    y = s[start + lv + lx:start + lv + lx + ly]
                    z = s[start + lv + lx + ly:]
                    if all(in_abc(u + v * i + x + y * i + z) for i in (0, 2)):
                        return False             # this cut survives
    return True

print(all(every_cut_breaks(p) for p in range(1, 7)))   # True

Six questions. Answer before you click. Being wrong here costs nothing and teaches you something.

This week closes the grammar part of the course. You've seen what grammars can build, the machine that checks them, the strings they can't reach, and how real parsers put them to work. Next week we climb the last rung of the ladder.

Coming up

Sessions 16 and 17 (Oct 27, 29): Notes 09. Turing machines. Take away the stack's one rule, "only touch the top," and give the machine a tape it can read, write, and move along in both directions. That small change is enough to check equal a's, b's, and c's, strings written twice, and, as it turns out, anything any computer can do. The Project 3 specification is released that week.

If any part of this week didn't land, email me at yair.chaya@liu.edu or ask for an office-hours slot. I reply within 24 hours.