- Left recursion
In
computer science , left recursion is a special case ofrecursion .In terms of
context-free grammar , a non-terminalr
is left-recursive if the left-most symbol in any ofr
’s ‘alternatives’ either immediately (direct left-recursive) or through some other non-terminal definitions (indirect/hidden left-recursive) rewrites tor
again.Definition
"A grammar is left-recursive if we can find some non-terminal A which will eventually derive a
sentential form with itself as the left-symbol." [ [http://www.cs.may.ie/~jpower/Courses/parsing/parsing.pdf#search='indirect%20left%20recursion' Notes on Formal Language Theory and Parsing] , James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.JPR02 ]Immediate left recursion
Immediate left recursion occurs in rules of the form
A ightarrow Aalpha,|,eta
Where alpha and eta are sequences of nonterminals and terminals, and eta doesn't start with A.
Example : The rule
Expr ightarrow Expr,+,Term
is immediately left-recursive. The "
recursive descent parser " for this rule might look like ::"function Expr() { :" Expr(); match('+'); Term(); :"}and a recursive descent parser would fall into infinite recursion when trying to parse a grammar which contains this rule.Indirect left recursion
Indirect left recursion in its simplest form could be defined as :
A ightarrow Balpha,|,C
B ightarrow Aeta,|,D
Possibly giving the derivation A Rightarrow Balpha Rightarrow Aetaalpha Rightarrow ...
More generally, for the non-terminals A_0, A_1, ..., A_n, indirect left recursion can be defined as being of the form :
A_0 ightarrow A_1alpha_1,|...
A_1 ightarrow A_2alpha_2,|...
A_n ightarrow A_0alpha_{(n+1)},|...
Where alpha_1, alpha_2, ..., alpha_n are sequences of nonterminals and terminals.
Accommodating Left Recursion in Top-down Parsing
A
formal grammar that contains left recursion cannot be parsed by a naiverecursive descent parser unless it is converted to a weakly equivalent right-recursive form. (In contrast, left recursion is preferred forLALR parsers because it results in lower stack usage thanright recursion .) However, recent research demonstrates that it is possible to accommodate left-recursive grammars (along with all other forms of general CFGs) in a more sophisticated top-down parser by use of curtailment. A recognition algorithm which accommodates ambiguous grammars with direct left-recursive production rules is described by Frost and Hafiz in 2006 Frost, R. and Hafiz, R. (2006) [http://portal.acm.org/citation.cfm?id=1149988 "A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time."] "ACM SIGPLAN Notices", Volume 41 Issue 5, Pages: 46 - 54.] . That algorithm was extended to a completeparsing algorithm to accommodate indirect as well as direct left-recursion inpolynomial time, and to generate compact polynomial-size representations of the potentially-exponential number of parse trees for highly-ambiguous grammars by Frost, Hafiz and Callaghan in 2007 Frost, R., Hafiz, R. and Callaghan, P. (2007) [http://acl.ldc.upenn.edu/W/W07/W07-2215.pdf "Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars."] "10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE ", Pages: 109 - 120, June 2007, Prague. ] . The algorithm has since been implemented as a set of parser combinators written in the Haskell programming language. The implementation details of these new set of combinators can be found in a paper Frost, R., Hafiz, R. and Callaghan, P. (2008) [http://cs.uwindsor.ca/~hafiz/PADL_PAPER_FINAL.pdf "Parser Combinators for Ambiguous Left-Recursive Grammars."] " 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN ", Volume 4902/2008, Pages: 167-181, January 2008, San Francisco.] by the above-mentioned authors, which was presented in PADL'08.The [http://www.cs.uwindsor.ca/~hafiz/proHome.html X-SAIGA] site has more about the algorithms and implementation details.Removing left recursion
Removing immediate left recursion
The general algorithm to remove immediate left recursion follows. Several improvements to this method have been made, including the ones described in "Removing Left Recursion from Context-Free Grammars" [ [http://research.microsoft.com/users/bobmoore/naacl2k-proc-rev.pdf Removing Left Recursion from Context-Free Grammars] , Robert C. Moore, Microsoft Research, Redmond, WA, USA] , written by Robert C. Moore.
For each rule of the form
A ightarrow Aalpha_1,|,...,|,Aalpha_n,|,eta_1,|,...,|,eta_m
Where :
* A is a left-recursive nonterminal
* alpha is a sequence of nonterminals and terminals that is not null (alpha e epsilon )
* eta is a sequence of nonterminals and terminals that does not start with A.Replace the A-production by the production :
A ightarrow eta_1A^prime, |, ..., |, eta_mA^prime
And create a new nonterminal
A^prime ightarrow epsilon, |, alpha_1A^prime, |, ..., |, alpha_nA^prime
This newly created symbol is often called the "tail", or the "rest".
As an example, consider the rule
Expr ightarrow Expr,+,Expr,|,Int,|,String
This could be rewritten to avoid left recursion as
Expr ightarrow Int,ExprRest,|,String,ExprRest
ExprRest ightarrow epsilon,|,+,Expr,ExprRest
The last rule happens to be equivalent to the slightly shorter form
ExprRest ightarrow epsilon,|,+,Expr
Removing indirect left recursion
If the grammar has no epsilon-productions (no productions of the form A ightarrow ... | epsilon | ... ) and is not cyclic (no derivations of the form A Rightarrow ... Rightarrow A for any nonterminal A), this general algorithm may be applied to remove indirect left recursion :
Arrange the nonterminals in some (any) fixed order A_1, ... A_n.
: for i = 1 to n {::for j = 1 to i – 1 {:::* let the current A_j productions be:::A_j ightarrow delta_1 | ... | delta_k:::* replace each production A_i ightarrow A_j gamma by:::A_i ightarrow delta_1gamma | ... | delta_kgamma:::* remove direct left recursion for A_i::}:}
Pitfalls
The above transformations remove left-recursion by creating a right-recursive grammar; but this changes the associativity of our rules. Left recursion makes left associativity; right recursion makes right associativity.Example :We start out with a grammar :
Expr ightarrow Expr,+,Term,|,Term
Term ightarrow Term,*,Factor,|,Factor
Factor ightarrow (Expr),|,Int
After having applied standard transformations to remove left-recursion, we have the following grammar :
Expr ightarrow Term Expr'
Expr' ightarrow {} + Term Expr',|,epsilon
Term ightarrow Factor Term'
Term' ightarrow {} * Factor Term',|,epsilon
Factor ightarrow (Expr),|,Int
Parsing the string 'a + a + a' with the first grammar in an LALR parser (which can recognize left-recursive grammars) would have resulted in the parse tree: Expr / Expr + Term / | Expr + Term Factor
|
Term Factor Int
Factor Int
Int This parse tree grows to the left, indicating that the '+' operator is left associative, representing (a + a) + a.But now that we've changed the grammar, our parse tree looks like this : Expr --- / Term Expr' --
/ | Factor + Term Expr' ------
| | Int Factor + Term Expr'
|
Int Factor epsilon
IntWe can see that the tree grows to the right, representing a + ( a + a). We have changed the associativity of our operator '+', it is now right-associative. While this isn't a problem for the associativity of addition with addition it would have a significantly different value if this were subtraction.
The problem is that normal arithmetic requires left associativity. Several solutions are: (a) rewrite the grammar to be left recursive, or (b) rewrite the grammar with more nonterminals to force the correct precedence/associativity, or (c) if using
YACC or Bison, there are "operator declarations," %left, %right and %nonassoc, which tell theparser generator which associativity to force.See also
*
Tail recursion References
External links
* http://www.cs.may.ie/~jpower/Courses/parsing/parsing.pdf
* http://www.cs.umd.edu/class/fall2002/cmsc430/lec4.pdf
* http://www.wvutech.edu/mclark/Systems%20Programming/Removing%20Left%20Recursion.pdf
* [http://lambda.uta.edu/cse5317/notes/node21.html Practical Considerations for LALR(1) Grammars]
* [http://www.cs.uwindsor.ca/~hafiz/proHome.html X-SAIGA] - eXecutable SpecificAtIons of GrAmmars
Wikimedia Foundation. 2010.