# In general, how does one make a context-free grammar unambiguous?

Say I have a context-free grammar defined by the following rule.

$$\langle EXPR\rangle \rightarrow \langle EXPR\rangle + \langle EXPR\rangle~|~\langle EXPR\rangle \times \langle EXPR\rangle~|~(\langle EXPR \rangle)~|~x$$

This grammar is ambiguous since, for instance, I can generate the string $x + x \times x$ via more than 1 leftmost derivation.

How could I make this grammar unambiguous? Should I make sure that no $\langle EXPR\rangle + \langle EXPR\rangle$ is evaluated after a $\langle EXPR\rangle \times \langle EXPR\rangle$ as such:

$$\langle EXPR\rangle \rightarrow \langle EXPR\rangle + \langle EXPR\rangle~|~\langle MUL\_EXPR\rangle \times \langle MUL\_EXPR\rangle~|~(\langle EXPR \rangle)~|~x \\ \langle MUL\_EXPR \rangle \rightarrow \langle EXPR\rangle \times \langle EXPR\rangle~|~(\langle EXPR \rangle)~|~x \\$$

-
So, do you mean in general or in this case? –  Raphael Jan 16 '13 at 10:19

Indeed you made a step to resolve ambiguity, but your solution does not give a fully unmabiguous grammar yet. The string $x+x+x$ can be parsed in two different ways, like $x + [x+x]$ or like $[x+x]+x$, where the brackets indicate parses. As far as I see your solution resolves semantical ambiguities (it fixes the relative order of + and x) but not the syntactical ambiguity. So obtaining an umambiguous grammar is not the only goal for an example like this: we want to respect meaning (here operator precedence). (Perhaps there is more official terminology for that)

Your example is a familiar one, and is used in wikipedia/Syntax diagram:

<expression> ::= <term> | <expression> "+" <term>
<term>       ::= <factor> | <term> "*" <factor>
<factor>     ::= <constant> | <variable> | "(" <expression> ")"


Probably you will know that not every grammar has an unambiguous equivalent, so no general approach is possible.

-

i don't think there is a fixed method of derivations to make a grammar unambiguous. you have to try by trail and error method by adding new non-terminals to the grammar without changing the definition of that grammar.

-
Indeed, no such method exists: see e.g. people.cis.ksu.edu/~rhowell/770s03/lectures/23-twoup.pdf –  reinierpost Jan 16 '13 at 14:45
BTW, I found this with google.com/search?q=ambiguity+undecidable which comes up with quite a few more useful links. –  reinierpost Jan 16 '13 at 14:46