Parsing and grammars

Parsing is the act of reading a flat run of text against a set of rules called a grammar, so that the machine can rebuild the nested structure the author actually meant. It turns a string of characters, which has no shape of its own, into a tree that mirrors how the parts of the program fit inside one another.

What a grammar is

A grammar is a set of rules that say what counts as a valid piece of a language and how the pieces may be combined. You already carry one for English, even if you never wrote it down. A sentence can be a subject followed by a verb followed by an object. A subject can be a noun, or an adjective and a noun. Each rule names a kind of thing and lists the smaller things it can be built from. That is all a grammar is: names for kinds of things, and the recipes for building each kind out of smaller ones.

Programming languages have grammars too, and unlike English theirs are written down exactly and admit no exceptions. To see how one works, we do not need a real language. A tiny one will do. Let us invent a language of arithmetic, just numbers with plus and times, and write its grammar in plain words:

expression = term, then zero or more of ("+" then term)
term       = factor, then zero or more of ("*" then factor)
factor     = a number, or "(" expression ")"

Read it from the bottom. A factor is the smallest thing: either a plain number, or a whole expression wrapped in parentheses. A term is one or more factors joined by times. An expression is one or more terms joined by plus. Three short rules, and they define an infinite set of valid arithmetic expressions, from a bare 4 to something deeply nested. The rules refer to each other, and a factor can contain an expression, which is what lets the language nest without limit from a handful of lines.

First split the text into tokens

Before the rules can be applied, the raw characters have to be grouped into the smallest meaningful units. This first pass is called lexing, sometimes tokenizing, and the units it produces are called tokens. A token is a chunk of characters that belongs together and has one role: a number, a plus sign, an opening parenthesis, a name, a keyword.

Take the text 12 + 3. As characters it is a one, a two, a space, a plus, a space, a three. The lexer reads left to right and groups them. It sees the one and the two next to each other and emits a single number token, 12. It skips the space, which carries no meaning here. It emits a plus token. It skips the next space. It emits a number token, 3. The messy stream of six characters becomes a clean list of three tokens: number 12, plus, number 3. Lexing is the step that decides that the two adjacent digits are one number and not two, and that the spaces can be thrown away.

Splitting the work into lexing first and parsing second keeps each job simple. The lexer worries only about characters and never about structure. The parser then works with tidy tokens and never has to think about individual letters or spaces again. It is the same reason you would separate the sound of English into words before worrying about grammar. Words first, sentence structure second.

The lexer also carries the small but real judgments about what a chunk of characters is. When it sees the letters f, o, r together, it has to decide whether that is a keyword of the language or just a name someone chose. When it sees a run of digits with a dot in the middle, it decides that is one number and not two numbers around a period. When it meets a quotation mark, it knows everything until the closing mark is a single string token, even if that text contains spaces and plus signs that would otherwise be their own tokens. Getting these calls right at the lexing stage is what lets the parser trust that a token means one clean thing, so it can spend all its attention on how the tokens fit together rather than on what each one is.

Then apply the rules to recover the nesting

With a list of tokens in hand, parsing proper begins. The parser tries to match the tokens against the grammar rules, and each time a rule matches it builds a piece of structure. The output is a tree: a shape where a thing can contain other things, which contain still others, as deep as the input goes.

Walk it through on 2 + 3 * 4. The tokens are number 2, plus, number 3, times, number 4. The parser starts at the top rule, expression, which wants a term followed by optional plus and more terms. It reads the first term, which is just the factor 2. It sees a plus, so it expects another term. Now the term rule takes over, and a term is factors joined by times. So it reads 3, sees the times, and reads 4, binding 3 and 4 together into a single term, three times four. The result is an expression that adds two things: the number 2, and the product of 3 and 4.

Notice what the grammar just did for free. It made times bind tighter than plus, so the answer groups as 2 plus the quantity 3 times 4, not as the quantity 2 plus 3, then times 4. We did not write a rule that says “do multiplication first.” We got it by putting term between expression and factor, so multiplication lives one level deeper in the tree and therefore groups first. The nesting of the rules becomes the nesting of the structure, and the structure carries the meaning.

A parser does not just check that text is valid. It rebuilds the shape the author had in mind, turning a flat line into a tree where containment is the meaning.

Parentheses show the recursion at work. Feed the parser (2 + 3) * 4 and, when it reaches the factor rule inside the term, that factor is not a plain number but an open parenthesis. The factor rule says a factor can be a whole expression in parentheses, so the parser dives back into the expression rule, parses 2 plus 3 as its own little tree, and then treats that entire tree as one factor to be multiplied by 4. The rule referring back to itself is what lets a short grammar describe arbitrarily deep nesting. This is the heart of parsing: rules that call each other to recover structure that goes as deep as the text does.

When the rules do not decide: ambiguity

A grammar is only as good as its ability to give one answer. If the same tokens can be built two different ways by the rules, the grammar is ambiguous, and ambiguity is a real problem because the two structures can mean different things. Our arithmetic grammar avoided it on purpose. Had we written a single flabby rule that said an expression is expressions joined by plus or times with no layering, then 2 plus 3 times 4 could be grouped either way, and the language would not know which one you meant.

Real language designers spend serious effort making their grammars unambiguous, or adding tie-breaking rules for the cases that remain. The classic example even outside code is the dangling question of which if an else belongs to when they are stacked. Languages resolve it by fiat, usually by attaching the else to the nearest if. The lesson is that a grammar is not only a description of what is valid. It is also a set of decisions about how to read the valid things, so that every program has exactly one structure and therefore one meaning.

When the text breaks the rules: parse errors

What happens when the tokens simply cannot be matched to any rule? That is a parse error, sometimes called a syntax error, and it is the moment the parser can prove the text is not a valid program. Feed it 2 + + 3 and it reads the 2, reads the plus, then expects a term, which must start with a number or an open parenthesis. Instead it finds another plus. No rule allows that, so the parser stops and reports where the trouble is.

This is the same experience you have every time an editor underlines a line in red before you have run anything. Some tool has parsed your code, found tokens that fit no rule, and told you. A basic parser gives up at the first error. That is fine for a compiler, which will refuse to build a broken program anyway. It is a serious limitation for a tool that wants to understand code as you type it, when the code is broken most of the time, and we will return to that when we reach the parsing technology built for editors.

It is worth separating two very different kinds of wrong at this point, because people often blur them. A parse error means the text does not even form a valid program: the grammar cannot make sense of the tokens at all, the way a sentence with no verb is not a sentence. That is a question of shape, and the parser is the thing that catches it. A program can be perfectly valid in shape and still be wrong in what it does: it parses cleanly, it runs, and it computes the wrong answer or crashes. That second kind of wrong is invisible to the parser, because the parser only checks structure against the grammar, not behavior against your intent. Parsing tells you the text is a well-formed program. It never claims the program is a good one.

Everyone parses, all the time

Parsing is not a niche activity. It is one of the most run pieces of software on earth, because almost every tool that touches code has to parse it first. A compiler parses your program to turn it into something the machine can execute. An interpreter parses it to run it directly. The editor that colors your keywords parses to know which words are keywords. The feature that jumps you to where a function is defined parses to know where that is. The formatter that tidies your indentation parses to know the structure it is re-indenting.

Every one of these starts from the same flat text and rebuilds the same kind of tree, because you cannot do anything intelligent with code until you have recovered its structure. The pretty colors and the smart jumps are downstream of a parse. This is why parsing is foundational rather than optional. It is the gate between characters and meaning, and nearly every tool has to pass through it.

Where a parser comes from

There are two ways to get a parser, and the difference matters for what comes later. You can write one by hand, coding the rules directly as functions that call each other, one function per grammar rule, matching tokens as they go. Hand-written parsers can be very fast and can give beautifully tailored error messages, which is why some major languages ship one. The cost is labor. Every rule is code you wrote and must maintain, and every language you want to support is a fresh parser from scratch.

The other way is to describe the grammar in a compact notation, close to the three lines we wrote for arithmetic, and hand it to a program that reads the grammar and generates the parser for you. Such a program is called a parser generator. You write the rules; it writes the code that matches them. The advantage is leverage. One tool can produce a parser for any language whose grammar you can describe, which is exactly what you need when your goal is to understand many languages at once rather than championing one.

Either way, the product is the same: a nested, typed structure recovered from flat text, with every construct as a node and containment as the shape. That structure is the real prize of parsing, the thing everything downstream actually works on, and it has a name of its own. It is called the abstract syntax tree, and it is the subject of the next idea in this hub.