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

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

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