Re: Algorithm efficiently generating L(G), for a non-selfembedding CFG G

"Joachim Durchholz" <joachim_d@gmx.de>
4 Apr 2001 00:16:41 -0400

          From comp.compilers
Related articles
Re: Algorithm efficiently generating L(G), for a non-selfembedding CFG miles@mail.jct.ac.il (2001-03-31)
Re: Algorithm efficiently generating L(G), for a non-selfembedding CFG joachim_d@gmx.de (Joachim Durchholz) (2001-04-04)
| List of all articles for this month |
From: "Joachim Durchholz" <joachim_d@gmx.de>
Newsgroups: comp.compilers
Date: 4 Apr 2001 00:16:41 -0400
Organization: Compilers Central
References: 01-03-186
Keywords: parse
Posted-Date: 04 Apr 2001 00:16:41 EDT

"Gershon Miles" <miles@mail.jct.ac.il> 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.


Regards,
Joachim

Post a followup to this message

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