Re: additional regular expression operators

Ralph Boland wrote:
> I am building a tool for translating regular expressions
...
> I plan to provide support for at least three additional
> unary operators to the standard three (?,*, and +)
> (plus new binary operators but that's a topic for another day).
> For a regular expression R they are:
>
> R! :does not accept the empty string but otherwise
> accepts every expression that R does. Very useful.
>
> R~ :accepts exactly the set of strings that R does not accept.
> note that R = R~~.
>
> R% : equivalent to the string (R~)R


Here is some formalism, that perhaps is useful:


Let C be a set of characters, and C* the set of empty strings from C
(i.e., the free monoid). A language L is a subset of C*. Denote the set
of languages of C by Lang(C).


Given two languages L, M, one can form the following set operations:
      complement, union, intersection, difference, symmetric difference
and the monoid operations:
      (concatenation) L * M b  {x*y|x in L or y in M}
      (exponent) L^k b  {x_1 *...*x_k|x_i in L}
      (monoid closure) L* b  union of all L^k, zero or more concatenations
(positive closure) L+ b  union of all L^k, k > 0, one or more
                                                  concatenations
      (S closure) L^S b  union of all L^i, i in S
The monoid closure of L is the submonoid generated by L, and also the
smallest submonoid containing L. The monoid closure is also called the
Kleene closure.


A regular expression language contains symbols representing elements
from C, Lang(C), C*, the set and monoid operations above, plus
parenthesizes, with the obvious semantics.


Now, your operation R~ above is the set complement, and R! is R minus
the empty language. The last one can also easily be constructed from the
other, so it may not be needed to be added explictly.


All the operations above are traditionally written (superscript)
postfix, except the complement which is (inline) prefix, but that is
often not added in regular expression algebras (or only as complements
in C, i.e. for a character set A, take language set difference C-A). But
if you add it, it might be natural to have it prefix.


      Hans Aberg

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