Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Left recursion
Summary
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.
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).
Formal language theory may come across as very difficult. Let's start off with a very simple example just to show the problem. If we take a look at the name of a former Dutch bank, VSB Bank, you will see something odd.
What do you think the B stands for? Bank. The same word again. How many banks are in this name?
Let's chop down the name in parts:
VSB Bank:
V = Verenigde (United)
S = Spaarbank (Savings Bank)
B = Bank
Bank.
Concluding: VSB Bank = Verenigde Spaarbank Bank Bank.
Now you see what a left recursive name abbreviation is all about. The remainder of this article is not using examples, but abstractions in the forms of symbols.
A grammar is left-recursive if and only if there exists a nonterminal symbol that can derive to a sentential form with itself as the leftmost symbol. Symbolically,
where indicates the operation of making one or more substitutions, and is any sequence of terminal and nonterminal symbols.
Direct left recursion occurs when the definition can be satisfied with only one substitution. It requires a rule of the form
where is a sequence of nonterminals and terminals . For example, the rule
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 occurs when the definition of left recursion is satisfied via several substitutions.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.