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

    Hello Folks,


        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. The actual application involves constructing a
valid message for a simulation system where the simulation system
understands a "message" that is made up of an ordered sequence of
records which in turn have fields. There is a "grammar" to the
placement and sequence of these records, so the analogy to
constructing an english sentence from a "pile of words" works well.
The input to the problem is a series of tables that hold data to go
into the records that will make up the message that I'm
constructing. There is one table per record type, and after these
tables are filled with data, the tables need to be placed into the
correct sequence and placement according to the grammar, possibly into
a linked list or whatever.


        It's been a while since my last compiler class, so I dug up my
compiler texts to research the problem. I understand how to recognize
a sentence given a grammar, but I can't seem to come up with a good
solution to "going the opposite direction"; constructing a sentence
from a group of words.


        I also tried to apply the "Composite" pattern from the Design
Patterns "gang of four" book, but I'm not sure that pattern applies
very well to this problem.


        What's frustrating is that I know this problem has probably been
solved many times before, but I can't seem to find an algorithm or
pattern to apply here.


        I'd really appreciate someone helping me to find my "blind spot"
here. I'll post the responses if anyone is interested.


        The language we are using is Java, specifically the JDK 1.1.4.
                Thanks in advance for helping me out,


                        Glen Plantz
                        Senior Software Engineer
                        FGM Inc.
                        email - Work - "plantz@fgm.com"
                                        Personal - "gplantz@cts.com"
[There's been discussions here on generating test data for parsers, which
is close to what you want. -John]


--

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