CFGs for Arithmetic Expressions
What you'll learn: How to write context-free grammars that correctly handle operator precedence (like multiplication before addition) and associativity (like left-to-right evaluation).
When designing grammars for arithmetic expressions like 3 + 5 * 2, we face a challenge: the grammar must encode the rules we learned in math class—multiplication happens before addition, and operations of equal precedence go left-to-right.
The Core Idea
We use separate non-terminals for each precedence level. Lower-precedence operators (like +) appear higher in the grammar hierarchy, while higher-precedence operators (like *) appear lower, closer to the actual numbers.
Here's a classic grammar:
E → E + T | T
T → T * F | F
F → (E) | number
Why this works: To derive 3 + 5 * 2, the grammar forces 5 * 2 to form a complete subtree (via T → T * F) before it can participate in addition. The * binds tighter because it's nested deeper in the grammar structure.
Left associativity: Notice E → E + T puts the recursive E on the left. This makes a + b + c parse as (a + b) + c, evaluating left-to-right. If we wrote E → T + E instead, we'd get right associativity: a + (b + c).
Think of it like nesting dolls: Expressions (E) contain terms (T), terms contain factors (F), and factors are either parenthesized expressions or atomic numbers. Each layer respects the precedence above it.
Key Takeaway: Operator precedence in CFGs is encoded by grammar structure—higher-precedence operators appear in lower (more deeply nested) non-terminals, and associativity is controlled by whether recursion appears on the left or right side of a production.