|need help with using a grammar to construct a sentence from a group of email@example.com (Glen Plantz) (1998-04-13)|
|Re: need help with using a grammar to construct a sentence from a grou firstname.lastname@example.org (1998-04-18)|
|Re: need help with using a grammar to construct a sentence from a grou email@example.com (resslere) (1998-04-21)|
|Re: need help with using a grammar to construct a sentence from a grou firstname.lastname@example.org (Jake Donham) (1998-04-27)|
|Re: need help with using a grammar to construct a sentence from a grou email@example.com (1998-05-04)|
|Re: need help with using a grammar to construct a sentence from a grou firstname.lastname@example.org (Axel Schairer) (1998-05-04)|
|Date:||21 Apr 1998 00:42:40 -0400|
I did this some years ago to generate test sets for student parser
projects. What Kevin suggests will work--expand parse trees top down
until you get all terminals, then print.
You need to think about how you will handle potentially infinite
recursions. I was out to generate _all_ possible strings of length <=
N. So I kept a priority queue of sentential forms and, in a loop,
picked off the next form and expanded the leftmost non-terminal with
rules having the matching LHS. Expansions that were all terminals
were printed. Non-duplicates with remaining nonterminals went back on
[If this looks to you something like AI-esque solution search
algorithms a la A*, you're getting the idea.]
The queue priority function is the interesting part. There are
various possiblilities. If you eliminate null and unit productions
(see your favorite text on CFGs), then each expansion must grow the
string, so a reasonable strategy is to expand the _longest_ string
before all others (of course discarding any with length > N). This
keeps the queue short, though (depending on the grammar) can chew up a
lot of processor time between emitted strings.
All this was pretty quick to implement in lisp. Sorry I don't have the
code any more.
Return to the
Search the comp.compilers archives again.