Xref: utzoo comp.ai:5428 comp.lang.prolog:2283
Path: 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

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