Article View: comp.ai
Article #8667Re: Bidirectional Grammars - Request for References
From: John Cleary
Date: Tue, 09 Jan 1990 04:10
Date: Tue, 09 Jan 1990 04:10
20 lines
1385 bytes
1385 bytes
In article <2980@munnari.oz.au>, richard@satori.cs.mu.OZ.AU (Richard Hagen) writes: > Has anyone seen any references for the problems/advantages of bidirectional > grammars? I'm working on an implementation in NU-Prolog, but *any* pointers > would be appreciated. > > Thanks, > > richard I have done this a number of times, at least once to actually achieve something other than an academic exercise. What you have to realize is that you need a breadth first search to get a reasonably interesting behaviour when you reverse the grammar. The easiest way to do a breadth first search is to use a bounded depth search where the depth is increased after all the solutions at the earlier depth are found. It is straightforward to write an interpreter to do this, and if you are a little more bold you can even compile away the interpreter. John Cleary
Technical Details
Message-ID:
<2313@cs-spool.calgary.UUCP>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!mailrus!cornell!uw-beaver!ubc-cs!alberta!calgary!cpsc!clearyReferences:
<2980@munnari.oz.au>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!mailrus!cornell!uw-beaver!ubc-cs!alberta!calgary!cpsc!cleary From: cleary@cpsc.ucalgary.ca (John Cleary) Newsgroups: comp.ai,comp.lang.prolog Subject: Re: Bidirectional Grammars - Request for References Summary: need breadth first search Keywords: parsing and generation without taking your boots off Message-ID: <2313@cs-spool.calgary.UUCP> Date: 9 Jan 90 04:10:18 GMT References: <2980@munnari.oz.au> Sender: news@calgary.UUCP Lines: 20