Talk:Left recursion

From Wikipedia, the free encyclopedia

	Philosophy Portal This article is within the scope of the WikiProject Philosophy, which collaborates on articles related to philosophy. To participate, you can edit this article or visit the project page for more details.
???	This article has not yet received a rating on the quality scale.
???	This article has not yet received an importance rating on the importance scale.
Additional information: Related task forces (core areas): Logic

[edit] 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)

[edit] 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

where α,β,γ 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α from A, we may now derive Aα, because from B we may derive ε, 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)