|Closure conditions for languages? firstname.lastname@example.org (1994-03-21)|
|Re: Closure conditions for languages? email@example.com (1994-03-23)|
|From:||firstname.lastname@example.org (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
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
email@example.com ... !mcnc!sas!sasghm
Return to the
Search the comp.compilers archives again.