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

miles@mail.jct.ac.il wrote:
> 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.


Yes, but the time taken is linear in the size of the output. You
can't do asymptotically better, unless you are trying to avoid
generating duplicate copies of the same word.


If that is the case, then you are probably trying to perform some type
of minimization on the regular expression, so that it is minimally
redundant. If I recall correctly (and I may not, because the results
are at best tangentially connected to what I consider my area of
expertise (and even there I have my limits . . . )), there is no
algorithm that will find an absolute minimal regular expression.


However, you might find that turning your expression into a DFA is
what you are looking for. That is simple and it removes certain types
of redundancies (e.g. it will not generate duplicate copies of the
same word). Of course, there is the exponentially blow-up problem in
the size of the DFA for certain regular expressions. That is simply
inherent. The regular expression (or equivalently NFA) format can
simply minimize those expressions by allowing the duplicate copies of
the words to be expressed.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

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