Wed, 23 Mar 1994 23:57:45 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 |

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.