0
$\begingroup$

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
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.