# Convert ambiguous grammar to unambiguous and SLR(1)

I have the following ambiguous operator grammar:

E->E+E*E | E-E*E
E->E+E | E-E | E+E | E*E | E/E
E->(E) | x


I must convert it to an unambiguous one which is also SLR(1). The following rules regarding precedence and associativity must hold:

• Operators * and / have the highest precedence (and precedence between them must be equal)
• Operators - and + have the same precedence (lower than * and /)
• All operators are left associative.
• Reducing with the first 2 rules is preferred if it does not break the precedence and associativity rules.

My problem is the first line of the grammar (E+E*E , E-E*E). I can't find i way to convert it and the new grammar will be SLR(1).

Edit: The closest i came is this grammar, but it has 2 SLR conflicts:

E->E+F | E-F | T
T->T+F | T-F | F
F-> F*C | F/C | C
C-> (E) | x


Let's start where you probably started, with the classic expression grammar:

\begin{align}E&\to T\mid E + T\mid E - T\\ T&\to F\mid T * F\mid T / F\\ F&\to ( E )\mid x\\ \end{align}

and then we add the "fused" productions:

\begin{align}E&\to E + T * F\mid E - T * F\\ \end{align}

That grammar has a conflict because of the ambiguity:

\begin{align}E&\to E+T*F\\E&\to E+T \to E+T*F\end{align} (and similarly for the $$-$$ operator).

So how to get rid of the ambiguity? Clearly, we don't want $$E\to E+T$$ to match $$E+T*F$$. So we need to define $$T' = T \setminus T * F$$ in order to be able to restrict the $$E$$ production to $$E\to E + T'$$.

Since the set difference operator is not valid in a CFG, we need to write the definition out the long way:

\begin{align}E\to&\;T\mid E + T'\mid E - T'\;\mid\\ &\;E + T * F\mid E - T * F\\ T'\to&\;F\mid T / F\\ T\to&\;T'\mid T * F\\ F\to&\;( E )\mid x\\ \end{align}