Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!uhccux!munnari.oz.au!cs.mu.oz.au!ok From: ok@cs.mu.oz.au (Richard O'Keefe) Newsgroups: comp.lang.prolog Subject: Re: A phrase generator for Prolog DCG's Keywords: dcg prolog sentences Message-ID: <2103@munnari.oz.au> Date: 14 Sep 89 08:20:25 GMT References: <873@skye.ed.ac.uk> Sender: news@cs.mu.oz.au Lines: 63 In article <873@skye.ed.ac.uk>, ken@aiai.ed.ac.uk (Ken Johnson) writes: > I've found that the usual way of teaching about grammars with Lisp and > Logo involves generating random phrases freom a grammar whereas Prolog's > DCG mechanism does not allow you to do that: it just checks whether a > given string of non-terminals can be derived from the grammar or not. The claim about DCGs is strictly false: in my programs I use DCGs to build lists far more often than I use them to parse things. What's more, I left a program at Edinburgh which generated "random plots for science fiction stories". That program was a Prolog rewrite of a C program written by David Tilbrook. I find "stories" like Giant mushrooms invade Reading, but Ronald Reagan's dog invents laser weapons, and it is the end of civilisation as we know it. _much_ more interesting than insults. If you want to generate random phrases, you had better work out what probability model you want to use (for example, do you want all phrases of length N to be equiprobable). A simple hack is just to pull maybe(+P) % succeeds with probability P out of the library and code your rules as --> {maybe(P)}, . If all the rules in a grammar are epsilon-free, it may be possible to enumerate all the sentences in increasing order of length. If your start symbol is s//0, the device is s(Sentence) :- length(Sentence, _dont_care_but_increasing), s(Sentence, []). This is just iterative deepening in another disguise. Here is an example: s --> monster(_), [meets], monster(_) | monster(male), [marries], monster(female). monster(Sex) --> relation(Sex), [of], monster2(_) | monster2(Sex). relation(male) --> [son] | [nephew]. relation(female) --> [daughter] | [niece]. monster2(male) --> [dr], ( [who] | [strangelove] | [death] ). monster2(female) --> [shelob] | [mrs,thatcher] | [vampirella]. monster2(_) --> [the], monster3, [from], place. monster3 --> [thing] | [blob] | [mp]. place --> [hell] | [mars] | [edinburgh]. s(X) :- length(X, _), % generate increasingly longer lists s(X, []). % fill them with words. If your length/2 is broken, use list([]). list([_|L]) :- list(L). instead. -- I hear the handwriting on the wall. -- farb(1), UofArizona 'icon' system.