patternCritical
Why are ambiguous grammars bad?
Viewed 0 times
whyarebadgrammarsambiguous
Problem
I understand that if there exist 2 or more left or right derivation trees, then the grammar is ambiguous, but I am unable to understand why it is so bad that everyone wants to get rid of it.
Solution
Consider the following grammar for arithmetic expressions:
$$
X \to X + X \mid X - X \mid X * X \mid X / X \mid \texttt{var} \mid \texttt{const}
$$
Consider the following expression:
$$
a - b - c
$$
What is its value? Here are two possible parse trees:
According to the one on the left, we should interpret $a-b-c$ as $(a-b)-c$, which is the usual interpretation. According to the one on the right, we should interpret it as $a-(b-c) = a-b+c$, which is probably not what was intended.
When compiling a program, we want the interpretation of the syntax to be unambiguous. The easiest way to enforce this is using an unambiguous grammar. If the grammar is ambiguous, we can provide tie-breaking rules, like operator precedence and associativity. These rules can equivalently be expressed by making the grammar unambiguous in a particular way.
Parse trees generated using syntax tree generator.
$$
X \to X + X \mid X - X \mid X * X \mid X / X \mid \texttt{var} \mid \texttt{const}
$$
Consider the following expression:
$$
a - b - c
$$
What is its value? Here are two possible parse trees:
According to the one on the left, we should interpret $a-b-c$ as $(a-b)-c$, which is the usual interpretation. According to the one on the right, we should interpret it as $a-(b-c) = a-b+c$, which is probably not what was intended.
When compiling a program, we want the interpretation of the syntax to be unambiguous. The easiest way to enforce this is using an unambiguous grammar. If the grammar is ambiguous, we can provide tie-breaking rules, like operator precedence and associativity. These rules can equivalently be expressed by making the grammar unambiguous in a particular way.
Parse trees generated using syntax tree generator.
Context
StackExchange Computer Science Q#110402, answer score: 57
Revisions (0)
No revisions yet.