|Re: Algorithm efficiently generating L(G), for a non-selfembedding CFG email@example.com (2001-03-31)|
|Re: Algorithm efficiently generating L(G), for a non-selfembedding CFG firstname.lastname@example.org (Joachim Durchholz) (2001-04-04)|
|From:||"Joachim Durchholz" <email@example.com>|
|Date:||4 Apr 2001 00:16:41 -0400|
|Posted-Date:||04 Apr 2001 00:16:41 EDT|
"Gershon Miles" <firstname.lastname@example.org> wrote:
> I am looking for an time-efficient algorithm to generate
> all words of a context free grammar G.
> In my application the language, L(G), is finite so there are no
> self-embedding variables.
> Speed is my #1 concern, but I am seeking a practical algorithm that
> could be run on a PC, where L(G) has up to millions of words.
I'd go for minimum space - storing the words in memory might cause
your PC to get into endless swapping. My first idea would be to
explore all substitutions in the grammer, build the corresponding
sequence of parse trees (or, rather, build one tree and modify it) and
generate the corresponding language string off that.
Return to the
Search the comp.compilers archives again.