It is a well-known problem that many top-down parsers have problems parsing a context-free grammar with left recursive rules. There exist algorithms to convert grammars with direct or indirect left-recursive rules to equivalent grammars that don't have such rules.

For example, a simple left-recursive grammar

$$\begin{alignat}{2} &E &&\to E \ \text{'-'}\ V \ \vert \ V\\ &V &&\to \text{'a'} \ \vert\ \text{'b'} \end{alignat} $$ can be converted to an equivalent right-recursive one $$\begin{alignat}{2} &E &&\to V \ E'\\ &E' &&\to \text{'-'}\ V \ E' \ \vert \ \varepsilon\\ &V &&\to \text{'a'} \ \vert\ \text{'b'} \end{alignat} $$ that accepts the same language.

The problem with that conversion in that the parse trees for the same input string look fundamentally different. In the first case the result is a left-leaning tree, reflecting the left-associativity of the subtraction operator. On the other hand, the parse tree for the second grammar would yield a right-leaning tree, which makes it harder to process or evaluate the built parse tree.

In terms of equivalence, this conversion yields a non-left-recursive grammar that is weakly equivalent to the original one, i.e. accepting the same language, but not strongly equivalent. The latter also requires structurally equivalent parse trees.

For every left-recursive context-free grammar, does there exist a non-left-recursive, strongly equivalent version that describes the same language? If so, how would an algortihm look like that performs such a conversion?

  • $\begingroup$ No, there doesn't. The left-leaning parse tree can only be produced with a left-recursive grammar, since the parse tree is literally a manifestation of the grammar. $\endgroup$ – rici Sep 28 at 21:14
  • $\begingroup$ Too bad. Papers I read usually only concentrate on what languages certain types of grammars describe, but I'm still wondering if the languages that yield certain types of parse trees can be formally categorized too. If we e.g. replace the first alternative of $E$ by $\text{'('}\ E\ \text{')' '-'}\ N$, we can construct left-leaning trees. So there seems to exist a subset of context-free languages where such trees are possible and some where they are not. Is there any literature about formal languages/grammars that also takes various parse tree types into account? $\endgroup$ – siracusa Sep 29 at 0:53
  • $\begingroup$ I don't know. What's a parse tree type? I'd say that the tree with parentheses is not really left-leaning (although it's left-biased, to be sure) but it would depend on a formal definition of "left-leaning". Also, with the classic expression grammar, not every expression is parsed to a left-leaning tree; you can generate a right-biased tree by using enough parentheses (and the $E\to \text{'('} E \text{')'}$ production). But my point is still that the parse tree is a manifestation of the grammar. (Also see, eg., the pumping lemma.) $\endgroup$ – rici Sep 29 at 1:16
  • $\begingroup$ Thinking about it, those parse tree types wouldn't make much sense. I'm still a bit confused about how what strong equivalence then really means. $\endgroup$ – siracusa Sep 30 at 8:01
  • 1
    $\begingroup$ "Strong equivalence" does not (IMHO) have a single clearly-defined meaning in this context. If you want to explore this, you might try a more open-ended question, and I might try an answer (although I don't know if I am the most qualified to do so). $\endgroup$ – rici Sep 30 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.