# Re: Closure conditions for languages?

## torbenm@diku.dk (Torben AEgidius Mogensen)Wed, 23 Mar 1994 23:57:45 GMT

From comp.compilers

Related articles
Closure conditions for languages? sasghm@unx.sas.com (1994-03-21)
Re: Closure conditions for languages? torbenm@diku.dk (1994-03-23)
| List of all articles for this month |

 Newsgroups: comp.compilers From: torbenm@diku.dk (Torben AEgidius Mogensen) Keywords: theory, parse, LL(1) Organization: Compilers Central References: 94-03-080 Date: Wed, 23 Mar 1994 23:57:45 GMT

sasghm@unx.sas.com (Gary Merrill) writes:

>I see that it is known 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 answers to:

>1. What is the set of conditions C such that the following is
> a theorem:

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

Well, if FIRST(L) and FIRST(L') are disjoint, then the union of L and
L' will obviously also be LL(1). I don't know of any stronger results.

>2. Are there "interesting" languages L and L' which are both
> LL(1) languages and whose union is not?

That depends on what you mean by 'interesting'. An example is

L = {a^m b^m c^n}
L' = {a^m b^n c^n}

represented by the LL(1) grammars

L -> A' C
A' -> _ | a A' b /* _ is the "empty" symbol */
C -> _ | c C

L' -> A B'
A -> _ | a A
B' -> _ | b B' c

The union of L and L' is a language that can't be represented by an
unambigous grammar, and hence not by any LL(k) grammar.

>3. Do similar results hold for LR languages?

The same example can be used for LR languages.

Torben Mogensen (torbenm@diku.dk)
--

Post a followup to this message

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