From words to trees

The lexer hands over a list: 1, +, 2, *, 3. Every schoolchild knows the answer is 7, not 9, because multiplication “goes first”. The list does not say so. The rule lives in the language's grammar, and the parser applies it to build a tree in which 2 * 3 hangs below the +. From here on the compiler never looks at the text again: it works on trees.

§Grammars

In 1956 the linguist Noam Chomsky classified the ways of describing languages by how much memory a machine needs to recognise them. Regular languages (the lexer's, chapter 01) need a finite memory; one level up, context-free languages need a stack, and can express nesting to any depth. Almost every programming language's syntax is designed to be context-free.

Three years later John Backus, fresh from FORTRAN, needed a precise way to define the syntax of the new international language ALGOL. His notation, polished by Peter Naur as editor of the ALGOL 60 report, became BNF (Backus–Naur form), and every language definition since descends from it. Here is part of Wahoo's grammar in the extended form with [ ] for optional parts and { } for repetition:

program  := item*
item     := 'pipe' NAME '(' [param {',' param}] ')' ['->' NAME] block
          | 'world' INT '-' INT block
block    := '{' stmt* '}'
stmt     := 'coin' NAME [':' NAME] '=' expr
          | 'question' expr block ['else' (question | block)]
          | 'bounce' expr block
          | 'run' NAME 'from' expr 'to' expr block
          | 'flag' [expr]
          | NAME '=' expr
          | call
expr     := or
or       := and {'or' and}
and      := not {'and' not}
not      := 'not' not | cmp
cmp      := sum [('==' | '!=' | '<' | '<=' | '>' | '>=') sum]
sum      := term {('+' | '-') term}
term     := unary {('*' | '/' | '%') unary}
unary    := '-' unary | primary
primary  := INT | TEXT | 'star' | 'goomba' | call | NAME | '(' expr ')'

Read the expression rules from top to bottom: each level is built from the level below, so the lower a rule, the tighter its operators bind. That layering is the precedence table, written as grammar.

§Parse trees and abstract syntax trees

A derivation can be drawn as a parse tree, with one node per rule applied. It records everything, including the parentheses and the chain expr → or → and → not → cmp → sum that a lone number goes through. Compilers keep a slimmer version, the abstract syntax tree (AST): one node per construct that means something, with punctuation and grouping dropped because the shape of the tree already encodes them. In the figure, (1 + 2) * 3 has no parenthesis node; the + simply sits below the *.

§Ambiguity, precedence and associativity

The obvious grammar for arithmetic, expr := expr op expr | INT, is ambiguous: 10 - 4 - 3 has two trees, one meaning (10 - 4) - 3 = 3 and the other 10 - (4 - 3) = 9. A language must pick one, and two pieces of information settle every case:

• Precedence says which operators bind tighter: * before +, both before <, that before and, that before or.
• Associativity says how to group a chain of operators of the same level: left for - and / (so 10 - 4 - 3 = 3), right for exponentiation in languages that have it (2 ** 3 ** 2 = 2 ** 9 in Python).

The best-known ambiguity in language design is the dangling else: in if a if b x else y, which if owns the else? C and Java say “the nearest one”. Wahoo sidesteps the question by making braces mandatory: question a { question b { x } else { y } } can only be read one way.

Comparisons deserve a special decision. In C, 1 < 2 < 3 is legal and means (1 < 2) < 3, that is 1 < 3, which is true by accident; 3 > 2 > 1 is false for the same reason. Python reads it as 1 < 2 and 2 < 3. Wahoo refuses it (error E102) and asks you to write the and.

§Recursive descent

The most natural way to write a parser by hand is to turn each grammar rule into a function. block expects a {, then calls stmt until it sees }; stmt looks at the next token and decides which rule applies; question calls expr and then block. The functions call each other recursively exactly as the rules refer to each other, and the call stack plays the role of the stack that context-free languages need. This is recursive descent, and it is how GCC, Clang, rustc, Go, V8 and Wahoo parse.

It works smoothly when one token of look-ahead is enough to choose a rule, a property called LL(1). Wahoo's statements were designed for it: each starts with its own keyword, except assignment and calls, which both start with a name and are told apart by the token after it (= or (). The one thing recursive descent cannot do is left recursion: a rule sum := sum '+' term would make sum call itself before consuming anything, forever. That is why the grammar above uses repetition, sum := term {'+' term}, and builds the left-leaning tree in a loop.

§Pratt parsing

Eight levels of expression rules mean eight nested function calls just to parse the number 3. In 1973 Vaughan Pratt proposed a neater method, top-down operator precedence: give every infix operator two numbers, a left and a right binding power, and parse all expressions with one loop.

Operators	Left power	Right power	Effect
or	1	2	loosest, left-associative
and	3	4	left-associative
not (prefix)	—	5	applies to a whole comparison
== != < <= > >=	7	8	not chainable (checked separately)
+ -	9	10	left-associative
* / %	11	12	left-associative
- (prefix)	—	13	binds tightest

The parser reads an operand, then looks at the next operator. If its left power is at least the minimum it was asked for, it takes the operator and parses the right-hand side with the operator's right power as the new minimum; otherwise it stops and returns what it has. A right power one higher than the left makes a chain group to the left; equal powers would make it group to the right. This is the heart of Wahoo's expression parser:

fn expr_bp(&mut self, min_power: u8) -> PResult<Expr> {
    let mut lhs = self.prefix()?;                      // a number, a name, (…), -x, not x
    while let Some((op, left, right)) = infix(&self.peek().kind) {
        if left < min_power {
            break;                                     // binds too loosely: let the caller take it
        }
        self.advance();
        let rhs = self.expr_bp(right)?;
        lhs = Expr::binary(op, lhs, rhs);
    }
    Ok(lhs)
}

§Bottom-up parsing: LL versus LR

Recursive descent builds the tree from the root down, predicting which rule comes next: it is a top-down, LL parser. The other great family works bottom-up: it shifts tokens onto a stack and, whenever the top of the stack matches the right-hand side of a rule, reduces it to that rule's nonterminal. In 1965 Donald Knuth defined the LR(k) grammars that can be parsed this way deterministically, a strictly larger class than LL(k) that includes left-recursive rules. The tables were enormous for the computers of the time, until Frank DeRemer's LALR(1) (1969) made them practical. In 1975 Stephen Johnson's Yacc (“Yet Another Compiler-Compiler”) generated LALR parsers from a grammar file, and its descendant Bison is still used.

Generators did not win everywhere. Error messages from table-driven parsers tend to be poor (“syntax error near line 12”), and grammars for real languages are full of special cases. GCC replaced its Bison parser for C++ with a hand-written recursive-descent one in 2004, and did the same for C two years later. Parser generators thrive elsewhere: ANTLR for tools and domain-specific languages, and tree-sitter (2018), which parses incrementally as you type and gives editors such as Neovim and GitHub's code viewer their syntax trees.

§When the parse fails

A parser that stops at the first syntax error is easy to write and annoying to use. Wahoo's parser uses panic-mode recovery: after reporting an error it skips tokens until it reaches a safe point, the start of a line that begins a statement or the } that closes the current block, and resumes from there. Then a typo in line 3 and another in line 9 are reported in the same run. One extra heuristic catches the most common slip of all, a forgotten }: if a new pipe or world appears at the start of a line inside a block, the block is closed there and the error points at it.

error[E101]: expected `}`, found `world`
 --> level.wahoo:5:1
  |
5 | world 1-1 {
  | ^^^^^ Lakitu lost the thread here

Recovery is a matter of judgement, not theory: skip too little and one mistake produces a cascade of false errors; skip too much and real ones are missed. Wahoo also stops after twenty errors, because by then the later ones are usually echoes of the first. A program that parses is not yet a correct program, though: wahoo(lifes) is grammatical even if nobody ever declared lifes. Meaning is the next chapter's business.

§References

1. N. Chomsky (1956). “Three Models for the Description of Language”. IRE Transactions on Information Theory, 2(3).
2. J. W. Backus (1959). “The Syntax and Semantics of the Proposed International Algebraic Language of the Zurich ACM-GAMM Conference”. Proceedings of the International Conference on Information Processing, UNESCO.
3. P. Naur (ed.) (1960). “Report on the Algorithmic Language ALGOL 60”. Communications of the ACM, 3(5).
4. D. E. Knuth (1965). “On the Translation of Languages from Left to Right”. Information and Control, 8(6).
5. V. R. Pratt (1973). “Top Down Operator Precedence”. Proceedings of the 1st ACM Symposium on Principles of Programming Languages.
6. S. C. Johnson (1975). Yacc: Yet Another Compiler-Compiler. Bell Laboratories Computing Science Technical Report 32.