Questions tagged [left-recursion]
The left-recursion tag has no usage guidance.
44
questions
1
vote
1
answer
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?
...
- 11
0
votes
0
answers
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 ...
- 1
0
votes
1
answer
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,112
1
vote
1
answer
108
views
eliminate left recursion of below grammar
Please look at this grammar:
$$𝑆 → 𝑆𝐴𝐵 \ | \ 𝐴𝑏 \ | \ 𝑏 \\
𝐴 → 𝑆𝐵 \ | \ 𝑎 \ | \ 𝐵𝑆 \\
𝐵 → 𝐴𝑆 \ | \ d$$
I eliminated B from the grammar and it converted to:
$$ S → SAAS \ | SAd \ ...
- 75
2
votes
2
answers
135
views
Generating a recursive descent parser for grammar having Kleene star
From what I have been taught, I cannot use left-recursive, nondeterministic, or ambiguous grammars in recursive descent parsers. So, here is the grammar:
\begin{align}
&E \to E+T \mid T \\
&T \...
- 121
1
vote
1
answer
88
views
Would a parser for this left-recursive grammar require infinite input?
I am considering this left recursive language grammar production rule:
Expr = Expr, "a" ;
As a production rule, I believe that this can be used to ...
0
votes
0
answers
28
views
I am trying to design an LL(1) Parser that accepts T = {a, b *, +, ?, E, U, (, ) }
I am trying to design an LL(1) Parser that accepts regular notation where 'E' represents epsilon, and 'U' represents "or" like ' | '.
So far I made one that accepts T = { a, b, *, +, (, ), E}...
-2
votes
1
answer
92
views
Removing left recursion with terminals only
I have a grammar:
$G → id > id$
$| id < id$
$| G and id$
Does anybody know how I can do left recursive elimination on this one, when it doesn't have any extra non terminals?
- 109
0
votes
2
answers
161
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. ...
- 3
0
votes
1
answer
1k
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 ...
- 251
0
votes
0
answers
396
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-...
- 360
0
votes
0
answers
60
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
1
answer
156
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 | ...
- 13
3
votes
1
answer
377
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 ...
- 31
1
vote
0
answers
86
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 ...
4
votes
3
answers
4k
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$$
...
- 43
9
votes
2
answers
2k
views
Correct name for a recursive descent parser that uses loops to handle left recursion?
This grammar is left recursive:
...
- 91
1
vote
1
answer
317
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 ( $...
- 179
2
votes
1
answer
117
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 ...
- 23
6
votes
2
answers
1k
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 ...
- 103
1
vote
1
answer
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
1
answer
447
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
2
answers
571
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 ...
- 18
0
votes
2
answers
5k
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 ...
- 11
2
votes
1
answer
1k
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 ...
- 21
1
vote
0
answers
45
views
Am I allowed to remove left recursion like this?
I have:
<A> -> <B> <C> <D>
<D> -> <D> <C>
<D> -> lambda
Since ...
- 11
-1
votes
1
answer
152
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
1
answer
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$
...
- 11
2
votes
0
answers
723
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-...
- 21
1
vote
1
answer
168
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 ...
- 143
3
votes
0
answers
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 ...
- 143
1
vote
1
answer
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 ...
- 193
-1
votes
1
answer
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
<...
- 13
1
vote
2
answers
450
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 \...
- 167
0
votes
1
answer
476
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 ...
- 131
2
votes
2
answers
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 ...
- 214
22
votes
4
answers
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?
user56833
3
votes
1
answer
193
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 ...
- 457
3
votes
2
answers
431
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 \...
- 513
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 ...
- 183
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 ...
- 139
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:
...
- 290
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 ...
- 355
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$ ...
clebert