Questions tagged [left-recursion]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
21 views

Turning grammar to LL(1)

I have difficulty / doubt in transforming a grammar into LL (1), I tried remove left recursion but grammar still not LL(1). ...
0
votes
2answers
33 views

removing indirect left recursion

I want to remove indirect left recursion from these rules: S-->TU, T-->US|b, U-->ST|a I don't know if I can implement the algorithm correctly. ...
0
votes
0answers
35 views

Handling left recursion without left factoring with stateful parser combinators

Consider the language of simple types $$ T \mapsto B \ \mid\ T \rightarrow T \\ B \mapsto \text{Bool} \ \mid\ \text{Int} $$ where $\mapsto$ stands for productions to avoid ambiguity with the ...
0
votes
0answers
30 views

Is this correct transformation of a grammar to one without left recursion?

So the last few days I am writing a compiler for a subset of C language by given grammar for a class at university. I encountered this problem and then I realized I need to remove left-recursion in my ...
0
votes
1answer
134 views

How to convert the left recursive grammar into right recursive grammar

I have a grammar: $A\rightarrow Aa|bB|c$ The above is the left recursive grammar. I understand that I have to remove the string "Aa" from the above grammar or to convert it into the form "aA" to ...
0
votes
0answers
69 views

Conversion of left-recursive context-free grammars to strongly equivalent ones without left-recursion

It is a well-known problem that many top-down parsers have problems parsing a context-free grammar with left recursive rules. There exist algorithms to convert grammars with direct or indirect left-...
0
votes
0answers
56 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
74 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
189 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
85 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$$ ...
8
votes
2answers
1k views
1
vote
1answer
230 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
90 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
552 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
2k 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
381 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
325 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
2answers
2k 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 ...
2
votes
1answer
985 views

Indirect Left recursion

I'm resolving indirect left recursion for these production rules: S -> Aa / a eq1 A -> Sb / b. eq2 Where S is the ...
1
vote
0answers
41 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
122 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
1k 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
621 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
158 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
341 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
441 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
327 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
357 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 ...
21
votes
4answers
15k 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
169 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
241 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 \...
8
votes
1answer
13k 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 ...
9
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: ...
8
votes
1answer
18k 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$ to $n$ ...