# Questions tagged [left-recursion]

The tag has no usage guidance.

44 questions
Filter by
Sorted by
Tagged with
1 vote
89 views

### How would this grammar be converted to a non-left recursive rule?

With recursive-descent parsing, direct/indirect left recursive rules do not allow top-down parsing. How would this grammar be converted to be non-left recursive? ...
30 views

### First Set for this grammar? Is it Indirect Left-recursive

Given the grammar (Uppercase alphabet is non-terminal, lower-case alphabet is terminal), how to find FIRST set? A -> mB | CD B -> CBn | epsilon C -> pA | epsilon D -> q This is NOT a ...
638 views

### Remove left recursion from a grammar without necessarily removing epsilon production

Consider the grammar $$S →Aa∣b$$ $$A →Ac∣Sd∣ϵ$$ Construct an equivalent grammar with no left recursion and with minimum number of production rules. $\tag {GATE-CS-1998}$ While solving this question, ...
1 vote
108 views

1k views

### Automatic tool for resolving left-recursion within CFG [closed]

Though facing the fear that someone might not like my question but does somebody know a useful tool to either resolve left recursion or to simplify a context-free grammar automatically ? I need to ...
1 vote
468 views

### Why does left recursion have to be eliminated? [closed]

For example, Let the Grammar be: S->Sa|B Thus, S->Sa->Saa->...->Saa...aaa->Baa...aaa What's wrong with ...
780 views

### Left recursion for LL(1) [closed]

Hi I am trying to solve a LL(1) form question for first n follow rule The question is A::=BC|C B::=Bd|ef C::=gh|j What I have done to eliminate left recursion <...
1 vote
450 views

2k views

### Need solution for infinite right recursive grammar in Predictive parsing?

i am new to compiler design, currently studying Ullmans book on this.He says: Problem with predictive parsing (both recursive and non recursive) is that Left recursive productions can go infinite ...
19k views

### Why is left recursion bad?

In compiler design, why should left recursion be eliminated in grammars? I am reading that it is because it can cause an infinite recursion, but is it not true for a right recursive grammar as well? Is there any algorithm that tells us how to modify semantic actions associated with a left-recursive grammar? For example, we have the following grammar, and its associated semantic actions: $S \... 8 votes 1 answer 16k views ### Left-Factoring a grammar into LL(1) I have a homework assignment where I need to convert a grammar into LL(1). I've already removed the left recursion, but I'm having trouble doing left-factoring. All of the examples I've found are ... 1 vote 2 answers 2k views ### LL(1) parsing table of left-recursive grammar I have been taking a compiler course of Stanford on coursera. I have a slight misunderstanding on the parsing table of the following grammar: S -> Sa | b According to the professor parsing table ... 9 votes 1 answer 1k views ### Arithmetic expressions grammar transformation In the article Parsing Expressions by Recursive Descent by Theodore Norvell (1999) the author starts with the following grammar for arithmetic expressions: ... 9 votes 1 answer 20k views ### Left recursion and left factoring -- which one goes first? if I have a grammar having a production that contains both left recursion and left factoring like$\qquad \displaystyle F \to FBa \mid cDS \mid c$which one has priority, left recursion or left ... 4 votes 1 answer 9k views ### Removing Left Recursion from Context-Free Grammars - Ordering of nonterminals I have recently implemented the Paull's algorithm for removing left-recursion from context-free grammars: Assign an ordering$A_1, \dots, A_n$to the nonterminals of the grammar. for$i := 1$to$n\$ ... 