15 Jan 1997 10:48:05 -0500

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

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.