How does one make an unambiguous context-free grammar for arithmetic expressions?

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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*}$