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

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


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


Gene
--

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