Re: using a grammar to construct a sentence from a group of words

On 13 Apr 1998 00:51:14 -0400, Glen Plantz <plantz@fgm.com> wrote:


> I have a problem where I need to do the opposite of parsing;
> given a grammar and a group of words, I need to use the grammar
> to construct a valid sentence.


[SNIP]


> The language we are using is Java, specifically the JDK 1.1.4.


You might want to take a look at Prolog.


Because of the way unification works in Prolog, programs [in
theory] at least 'run' backwards as well as forwards -- although,
as another poster, <resslere@erols.com>, noted:


> You need to think about how you will handle potentially
> infinite recursions.


Parsers written in Prolog are [typically] recursive descent parsers,
so just as your grammar needs to be transformed (by eliminating left
recursion) in order for it to be acceptable for this sort of parser,
it must likewise be transformed in order for it to be acceptable as an
'unparser'. It's doable, at least for very small simple grammars; and
it gets complicated to say the least for not-so-simple ones.


On the plus side, most Prologs accept a modifed BNF notation as
syntatic sugar for a valid Prolog program. So the following BNF:


    sentence ==> noun , verb_phrase .


    noun ==> dog .
    noun ==> cat .
    noun ==> fleas .


    verh_phrase ==> verb , direct_object .


    direct_object ==> noun .


    verb ==> chases .
    verb ==> eats .
    verb ==> claws .
    verb ==> scratches .


is also a valid Prolog program that parses or generates all
possible sentences matching an [extremely] simple grammar.


<resslere@erols.com> also noted:


> [If this looks to you something like AI-esque solution
> search algorithms a la A*, you're getting the idea.]


which is exactly what Prolog is good for. ;-)


Hope this helps.


N.
--
--

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