Left recursion

From Wikipedia, the free encyclopedia

The introduction to this article provides insufficient context for those unfamiliar with the subject.
Please help improve the article with a good introductory style.

In computer science, left recursion is a special case of recursion.

In terms of context-free grammar, a non-terminal r is left-recursive if the left-most symbol in any of r’s ‘alternatives’ either immediately (direct left-recursive) or through some other non-terminal definitions (indirect/hidden left-recursive) rewrites to r again.

1 Definition
- 1.1 Immediate left recursion
- 1.2 Indirect left recursion
2 Accommodating Left Recursion in Top-down Parsing
3 Removing left recursion
- 3.1 Removing immediate left recursion
- 3.2 Removing indirect left recursion
4 Pitfalls
5 See also
6 References
7 External links

[edit] 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."^[1]

[edit] Immediate left recursion

Immediate left recursion occurs in rules of the form

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

Where $α$ and $β$ are sequences of nonterminals and terminals, and $β$ doesn't start with A.

Example : The rule

$Expr \rightarrow 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.

[edit] Indirect left recursion

Indirect left recursion in its simplest form could be defined as :

$A \rightarrow B\alpha\,|\,C$

$B \rightarrow A\beta\,|\,D$

Possibly giving the derivation $A \Rightarrow B\alpha \Rightarrow A\beta\alpha \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 \rightarrow A_1\alpha_1\,|...$

$A_1 \rightarrow A_2\alpha_2\,|...$

$...$

$A_n \rightarrow A_0\alpha_{(n+1)}\,|...$

Where $α 1,α 2,...,α n$ are sequences of nonterminals and terminals.

[edit] Accommodating Left Recursion in Top-down Parsing

A formal grammar that contains left recursion cannot be parsed by a naive recursive descent parser unless they are converted to a weakly equivalent right-recursive form. (In contrast, left recursion is preferred for LALR parsers because it results in lower stack usage than right 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 ^[2] . That algorithm was extended to a complete parsing algorithm to accommodate indirect as well as direct left-recursion in polynomial 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 ^[3]. 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 ^[4] by the above-mentioned authors, which was presented in PADL'08. The X-SAIGA site has more about the algorithms and implementation details.

[edit] Removing left recursion

[edit] 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" ^[5], written by Robert C. Moore.

For each rule of the form

Where :

A is a left-recursive nonterminal
$α$ is a sequence of nonterminals and terminals that is not null ( $\alpha \ne \epsilon$ )
$β$ is a sequence of nonterminals and terminals that does not start with A.

Replace the A-production by the production :

$A \rightarrow \beta_1A^\prime\, |\, ...\, |\, \beta_mA^\prime$

And create a new nonterminal

$A^\prime \rightarrow \epsilon\, |\, \alpha_1A^\prime\, |\, ...\, |\, \alpha_nA^\prime$

This newly created symbol is often called the "tail", or the "rest".

[edit] Removing indirect left recursion

If the grammar has no $ε$ -productions (no productions of the form $A \rightarrow ... | \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 \rightarrow \delta_1 | ... | \delta_k$

replace each production $A_i \rightarrow A_j \gamma$ by

$A_i \rightarrow \delta_1\gamma | ... | \delta_k\gamma$

remove direct left recursion for $A i$

}

[edit] 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 \rightarrow Expr\,+\,Term\,|\,Term$

$Term \rightarrow Term\,*\,Factor\,|\,Factor$

$Factor \rightarrow (Expr)\,|\,Int$

After having applied standard transformations to remove left-recursion, we have the following grammar :

$Expr \rightarrow Term\ Expr'$

$Expr' \rightarrow {} + Term\ Expr'\,|\,\epsilon$

$Term \rightarrow Factor\ Term'$

$Term' \rightarrow {} * Factor\ Term'\,|\,\epsilon$

$Factor \rightarrow (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    $ε$ 
                                                 |
                                                Int

We 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 the parser generator which associativity to force.

[edit] See also

tail recursion

[edit] References

^ Notes on Formal Language Theory and Parsing, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.JPR02
^ Frost, R. and Hafiz, R. (2006) "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.
^ Frost, R., Hafiz, R. and Callaghan, P. (2007) "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.
^ Frost, R., Hafiz, R. and Callaghan, P. (2008) "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.
^ Removing Left Recursion from Context-Free Grammars, Robert C. Moore, Microsoft Research, Redmond, WA, USA

[edit] 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
Practical Considerations for LALR(1) Grammars
X-SAIGA - eXecutable SpecificAtIons of GrAmmars

Categories: Parsing algorithms | Formal languages

Hidden categories: Wikipedia articles needing context | Wikipedia introduction cleanup

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Left recursion

From Wikipedia, the free encyclopedia

Contents

[edit] Definition

[edit] Immediate left recursion

[edit] Indirect left recursion

[edit] Accommodating Left Recursion in Top-down Parsing

[edit] Removing left recursion

[edit] Removing immediate left recursion

[edit] Removing indirect left recursion

[edit] Pitfalls

[edit] See also

[edit] References

[edit] External links

Views

Navigation

Interaction

Search

Languages