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 \\ $$


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.


If you do not care about semantics, the way to remove ambiguities is to

  1. derive different operators in non-overlapping "phases" (operator precedence) and
  2. create the same operators in a fixed order (associativity).

So, for instance, if you want $\times$ to bind stronger than $+$ and left-associativity, you'd do

$\qquad\begin{align*} S &\to S + A \mid A, \\ A &\to A \times T \mid T, \\ T &\to \text{[any atoms you want]}. \end{align*}$

This is now unambiguous, and quite restricted in terms of what expressions we can write down (semantically speaking); the user has to multiply all their expressions out completely.

You note, of course, that I left out the parentheses. That is because they pose no problem; if we demanded parentheses everywhere, we would not have ambiguity. Therefore, we can add parenthesized expressions to our grammar without introducing ambiguity. By adding an alternative $(S)$ ("start anew inside a new scope") to every "move to the next phase" non-terminal, we get this:

$\qquad\begin{align*} S &\to S + (S) \mid S + A \mid (S) \mid A, \\ A &\to A \times T \mid A \times (S) \mid (S) \mid T, \\ T &\to \text{[any atoms you want]}. \end{align*}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.