The field linguist

The museum of languages ended with the line 2 + 3 * (4 - 1). Python sees the number eleven in it, not a scatter of digits, signs and parentheses. For a single formula we already know how to do this: Dijkstra’s shunting yard from Chapter 15 reorders the operators by a table of precedence. But the yard has no idea what to do with an if inside a for inside a def, or with a list inside a call inside an index. We need a way to describe how any language is built, and then to take apart any text in it by that description. The method came to programming from linguistics, so we will learn it the way linguists do.

A field linguist arrives among the speakers of a language that has neither a dictionary nor a textbook, writes down phrases, tries out new ones and asks: can you say that? The speakers can’t explain the rules. They only feel that ka lo ka sounds fine and lo ka sounds wrong. From such answers the linguist recovers rules that nobody ever dictated. The island and its language in this chapter are invented, but the work is not: every program that reads another program does the same.

Day one: yes and no

The islanders speak in short phrases. Here are the first entries from the diary: in the left column, what the informant agreed people say; in the right, what made him wince.

The pattern jumps out: ka repeats, and two neighboring kas must have a lo between them. Stated as a rule: a phrase is either ka, or ka followed by lo and another phrase. In short:

The arrow reads “can be,” the vertical bar “or.” S is the name of the thing we are describing, a phrase (S for “sentence”). A description like this is a grammar: a set of rules that builds all the correct phrases of a language, and only those. The words of the language itself, ka and lo, are called terminals: there is nothing left to break them into. Names of parts, like S, are nonterminals: the rules say what they can be replaced with.

The rule refers to itself. Like a recursive function from Chapter 9, it describes infinitely many phrases with a finite text: the island’s language has phrases with a hundred kas, though nobody has ever said one. Test the grammar against the diary. In the field journal below, you write the grammar, and the journal checks it against every mark the informant made.

Day two: parentheses

On the second day two more words turned up, nu and ti, and always as a pair: nu ka ti, nu nu ka ti ti, ka lo nu ka lo ka ti. Yet the informant rejected nu ka without its ti, and nu ka ti ti as well. Any phrase from day one can stand inside a nu … ti pair, and the pair itself behaves like a single ka: a lo can come before it or after it.

So a phrase has parts. Call the thing that stands between the los a T: it is either ka, or nu, a whole phrase and ti. The grammar of day two:

Now the rules refer to each other in a circle: S goes through T, and T through S. Time to confess what this language is. Ka is a number, lo is plus, nu and ti are the opening and closing parentheses. Ka lo nu ka lo ka ti is 1 + (2 + 3). You have recovered the grammar of arithmetic expressions with addition and parentheses, which every programming language understands. Programmers, as it happens, learned to write such rules down not on an island but in Paris.

Paris, 1959–1960: how to write the rules down

Here, down to the details, is how the ALGOL 60 report defines an unsigned integer:

An unsigned integer is a digit, or an unsigned integer followed by one more digit: the same recursion as in our S. Rules written this way are called Backus–Naur form, or BNF. Every rule has a single nonterminal on its left side, and that nonterminal can be replaced no matter what surrounds it. Grammars with this property are called context-free, and the syntax of almost every programming language is described by them. The description of Python’s grammar that sits in its source code is BNF too, only extended with repetition and optional parts.

Derivations and trees

This is how a grammar checks a phrase. Begin with the start nonterminal S and replace some nonterminal with one of its right-hand sides, again and again, until only words are left. If what you get is our phrase, the phrase is correct. Here is how the grammar of day two arrives at ka lo nu ka ti, replacing the leftmost nonterminal at every step:

$$S \Rightarrow T\ \text{lo}\ S \Rightarrow \text{ka lo}\ S \Rightarrow \text{ka lo}\ T \Rightarrow \text{ka lo nu}\ S\ \text{ti} \Rightarrow \text{ka lo nu}\ T\ \text{ti} \Rightarrow \text{ka lo nu ka ti}$$

A chain of replacements like this is called a derivation. The chain itself is long and awkward, but if you draw what replaced what, you get a tree: S at the root, its three children T, lo, S under it, and so on down to the words in the leaves. This is the parse tree. Read from left to right, its leaves give the phrase, and its inner nodes show how the phrase is built: what is grouped with what. Tap any phrase in the journal above and you will see both the derivation and the tree. The tree is what a program needs. The expression tree from Chapter 17, whose outline we traced with a dot, is a parse tree with the extra parts thrown away.

A grammar also works in the other direction. Pick a rule at random at every step, and it will generate correct phrases that nobody has said yet. That is why linguists call such grammars generative. Let the grammar of day two make up some phrases, and we will translate them into arithmetic.

Every phrase is a correct expression: eval computed them all. Test generators for compilers work this way: from the grammar of a language they generate thousands of random programs and check that the compiler copes with each. The depth limit keeps the generator from sliding into endlessly nested parentheses. The recursion without a base case from Chapter 9 lies in wait here too.

How much memory a language needs

In 1956, three years before Backus’s talk, the MIT linguist Noam Chomsky published a paper called Three Models for the Description of Language in a journal on information theory. He compared the devices that might describe English: a machine with a finite number of states, a grammar of rules of the form “part → parts,” and a stronger, transformational grammar. Chomsky argued that the first model falls short of human language. Out of this work grew a classification of grammars now known as the Chomsky hierarchy.

You have already felt the difference between the first two rows. To check the phrases of day one, you need to remember only one thing: whether the last word was ka or lo. That is a finite automaton from Chapter 31 with two states, and it needs no other memory. To check the parentheses of day two, though, you have to remember how many nus are open, and there can be any number of them. A finite automaton with, say, a hundred states will lose count on a phrase with a hundred and one nus. You need a stack, as in the bracket check of Chapter 15. The rigorous proof that a finite automaton cannot check parentheses comes in Chapter 54.

Whether Backus had read Chomsky, even Backus himself could not say for sure. In one of his recollections, the notation grew out of the “productions” of the logician Emil Post, rules for rewriting strings. In a 2006 interview he said that for years he had named Chomsky as his source, until somebody “sort of proved” he was wrong, “because the dates were all wrong somehow.” Either way, soon after ALGOL 60 people noticed that BNF and Chomsky’s context-free grammars are the same thing, and a linguistic theory became the theory of compilers. That line between the first two rows shapes almost every parser: words are found with a finite automaton, and the structure of a phrase with a stack or recursion.

The man with the telescope

The third day brought a surprise. The informant was talking about apples, and a new word came up, la: minus. He translated ka la ka la ka without hesitation: eight apples, three eaten, then two more, and three left. But the grammar that suggests itself after day two, S → S lo S | S la S | ka, sees two different trees in this phrase: $(8 - 3) - 2 = 3$ and $8 - (3 - 2) = 7$. A grammar under which a phrase can have more than one tree is called ambiguous. In human language this happens all the time, and we resolve the ambiguity by sense. The classic example is “I saw the man with the telescope.” Who had the telescope, me or the man?

A computer cannot guess by sense, so in a programming language a text must have one tree and only one. The ambiguity is removed in the grammar itself. For minus, one device does the job: the right-hand side allows only ka on the right, and the continuation grows to the left, S → S la ka | ka. Then ka la ka la ka parses in only one way, as $(8 - 3) - 2$.

Programming languages have a famous ambiguity of their own, the dangling else. In C an if may have no else, and then in if (a) if (b) x(); else y(); it is unclear whose else this is, the first if’s or the second’s. The C standard settles it in favor of the nearest one. The indentation a human sees means nothing to the compiler.

There is no ticket, and the author expected “buy a ticket”, but the program quietly prints nothing but “the end”. The indentation lies: the else belongs to the inner if, and since the outer one didn’t fire, nothing did. ALGOL 60 closed this trap with grammar: another if may not stand right after then; it has to be wrapped in begin … end. Python closed it differently. A block in Python is marked by indentation, and every else sits at the level of its own if, so the ambiguity has nowhere to appear.

Who outranks whom

On the fourth day the word mi appeared: times. With every number a two, the informant worked out ka lo ka mi ka as $2 + 2 \cdot 2 = 6$, not $(2 + 2) \cdot 2 = 8$: mi binds words more tightly than lo does. This is operator precedence. In Chapter 15 it lived in the table of the shunting yard. A grammar keeps it differently, in floors. On the ground floor is whatever binds tightest: numbers and parentheses. One floor up, products made of them. Higher still, sums of products.

Under this grammar the multiplication in ka lo ka mi ka can end up only inside a T, which is lower in the tree than the addition, and so it is done first. The grammar allows no other tree. It also settles the question of minus and division: E → E la T grows to the left, so $8 - 3 - 2$ is $(8 - 3) - 2$. This behavior is called left associativity. There is right associativity too: in Python 2 ** 3 ** 2 is $2^{(3^2)} = 512$, as in mathematics. And unary minus in Python binds more loosely than the power: -2 ** 2 equals −4.

Words first

The islanders paused between words, and that made things easy. Program text gives no such help: x1=12+y**2 has not a single space, yet it holds seven words. Live speech runs together too, and the first thing a linguist learns is to cut it into words. So parsing a program happens in two stages. First a lexer cuts the text into tokens (numbers, names, operators), throwing away spaces and comments. Then the parser builds a tree from the tokens by the grammar, and to the parser 12 is one word made of two digits.

The calculator from Chapter 15 could already glue digits into a number. Here we add names and two-character operators.

A lexer always takes the longest piece that is still a token. That is why x1 is one name, ** is a power, and <= is one operator, though each of them could have been cut in two. And that is why two-character operators are checked before one-character ones. The last line fails with a clear error: our language has no @. Python’s lexer works the same way, only it knows more kinds of tokens, and it has a feature that C and Java lack.

The output contains INDENT and DEDENT. Python’s lexer keeps track of indentation itself: when a line moves to the right, it emits a token that says “an indented block begins,” and when the lines move back, “the block ends.” To the parser these are the same as C’s curly braces or ALGOL’s begin … end: Python’s grammar writes a block as INDENT, statements, DEDENT. The indentation we argued about in the section on the dangling else becomes words of the language before parsing even starts.

A parser by hand

What remains is to teach a program to build the tree. The grammar itself suggests the plainest way: one function per nonterminal. The function expr parses a sum, term a product, factor a number or parentheses. Each looks at the next token, decides which rule to apply and calls the functions for the parts of that rule. Parentheses inside parentheses mean that factor calls expr, which calls term, which calls factor again: recursion in a circle, as in the grammar of day two. Hence the name, recursive descent.

There is one snag. The rule E → E + T begins with E itself, and a function expr that followed it to the letter would start by calling itself before reading anything, and so on until the stack overflows. This is the same infinity as in the swapped Prolog rules of the last chapter. The cure is to rewrite the rule: a sum is a term followed by any number of “plus or minus, and another term.” The repetition becomes a while loop, and left associativity survives: each new node takes the old tree as its left child.

The three parsing functions repeat the three rules of the day-four grammar almost word for word, and that is the charm of the method: you can see the grammar in the code. The tree is nested tuples (op, left, right), and evaluating it takes five lines of recursion. The errors make sense too, because the parser knows what it was waiting for. Production compilers are built this way too: the C++ parser in Clang, for one, is hand-written recursive descent. Below, you can step through the descent and also break its grammar.

The tree Python builds

Python does the same with your code, only by a grammar of some two hundred and fifty rules. And you can look at its tree: the ast module parses text and returns a tree of objects.

This is our tree, only the nodes have long names: BinOp is a binary operation, Add, Mult and Sub say which one, Constant is a number. There are no parentheses in the tree. The text needed them to show what goes with what, and the tree shows that by its shape. A tree stripped of everything that only the notation needs (parentheses, commas, keywords, chains of intermediate nonterminals like T → F) is called an abstract syntax tree, or AST; the module takes its name from these letters. The last line shows that the tree is good for more than pictures: compile turns it into the bytecode of Chapter 33, and Python runs it.

Interpreters aren’t the only programs that parse Python code. Programs that check style, hunt for bugs and rearrange code all work on the tree. Say you want every function call in a program. With text search that is hard; with the tree it is easy, because every call is a Call node.

The function ast.walk visits every node of the tree, and all we have to do is pick out the ones we want. Among the kinds of nodes are Store and Load: that is how the tree marks whether a name is being written or read. The last task of the chapter rests on this mark. Try the same on your own code.

One last thing, useful every day. Config files, settings and data often arrive as a string that looks like Python: {'width': 800, 'debug': False}. It is tempting to run it through eval. But eval will just as happily run __import__('os').system(...) if the string came from an attacker. The safe way is ast.literal_eval: it parses the text into a tree and agrees to evaluate it only if the tree holds nothing but literals, such as numbers, strings, lists and dictionaries.

Even the harmless 2 ** 10 was refused: it is already a calculation. And a function call will never get through. The same principle (parse, look at the tree, and only then decide what to do with it) underlies every parser of configs, formulas and data formats. You are about to parse one such format yourself.

Tasks

Four tasks, four stages of working with a language: cut the text into words, build the tree of a formula, parse a data format that is in use everywhere, and check a program by its tree.

Write tokenize(text), a lexer for a small language. The function returns a list of (kind, value) pairs. The kinds are these. "NUM" is a number: digits, possibly with a fractional part after a point (3.14); the value is an int or a float. "NAME" is a name: a letter or _, followed by letters, digits and _. "STR" is a string in double quotes; its value is the contents without the quotes, with \", \\, \n and \t replaced by a quote, a backslash, a newline and a tab. "OP" is one of the operators ** <= >= == != + - * / % ( ) < > = , : [ ]. Spaces and newlines are skipped, and everything from # to the end of the line is a comment. An unknown character, an unclosed string or an unknown escape sequence raises SyntaxError.

Check two-character operators before one-character ones: text[i:i + 2] in ("**", "<=", …). A slice that runs past the end of the string raises no error: it comes out shorter, that’s all.

Fractions: after the digits, check whether there is a point with a digit after it. Only then read the fractional part and turn the piece into a float. Comments: when you see #, move i forward to the "\n" character or to the end of the text.

Strings: collect characters in a list until you meet the closing quote. A backslash means “the next character is special”: look it up in the dictionary {'"': '"', "\\": "\\", "n": "\n", "t": "\t"} and move on by two. If the text ends before the quote, the string is unclosed.

A lexer is a finite automaton: at every moment it is in one of a few states (“between tokens,” “inside a number,” “inside a string,” “after a backslash”), and the next character decides what happens next. In Chapter 54 such automata will build themselves from regular expressions, so a lexer can be given as a list of regexes, one for each kind of token. Character-by-character lexers with clear error messages are still written by hand, though, and this one will be back later in the course: in the interpreter and the compiler.

Write parse(text): given a string with a formula, it returns the formula’s tree. The lexer is ready; what you need is a parser for this grammar:

In the tree a number is the number itself, a name is a string, an operation is a tuple (op, left, right), and unary minus is ("neg", x). For example, parse("2 + 3 * (4 - 1)") is ("+", 2, ("*", 3, ("-", 4, 1))), and parse("-2 ** 2") is ("neg", ("**", 2, 2)), as in Python. Minus, division and remainder group from left to right, the power from right to left. If the text is not a formula, raise SyntaxError. The tests evaluate your tree on hundreds of random formulas and compare the results with Python itself.

One function per rule: expr, term, unary, power, atom. An asterisk in the grammar is a while loop, as in parser.py from the chapter; a question mark is a single if.

Why does power call unary on its right, and not power? So that 2 ** -1 parses. Right associativity then comes for free: unary will get back down to power, and 2 ** 3 ** 2 becomes ("**", 2, ("**", 3, 2)). In expr and term, on the contrary, each new node takes the old tree as its left child.

Errors. atom raises SyntaxError if what arrives is not a number, a name or a parenthesis, and that includes running out of tokens. A parenthesized expression must be followed by ). And after parsing, parse checks that no tokens are left over; otherwise "1 2" would quietly parse as 1.

Five rules, five functions, and precedence is not written down in any table: it lies in who calls whom. Compare this with the shunting yard with powers from Chapter 15: there the right associativity of the power was one comparison in a table, here it is the fact that power calls a function of its own level on the right. The subtle spot is -2 ** 2: unary minus sits above the power in the grammar, so it applies to a power that is already built and gives −4, as in Python and in mathematics. JavaScript, incidentally, forbids writing this without parentheses at all: too many people got it wrong.

JSON from Chapter 8 is described by a grammar that fits on a postcard. Write parse_json(text), which parses JSON text and returns the same thing as json.loads: an object becomes a dict, an array a list, a string a str, a number an int or (if it has a point or an exponent) a float, and true, false, null become True, False, None. The json module, eval and literal_eval are off limits. Anything that is not JSON raises ValueError: a comma before ], single quotes, 01, a tab or a newline right inside a string (those may only be written as \t and \n), extra characters at the end.

This is recursive descent: one method per rule. value looks at the first significant character ({, [, ", a digit or a minus, a letter) and calls the right method. After the [, array checks whether the array is empty, and then repeats “a value, then a comma or ].”

Numbers are easiest not to compute yourself: find where the number ends by the grammar and hand that piece to int(...) or float(...). But you do have to check the notation against the grammar: Python will swallow int("01") and float(".5"), and JSON won’t.

The catch is in \uXXXX. Characters beyond the first 65,536, emoji for example, are written in JSON as two such codes, a surrogate pair: the smiley with the code 1F600 is \ud83d\ude00. If the first code lies between D800 and DBFF and is followed by a second one between DC00 and DFFF, glue them together: $\text{0x10000} + (h - \text{0xD800}) \cdot 1024 + (l - \text{0xDC00})$.

The methods obj and array call value, which calls them in turn: the nesting of the document becomes the depth of the recursion. That is why a document with a mere five hundred nested brackets is enough to bring this parser down: Python stops the recursion with a RecursionError, as in Chapter 9. This is a known way to attack servers, and production JSON parsers defend against it with a depth limit. There is no separate lexer here; it is built into the parser: peek skips spaces, and numbers and strings are read character by character. Small formats are often handled this way, since the JSON grammar is simple enough that its “words” can be told apart by their first character.

Linters, the programs that look for suspicious spots in code, work on the tree. Write unused(source): given the text of a Python program, it returns a sorted list of the names that get assigned but are never read. “Assigned” and “read” mean what the ast module marks them as: an ast.Name node marked ast.Store is a write (an assignment, a loop variable, unpacking), and one marked ast.Load is a read. Names that start with an underscore conventionally mean “unused on purpose,” so leave them out. If the code has a syntax error, let the SyntaxError fly.

Walk all the nodes with ast.walk(tree) and collect two sets: the names from ast.Name nodes with isinstance(node.ctx, ast.Store), and those with ast.Load. The answer is the difference of the two sets, minus the names starting with _, sorted.

Searching the program text for substrings won’t work: print("total") contains the word total but doesn’t read the variable, while f"{name}" reads it, even though it is a string. The tree tells the two apart: a string is a Constant, and an expression inside an f-string is a full-fledged Name.

Nine lines, and you have one of the checks that linters like pyflakes make. Our mini linter is cruder: it knows nothing about scopes, so an x in one function and an x in another are the same name to it, and it counts count += 1 as a write without a read. Pyflakes and its relatives build a table of scopes from the tree (the next chapter will call them environments). But they start the same way, with ast.parse.

What next

The expedition is over. You can now turn a string into a tree, Python does the same with every program you write, and the ast module shows you the result.

But a tree does nothing by itself. ("+", 2, ("*", 3, ("-", 4, 1))) is only tuples, and eleven came out of them because we wrote evaluate. For a formula, five lines were enough. But what if the tree holds variables defined somewhere else, functions that call themselves, and functions that return functions? Where are the values of names kept, how does a call learn its arguments, why does a function remember the variables of the place where it was created? We have the tree. How do we make it work? In the next chapter we will write an interpreter, starting with Lisp, whose programs, as we saw in the museum, already come as ready-made trees.