Regular expressions or parts of a regular expression can be repeated. I specify the number of repetitions with a type of operator called quantifiers. A quantifier has two attributes:
- A lower limit for the number of repetitions is represented by a natural number (i.e. a non-negative integer)
- An upper limit for the number of repetitions is represented either by a natural number or the empty string. The latter means unlimited.
I write the quantifiers inside a pair of braces, with a comma between the lower and upper limit, for example:
- Zero or one repetition: {0,1}
- One, two or three repetitions: {1,3}
- Fourteen or fifteen repetitions: {14,15}
- Two or more repetitions: {2,}
The quantifier {1,1} is an identity operator:
- a{1,1} equals a
Quantifiers are unary, left associative, and has high precedence. Concatenation as well as Alternation have lower precedence. That gives the following rules:
- Concatination: ab{1,2} equals a(b{1,2})
- Concatination: a{1,2}b equals (a{1,2})b
- Alternation: a|b{1,2} equals a|(b{1,2})
- Alternation: a{1,2}|b equals (a{1,2})|b
I’ve got a lot of syntactic sugar in my regular expression jar. A single natural number in a quantifier represents both the lower and upper limit:
- {3} equals {3,3}
I may write Kleene closure — zero or more repetitions — as an asterisk without braces:
- a* equals a{0,}
I may write Positive closure — one or more repetitions — as a plus sign without braces:
- a+ equals a{1,}
I may write the Optional operation — zero or one repetition — as a question mark without braces:
- a? equals a{0,1}
More algebra:
- (a*)* equals a*
- (a+)+ equals a+
- (a?)? equals a?
- (a*)+ equals (a+)* equals a*
- (a*)? equals (a?)* equals a*
- (a+)? equals (a?)+ equals a*
- Kleene closure is Positive closure or nothing: a* equals (a+|)
- Optional a is a or nothing: a? equals (a|)? equals (a|)
- Kleene closure of a or nothing is Kleene closure of a: (a|)* equals a*
- Positive closure of a is a concatenated with Kleene closure of a: a+ equals aa*
0 Responses to “Regex Quantifiers Algebra”