Re: Recursive descent and left recursion

fjh@mundook.cs.mu.OZ.AU (Fergus Henderson)
15 Jan 1997 10:48:05 -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)
[2 later articles]
| List of all articles for this month |

From: fjh@mundook.cs.mu.OZ.AU (Fergus Henderson)
Newsgroups: comp.compilers
Date: 15 Jan 1997 10:48:05 -0500
Organization: Comp Sci, University of Melbourne
References: 97-01-099
Keywords: parse, LL(1)

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


Post a followup to this message

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