# Tag Info

## Hot answers tagged left-recursion

11

It is just an LL(1) parser implemented with recursive descent. Starts with: AdditionExpression ::= MultiplicationExpression | AdditionExpression '+' MultiplicationExpression | AdditionExpression '-' MultiplicationExpression apply left-recursion removal to get an LL(1) grammar: AdditionExpression ::= MultiplicationExpression ...

6

(I know this question's pretty old by now, but in case other people have the same question...) Are you asking in the context of recursive descent parsers? For example, for the grammar expr:: = expr + term | term, why something like this (left recursive): // expr:: = expr + term expr() { expr(); if (token == '+') { getNextToken(); } term();...

6

You want to look into LL($k$) parsing. The Wikipedia article is mostly useless, but it's basically recursive descent with $k$ symbols lookahead. There is also LL($*$) which permits unbounded lookahead. See here for a comprehensive overview on how powerful this class of parsers is.

6

The left recursive and the right recursive grammars describe the same language. But grammars do more than give the set of allowed strings in the language, they also give a structure to such strings and that structure is sometimes meaningful. Consider a+b+c; the structure implied by the left recursive grammar is {a+b}+c (I'm using braces and not parenthesis ...

5

Yes that is correct. Also you can safely remove $A\rightarrow A$ type of production rules. So the equivalent grammar is $S'\rightarrow aS'\ |\ \epsilon$. If you analyze carefully you will see that you are not applying Algorithm 4.19 at all. We are just removing left recursion where we have only immediate left recursion. Cycles are of the form $A\rightarrow ... 3 A grammar$G$is non-amgibuous if every word in$L(G)$has a unique parse tree. The simplest way to prove that your grammar non-ambiguous is to prove that$L(S + S),L(S * S),L(a)$are all distinct (here$L(\alpha)$is the set of all words that can be generated from the sentential expression$\alpha$); given this, an easy induction shows that$L(G)$is non-... 3 You should focus on trying to only modify productions that aren't "good". A production is "good" if it : Starts with a terminal, Is an epsilon production, or Is in the form A->B (followed by a series of terminals and non-terminals) and we can partially order the non-terminals so that A<B. We'd also have to do some extra checks if B being nullable. ... 3 You don't get infinite recursion with right recursive rules if the prediction sets for the rules are different. In the example T -> E + T | t, if the first set of E does not contain t (I am presuming t is a terminal), you are fine. The parsing procedure will be: def T if look_ahead is in first(E) E match ('+') T else if look_ahead == t ... 3 Let's construct an LL(1) grammar for the language$\mathscr{L}(a^+)$. Firstly, observe that all the production rules in this case must have one of two forms: $$A \to a\Gamma$$ or $$A \to \epsilon,$$ where$\Gamma$is a (possibly empty) sequence of non-terminals and the terminal 'a'. The first step would be adding the rule$S \to aS'$, since it's clear that ... 3 This explanatory part can be skipped : Non-terminal in a Context-Free Grammar can be interpreted as standing for the set of strings they generate (this is actually one standard interpretation of CF grammars as string set equations). For example$A \rightarrow C \mid D \mid a$may be read as a set equation$A = C \cup D \cup \{a\}$where$A$,$C$and$D$... 3 I am assuming that you are talking about context free grammars. There is no difference between the two grammars. They are a different representation of the same set. What do you mean by a problem? Left recursion is a problem for LL(k) parsers, but they can handle right recursion. LL(k) parsers are preferred because of they use less stack space and they ... 3 What is a name for ? There may be a name for that recursion, but then I would have forgotten it. It does not really matter. Call it central recursion or middle recursion if you will. And you can even define it simply : A recursive rule (or non-terminal) is said to be middle recursive iff it is recursive, but neither left recursive nor right recursive. ... 3 Yes, both your answers are correct. Note that the language under consideration is regular, see wikipedia. The first grammar is equivalent to this regular expression: $$r_1 = a(ba)^* \mid (ba)^+.$$ The second grammar is equivalent to this regular expression: $$r_2 = (ab)^+a \mid b(ab)^*a \mid a.$$ It's easy to prove those regexes generate equal languages$...

3

From Bison manual: "Any kind of sequence can be defined using either left recursion or right recursion, but you should always use left recursion, because it can parse a sequence of any number of elements with bounded stack space. Right recursion uses up space on the Bison stack in proportion to the number of elements in the sequence, because all the ...

2

This language is left-recursion If you try to derive using the first production, you will get some kind of infinite loop $S \rightarrow Sa \rightarrow Saa \rightarrow Saaa ... \rightarrow Saaa...aaa$ So it cannot be parsed using LL(1). As @Alex ten Brink said, you should change the grammar.

1

$$𝑆 → YX \ | \ Y \\ Y → Ab \ | \ b \\ X → ABX \ | \ AB \\ A → SB \ | \ BS \ | \ a \\ 𝐵 → 𝐴𝑆 \ | \ d$$ At first I say which rules have a left recursion, considering that the middle tree which is A(the one that A node is the root) has not called itself in its children from the beginning of the left of each child so there is no left recursion in tree ...

1

Your grammar captures the empty language. To see this, you need to use the definition of a language described by a context-free grammar. A context-free grammar is a tuple $(T,N,S,P)$, where $T$ is the set of terminals (a non-empty finite set), $N$ is the set of nonterminals (a non-empty finite set disjoint from $T$), $S \in N$ is the starting symbol, and $P$ ...

1

I don't want to do your homework, but the two insights that appear to solve it for me are: What the first rules $S \rightarrow SoS$ $S \rightarrow SlSr$ say is that whatever else $S$ can be rewritten to (which, in this case, is just $i$) can be followed by any number of occurrences of $oS$ and $lSr$ arbitrarily often. If we introduce a nonterminal for ...

1

You can use a grammar to recognize a language, but usually you want more: You want to know how a string was parsed. (That's why we want grammars that are unique, otherwise there are sentences that can be parsed in more than one way). Your changes don't change the language that is recognised, but they change the parse tree. If the sentence is a - b + c, ...

1

check this image the problem is explained

1

The "standard" pattern to eliminate the immediate left recursion would have been: B -> F B' | A B' B' -> ε | A B' I guess this is why you have been told your solution is not right. Nevertheless the information that your solution is incorrect is incorrect. Terms derivable from the original grammar fragment B -> F | B A | A are of the form (F|A)A*...

1

The fact confusing you might be, that the given grammar isn't left recursive at all and so nothing has to be done. To be left recursive there would have to be a nonterminal Symbol, that by a chain of productions results in a sequence of sybols starting with the same nonterminal. This is not true for A since after A -> B the only options available are A -...

1

The idea of the algorithm is to first find out which non-terminals can produce $\epsilon$, and then eliminate them in all possible ways. Finding out which non-terminals produce $\epsilon$. The idea here is to start with the set $X^{(0)}$ of non-terminals which have an $\epsilon$ production. We then construct the set $X^{(1)}$ which includes $X^{(0)}$ and ...

Only top voted, non community-wiki answers of a minimum length are eligible