Left recursion

Short description: Theory of computer sciences

This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (November 2015) (Learn how and when to remove this template message)

|

In the formal language theory of computer science, left recursion is a special case of recursion where a string is recognized as part of a language by the fact that it decomposes into a string from that same language (on the left) and a suffix (on the right). For instance, 1+2+3 can be recognized as a sum because it can be broken into 1+2, also a sum, and +3, a suitable suffix.

In terms of context-free grammar, a nonterminal is left-recursive if the leftmost symbol in one of its productions is itself (in the case of direct left recursion) or can be made itself by some sequence of substitutions (in the case of indirect left recursion).

## Contents

* 1 Definition
* 1.1 Direct left recursion
* 1.2 Indirect left recursion
* 2 Uses
* 3 Removing left recursion
* 3.1 Removing direct left recursion
* 3.2 Removing all left recursion
* 4 Pitfalls
* 5 Accommodating left recursion in top-down parsing
* 6 See also
* 7 References
* 8 External links

## Definition

A grammar is left-recursive if and only if there exists a nonterminal symbol A that can derive to a sentential form with itself as the leftmost symbol.[1] Symbolically,

A⇒+Aα,

where ⇒+ indicates the operation of making one or more substitutions, and α is any sequence of terminal and nonterminal symbols.

### Direct left recursion

Direct left recursion occurs when the definition can be satisfied with only one substitution. It requires a rule of the form

A->Aα

where α is a sequence of nonterminals and terminals . For example, the rule

Expression->Expression+Term

is directly left-recursive. A left-to-right recursive descent parser for this rule might look like

void Expression() {
Expression();
match('+');
Term();

and such code would fall into infinite recursion when executed.

### Indirect left recursion

Indirect left recursion occurs when the definition of left recursion is satisfied via several substitutions. It entails a set of rules following the pattern

A0->β0A1α0
A1->β1A2α1

An->βnA0αn

where β0,β1,…,βn are sequences that can each yield the empty string, while α0,α1,…,αn may be any sequences of terminal and nonterminal symbols at all. Note that these sequences may be empty. The derivation

A0⇒β0A1α0⇒+A1α0⇒β1A2α1α0⇒+⋯⇒+A0αn…α1α0

then gives A0 as leftmost in its final sentential form.

## Uses

Left recursion is commonly used as an idiom for making operations left-associative: that an expression `a+b-c-d+e` is evaluated as `(((a+b)-c)-d)+e`. In this case, that evaluation order could be achieved as a matter of syntax via the three grammatical rules

Expression->Term
Expression->Expression+Term
Expression->Expression−Term

These only allow parsing the Expression `a+b-c-d+e` as consisting of the Expression `a+b-c-d` and Term `e`, where `a+b-c-d` in turn consists of the Expression `a+b-c` and Term `d`, while `a+b-c` consists of the Expression `a+b` and Term `c`, etc.

## Removing left recursion

Left recursion often poses problems for parsers, either because it leads them into infinite recursion (as in the case of most top-down parsers) or because they expect rules in a normal form that forbids it (as in the case of many bottom-up parsers[clarification needed]). Therefore, a grammar is often preprocessed to eliminate the left recursion.

### Removing direct left recursion

The general algorithm to remove direct left recursion follows. Several improvements to this method have been made.[2] For a left-recursive nonterminal A, discard any rules of the form A->A and consider those that remain:

A->Aα1∣…∣Aαn∣β1∣…∣βm

where:

* each α is a nonempty sequence of nonterminals and terminals, and
* each β is a sequence of nonterminals and terminals that does not start with A.

Replace these with two sets of productions, one set for A:

A->β1A′∣…∣βmA′

and another set for the fresh nonterminal A′ (often called the "tail" or the "rest"):

A′->α1A′∣…∣αnA′∣ϵ

Repeat this process until no direct left recursion remains.

As an example, consider the rule set

Expression->Expression+Expression∣Integer∣String

This could be rewritten to avoid left recursion as

Expression->IntegerExpression′∣StringExpression′
Expression′->+ExpressionExpression′∣ϵ

### Removing all left recursion

The above process can be extended to eliminate all left recursion, by first converting indirect left recursion to direct left recursion on the highest numbered nonterminal in a cycle.

Inputs A grammar: a set of nonterminals A1,…,An and their productions
Output A modified grammar generating the same language but without left recursion

1. For each nonterminal Ai:
1. Repeat until an iteration leaves the grammar unchanged:
1. For each rule Ai->αi, the αi being a sequence of terminals and nonterminals:
1. If αi begins with a nonterminal Aj and j<i:
1. Let βi be αi without its leading Aj.
2. Remove the rule Ai->αi.
3. For each rule Aj->αj:
1. Add the rule Ai->αjβi.
2. Remove direct left recursion for Ai as described above.

Step 1.1.1 amounts to expanding the initial nonterminal Aj in the right hand side of some rule Ai->Ajβ, but only if j<i. If Ai->Ajβ was one step in a cycle of productions giving rise to a left recursion, then this has shortened that cycle by one step, but often at the price of increasing the number of rules.

The algorithm may be viewed as establishing a topological ordering on nonterminals: afterwards there can only be a rule Ai->Ajβ if j>i. Note that this algorithm is highly sensitive to the nonterminal ordering; optimizations often focus on choosing this ordering well.[clarification needed]

## Pitfalls

Although the above transformations preserve the language generated by a grammar, they may change the parse trees that witness strings' recognition. With suitable bookkeeping, tree rewriting can recover the originals, but if this step is omitted, the differences may change the semantics of a parse.

Associativity is particularly vulnerable; left-associative operators typically appear in right-associative-like arrangements under the new grammar. For example, starting with this grammar:

Expression->Expression−Term∣Term
Term->Term*Factor∣Factor
Factor->(Expression)∣Integer

the standard transformations to remove left recursion yield the following:

Expression->Term Expression′
Expression′->−Term Expression′∣ϵ
Term->Factor Term′
Term′->*Factor Term′∣ϵ
Factor->(Expression)∣Integer

Parsing the string "1 - 2 - 3" with the first grammar in an LALR parser (which can handle left-recursive grammars) would have resulted in the parse tree:

Left-recursive parsing of a double subtraction

This parse tree groups the terms on the left, giving the correct semantics (1 - 2) - 3.

Parsing with the second grammar gives

Right-recursive parsing of a double subtraction

which, properly interpreted, signifies 1 + (-2 + (-3)), also correct, but less faithful to the input and much harder to implement for some operators. Notice how terms to the right appear deeper in the tree, much as a right-recursive grammar would arrange them for 1 - (2 - 3).

## Accommodating left recursion in top-down parsing

A formal grammar that contains left recursion cannot be parsed by a LL(k)-parser or other naive recursive descent parser unless it is 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, more sophisticated top-down parsers can implement general context-free grammars by use of curtailment. In 2006, Frost and Hafiz described an algorithm which accommodates ambiguous grammars with direct left-recursive production rules.[3] 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.[4] The authors then implemented the algorithm as a set of parser combinators written in the Haskell programming language.[5]

## See also

* Tail recursion

## References

1. ↑ "Notes on Formal Language Theory and Parsing". http://www.cs.nuim.ie/~jpower/Courses/parsing/parsing.pdf. . James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.JPR02
2. ↑ Moore, Robert C. (May 2000). "Removing Left Recursion from Context-Free Grammars". 6th Applied Natural Language Processing Conference: 249–255. https://www.microsoft.com/en-us/research/wp-content/uploads/2000/04/naacl2k-proc-rev.pdf.
3. ↑ Frost, R.; R. Hafiz (2006). "A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time.". ACM SIGPLAN Notices 41 (5): 46–54. doi:10.1145/1149982.1149988. http://portal.acm.org/citation.cfm?id=1149988. , available from the author at http://hafiz.myweb.cs.uwindsor.ca/pub/p46-frost.pdf
4. ↑ Frost, R.; R. Hafiz; P. Callaghan (June 2007). "Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars.". 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE: 109–120. http://acl.ldc.upenn.edu/W/W07/W07-2215.pdf.
5. ↑ Frost, R.; R. Hafiz; P. Callaghan (January 2008). "Parser Combinators for Ambiguous Left-Recursive Grammars". Practical Aspects of Declarative Languages. Lecture Notes in Computer Science. 4902. pp. 167–181. doi:10.1007/978-3-540-77442-6_12. ISBN 978-3-540-77441-9. https://cs.uwindsor.ca/~richard/PUBLICATIONS/PADL_08.pdf.

## External links

* Practical Considerations for LALR(1) Grammars

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Left recursion. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Left_recursion&oldid=4229392"