Re: Recursive descent and left recursion

hogan@rintintin.Colorado.EDU (Apollo)
15 Jan 1997 11:54:48 -0500

          From comp.compilers

Related articles
Recursive descent and left recursion mfinney@lynchburg.net (1997-01-14)
Re: Recursive descent and left recursion fjh@mundook.cs.mu.OZ.AU (1997-01-15)
Re: Recursive descent and left recursion hogan@rintintin.Colorado.EDU (1997-01-15)
Re: Recursive descent and left recursion dlmoore@ix.netcom.com (David L Moore) (1997-01-16)
Re: Recursive descent and left recursion cfc@world.std.com (1997-01-16)
Re: Recursive descent and left recursion fjh@murlibobo.cs.mu.OZ.AU (1997-01-16)
Re: Recursive descent and left recursion cfc@world.std.com (1997-01-17)
Re: Recursive descent and left recursion will@ccs.neu.edu (William D Clinger) (1997-01-17)
Re: Recursive descent and left recursion cfc@world.std.com (Chris F Clark) (1997-01-21)
[1 later articles]
| List of all articles for this month |

From: hogan@rintintin.Colorado.EDU (Apollo)
Newsgroups: comp.compilers
Date: 15 Jan 1997 11:54:48 -0500
Organization: University of Colorado, Boulder
References: 97-01-099
Keywords: parse, LL(1)

>However, I have been using recursive descent with left recursive
>grammers for more than a decade. All it takes is the trivially
>obvious check to allow the left recursion. Take, for example...
>
> (1) <exp> := <exp> + <term>
> (2) <exp> := <term>
>
> . . . .
>
>Has anyone else used this technique? Does anyone know if there are
>any "hidden" problems with it? Could it be applied to LR or LALR
>parsers?


It seems to me that this simple check will parse a different language
    than the original.


That is, if we have the grammar:
E -> E + T
E -> T
T -> a


Then this grammar will accept the following language:
a (+ a)*


However, with your parsing strategy (at least how I understand it,
    the string
a + a + a
will not be accepted, because we need the following parse tree:
                        E
                    / | \
                  / | \
                / | \
              / | \
            E + T
        / | \ |
      / | \ |
    / | \ |
  T + T a
  | |
  | |
  a a


Which requires expanding E twice while still on the same input token.


Am I confused?


--Apollo
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.