Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [left-recursion]

The tag has no usage guidance.

0
votes
0answers
45 views

Creating a grammar for a a language for instructions, with repititions

I have a language that consists of instructions for movement on a 2D-plane. You start at coordinate [0,0] The instructions DOWN 1 UP 10 LEFT 5 RIGHT 1 means you ...
1
vote
1answer
50 views

Can there still be infinite recursion if I remove all left recursion?

I have to transform the following grammar into a non left recursive grammar: S → aSb | bAS A → AaA | bAA | AAa | bAb This is what I came up with: A → bAAA’| bAbA’ A’ → aAA’| AaA’| ε S → aSb | ...
2
votes
1answer
137 views

Conversion of ambiguous left recursive grammar to LL(1)

I have been strugling with this LL(1) transformation for far longer than expected and am getting quite desperate. We are given a grammar $ G = \left\{V_N, V_T, S, \Phi \right\}$, with the non-terminal ...
1
vote
0answers
78 views

Where is left recursion in this little CF grammar?

S → D D → E | EC E → anyId C → B | .D | B.D B → <S> | <SA> A → ,S | ,SA The tool I am using keeps complaining about left recursion in this grammar. I ...
3
votes
3answers
2k views

Why not use Right Recursion to avoid Left Recursion?

I am reading about Representative Grammars from book, where I encountered the following grammar: $$ E \rightarrow E + T \ | \ T $$ $$ T \rightarrow T * F \ | \ F $$ $$ F \rightarrow (E) \ | \ id$$ ...
1
vote
1answer
163 views

Converting indirect recursion to direct one

I want to remove left recursion in grammar: $G = ({S, A,B,C,D}, {a,b,c},P,S)$ $S → A$ $A → Aa | Bc$ $B → B a |CD$ $C →C b | ε$ $D → Bb | a$ We see that this grammar contains direct recursion ( $...
2
votes
1answer
82 views

Explanation of Grammar Ambiguity

Consider now the grammar G S -> (S + S) S -> (S * S) S -> a Is it ambiguous? Answer: No because there are disambiguating parentheses and so no left or right recursion. Can someone explain how the ...
4
votes
0answers
465 views

How does this left-associative recursive descent parser work?

For personal enlightenment, I'm trying to write a recursive descent parser for lambda calculus without abstraction, i.e., just identifiers and function application. The BNF grammar that describes the ...
0
votes
1answer
1k views

Need to remove indirect left recursion from CFG

I need to remove indirect left recursion from the following CFG: remove indirect left recursion from the following CFG. $$A → Ba| b$$ $$B → Cd | e$$ $$C → Df | g$$ $$D → Df | Aa | Cg$$ In the ...
2
votes
1answer
317 views

Can I remove left recursion on this grammar

$S \rightarrow Sa \mid S \mid \epsilon$ This is a weird case where I have only one non-terminal. I'm trying to apply the algorithm 4.19 in the dragon book. It don't think it should be applicable but ...
0
votes
2answers
236 views

Transform grammar for repeating characters into LL(1)

I have the following simple production rule: S -> Sa | a Which is left-recursive, and can recognize strings such as a or aa, etc I tried to make it right-recursive, but I cannot find a way ...
-1
votes
1answer
1k views

Eliminating left recursion and left factoring this grammar

I have a grammar S-> SS* | SS+ | a Really confused on how to remove the left recursion and do left factoring My attempt on removing left recursion : S -> aS' S' -> S+S' | S*S' | epsilon If this is ...
1
vote
1answer
757 views

Indirect Left recursion

I'm solving (indirect Left Recursion) for these production rules . S is the starting symbol. S -> Aa / a eq1 A -> Sb / b. eq2 Now I can do this in two ...
1
vote
0answers
39 views

Am I allowed to remove left recursion like this?

I have: <A> -> <B> <C> <D> <D> -> <D> <C> <D> -> lambda Since ...
-1
votes
1answer
112 views

Eliminate Left Recursion

The part I want to modify: B -> F | B A | A What is the correct way to remove this left recursion? I was thinking ...
1
vote
1answer
847 views

Removing Left Recursion

Im currently learning about removing left recursion. Ive watched a few youtube clips and understand the basics. For example, i can remove left recursion for the following; $E \rightarrow E+T \mid T$ ...
2
votes
0answers
555 views

Removing hidden ambiguity in grammar using left factoring

I am trying to reduce the grammar to LL(1) for a hypothetical language we created. I have removed most of the left factoring issues in the grammar, using the general rule of introducing new non-...
1
vote
1answer
157 views

Resolve left-rescursion

Can anybody give me a hint on how to get rid of the left recursion in the following grammar? $$A \rightarrow B \mid a$$ $$B \rightarrow b \mid C \mid D \mid E \mid F \mid G$$ $$C \rightarrow c \mid A ...
4
votes
0answers
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
1answer
247 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 ...
-1
votes
1answer
235 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 <...
2
votes
2answers
292 views

What type of recursion is this?

I was trying to rule out whether this was LL(1) by checking for left-recursion in the following grammar: $\qquad A \to 0 A 1 \mid 0 1$ Which produces: $\qquad 0 A 1 \Rightarrow 0 0 A 1 1 \...
0
votes
1answer
289 views

Eliminating $\varepsilon$-productions during elimination of left recursion

I'm following the algorithm for left recursion elimination from a grammar. It says remove the epsilon production if there is any. I have the grammar $\qquad S \to Aa \mid b$ $\qquad A \to Ac \mid Sd ...
2
votes
2answers
1k 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 ...
19
votes
4answers
13k 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?
3
votes
1answer
166 views

LL grammars and left-recursiviity

Why LL(k) and LL(∞) are incompatible with left-recursion? I understand that a LL(k) language can support left-recursivity provided that with k-overahead tokens can be resolved any ambiguity. But, with ...
3
votes
2answers
199 views

How to modify semantic actions when removing left-recursion from a grammer

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 \...
5
votes
1answer
11k 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
2answers
1k 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 ...
8
votes
1answer
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: ...
7
votes
1answer
16k 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
1answer
8k 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$ ...