Closure conditions for languages? (Gary Merrill)
Mon, 21 Mar 1994 14:13:59 GMT

          From comp.compilers

Related articles
Closure conditions for languages? (1994-03-21)
Re: Closure conditions for languages? (1994-03-23)
| List of all articles for this month |

Newsgroups: comp.compilers,sci.logic
From: (Gary Merrill)
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

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 ... !mcnc!sas!sasghm

Post a followup to this message

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