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 loop.Thus, to make grammar suitable for predictive parsing we need to eliminate the left recursion by immediately or indirectly.

E -> E+T|t

My problem is, same can happen with right recursion also.What is the solution for it?

T -> E+T|t

Please correct me if i am wrong! thanks.

• Cross-posted to tcs.se Please do not do this: it is strongly discouraged because it fragments answers and wastes people's time when they answer a question that has already been answered somewhere else. – David Richerby Jan 11 '14 at 13:39
• you are parsing left-to-right ... hence left recursion can be a problem. If you were parsing right-to-left, then right recursion might be a problem, if it is in the grammar. Then, there are other parsing techniques that are not bothered by left recursion, even from left to right. – babou Apr 12 '14 at 16:33

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
else syntax_error

With this, the recursion will stop when the look ahead contains t.

With left recursion T -> T + E | t, you are in trouble because first(T) always contains t.

Conversion of left- to right recursion solves one problem but creates another. Right-recursive rules have the disadvantage that parsing lists requires stack space proportional to list length. Ideally you'd like the space a parser takes to be limited by a constant. So what to do?

The practical way to prevent many cases of right-recursion is to extend grammars to allow for iteration. In your case

T -> E + T | t

would become

T -> E + { E + } t

The curly braces denote "0 or more".

When the parser is implemented, the curly braces would become a while loop that uses the look ahead to decide whether to parse another instance of what's in the braces. With your example, you'd need first(E) not to contain terminal t.

A more common example is the standard expression grammar:

Expr -> Term { '+' Term }
Term -> Factor { '*' Factor }
Factor -> '0' | '(' Expr ')'

In this case, the recursive descent procedure for Expr would be

def Expr
Term
while look_ahead == '+'
Term

If we didn't have the curly braces, the grammar would have to be:

Expr -> Term ExprTail
ExprTail -> '+' Term ExprTail | \eps
Term -> Factor TermTail
TermTail -> '*' Factor TermTail | \eps
Factor -> '0' | '(' Expr ')'

To parse Exprs we now need two procedures:

def Expr
Term
ExprTail

def ExprTail
if look_ahead == '+'
Term
ExprTail

Interestingly, if you use a good compiler to compile both versions with optimizations turned on, it will detect tail recursion in ExprTail, convert it into a loop, and then in-line the loop in Expr. The resulting compiled codes will be exactly the same.

Left recursion is not supported by LL(k) parsers. They cannot generate a parse tree. So as you see, the real problem is the left recursion itself and not the ability to go infinite.

Why the infinity does not bother us? Here is a proof of mine:

In Computer Science, and generally in machines, infinity does not exist.

If you have a language with recursion, you could only achieve infinity in parsing only of you have a program of infinite (well formed) commands. In order to have such a program, you have to write it for infinite amount of time. Infinite does not stop. So you will never parse the infinite program. ;)

• Sure, everything is finite ... but if you do not know how finite ... it does not help you much. Useful recursions always stop, but the whole lot of them, globally amounts to an infinite situation (well, I am trying hard no to talk of limits). – babou Apr 12 '14 at 16:38
• My point is to make the OP understand the it's not the infinity that is our problem. As you said other parsing techniques perform better with left recursion. It's all about the particularities and the oddities of each technique. (Off Topic: By the way I read the history of babou in your profile. In greek, grandpa is papou (παππού) in latin characters. The Bs are reflected and seen as Ps :P) – gon1332 Apr 12 '14 at 16:45