Turning Text Into Instructions
Precedence Is Not a Table You Memorise, It Is the Shape of the Rules
Last timeFrom Text to Pieces
A parser turns a flat list into a tree. The order of operations you learned as a table is actually a consequence of how the grammar was layered, and nothing else.
A grammar is a set of shapes
The previous stage produced a flat list of tokens with no structure. This stage
builds the structure, and it does so against a written description of what
structures are allowed. That description is the grammar.
A grammar is nothing more than a list of rules, each saying that one kind of
thing may be made of some other things in a particular order.
expression -> expression + term
expression -> expression - term
expression -> term
term -> term * factor
term -> term / factor
term -> factor
factor -> number
factor -> identifier
factor -> [ expression ]
that is the whole thing: nine rules, three kinds
of thing, and no table of precedence anywhereParsing is fitting the token list into these shapes. Starting from the top kind
of thing, is there an arrangement of rules that accounts for every token, in
order, with none left over? If yes, that arrangement is the tree. If no, the
input is not a program in this language, and that is exactly what a syntax
error is.
| step | step | tokens left | what the parser decided | tree so far | what happened |
|---|---|---|---|---|---|
| 1 | 1 | a + b * c | a is a factor, and a factor is a term | one leaf | Working bottom up, the smallest shapes are recognised first. A bare name is a factor by the rule, and a lone factor is a term by another. |
| 2 | 2 | + b * c | hold the term, an operator follows | one leaf | The parser cannot finish the expression yet because the rule for addition needs a term on the right as well. |
| 3 | 3 | b * c | b times c is a term by the multiplicatio | two leaves joined | This is the moment that decides everything. The multiplication rule completes while the addition rule is still waiting, so the product becomes one object. |
| 4 | 4 | nothing | term plus term is an expression | three leaves, one shape | Only now does the addition complete, and what it adds is the finished product. The grouping was never chosen, it fell out of which rule could finish first. |
The tree is the program
The result is a tree, and from here on the tree is the program. The text was a
way of writing it down.
The lesson stops here
4 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents