Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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.

share|cite|improve this answer

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 A + S \mid A, \\ A &\to T \times A \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 A + S \mid (S) \mid A, \\ A &\to T \times A \mid (S) \times A \mid (S) \mid T, \\ T &\to \text{[any atoms you want]}. \end{align*}$

share|cite|improve this answer

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.

share|cite|improve this answer
Indeed, no such method exists: see e.g. – reinierpost Jan 16 '13 at 14:45
BTW, I found this with which comes up with quite a few more useful links. – reinierpost Jan 16 '13 at 14:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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