This is the
talk page for discussing improvements to the
Left recursion article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||||||||||||||
|
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.)
193.253.60.213 15:24, 28 June 2007 (UTC)
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 derive a sentential form starting with . The problem is that is [0], so if we start by deriving from , we may now derive , because from 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 "-case" ?
(Note : I think the sections on removing left recursion might also have to be altered to take into account.)
[0] Nullable in the sense of Modern Compiler Implementation in ML, First Edition, Andrew Appel, 1998, ISBN 0-521-58274-1 : is true if can derive the empty string.
StefanLjungstrand 85.224.18.100 11:08, 30 June 2007 (UTC)
It is not always necessary to remove -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)
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)
Lots of the math formatting needs to be fixed. I did two sections so far. In general, the problems are as follows:
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)
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)
This is the
talk page for discussing improvements to the
Left recursion article. This is not a forum for general discussion of the article's subject. |
Article policies
|
Find sources: Google ( books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||||||||||||||
|
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.)
193.253.60.213 15:24, 28 June 2007 (UTC)
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 derive a sentential form starting with . The problem is that is [0], so if we start by deriving from , we may now derive , because from 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 "-case" ?
(Note : I think the sections on removing left recursion might also have to be altered to take into account.)
[0] Nullable in the sense of Modern Compiler Implementation in ML, First Edition, Andrew Appel, 1998, ISBN 0-521-58274-1 : is true if can derive the empty string.
StefanLjungstrand 85.224.18.100 11:08, 30 June 2007 (UTC)
It is not always necessary to remove -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)
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)
Lots of the math formatting needs to be fixed. I did two sections so far. In general, the problems are as follows:
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)
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)