53.5.5 Composing regular expressions

Suppose r and s are regular expressions. Then the following expressions can be built:

r|s

Union. This regular expression matches a lexeme if the lexeme is matched by r or by s.

rs

Concatenation. This expression matches a lexeme if the lexeme can be written as the concatenation of a lexeme matched by r and a lexeme matched by s.

r?

Optional expression. A lexeme matches this expression if it is the empty lexeme or if it matches r.

r+

Positive closure. This expression matches a lexeme that can be written as the concatenation of one or more lexemes, where each of those matches r.

r*

Kleene closure. A lexeme is matched by this expression if it can be written as the concatenation of zero or more lexemes, where each of those matches r.

r{i}

r{i,}

r{i,j}

Power or repetition of an expression. These expressions allow the “repetition” of a regular expression a certain number of times. i and j must be positive integers and j must be greater than, or equal to, i.

The first form repeats the expression r exactly i times. The second form repeats r at least i times. The last form repeats r at least i times and at most j times.

We should avoid using large numbers (more than 10), because the finite automaton for r is copied once for each repetition. The tables of the analyser may quickly become very large. We should note that the syntax of these expressions does not conflict with the syntax of the macro reference.

(r)

Parentheses. This expression matches the same lexemes as r. It is used to override the precedence of the operators.

The building operators are listed in order of increasing precedence. The ?, +, * and repetition operators have the same precedence.