Semantics
type SemanticException = oneof {syntaxError}
Unicode Character Classes
Syntax
UnicodeCharacter  Any Unicode character
UnicodeAlphanumeric  Any Unicode alphabetic or decimal digit character (includes ASCII 0‑9, A‑Z, and a‑z)
LineTerminator  «LF» | «CR» | «u2028» | «u2029»
Semantics
lineTerminators : {Character} = {‘«LF»’, ‘«CR»’, ‘«u2028»’, ‘«u2029»’}
reWhitespaces : {Character} = {‘«FF»’, ‘«LF»’, ‘«CR»’, ‘«TAB»’, ‘«VT»’, ‘ ’}
reDigits : {Character} = {‘0’ ... ‘9’}
reWordCharacters : {Character} = {‘0’ ... ‘9’, ‘A’ ... ‘Z’, ‘a’ ... ‘z’, ‘_’}
Regular Expression Definitions
Semantics
type REInput = tuple {str: String; ignoreCase: Boolean; multiline: Boolean}
Field str is the input string. ignoreCase and multiline are the corresponding regular expression flags.
type REResult = oneof {success: REMatch; failure}
type REMatch = tuple {endIndex: Integer; captures: Capture[]}
A REMatch holds an intermediate state during the pattern-matching process. endIndex is the index of the next input character to be matched by the next component in a regular expression pattern. If we are at the end of the pattern, endIndex is one plus the index of the last matched input character. captures is a zero-based array of the strings captured so far by capturing parentheses.
type Capture = oneof {present: String; absent}
type Continuation = REMatch  REResult
A Continuation is a function that attempts to match the remaining portion of the pattern against the input string, starting at the intermediate state given by its REMatch argument. If a match is possible, it returns a success result that contains the final REMatch state; if no match is possible, it returns a failure result.
type Matcher = REInput  REMatch  Continuation  REResult
A Matcher is a function that attempts to match a middle portion of the pattern against the input string, starting at the intermediate state given by its REMatch argument. Since the remainder of the pattern heavily influences whether (and how) a middle portion will match, we must pass in a Continuation function that checks whether the rest of the pattern matched. If the continuation returns failure, the matcher function may call it repeatedly, trying various alternatives at pattern choice points.
The REInput parameter contains the input string and is merely passed down to subroutines.
type MatcherGenerator = Integer  Matcher
A MatcherGenerator is a function executed at the time the regular expression is compiled that returns a Matcher for a part of the pattern. The Integer parameter contains the number of capturing left parentheses seen so far in the pattern and is used to assign static, consecutive numbers to capturing parentheses.
characterSetMatcher(acceptanceSet: {Character}, invert: Boolean) : Matcher
  = function(t: REInput, x: REMatch, c: Continuation)
         let i: Integer = x.endIndex;
             s: String = t.str
         in if i = |s|
             then failure
             else if s[i]  acceptanceSet xor invert
             then c(endIndex (i + 1), captures x.captures)
             else failure
characterSetMatcher returns a Matcher that matches a single input string character. If invert is false, the match succeeds if the character is a member of the acceptanceSet set of characters (possibly ignoring case). If invert is true, the match succeeds if the character is not a member of the acceptanceSet set of characters (possibly ignoring case).
characterMatcher(ch: Character) : Matcher = characterSetMatcher({ch}, false)
characterMatcher returns a Matcher that matches a single input string character. The match succeeds if the character is the same as ch (possibly ignoring case).
Regular Expression Patterns
Syntax
RegularExpressionPattern  Disjunction
Semantics
action Exec[RegularExpressionPattern] : REInput  Integer  REResult
Exec[RegularExpressionPattern  Disjunction]
  = let match: Matcher = GenMatcher[Disjunction](0)
     in function(t: REInput, index: Integer)
             match(
                 t,
                 endIndex index, captures fillCapture(CountParens[Disjunction]),
                 successContinuation)
successContinuation(x: REMatch) : REResult = success x
fillCapture(i: Integer) : Capture[]
  = if i = 0
     then []Capture
     else fillCapture(i – 1)  [absent]
Disjunctions
Syntax
Disjunction 
	Alternative
|	Alternative | Disjunction
Semantics
action GenMatcher[Disjunction] : MatcherGenerator
GenMatcher[Disjunction  Alternative] = GenMatcher[Alternative]
GenMatcher[Disjunction  Alternative | Disjunction1](parenIndex: Integer)
  = let match1: Matcher = GenMatcher[Alternative](parenIndex);
         match2: Matcher = GenMatcher[Disjunction1](parenIndex + CountParens[Alternative])
     in function(t: REInput, x: REMatch, c: Continuation)
             case match1(t, x, c) of
                success(y: REMatch): success y;
                failure: match2(t, x, c)
                end
action CountParens[Disjunction] : Integer
CountParens[Disjunction  Alternative] = CountParens[Alternative]
CountParens[Disjunction  Alternative | Disjunction1]
  = CountParens[Alternative] + CountParens[Disjunction1]
Alternatives
Syntax
Alternative 
	«empty»
|	Alternative Term
Semantics
action GenMatcher[Alternative] : MatcherGenerator
GenMatcher[Alternative  «empty»](parenIndex: Integer)
  = function(t: REInput, x: REMatch, c: Continuation)
         c(x)
GenMatcher[Alternative  Alternative1 Term](parenIndex: Integer)
  = let match1: Matcher = GenMatcher[Alternative1](parenIndex);
         match2: Matcher = GenMatcher[Term](parenIndex + CountParens[Alternative1])
     in function(t: REInput, x: REMatch, c: Continuation)
             let d: Continuation
                     = function(y: REMatch)
                            match2(t, y, c)
             in match1(t, x, d)
action CountParens[Alternative] : Integer
CountParens[Alternative  «empty»] = 0
CountParens[Alternative  Alternative1 Term]
  = CountParens[Alternative1] + CountParens[Term]
Terms
Syntax
Term 
	Assertion
|	Atom
|	Atom Quantifier
Semantics
action GenMatcher[Term] : MatcherGenerator
GenMatcher[Term  Assertion](parenIndex: Integer)
  = function(t: REInput, x: REMatch, c: Continuation)
         if TestAssertion[Assertion](t, x)
         then c(x)
         else failure
GenMatcher[Term  Atom] = GenMatcher[Atom]
GenMatcher[Term  Atom Quantifier](parenIndex: Integer)
  = let match: Matcher = GenMatcher[Atom](parenIndex);
         min: Integer = Minimum[Quantifier];
         max: Limit = Maximum[Quantifier];
         greedy: Boolean = Greedy[Quantifier]
     in if 
             (case max of
                finite(m: Integer): m < min;
                infinite: false
                end)
         then throw syntaxError
         else repeatMatcher(match, min, max, greedy, parenIndex, CountParens[Atom])
action CountParens[Term] : Integer
CountParens[Term  Assertion] = 0
CountParens[Term  Atom] = CountParens[Atom]
CountParens[Term  Atom Quantifier] = CountParens[Atom]
Syntax
Quantifier 
	QuantifierPrefix
|	QuantifierPrefix ?
QuantifierPrefix 
	*
|	+
|	?
|	{ DecimalDigits }
|	{ DecimalDigits , }
|	{ DecimalDigits , DecimalDigits }
DecimalDigits 
	DecimalDigit
|	DecimalDigits DecimalDigit
DecimalDigit  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Semantics
type Limit = oneof {finite: Integer; infinite}
resetParens(x: REMatch, p: Integer, nParens: Integer) : REMatch
  = if nParens = 0
     then x
     else let y: REMatch = endIndex x.endIndex, captures x.captures[p  absent]
           in resetParens(y, p + 1, nParens – 1)
repeatMatcher(body: Matcher, min: Integer, max: Limit, greedy: Boolean, parenIndex: Integer, nBodyParens: Integer)
  : Matcher
  = function(t: REInput, x: REMatch, c: Continuation)
         if 
             (case max of
                finite(m: Integer): m = 0;
                infinite: false
                end)
         then c(x)
         else let d: Continuation
                       = function(y: REMatch)
                              if min = 0 and y.endIndex = x.endIndex
                              then failure
                              else let newMin: Integer
                                            = if min = 0
                                               then 0
                                               else min – 1;
                                        newMax: Limit
                                            = case max of
                                                  finite(m: Integer): finite (m – 1);
                                                  infinite: infinite
                                                  end
                                    in repeatMatcher(
                                            body,
                                            newMin,
                                            newMax,
                                            greedy,
                                            parenIndex,
                                            nBodyParens)(t, y, c);
                   xr: REMatch = resetParens(x, parenIndex, nBodyParens)
               in if min ≠ 0
                   then body(t, xr, d)
                   else if greedy
                   then case body(t, xr, d) of
                             success(z: REMatch): success z;
                             failure: c(x)
                             end
                   else case c(x) of
                            success(z: REMatch): success z;
                            failure: body(t, xr, d)
                            end
action Minimum[Quantifier] : Integer
Minimum[Quantifier  QuantifierPrefix] = Minimum[QuantifierPrefix]
Minimum[Quantifier  QuantifierPrefix ?] = Minimum[QuantifierPrefix]
action Maximum[Quantifier] : Limit
Maximum[Quantifier  QuantifierPrefix] = Maximum[QuantifierPrefix]
Maximum[Quantifier  QuantifierPrefix ?] = Maximum[QuantifierPrefix]
action Greedy[Quantifier] : Boolean
Greedy[Quantifier  QuantifierPrefix] = true
Greedy[Quantifier  QuantifierPrefix ?] = false
action Minimum[QuantifierPrefix] : Integer
Minimum[QuantifierPrefix  *] = 0
Minimum[QuantifierPrefix  +] = 1
Minimum[QuantifierPrefix  ?] = 0
Minimum[QuantifierPrefix  { DecimalDigits }] = IntegerValue[DecimalDigits]
Minimum[QuantifierPrefix  { DecimalDigits , }] = IntegerValue[DecimalDigits]
Minimum[QuantifierPrefix  { DecimalDigits1 , DecimalDigits2 }]
  = IntegerValue[DecimalDigits1]
action Maximum[QuantifierPrefix] : Limit
Maximum[QuantifierPrefix  *] = infinite
Maximum[QuantifierPrefix  +] = infinite
Maximum[QuantifierPrefix  ?] = finite 1
Maximum[QuantifierPrefix  { DecimalDigits }] = finite IntegerValue[DecimalDigits]
Maximum[QuantifierPrefix  { DecimalDigits , }] = infinite
Maximum[QuantifierPrefix  { DecimalDigits1 , DecimalDigits2 }]
  = finite IntegerValue[DecimalDigits2]
action IntegerValue[DecimalDigits] : Integer
IntegerValue[DecimalDigits  DecimalDigit] = DecimalValue[DecimalDigit]
IntegerValue[DecimalDigits  DecimalDigits1 DecimalDigit]
  = 10*IntegerValue[DecimalDigits1] + DecimalValue[DecimalDigit]
action DecimalValue[DecimalDigit] : Integer = digitValue(DecimalDigit)
Assertions
Syntax
Assertion 
	^
|	$
|	\ b
|	\ B
Semantics
action TestAssertion[Assertion] : REInput  REMatch  Boolean
TestAssertion[Assertion  ^](t: REInput, x: REMatch)
  = if x.endIndex = 0
     then true
     else t.multiline and t.str[x.endIndex – 1]  lineTerminators
TestAssertion[Assertion  $](t: REInput, x: REMatch)
  = if x.endIndex = |t.str|
     then true
     else t.multiline and t.str[x.endIndex]  lineTerminators
TestAssertion[Assertion  \ b](t: REInput, x: REMatch)
  = atWordBoundary(x.endIndex, t.str)
TestAssertion[Assertion  \ B](t: REInput, x: REMatch)
  = not atWordBoundary(x.endIndex, t.str)
atWordBoundary(i: Integer, s: String) : Boolean = inWord(i – 1, s) xor inWord(i, s)
inWord(i: Integer, s: String) : Boolean
  = if i = -1 or i = |s|
     then false
     else s[i]  reWordCharacters
Atoms
Syntax
Atom 
	PatternCharacter
|	.
|	\ AtomEscape
|	CharacterClass
|	( Disjunction )
|	( ? : Disjunction )
|	( ? = Disjunction )
|	( ? ! Disjunction )
PatternCharacter  UnicodeCharacter except ^ | $ | \ | . | * | + | ? | ( | ) | [ | ] | { | } | |
Semantics
action GenMatcher[Atom] : MatcherGenerator
GenMatcher[Atom  PatternCharacter](parenIndex: Integer)
  = characterMatcher(PatternCharacter)
GenMatcher[Atom  .](parenIndex: Integer) = characterSetMatcher(lineTerminators, true)
GenMatcher[Atom  \ AtomEscape] = GenMatcher[AtomEscape]
GenMatcher[Atom  CharacterClass](parenIndex: Integer)
  = let a: {Character} = AcceptanceSet[CharacterClass]
     in characterSetMatcher(a, Invert[CharacterClass])
GenMatcher[Atom  ( Disjunction )](parenIndex: Integer)
  = let match: Matcher = GenMatcher[Disjunction](parenIndex + 1)
     in function(t: REInput, x: REMatch, c: Continuation)
             let d: Continuation
                     = function(y: REMatch)
                            let updatedCaptures: Capture[]
                                    = y.captures[parenIndex 
                                           present t.str[x.endIndex ... y.endIndex – 1]]
                            in c(endIndex y.endIndex, captures updatedCaptures)
             in match(t, x, d)
GenMatcher[Atom  ( ? : Disjunction )] = GenMatcher[Disjunction]
GenMatcher[Atom  ( ? = Disjunction )](parenIndex: Integer)
  = let match: Matcher = GenMatcher[Disjunction](parenIndex)
     in function(t: REInput, x: REMatch, c: Continuation)
             case match(t, x, successContinuation) of
                success(y: REMatch): c(endIndex x.endIndex, captures y.captures);
                failure: failure
                end
GenMatcher[Atom  ( ? ! Disjunction )](parenIndex: Integer)
  = let match: Matcher = GenMatcher[Disjunction](parenIndex)
     in function(t: REInput, x: REMatch, c: Continuation)
             case match(t, x, successContinuation) of
                success(y: REMatch): failure;
                failure: c(x)
                end
action CountParens[Atom] : Integer
CountParens[Atom  PatternCharacter] = 0
CountParens[Atom  .] = 0
CountParens[Atom  \ AtomEscape] = 0
CountParens[Atom  CharacterClass] = 0
CountParens[Atom  ( Disjunction )] = CountParens[Disjunction] + 1
CountParens[Atom  ( ? : Disjunction )] = CountParens[Disjunction]
CountParens[Atom  ( ? = Disjunction )] = CountParens[Disjunction]
CountParens[Atom  ( ? ! Disjunction )] = CountParens[Disjunction]
Escapes
Syntax
AtomEscape 
	DecimalEscape
|	CharacterEscape
|	CharacterClassEscape
Semantics
action GenMatcher[AtomEscape] : MatcherGenerator
GenMatcher[AtomEscape  DecimalEscape](parenIndex: Integer)
  = let n: Integer = EscapeValue[DecimalEscape]
     in if n = 0
         then characterMatcher(‘«NUL»’)
         else if n > parenIndex
         then throw syntaxError
         else backreferenceMatcher(n)
GenMatcher[AtomEscape  CharacterEscape](parenIndex: Integer)
  = characterMatcher(CharacterValue[CharacterEscape])
GenMatcher[AtomEscape  CharacterClassEscape](parenIndex: Integer)
  = characterSetMatcher(AcceptanceSet[CharacterClassEscape], false)
backreferenceMatcher(n: Integer) : Matcher
  = function(t: REInput, x: REMatch, c: Continuation)
         case nthBackreference(x, n) of
            present(ref: String):
                  let i: Integer = x.endIndex;
                      s: String = t.str
                  in let j: Integer = i + |ref|
                  in if j > |s|
                      then failure
                      else if s[i ... j – 1] = ref
                      then c(endIndex j, captures x.captures)
                      else failure;
            absent: c(x)
            end
nthBackreference(x: REMatch, n: Integer) : Capture = x.captures[n – 1]
Syntax
CharacterEscape 
	ControlEscape
|	c ControlLetter
|	HexEscape
|	IdentityEscape
ControlLetter 
	A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
|	a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z
IdentityEscape  UnicodeCharacter except UnicodeAlphanumeric
ControlEscape 
	f
|	n
|	r
|	t
|	v
Semantics
action CharacterValue[CharacterEscape] : Character
CharacterValue[CharacterEscape  ControlEscape] = CharacterValue[ControlEscape]
CharacterValue[CharacterEscape  c ControlLetter]
  = codeToCharacter(bitwiseAnd(characterToCode(ControlLetter), 31))
CharacterValue[CharacterEscape  HexEscape] = CharacterValue[HexEscape]
CharacterValue[CharacterEscape  IdentityEscape] = IdentityEscape
action CharacterValue[ControlEscape] : Character
CharacterValue[ControlEscape  f] = ‘«FF»’
CharacterValue[ControlEscape  n] = ‘«LF»’
CharacterValue[ControlEscape  r] = ‘«CR»’
CharacterValue[ControlEscape  t] = ‘«TAB»’
CharacterValue[ControlEscape  v] = ‘«VT»’
Decimal Escapes
Syntax
DecimalEscape  DecimalIntegerLiteral [lookahead{DecimalDigit}]
DecimalIntegerLiteral 
	0
|	NonZeroDecimalDigits
NonZeroDecimalDigits 
	NonZeroDigit
|	NonZeroDecimalDigits DecimalDigit
NonZeroDigit  1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Semantics
action EscapeValue[DecimalEscape] : Integer
EscapeValue[DecimalEscape  DecimalIntegerLiteral [lookahead{DecimalDigit}]]
  = IntegerValue[DecimalIntegerLiteral]
action IntegerValue[DecimalIntegerLiteral] : Integer
IntegerValue[DecimalIntegerLiteral  0] = 0
IntegerValue[DecimalIntegerLiteral  NonZeroDecimalDigits]
  = IntegerValue[NonZeroDecimalDigits]
action IntegerValue[NonZeroDecimalDigits] : Integer
IntegerValue[NonZeroDecimalDigits  NonZeroDigit] = DecimalValue[NonZeroDigit]
IntegerValue[NonZeroDecimalDigits  NonZeroDecimalDigits1 DecimalDigit]
  = 10*IntegerValue[NonZeroDecimalDigits1] + DecimalValue[DecimalDigit]
action DecimalValue[NonZeroDigit] : Integer = digitValue(NonZeroDigit)
Hexadecimal Escapes
Syntax
HexEscape 
	x HexDigit HexDigit
|	u HexDigit HexDigit HexDigit HexDigit
HexDigit  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | a | b | c | d | e | f
Semantics
action CharacterValue[HexEscape] : Character
CharacterValue[HexEscape  x HexDigit1 HexDigit2]
  = codeToCharacter(16*HexValue[HexDigit1] + HexValue[HexDigit2])
CharacterValue[HexEscape  u HexDigit1 HexDigit2 HexDigit3 HexDigit4]
  = codeToCharacter(
         4096*HexValue[HexDigit1] + 256*HexValue[HexDigit2] + 16*HexValue[HexDigit3] +
         HexValue[HexDigit4])
action HexValue[HexDigit] : Integer = digitValue(HexDigit)
Character Class Escapes
Syntax
CharacterClassEscape 
	s
|	S
|	d
|	D
|	w
|	W
Semantics
action AcceptanceSet[CharacterClassEscape] : {Character}
AcceptanceSet[CharacterClassEscape  s] = reWhitespaces
AcceptanceSet[CharacterClassEscape  S] = {‘«NUL»’ ... ‘«uFFFF»’} – reWhitespaces
AcceptanceSet[CharacterClassEscape  d] = reDigits
AcceptanceSet[CharacterClassEscape  D] = {‘«NUL»’ ... ‘«uFFFF»’} – reDigits
AcceptanceSet[CharacterClassEscape  w] = reWordCharacters
AcceptanceSet[CharacterClassEscape  W] = {‘«NUL»’ ... ‘«uFFFF»’} – reWordCharacters
User-Specified Character Classes
Syntax
CharacterClass 
	[ [lookahead{^}] ClassRanges ]
|	[ ^ ClassRanges ]
ClassRanges 
	«empty»
|	NonemptyClassRangesdash
  {dash, noDash}
NonemptyClassRanges 
	ClassAtomdash
|	ClassAtom NonemptyClassRangesnoDash
|	ClassAtom - ClassAtomdash ClassRanges
Semantics
action AcceptanceSet[CharacterClass] : {Character}
AcceptanceSet[CharacterClass  [ [lookahead{^}] ClassRanges ]]
  = AcceptanceSet[ClassRanges]
AcceptanceSet[CharacterClass  [ ^ ClassRanges ]] = AcceptanceSet[ClassRanges]
action Invert[CharacterClass] : Boolean
Invert[CharacterClass  [ [lookahead{^}] ClassRanges ]] = false
Invert[CharacterClass  [ ^ ClassRanges ]] = true
action AcceptanceSet[ClassRanges] : {Character}
AcceptanceSet[ClassRanges  «empty»] = {}Character
AcceptanceSet[ClassRanges  NonemptyClassRangesdash]
  = AcceptanceSet[NonemptyClassRangesdash]
action AcceptanceSet[NonemptyClassRanges] : {Character}
AcceptanceSet[NonemptyClassRanges  ClassAtomdash] = AcceptanceSet[ClassAtomdash]
AcceptanceSet[NonemptyClassRanges  ClassAtom NonemptyClassRangesnoDash1]
  = AcceptanceSet[ClassAtom]  AcceptanceSet[NonemptyClassRangesnoDash1]
AcceptanceSet[NonemptyClassRanges  ClassAtom1 - ClassAtomdash2 ClassRanges]
  = let range: {Character}
             = characterRange(AcceptanceSet[ClassAtom1], AcceptanceSet[ClassAtomdash2])
     in range  AcceptanceSet[ClassRanges]
characterRange(low: {Character}, high: {Character}) : {Character}
  = if |low| ≠ 1 or |high| ≠ 1
     then throw syntaxError
     else let l: Character = min low;
               h: Character = min high
           in if l ≤ h
               then {l ... h}
               else throw syntaxError
Character Class Range Atoms
Syntax
ClassAtom 
	ClassCharacter
|	\ ClassEscape
ClassCharacterdash  UnicodeCharacter except \ | ]
ClassCharacternoDash  ClassCharacterdash except -
ClassEscape 
	DecimalEscape
|	b
|	CharacterEscape
|	CharacterClassEscape
Semantics
action AcceptanceSet[ClassAtom] : {Character}
AcceptanceSet[ClassAtom  ClassCharacter] = {ClassCharacter}
AcceptanceSet[ClassAtom  \ ClassEscape] = AcceptanceSet[ClassEscape]
action AcceptanceSet[ClassEscape] : {Character}
AcceptanceSet[ClassEscape  DecimalEscape]
  = if EscapeValue[DecimalEscape] = 0
     then {‘«NUL»’}
     else throw syntaxError
AcceptanceSet[ClassEscape  b] = {‘«BS»’}
AcceptanceSet[ClassEscape  CharacterEscape] = {CharacterValue[CharacterEscape]}
AcceptanceSet[ClassEscape  CharacterClassEscape] = AcceptanceSet[CharacterClassEscape]