Talk:Left recursion

pitfalls needs improved example

The pitfalls section uses the example of left recursion (a+a)+a and right recursion a+(a+a), but these have the same value. Should be changed so one of these is a '*' instead of a '+', such as (a+a)*a vs a+(a*a). (But I'm not comfortable enough at this moment to make that comprehensive a change and be sure of gettign the trees drawn exactly right.)

It is not the precedence that changes but the associativity. Hence a+a*a results in the same tree for both the left and the right recursive one. However a-a-a causes a problem since (a-a)-a=-a and a-(a-a)=a. So maybe this should be used as an example. It might also be worth to mention a further pitfall, that by removing left recursion using Paull's algorithm, a grammar can grow exponentially even though the grammar is not left recursive at all. Consider the grammar A(1)-->0|1 and A(i+1)-->A(i) 0| A(i) 1 for 1 <=i <= n. If the initial ordering is choosen ascending (A1, A2, .. An) then the grammar will grow exponentially. If the ordering is reversed (An, An-1, .. A1) the grammer is left untouched since every direct left corner already precedes it's definition. A good article on this and alternative algorithms for removing left recursion is Removing Left Recursion from Context-Free Grammars.

193.253.60.213 15:24, 28 June 2007 (UTC)

Left recursion and nullable

It appears to me that the two sections on immediate and indirect left recursion doesn't together cover the concept defined above in the definition. Consider

$A\rightarrow BA\alpha \,|\,\beta$

$B\rightarrow \epsilon \,|\,\gamma$

where $\alpha ,\beta ,\gamma$ are sequences of nonterminals and terminals. Now certainly we can from the non-terminal $A$ derive a sentential form starting with $A$. The problem is that $A$ is $nullable$[0], so if we start by deriving $BA\alpha$ from $A$, we may now derive $A\alpha$, because from $B$ we may derive $\epsilon$, the empty string, thus satisfying the definition of left-recursive grammar.

Am I correct in the existence and characterization of the problem ? (I can't see it being claimed that immediate and indirect left recursion exhausts the possibilities for left recursion.) If there is a problem, what to do about it ? Remove the claims of definition in the two subsections ? Remark that all possibilities are not exhausted, possibly by mentioning or even characterizing other cases ? Change the two subsections to also treat the "$nullable$-case" ?

(Note : I think the sections on removing left recursion might also have to be altered to take $nullable$ into account.)

[0] Nullable in the sense of Modern Compiler Implementation in ML, First Edition, Andrew Appel, 1998, ISBN 0-521-58274-1 : $nullable(X)$ is true if $X$ can derive the empty string.

StefanLjungstrand 85.224.18.100 11:08, 30 June 2007 (UTC)

Eight years late, but now addressed. 98.19.57.54 (talk) 08:14, 27 May 2015 (UTC)

In case of indirect recursion, when do we need to remove $\epsilon$-productions?

It is not always necessary to remove $\epsilon$-productions in order to use the algorithm given in the section on removing indirect left recursion.  – ∃ Aditya 7  ¦  12:22, 31 March 2014 (UTC)

I concur, at least the algorithm on removing direct recursion is incorrect because it fails to account for a nullable prefix prior to the occurrence of the nonterminal under consideration. 49.178.9.92 (talk) 16:52, 2 December 2016 (UTC)

Clear picture needed

Suggestion: This article needs a picture that clearly shows what left recursion is. Left recursion or right recursion, I never know which is which, but I'd just have to look at the corresponding trees. There are some ASCII trees at the bottom of the page, but it's not immediately clear what they represent. --96.234.243.131 (talk) 05:46, 21 April 2009 (UTC)

Candidate replacements for the ASCII art now in the queue here and here. An earlier image with a nonterminal S under itself in a parse tree might be nice too. 98.19.57.54 (talk) 08:21, 27 May 2015 (UTC)

Fix up math formatting

Lots of the math formatting needs to be fixed. I did two sections so far. In general, the problems are as follows:

1. Currently, $a\,|\,b$ (a\,|\,b) or $a|b$ (a|b) is used. It is preferable to use $a\mid b$ (a \mid b). The command \mid is the binary operator form and will put in the correct spacing as defined by LaTeX.
2. "Variable" names in LaTeX, such as the (non)terminals in this article like $Term$ or $Factor$ should actually be written using \mathit{} as in ${\mathit {Term}}$ (\mathit{Term}) and ${\mathit {Factor}}$ (\mathit{Factor}). The reason is that there are two different sets of glyphs with, e.g., different kerning pairs, so spacing can be all wacky. Compare $Taffy$ with ${\mathit {Taffy}}$. You see the second one is formatted much nicer.
3. Instead of using `...' to denote an ellipsis, please use \ldots. Compare $x\mid y\mid ...\mid z$ with $x\mid y\mid \ldots \mid z$. You see the second one is formatted with more consistent (and correct!) spacing.

I also began changing \rightarrow to \to only because it is shorter and cleaner. Otherwise they are not at all different.

Anyway, I think it's apparent that this page needs lots of cleaning up (ASCII diagrams, mediocre listings, etc.)

-- quadrescence (talk) 13:45, 7 June 2010 (UTC)

I hit it with a lot of corrections and cleanup and removed the expert-attention and cleanup-required banners. They can be put back in if the bar's not yet met. 98.19.57.54 (talk) 08:16, 27 May 2015 (UTC)

Algorithm sources

The algorithms on this page have no attribution or citations. Does anyone know where they came from? What reference was used? I've added some maintenance tags until these questions are resolved. Lucas "nicatronTg" Nicodemus (talk) 22:28, 19 November 2015 (UTC)

@NicatronTg: The article cites this paper, though this section has no citations yet. Jarble (talk) 19:08, 14 February 2019 (UTC)