Two answers to one sum
A spreadsheet export script works out a discount as 2 + 3 * 4. One tester says the answer is 14. Another says 20.
Both read the same tokens in the same order. They grouped them differently. A compiler must group tokens one way only, every time, and that way is written down as a grammar.
By the end of this lesson
Note
I can build a syntax tree from tokens.
Key words
| Word | What it means | Example |
|---|---|---|
| Grammar | the rules for which token orders are allowed | |
| Syntax tree | a tree showing how the tokens group | |
| Parser | the part of a compiler that builds the tree | |
| Precedence | which operator groups first | * before + |
| Associativity | which side groups first for equal operators | left |
| Recursive descent | a parser with one function for each rule |
The cells students fill in are left blank in this preview.
A grammar says how tokens group
A grammar is a short list of rules. Each rule names a part of a sentence and says what it is made of.
The three rules below give * and / a higher precedence than + and -. A sum is made of products, so products are grouped first. Brackets start again at the top, which is how they override the order.
Worked example: three rules for sums
| Rule | Is made of | Example |
|---|---|---|
| expr | A term, then + or - and another term, as often as needed | 2 + 3 * 4 |
| term | A factor, then * or / and another factor, as often as needed | 3 * 4 |
| factor | A number, or an expr inside brackets | 4 or (2 + 3) |
The cells students fill in are left blank in this preview.
One function for each rule
A recursive descent parser has one function for each rule. parse_expr calls parse_term, which calls parse_factor. A bracket makes parse_factor call parse_expr again: that is the recursion.
Each loop of parse_expr takes the tree built so far as its left side. That is what makes - lean left. The demo is that loop alone, with plain numbers for terms.
The loop that makes minus lean left
# A parser for sums like 10 - 4 - 3: numbers joined by + and -.
tokens = ["10", "-", "4", "-", "3"]
pos = 0
# The first number starts the tree.
tree = int(tokens[pos])
pos = pos + 1
while pos < len(tokens):
op = tokens[pos]
right = int(tokens[pos + 1])
# The tree so far becomes the left side, so - leans left.
tree = [op, tree, right]
pos = pos + 2
print(tree)
# Change tokens to ["1", "+", "2", "-", "3", "+", "4"] and run again.
bison builds the parser from a grammar
A parser generator such as bison reads a grammar and writes the parser in C. In calc.y the rule expr has a line for each operator. That alone is ambiguous: it could group 2 + 3 * 4 either way.
Two %left lines settle it. Each says its operators lean left. The later line binds tighter, so * and / group before + and -.
Go into the compiler folder
cd ~/compilerShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Make sure the calculator is built
makeShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
The two precedence lines
grep -n "%left" calc.yShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Minus leans left
echo "10 - 4 - 3" | ./calcShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
So does whole-number division
echo "100 / 7 / 2" | ./calcShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Brackets change the tree
echo "(2 + 3) * 4" | ./calcShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Two signs in a row
echo "2 + * 3" | ./calcShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A minus with nothing before it
echo "-3" | ./calcShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think a parser works left to right, so 2 + 3 * 4 is 20. The grammar decides the tree, and the tree decides the order. Precedence puts 3 * 4 lower in the tree, so it is worked out first. Left to right only settles operators of equal precedence.
Take the precedence away
The next Run copies calc.y without its two %left lines. Then bison reads the copy.
Without precedence, bison often has two moves and no rule to pick one. It calls each such place a shift/reduce conflict. The last Run asks bison for an example of the first one.
Copy the grammar without precedence
sed "/%left/d" calc.y > noprec.yShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Ask bison to build it
bison noprec.yShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Show one conflict
bison -Wcounterexamples noprec.y 2>&1 | head -n 3Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Going further
Add a power operator ^ to your parser. It binds tighter than * and leans right: 2 ^ 3 ^ 2 is 2 ^ (3 ^ 2).
Add a new rule between term and factor. Say why a loop like the one in parse_expr gives the wrong tree here, and what to write instead.