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

js10@doc.ic.ac.uk (Joachim Schimpf)
4 May 1998 22:55:31 -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: need help with using a grammar to construct a sentence from a grou kelley@iguana.ruralnet.net (1998-04-18)
Re: need help with using a grammar to construct a sentence from a grou resslere@erols.com (resslere) (1998-04-21)
Re: need help with using a grammar to construct a sentence from a grou donham@linex.com (Jake Donham) (1998-04-27)
Re: need help with using a grammar to construct a sentence from a grou js10@doc.ic.ac.uk (1998-05-04)
Re: need help with using a grammar to construct a sentence from a grou schairer@dfki.de (Axel Schairer) (1998-05-04)
| List of all articles for this month |

From: js10@doc.ic.ac.uk (Joachim Schimpf)
Newsgroups: comp.compilers,comp.lang.java.programmer
Date: 4 May 1998 22:55:31 -0400
Organization: Dept. of Computing, Imperial College, University of London, UK.
References: 98-04-049 98-04-075 98-04-092
Keywords: prolog, parse

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


That's quite easy with Prolog and its definite clause grammars (DCGs).
Due to Prolog's relational nature, you can use the same grammar
for parsing and generating, e.g. given the grammar


    sentence --> subject,predicate,object.
    subject --> [the,man].
    subject --> [the,dog].
    predicate --> [eats].
    predicate --> [kicks].
    object --> subject.


you can either check:


    ?- phrase(sentence, [the,man,eats,the,dog]).


    yes.
    ?- phrase(sentence, [the,man,eats,a,dog]).


    no (more) solution.


or generate:


    ?- phrase(sentence, S).


    S = [the, man, eats, the, man] More? (;)


    S = [the, man, eats, the, dog] More? (;)


    S = [the, man, kicks, the, man] More? (;)


    S = [the, man, kicks, the, dog] More? (;)


    S = [the, dog, eats, the, man] More? (;)


    S = [the, dog, eats, the, dog] More? (;)


    S = [the, dog, kicks, the, man] More? (;)


    S = [the, dog, kicks, the, dog]
    yes.


You can also add arguments to the nonterminals to pass
semantic information around.


------------------------------------------------------------------------
  Joachim Schimpf / phone: +44 171 594 8187
  IC-Parc, Imperial College / mailto:J.Schimpf@ic.ac.uk
  London SW7 2AZ, UK / http://www.icparc.ic.ac.uk/eclipse
--


Post a followup to this message

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