Rules That Build Strings

Last week ended with a wall. Some languages have no DFA, no NFA, and no pattern. The standard example is "some a's followed by the same number of b's." A finite machine has a fixed amount of memory, and counting with no upper limit needs more memory than any fixed amount. This week we step over the wall.

That example looks artificial, but it is everywhere in disguise. Replace a with an opening parenthesis and b with a closing one, and "same number, in the right order" becomes balanced parentheses. Every programming language has them: parentheses in expressions, braces around blocks, tags in HTML, brackets in JSON. The key feature is nesting. Things open and close inside other things, as deep as you like. No finite machine can check nesting of unlimited depth, so no regular expression can either. That is why you can't validate HTML with a regex, no matter how long the regex gets.

So we need a more powerful way to describe languages. Machines describe a language by checking strings. This week's new tool describes a language by building strings, using rules that say how a big piece is made out of smaller pieces. Because a piece can contain a smaller piece of the same kind, nesting comes for free.

A machine reads a string and says yes or no. A grammar starts from nothing and builds every string in the language.

Here is a complete grammar for "some a's followed by the same number of b's":

Read each rule as "you may replace the thing on the left with the thing on the right." S is a placeholder, a piece that isn't finished yet. Start with S. The first rule says: replace S with a, then a smaller S, then b. The second rule says: replace S with nothing (ε, the empty string), which finishes it. Keep replacing until no placeholders are left. What remains is a string in the language.

Build aabb, for example: S becomes aSb, which becomes aaSbb, which becomes aabb. Each use of the first rule adds one a on the left and one b on the right at the same moment. The two sides can't get out of step, so the counts always match. The grammar doesn't count at all; it builds in matching pairs. That is the whole trick.

Rules for the same variable are often written on one line, separated by a bar meaning "or." So the grammar above is usually written S → aSb | ε. The bar plays the same role as "or" in a pattern.

Why is it called "context-free"? Because a rule for S can be used on any S, wherever it appears. What sits to its left or right doesn't matter. That one restriction keeps grammars simple enough to work with, and simple enough to turn into parsers. Later in the course you'll meet systems without it, and they turn out to be as powerful as any computer.

Two more grammars to read

Balanced parentheses: S → (S)S | ε. A balanced string is either empty, or an opening parenthesis, a balanced string inside, the matching close, and then another balanced string after it. Read the rule as a sentence and it says exactly that.

Palindromes over {a, b}: S → aSa | bSb | a | b | ε. Build from the outside in: wrap the middle in a matching pair of letters, and end with a single middle letter or nothing. Every palindrome is made this way, and nothing else is.

The sequence of replacements that produces a string is called a derivation. We write the steps with a double arrow:

When there are several variables in the middle of a build, you could replace any of them next. To keep things tidy, we usually agree to always replace the leftmost variable first. That is a leftmost derivation. It doesn't change which strings you can build. It just means two people building the same string the same way will write down the same steps.

The best way to get a feel for derivations is to do some. In the lab, the highlighted variable is the leftmost one, and the buttons are the rules you can apply to it. Try to build a chosen target: ()(()) with the parentheses grammar, or abba with the palindrome grammar. If you get stuck, Undo is free.

A derivation is a list of steps. A parse tree shows the same build as a picture. The start variable is at the top. Each time a rule replaces a variable, that variable gets children: the symbols the rule put in its place, in order. Terminals are leaves, and reading the leaves left to right spells out the string.

The tree shows something a flat string can't: which parts belong together. In the tree for aabb, the outer a and the last b hang from the same S, so they are a matched pair. The inner pair hangs from the S below. That grouping is the structure of the string, and it is exactly what a compiler needs. When Python reads 2 + 3 * 4, it doesn't care about the characters as such. It cares that 3 * 4 is a group that gets added to 2. The parse tree is that grouping, written down.

One more useful fact: the order you replace variables in changes the derivation but not the tree. A leftmost derivation and a rightmost derivation of the same build give the same tree. So the tree is the honest record of how a string was built. The list of steps is just one way of reading it out.

Here is a natural first try at a grammar for arithmetic, with a standing in for any number:

It builds exactly the right strings. But try a+a*a in the parse lab below and you'll find two different trees. In one, the a*a part is grouped first and then added: that's the usual meaning. In the other, a+a is grouped first and then multiplied. If the a's were 2, 3, and 4, the first tree means 2 + 12 = 14 and the second means 5 × 4 = 20. Same string, two meanings.

For a programming language, ambiguity is a bug. The compiler has to pick one meaning, and if the grammar doesn't say which, two compilers might pick differently. The usual fix is to rewrite the grammar in layers, one per level of grouping:

Now a plus sign can only join whole terms, and a term is a product. So in a+a*a, the multiplication is forced to group first. There's exactly one tree, and it's the right one. The layering also settles the other question, a+a+a: the rule E → E + T puts the leftmost addition deepest, so it groups as (a+a)+a, left to right, the way arithmetic is normally read. This E/T/F pattern appears in nearly every real language grammar. If the language you invent for Project 2 has operations with different strengths, it's the fix you'll reach for.

Try these in the lab: a+a*a and a+a+a in both arithmetic grammars; then (a+a)*a, where the parentheses remove the ambiguity even in the first grammar. Then try the parentheses grammar on ()() and the palindrome grammar on abba. They give one tree each, so those grammars are not ambiguous (at least for those strings).

Grammars aren't just a classroom tool. They are how real languages are officially defined. Python's documentation includes the full grammar of Python. The JSON standard is a page of grammar rules. Programmers usually write them in a notation called BNF (Backus–Naur Form), which is the same idea with longer names:

value   ::= object | array | string | number | "true" | "false" | "null"
object  ::= "{" "}" | "{" members "}"
members ::= pair | pair "," members
pair    ::= string ":" value
array   ::= "[" "]" | "[" elements "]"
elements ::= value | value "," elements

That is most of JSON. Notice the nesting: a value can be an object, which contains pairs, which contain values, which can be objects again. That loop back to "value" is exactly what no regular expression can express, and exactly what a grammar handles easily.

How do the new grammars relate to the regular languages from Weeks 2–5? Every regular language has a grammar. Take any DFA. Make a variable for each state. For each arrow "from state P on symbol x to state Q," add the rule P → x Q. For each accepting state, add P → ε. Each derivation then walks the machine step by step. So grammars can do everything machines could, plus nesting. The ladder of models has a new, higher rung.

The last row is a teaser. Grammars build in matching pairs, but they can't keep three counts in step. Week 8's pumping lemma for grammars proves it.

A grammar fits in a dictionary: each variable maps to a list of its rules, and each rule is a list of symbols. Anything that is a key in the dictionary is a variable; anything else is a terminal. An empty list is the ε rule.

PARENS = {
    "S": [["(", "S", ")", "S"], []],         # S -> (S)S | ε
}

ARITH = {                                    # the layered grammar from §05
    "E": [["E", "+", "T"], ["T"]],
    "T": [["T", "*", "F"], ["F"]],
    "F": [["(", "E", ")"], ["a"]],
}

The first tool generates the language: list every string the grammar can build, up to some length. It explores leftmost derivations breadth-first, the same way you clicked through the lab, and throws away any partial build that already has too many terminals, since terminals never disappear.

from collections import deque

def generate(grammar, start, max_len):
    """Every string the grammar builds, up to max_len, shortest first."""
    found, seen = set(), set()
    queue = deque([(start,)])
    while queue:
        form = queue.popleft()
        if form in seen:
            continue
        seen.add(form)
        if sum(1 for s in form if s not in grammar) > max_len:
            continue                         # already too long
        spots = [i for i, s in enumerate(form) if s in grammar]
        if not spots:
            found.add("".join(form))         # no variables left: a real string
            continue
        i = spots[0]                         # leftmost variable
        for rule in grammar[form[i]]:
            queue.append(form[:i] + tuple(rule) + form[i + 1:])
    return sorted(found, key=lambda w: (len(w), w))

print(generate(PARENS, "S", 4))   # ['', '()', '(())', '()()']

This works well for small grammars like the ones in these notes. The "too long" check only limits terminals, so a grammar that can pile up variables forever without adding terminals would keep it busy. Keep that in mind when you test your own grammars.

The second tool goes the other way: given a string, find its structure. That is a parser. The simplest kind to write by hand is a recursive-descent parser: one function per variable, each one reading its own part of the input. Here it is for the layered grammar, with digits in place of a. One adjustment: a rule like E → E + T would make expr() call itself forever before reading anything, so the "repeat" parts are written as loops instead. The grouping stays the same.

def parse_expr(s):
    """Recursive-descent parser for the E / T / F grammar. Returns a tree."""
    pos = 0

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

    def eat(ch):
        nonlocal pos
        if peek() != ch:
            raise SyntaxError(f"expected {ch!r} at position {pos}")
        pos += 1

    def expr():                              # E: terms joined by +
        node = term()
        while peek() == "+":
            eat("+")
            node = ("+", node, term())
        return node

    def term():                              # T: factors joined by *
        node = factor()
        while peek() == "*":
            eat("*")
            node = ("*", node, factor())
        return node

    def factor():                            # F: ( E ) or a digit
        if peek() == "(":
            eat("(")
            node = expr()
            eat(")")
            return node
        ch = peek()
        if ch is None or not ch.isdigit():
            raise SyntaxError(f"expected a digit at position {pos}")
        eat(ch)
        return int(ch)

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

print(parse_expr("2+3*4"))     # ('+', 2, ('*', 3, 4))   — 3*4 grouped first
print(parse_expr("(2+3)*4"))   # ('*', ('+', 2, 3), 4)

Look at how closely the code follows the grammar. Each variable is a function, each layer calls the layer below, and the parentheses rule calls back up to expr(), which is where the nesting comes from. Getting the answer is one short function away: walk the tree, adding at "+" nodes and multiplying at "*" nodes. That is a tiny interpreter — the seed of every real compiler.

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

Project 1 is behind you and Project 2 starts now. This week is about getting comfortable writing grammars and reading their trees. Everything in Project 2 builds on that.

Coming up

Sessions 12 and 13 (Oct 13, 15): Notes 07. Pushdown automata: a finite automaton plus a stack. We'll see how one stack is just enough memory to check nesting, and why these machines recognize exactly the languages grammars describe. Project 2 continues.

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.