Understanding Ambiguity in Context-Free Grammars
Classified in Teaching & Education
Written on in English with a size of 56.6 KB
Ambiguity in Context-Free Grammars
Definition of CFG Ambiguity
A Context-Free Grammar (CFG) is called ambiguous if, for at least one word in the language it generates, there are two or more possible derivations of the word that correspond to different syntax trees.
Example 1: Simple Ambiguity
Consider the language generated by the following CFG:
PROD 1: S → AB PROD 2: A → a PROD 3: B → b
There are two different sequences of production applications that generate the word ab:
- Sequence 1: PROD 1, PROD 2, PROD 3
- Sequence 2: PROD 1, PROD 3, PROD 2
These sequences lead to the following derivations:
S → AB → aB → ab S → AB → Ab → ab
When the corresponding syntax trees are drawn, we observe that these two derivations are essentially the... Continue reading "Understanding Ambiguity in Context-Free Grammars" »