Grammar has ambiguity. The same string can have multiple meanings or produce multiple parse trees.
Compilers
- Alternation is the source of Ambiguity (e.g., the bar |)
- Not every | causes grammatical ambiguity
- Every grammatical ambiguity is caused by a |
- Linguists want to model ambiguity in human languages
- The Context-Free Grammar (CFG) idea is from linguists
- We want to design computer languages without ambiguity
- The Parsing Expression Grammar (PEG) idea is ours
- PEGs include all unambiguous regular + LL(1) + CFG
In Practice
- If we do not specify the operator associativity properly, then we might have an ambiguous grammar.
- Ex. Multiplication binds tighter than addition. If we do not specify the operator precedence properly, then we might have an ambiguous grammar
Fixing Precedence
- Each level of precedence should be its own non-terminal
- The lowest level of precedence should be the top level production
- Each production should use the next highest level of precedence