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

"Nicholas Carey BEST Consulting" <a-bnc@MICROSOFT.com>
29 Apr 1998 22:29:53 -0400

          From comp.compilers

Related articles
need help with using a grammar to construct a sentence from a group of plantz@fgm.com (Glen Plantz) (1998-04-13)
Re: using a grammar to construct a sentence from a group of words a-bnc@MICROSOFT.com (Nicholas Carey BEST Consulting) (1998-04-29)
Re: using a grammar to construct a sentence from a group of words zvr@softlab.ece.ntua.gr (Alexios Zavras) (1998-05-04)
| List of all articles for this month |

From: "Nicholas Carey BEST Consulting" <a-bnc@MICROSOFT.com>
Newsgroups: comp.compilers
Date: 29 Apr 1998 22:29:53 -0400
Organization: Compilers Central
References: 98-04-049
Keywords: parse, testing, prolog

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


Post a followup to this message

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