Stack Overflow
Stack Overflow

Questions tagged [left-recursion]

A special kind of recursion, defined through a particular grammar property: grammar is left-recursive if we can find some non-terminal A which will eventually derive a sentential form with itself as the left-symbol.

Left-recursive grammar can be immediate or indirect:

Immediate left recursion

Immediate left recursion occurs in rules of the form

A → Aa | b

where a and b are sequences of nonterminals and terminals, and b doesn't start with A. For example, the rule

Expr → Expr + Term

is immediately left-recursive.

Indirect left recursion

Indirect left recursion in its simplest form could be defined as:

A → Ba | C
B → Ab | D

possibly giving the derivation A ⇒ Ba ⇒ Aba ⇒ ...

More generally, for the nonterminals A0, A1, ..., An, indirect left recursion can be defined as being of the form:

A0 → A1a_1 | ...
A1 → A2a_2 | ...
...
An → A0a_n+1 | ...

where a_1, a_2, ..., a_n are sequences of nonterminals and terminals.

Source: Wikipedia

179 questions
19
votes
4 answers

Why can't a LL grammar be left-recursive?

In the dragon book, LL grammar is defined as follows: A grammar is LL if and only if for any production A -> a|b, the following two conditions apply. FIRST(a) and FIRST(b) are disjoint. This implies that they cannot both derive EMPTY If b can…
wangshuaijie
  • 1,821
  • 3
  • 21
  • 37
14
votes
2 answers

Step by step elimination of this indirect left recursion

I've seen this algorithm one should be able to use to remove all left recursion. Yet I'm running into problems with this particular grammar: A -> Cd B -> Ce C -> A | B | f Whatever I try I end up in loops or with a grammar that is still indirect…
Flion
  • 10,468
  • 13
  • 48
  • 68
13
votes
1 answer

Expression parser grammar and left-associativity

I have been trying create my parser for expression with variables and simplify them to quadratic expression form. This is my parser grammar: Exercise : Expr '=' Expr Expr : Term [+-] Expr | Term Term : Factor [*/] Term | Factor Factor: Atom [^]…
Martin Bodocky
  • 651
  • 1
  • 5
  • 16
8
votes
1 answer

Left Associativity vs Left Recursion

I'm trying to write a compiler for C (simpler grammar though). There is something that I've been stuck on for a while. If I understated correctly, all binary operations are left associative. So if we have we "x+y+z", x+y occurs first and then…
Babak
  • 497
  • 1
  • 7
  • 15
8
votes
2 answers

Left recursion parsing

Description: While reading Compiler Design in C book I came across the following rules to describe a context-free grammar: a grammar that recognizes a list of one or more statements, each of which is an arithmetic expression followed by a…
Algo
  • 841
  • 1
  • 14
  • 26
7
votes
1 answer

Help with left factoring a grammar to remove left recursion

I have a small custom scripting language, and I am trying to update it to allow boolean expressions such as a > 2 and a > 2 and (b < 3 or c > 5). It's the parenthetical expressions that I am having trouble with here. Here is a (edited since the…
Chris Farmer
  • 24,974
  • 34
  • 121
  • 164
7
votes
1 answer

Removing Left Recursion in a Basic Expression Parser

As an exercise, I'm implementing a parser for an exceedingly simple language defined in Haskell using the following GADT (the real grammar for my project involves many more expressions, but this extract is sufficient for the question): data Expr a…
user3594595
6
votes
1 answer

How to deal with Treetop left-recursion

I have a grammar file for a new general-purpose programming language I'm trying to build. I'm trying to make the language robust and natural to use (it is heavily inspired by Ruby, among others), and in doing so I have introduced some left-recursive…
ravinggenius
  • 816
  • 1
  • 6
  • 14
6
votes
2 answers

How best to parse a comma separate list in PEG grammar

I'm trying to parse a comma separated list. To simplify, I'm just using digits. These expressions would be valid: (1, 4, 3) () (4) I can think of two ways to do this and I'm wondering why exactly the failed example does not work. I believe it is a…
Leon Starr
  • 480
  • 1
  • 4
  • 10
6
votes
2 answers

Why do right recursive parsers not loop infinitely?

Left recursion will make the parser go into an infinite loop. So why does the same not happen with right recursion?
Shraddha
  • 79
  • 3
6
votes
2 answers

How to avoid mutual left-recursion in ANTLR 4

I am writing a grammar to handle scalar and vector expressions. The grammar below is simplified to show the problem I have where a scalar expression can be derived from a vector and a vector can be derived from a scalar. For example, a vector could…
Rangi Keen
  • 935
  • 9
  • 29
6
votes
4 answers

Removing left recursion in DCG - Prolog

I've got a small problem with left recursion in this grammar. I'm trying to write it in Prolog, but I don't know how to remove left recursion. -> -> …
Finley Osbert
  • 103
  • 2
  • 8
5
votes
1 answer

Solving antlr left recursion

I'm trying to parse a language using ANTLR which can contain the following syntax: someVariable, somVariable.someMember, functionCall(param).someMember, foo.bar.baz(bjork).buffalo().xyzzy This is the ANTLR grammar which i've come up with so far,…
pulse00
  • 1,294
  • 1
  • 16
  • 25
5
votes
2 answers

Remove Ambiguity in abstract syntax in other to write DCG parser Prolog

P => Program K => Block S => Single-command C => Commands E => Expression B => Boolean-expr I => Identifier N > Numeral P ::= K. K ::= begin C end C ::= C1 ; C2 | S S ::= I := E | if (B) then S | if (B) then S1 else S2 | while (B) do S | repeat C…
cgadjoro
  • 127
  • 1
  • 7
5
votes
1 answer

how to remove left-recursion

I'd like to make a grammar that will allow curried function calls. That is: a() /// good a()() /// good a()()() /// good a(a) /// good a(a()()) /// good /// etc My first stab was this: ID : ('a'..'z'|'A'..'Z'|'_')…
Aaron Yodaiken
  • 19,163
  • 32
  • 103
  • 184
1
2 3
…
11 12