|Looking for references on regular language decomposition email@example.com (1995-06-24)|
|Re: Looking for references on regular language decomposition firstname.lastname@example.org (1995-06-28)|
|From:||email@example.com (Reid M. Pinchback)|
|Organization:||Massachusetts Institute of Technology|
|Date:||Sat, 24 Jun 1995 12:13:45 GMT|
I'm looking for references for theorems and algorithms for the
- Let L1 ... Ln be regular languages. By "regular language" I mean
exactly the same thing as you get in any introductory compilers
- 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
Thanks in advance!
= Reid M. Pinchback =
= Senior Faculty Liaison =
= Academic Computing Services, MIT =
= Email: firstname.lastname@example.org =
= URL: http://web.mit.edu/user/r/e/reidmp/www/home.html =
Return to the
Search the comp.compilers archives again.