Recursive descent and left recursion

I have noticed the occassional post here, as well as assertions in
various texts, that left recursion is not usable with recursive
descent (and LR parsers in general).


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>


when expanding (1), at the first term I simply check to see if the
current token in the input stream is the same as the last time that
the rewriting rule was expanded. If it is, then the parse has not
advanced and you have the infinite loop situation. I simply fail the
expansion and select an alternate rewriting rule for expansion. This
approach only requires the storage of a token # per left recursive
rewriting rule and single check of that token # against the current
token # (which can just be the line and column of the first character
in the token since that is usually maintained for error reporting).
It is very fast and does not significantly slow down the parsing. It
does require backtracking in the sense that a different rewriting rule
has to be selected, but there is no work associated with the
backtracking since it only occurs at the start of the left recursive
rewriting rule.


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

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