Re: Closure conditions for languages?

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

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