Re: Recursive descent and left recursion

mfinney@lynchburg.net writes:


>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
>grammars for more than a decade.
[...]
>Has anyone else used this technique?


The XSB group at Stony Brook University has been working on automatic
"tabling" of logic programs. Tabling involves keeping track of
previously computed answers and using these answer tables, together
with some dynamic scheduling, to avoid infinite loops. (Tabled
evaluation of logic programs terminates for all programs that have the
"bounded term-depth" property, i.e. all programs that don't create
data structures of ever-increasing size.) One of the nice results
they have is that if you add tabling declarations to a define clause
grammar (DCG) recursive descent parser, then you don't need to
eliminate left recursion, since the tabled evaluation mechanism will
do that for you automatically; apparently you end up with a parser
that uses an algorithm similar to Earley's algorithm.


--
Fergus Henderson <fjh@cs.mu.oz.au>
WWW: <http://www.cs.mu.oz.au/~fjh>
PGP: finger fjh@128.250.37.3
--

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