Re: Recursive descent and left recursion

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

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