Context-Free Grammars: Ambiguity, Associativity and
Precedence
• Context-Free, or Type 2, Grammars, are used to for-
mally define the syntax of programming languages.
They are also known as BNF, or Backus-Naur Form.
• Two grammars are equivalent if they generate the
same language.
1
• A derivation in a context-free grammar can be rep-
resented by a parse tree.
– the root is the start symbol
– the interior nodes are non-terminals
– the leaves in left-to-right order form a sentential
form
– X1, X2,…,Xm are the children of A only if A ->
X1X2…Xm is a production
2
• A grammar is ambiguous if it generates a string with
two distinct parse trees.
Example:
< expr > ::= x|y|z|(< expr >)
| < expr > + < expr >
| < expr > ∗ < expr >
Ambiguous: x + y + z.
Rule: A grammar is ambiguous if it is both left and
right recursive.
Fix: remove right recursion
< expr > ::= < element >
| < expr > + < element >
| < expr > ∗ < element >
< element > ::= x|y|z|(< expr >)
3
Example: ”Dangling Else” Problem
S ::= if E then S
| if E then S else S
| other
Ambiguous: if E then if E then S else S
Fix:
S → S1 | S2
S1 → if E then S1 else S1
S1 → other
S2 → if E then S
S2 → if E then S1 else S2
4
Associativity
• Productions that are left-recursive force evaluation
in left-to-right order (left associativity).
• Productions that are right-recursive force evaluation
in right-to-left order (right associativity).
• Example: This left-recursive grammar enforces left-
associativity:
< expr > ::= < element >
| < expr > + < element >
| < expr > ∗ < element >
< element > ::= x|y|z|(< expr >)
– Parse x + y + z again.
– Parse x+y∗z and x∗y+z; note that left-associativity
is maintained, but + and * have the same prece-
dence.
5
Precedence
• Precedence is introduced by adding new non-terminal
symbols.
• Cascade symbols with lowest precedence closest to
the start symbol.
• Example
< expr > ::= < term >
| < expr > + < term >
< term > ::= < element >
| < term > ∗ < element >
< element > ::= x|y|z|(< expr >)
Now Parse x + y ∗ z and x ∗ y + z; note that left-
associativity and the correct precedence are enforced.
6
• Example
• Precedence: (), – (unary), ↑, */, +-
• Associativity:
left: */+-
right: ↑
< expr > ::= < term >
| < expr > + < term >
| < expr > − < term >
< term > ::= < factor >
| < term > ∗ < factor >
| < term > / < factor >
< factor > ::= < primary >↑< factor >
| < primary >
< primary > ::= − < primary >
| < element >
< element > ::= x|y|z|(< expr >)
7