Left recursion
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, can be recognized as a sum because it can be broken into , also a sum, and , a suitable suffix.
- Comment
- enIn 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, can be recognized as a sum because it can be broken into , also a sum, and , a suitable suffix.
- Depiction
- Has abstract
- enIn 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, can be recognized as a sum because it can be broken into , also a sum, and , 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).
- Is primary topic of
- Left recursion
- Label
- enLeft recursion
- Link from a Wikipage to an external page
- lambda.uta.edu/cse5317/notes/node21.html
- Link from a Wikipage to another Wikipage
- Ambiguous grammar
- Bottom-up parsing
- Category:Control flow
- Category:Formal languages
- Category:Parsing
- Category:Recursion
- Computer science
- Context-free grammar
- CYK algorithm
- Empty string
- File:Left-recursive-parse-of-a-double-subtraction.png
- File:Right-recursive-parse-of-a-double-subtraction.png
- Formal grammar
- Formal language theory
- Haskell (programming language)
- LALR parser
- LL parser
- Parse
- Parser combinator
- Parse tree
- Parsing
- Polynomial
- Recursion (computer science)
- Recursive descent parser
- Rewriting
- Right recursion
- Tail recursion
- Terminal and nonterminal symbols
- Top-down parsing
- Topological ordering
- Weak equivalence (formal languages)
- Witness (mathematics)
- SameAs
- 2tSQF
- Left recursion
- Levá rekurze
- Leva rekurzija
- Lijeva rekurzija
- m.04 yrw
- Q3121428
- Q54874560
- Récursivité gauche
- الاستدعاء الذاتي الايسر
- العودية اليسرى
- بازگشت چپ
- 左再帰
- 左遞歸
- Subject
- Category:Control flow
- Category:Formal languages
- Category:Parsing
- Category:Recursion
- Thumbnail
- WasDerivedFrom
- Left recursion?oldid=1122914473&ns=0
- WikiPageLength
- 11729
- Wikipage page ID
- 1418498
- Wikipage revision ID
- 1122914473
- WikiPageUsesTemplate
- Template:Citation needed
- Template:Clarify
- Template:Technical
