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?


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.)

  • $\begingroup$ the value at depth will be computed first , so in this way grammar2 and grammar3 both computes b & c first then the result is computed with a. My teacher was teaching to find equivalent right recursive grammar , as per your answet now I think that he is talking about converting to weak equivalent left recursive grammar. Then , why he said that grammar3 ( as per ques ) is wrong ? What may be the reason? $\endgroup$ Jun 24 '21 at 18:17
  • $\begingroup$ It should be $E\to T+E\mid T$. Other than that, I see no problem with it. The grammar given by your instructor is the result of the usual algorithm for eliminating left-recursion. $\endgroup$
    – rici
    Jun 24 '21 at 18:39

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.