Mon, 21 Mar 1994 14:13:59 GMT

Related articles |
---|

Closure conditions for languages? sasghm@unx.sas.com (1994-03-21) |

Re: Closure conditions for languages? torbenm@diku.dk (1994-03-23) |

Newsgroups: | comp.compilers,sci.logic |

From: | sasghm@unx.sas.com (Gary Merrill) |

Originator: | sasghm@theseus.unx.sas.com |

Keywords: | theory, question, parse, LL(1) |

Organization: | SAS Institute Inc. |

Date: | Mon, 21 Mar 1994 14:13:59 GMT |

For reasons I will not go into here, I have been cogitating lately over

certain closure conditions for languages. Not having done this sort of

stuff for a long time, I'm hoping that the answers to some questions I

have are well known.

Leafing through _The Theory of Parsing, Translation, Compiling, and

Everything Else in the Known Universe_, I see that it is known (it's an

exercise in Chap. 8) that the LL languages are not closed under union (or

any number of other things as well). This has lead me to the following

questions which I am hoping someone will have ready answeres to:

1. What is the set of conditions C such that the following is

a theorem:

If C, then if L is an LL language and L' is an LL language,

the union of L and L' is an LL language.

Of more specific interest, of course:

If C, then if L is an LL(1) language and L' is an LL(1)

language, the union of L and L' is an LL(1) language.

2. Are there "interesting" languages L and L' which are both

LL(1) languages and whose union is not?

3. Do similar results hold for LR languages? In particular,

do the LR languages fail to be closed under union? Are

there theorems similar to those in 1 that hold for LR

languages?

Acknowledging a certain laziness in this approach, any information

will be greatly appreciated.

--

Gary H. Merrill [Principal Systems Developer, Compiler and Tools Division]

SAS Institute Inc. / SAS Campus Dr. / Cary, NC 27513 / (919) 677-8000

sasghm@theseus.unx.sas.com ... !mcnc!sas!sasghm

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.