Need solution for infinite right recursive grammar in Predictive parsing?

Question

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.

Answer 1

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
    advance_lookahead
  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 == '+'
    advance_lookahead
    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 == '+'
    advance_lookahead
    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.

Answer 2

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. ;)