We impose precedence among operations by nesting them more deeply in the parse tree, which in turn causes them to be evaluated first. For instance, this math expression:
1 | 1 + 2 * 3 + 4 |
Must be evaluated as if it were written like so:
1 | ((1 + (2 * 3)) + 4) |
Or rearranged into S-expressions:
Our grammar should naturally produce this parse tree.
Left-to-right associativity (e.g., a+b+c means (a+b)+c, not a+(b+c)) is handled by recursive rules in the grammar (e.g., sum is defined in terms of sum).
Which of these grammars is correct?
And what’s wrong with the other two?
1 2 | #lang brag sum : sum "+" ("a" | "b" | "c") |
1 2 | #lang brag sum : ("a" | "b" | "c") ["+" sum] |
1 2 | #lang brag sum : [sum "+"] ("a" | "b" | "c") |
1 | (parse-to-datum "a+b+c") |
Operator precedence (e.g., c*a+b*c means (c*a)+(b*c), not ((c*a)+b)*c) is implemented by chaining production rules in the grammar (e.g., sum is defined in terms of product).
Which of these grammars is correct?
And what’s wrong with the other two?
1 2 3 | #lang brag product : [product "*"] sum sum : [sum "+"] ("a" | "b" | "c" ) |
1 2 3 | #lang brag sum : [sum "+"] product product : [product "*"] ("a" | "b" | "c") |
1 2 3 4 | #lang brag sum : [product "+"] product product : [var "*"] var var : "a" | "b" | "c" |
1 | (parse-to-datum "c*a+b*c") |
Parenthesized operations are just one more level of precedence.
Keep doing this until you have your math tower.
Make a language called precalc that can evaluate the following source. Compared to algebra, notice that it adds support for:
Multiline comments.
Negative integers.
Multiplication, subtraction, and division.
Parenthesized math expressions.
BTW there are no expressions at the top level of the program. Just function definitions, function applications, or comments.
Example:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #lang precalc fun f(x, y, z) = x + x + x * (y + y) + y * z - z - z fun g(z) = f(z, z, z) # line comment g(-10) # = 300 fun h() = g(10) h() # = 300 fun k(x) = x / 10 / 10 / (x / x) k(h()) # = 3 k(-10 * (15 + 3 * 5)) # = -3 /* multiline comment 0 / 0 / 0 */ |
Result:
1 2 3 4 | 300 300 3 -3 |
Hint: start with your implementation of algebra and improve it.
Hint: - and + have the same precedence, as do / and *. You can put each of these pairs inside a shared production rule.
“With a long enough lever, I will move the earth.”