Regular Expression "Terms"

I've been investigating high-performance regular expression matching
and have come to need some words (terms) to describe particular types
of simple regular expressions. Obviously, if there are words already
in use, I would like to use the same ones. Here are the words we have
been tenatively been using. Please let me know if there are alternate
words you have seen to describe the same concepts.


A regular expression that consists only of "characters" (symbols from
the alphabet) and "concatenation" only describe "fixed strings" or
"literals".


If we extend that to include "or" operators, but no recursion or
closures ("plus" or "star" operators). You can describe bounded
length expressions which we call "terms". Note one can include
"question mark" operators and "character sets" in this class, without
increasing its expressive power. It's this concept, the "term"
concept I am most interested in feedback on. I believe we got this
word from looking at a regular expression grammar.


Finally, we use the term "separator" to describe regular expressions
that consist of unbounded regular expressions (or expressions with
"large" finite bounds). Typically, there are of the form ".*" aka
dot-star expressions. It is generally the presence of one-or-more of
these in a regular expression that causes the NFA to DFA conversion to
experience exponential state explosion. That's not the sole criteria
for explosion, but it is a simple one to describe.


Thanks in advance for any help,
-Chris


******************************************************************************
Chris Clark email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. Web Site: http://world.std.com/~compres
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris

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