4 Apr 2001 00:16:05 -0400

Related articles |
---|

Re: Algorithm efficiently generating L(G), for a non-selfembedding CFG miles@mail.jct.ac.il (2001-03-31) |

Re: Re: Algorithm efficiently generating L(G), for a non-selfembedding miles@mail.jct.ac.il (2001-04-04) |

Re: Re: Algorithm efficiently generating L(G), for a non-selfembedding plakal@cs.wisc.edu (Manoj Plakal) (2001-04-10) |

From: | miles@mail.jct.ac.il (\"Gershon Miles\") |

Newsgroups: | comp.compilers |

Date: | 4 Apr 2001 00:16:05 -0400 |

Organization: | Mailgate.ORG Server - http://www.Mailgate.ORG |

References: | 01-03-186 |

Keywords: | parse |

Posted-Date: | 04 Apr 2001 00:16:05 EDT |

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).

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.