Left recursive grammar to right recursive grammar

Question

I am studying conversion from left recursive grammar to right recursive grammar. The given grammar is

$$E \to E + T \mid T $$

It's equivalent right recursive grammar will be $$\begin{align}E &\to TA\\ A &\to +TA \mid \epsilon\\ \end{align}$$

I understood this, that it is derived from changing the grammar $A \to Aa \mid b$ to its equivalent right recursive grammar and then comparing it accordingly. But why the right recursive grammar for this grammar is not

$$E \to T + E \mid E$$

As it also generates the same language and when there is only addition in an equation then associativity doesn't matter. Why can't this grammar be the equivalent right recursive grammar?

Answer 1

The two grammars you provide are both right-recursive and they both recognise the same language. But they are only weakly equivalent to the original grammar (and to each other), because they do not generate the same parse tree. Strong equivalence would require that the same parse tree be derived.

            E→E+T         E→T+E              E→TA
              /  \          /  \              /  \
             /    \        /    \            /    \
          E→E+T    T       T   E→T+E        T    A→+TA
            / \    |       |     /  \       |       / \
           /   \   |       |    /    \      |      /   \
         E→T    T  c       a   T     E→T    a     T   A→+TA
           |    |              |       |          |      / \
           |    |              |       |          |     /   \
           T    b              b       T          b    T    A→ε
           |                           |               |
           |                           |               |
           a                           c               c

The only one of these grammars which correctly captures the desired parse of $a+b+c$ is the first one, because $+$ is syntactically left-associative. It's true that since $+$ is mathematically associative, meaning that $(a+b)+c = a+(b+c)$, the syntactic associativity doesn't really matter semantically. But syntax doesn't take semantics into account, and there is no guarantee that $+$ is associative. (Indeed, in computational floating-point arithmetic, it is not.) Had the operator had been $-$, for example, the semantics would clearly be altered by the different parses.

(It's not entirely clear how we are to interpret semantically the $A\to +TA\mid\epsilon$ grammar. But I think any natural interpretation would be right-associative.)