1  Reglo source language

A regular expression denotes a language whose vocabulary is the set of valuation of a some finite set of Boolean variables. We call memory such a finite set M = {x₁, ⋯, x_m}.

A valuation of the memory is a tuple of m Boolean values. The set of all possible valuations can be viewed as a vocabulary (with 2^m symbols).

A sequence of valuations is called a trace over the memory: indeed, it is a word over the vocabulary 2^m.

A set of traces is called a history of the Boolean memory.

The reglo source language allows the description of histories using classic regular constructs (sequence, iteration and union).

1.1  Lexical aspects

The comments are C++ like:

// line comment
/* multi
lines
comment */

The following strings are keywords of the source language:

• eps
• prefix

Any other string made of digits, letters and underscore can be used as identifier.

1.2  History declaration

A source program consists of a list of history declarations. A declaration is of the form:

and means that <ident> denotes the history over <ident-list> described by the regular expression <expression>.

1.3  Monomials

A basic item in a regular expression is a set of valuations, denoted as a Boolean function of the memory variables. This function may use logical and and not, but not the logical or, which is useless since we have the regular union operator. This means that basic items are boolean monomials over the memory variables:

A monomial is a bracket enclosed list of atoms. The comma in the list stands for the logical and operator.

Atoms are conditions on a single variable. Each variable may appear at most once in the monomial. The - prefix stands for the logical not operator. The ~ prefix can be used to outline the fact that a variable is “don’t care”, but it can be avoided: [X, -Y, ~Z ] is equivalent to [X, -Y ].

If the monomial contains a single atom, brackets can be avoided: [-X] is equivalent to -X.

The list of atoms in a monomial can be empty: the empty monomial [] stands for the “always true” function.

1.4  Expressions

The syntax is the following:

The first three operators are classical: concatenation, finite iteration and union.

The ~~ macro denotes the set of all possible traces; it is equivalent to []*.

The eps operator adds the empty trace to an history.

The expression “prefix( E )” denotes all the prefixes of the traces in “E”. For instance:

prefix(a.b.(a + b)*)

is equivalent to:

eps(a + a.b + a.b.(a + b)*)

1.5  Call of a regular expression

When it is defined, a regular expression can be called in the definition of an other regular expression. It allows the user to write programs which “look like” regular grammar. Note that recursive definitions are forbidden, even though they are semanticaly correct (like left or right-recursive grammars).

The syntax of call is the following:

Definition order

In order to (simply) reject recursive definitions, a regular expression must be defined before it it used.

Default parameters

If actual parameters are omited, the formal parameters of the caller are given, in the same order as they are declared. As a consequence, the call is correct if and only if the caller and the called have the same number of parameters.

toto(A, B) = (A + A.B)* ;
titi(X, Y) = <toto>.X ;  //equivalent to : <toto(X,Y)>.X
tutu(B, A) = <toto>.A ;  //equivalent to : <toto(B,A)>.A
bibi(B, A, C) = <toto>.C ; //wrong : not same number of parameters

Actual parameters

Each actual parameter must be a monomial:

toto(A, B) = (A + A.B)* ;
titi(X, Y, Z) = <toto([X,-Y],[Z])>.X ;  

Call semantics

A call can be viewed as a macro: it is equivalent to the regular expression obtained by substituing the formal parameters to the actual parameters of the call. In the previous example, the call <toto([X,-Y],[Z])> is equivalent to ([X,-Y] + [X,-Y].[Z])*.