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

Regarding [Can't you just walk the tree defined by the grammar? -John]


Simply "walking the tree" will require recalculating many variables
with the grammar.


Since the grammar has no self-embedding variables, a regular
expression R (only using product and union) can be created to describe
L(G), based on the grammar G.


The parentheses in R would represent the "tree" in G - in an
appropriate creation of R from G. Expanding R to a union of product
terms does not solve the problem of recalculating re-occurring
sub-product terms that may be common to several product terms in the
expansion of R.


The problem is not simply to enumerate the words of L(G) - that is
trivial. The challenge is to do it as quickly as possible!


In my application, the order of the letters is not significant, but
Parik's theorem (reducing the my problem to a regular expression does
not seem to help me).

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