Course contentsShow
← Computer Science
Lesson 1819 of 2,87241. Context-Free LanguagesFree lesson

CFGs for Arithmetic Expressions

Build grammars that capture operator precedence and associativity in mathematical expressions.

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.