Sat, 24 Jun 1995 12:13:45 GMT

Related articles |
---|

Looking for references on regular language decomposition reidmp@whirlwind.mit.edu (1995-06-24) |

Re: Looking for references on regular language decomposition mab@wdl.loral.com (1995-06-28) |

Newsgroups: | sci.math,comp.theory,comp.compilers |

From: | reidmp@whirlwind.mit.edu (Reid M. Pinchback) |

Keywords: | theory, question |

Organization: | Massachusetts Institute of Technology |

Date: | Sat, 24 Jun 1995 12:13:45 GMT |

Status: | RO |

I'm looking for references for theorems and algorithms for the

following problem.

- Let L1 ... Ln be regular languages. By "regular language" I mean

exactly the same thing as you get in any introductory compilers

course.

- Let L be the language consisting of strings of L1 ... Ln

concatenated in any order.

In other words, L = ( L1 | ... | Ln )* where "|" signifies choice and "*" is

star closure (ie: catenation 0 or more times)

Here is my question. What theorems are available that specify when

we can determine a *unique* decomposition of a string of L into

substrings from L1 ... Ln. In other words, when can you uniquely

parse a string of L so that you *know* which sublanguage each

substring is from.

Another variation on this is to answer the same question where the

languages L1 ... Ln are described by regular grammars.

Note: strictly speaking you could say "treat this as a context-free

language", but there are some problems with this:

1. It ain't what I'm looking for. :-)

2. Some problems are decidable for regular languages that aren't

decidable for context-free languages.

3. From a pragmatic "I wanna write some decent code" standpoint,

there are a lot of good reasons for wanting to use lexical scanners

and to want to implement them in terms of regular languages instead

of in terms of context free languages.

PS: I'm not looking for references on how to use LEX. I'm looking

for theoretical references, possibly with either an algebraic or

automata-theoretic approach.

Thanks in advance!

--

===============================================================

= Reid M. Pinchback =

= Senior Faculty Liaison =

= Academic Computing Services, MIT =

= =

= Email: reidmp@mit.edu =

= URL: http://web.mit.edu/user/r/e/reidmp/www/home.html =

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.