JavaScript 2.0
Formal Description
Regular Expression Semantics
|
JavaScript 2.0
Formal Description
Regular Expression Semantics
|
|
Thursday, July 22, 1999
The regular expression semantics describe the actions the regular expression engine takes in order to transform a regular expression pattern into a function for matching against input strings. For convenience, the regular expression grammar is repeated here. See also the description of the semantic notation.
This document is also available as a Word 98 rtf file.
The regular expression semantics below are working (except for case-insensitive matches) and have been tried on sample cases, but they could be formatted better.
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’, ‘_’}
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.
type CharSetGenerator = Integer {Character}
A CharSetGenerator is a function executed at the time the regular expression is compiled that returns a set of characters that are accepted by a part of the pattern. The Integer argument contains the number of capturing left parentheses seen so far in the pattern.
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).
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]
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]
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]
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
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]
*+?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)
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
.\ AtomEscapeaction 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](parenIndex)
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]
action GenMatcher[AtomEscape] : MatcherGenerator
GenMatcher[AtomEscape DecimalOrOctalEscape](parenIndex: Integer)
= case EscapeValue[DecimalOrOctalEscape](parenIndex) of
octalCharacter(c: Character): characterMatcher(c);
backreference(n: Integer): backreferenceMatcher(n)
end
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
= if n > 0 and n |x.captures|
then x.captures[n - 1]
else
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 | Za | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | zaction 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»’
type EscapeValue = oneof {octalCharacter: Character; backreference: Integer}
An EscapeValue represents the
interpretation of a \ followed by one, two, or three decimal or octal digits. If the
escape is interpreted as an octal character code, the EscapeValue
action returns an octalCharacter; if the
escape is interpreted as a decimal backreference to a prior set of capturing parentheses, the
EscapeValue action returns a
backreference.
action EscapeValue[DecimalOrOctalEscape] : Integer EscapeValue
EscapeValue[DecimalOrOctalEscape DecimalDigit [lookahead{DecimalDigit}]]
(parenIndex: Integer)
= let n: Integer = DecimalValue[DecimalDigit]
in if n = 0
then octalCharacter ‘«NUL»’
else if n > parenIndex
then
else backreference n
EscapeValue[DecimalOrOctalEscape ZeroToThree OctalDigit [lookahead{OctalDigit}]]
(parenIndex: Integer)
= twoDigitEscapeValue(parenIndex, OctalValue[ZeroToThree], OctalValue[OctalDigit])
EscapeValue[DecimalOrOctalEscape ZeroToThree EightOrNine](parenIndex: Integer)
= twoDigitEscapeValue(parenIndex, OctalValue[ZeroToThree], DecimalValue[EightOrNine])
EscapeValue[DecimalOrOctalEscape FourToNine DecimalDigit](parenIndex: Integer)
= twoDigitEscapeValue(parenIndex, DecimalValue[FourToNine], DecimalValue[DecimalDigit])
EscapeValue[DecimalOrOctalEscape ZeroToThree OctalDigit1 OctalDigit2]
(parenIndex: Integer)
= octalCharacter
codeToCharacter(
64*OctalValue[ZeroToThree] + 8*OctalValue[OctalDigit1] + OctalValue[OctalDigit2])
action OctalValue[ZeroToThree] : Integer = digitValue(ZeroToThree)
action DecimalValue[FourToNine] : Integer = digitValue(FourToNine)
action OctalValue[OctalDigit] : Integer = digitValue(OctalDigit)
action DecimalValue[EightOrNine] : Integer = digitValue(EightOrNine)
twoDigitEscapeValue(parenIndex: Integer, digit1: Integer, digit2: Integer) : EscapeValue
= let n: Integer = 10*digit1 + digit2
in if n 10 and n parenIndex
then backreference n
else if digit1 < 8 and digit2 < 8
then octalCharacter codeToCharacter(8*digit1 + digit2)
else
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)
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
action AcceptanceSet[CharacterClass] : CharSetGenerator
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] : CharSetGenerator
AcceptanceSet[ClassRanges «empty»](parenIndex: Integer) = {}Character
AcceptanceSet[ClassRanges NonemptyClassRangesdash]
= AcceptanceSet[NonemptyClassRangesdash]
action AcceptanceSet[NonemptyClassRangesd] : CharSetGenerator
AcceptanceSet[NonemptyClassRangesd ClassAtomdash] = AcceptanceSet[ClassAtomdash]
AcceptanceSet[NonemptyClassRangesd ClassAtomd NonemptyClassRangesnoDash1]
(parenIndex: Integer)
= AcceptanceSet[ClassAtomd](parenIndex)
AcceptanceSet[NonemptyClassRangesnoDash1](parenIndex)
AcceptanceSet[NonemptyClassRangesd ClassAtomd1 - ClassAtomdash2 ClassRanges]
(parenIndex: Integer)
= let range: {Character}
= characterRange(
AcceptanceSet[ClassAtomd1](parenIndex),
AcceptanceSet[ClassAtomdash2](parenIndex))
in range AcceptanceSet[ClassRanges](parenIndex)
characterRange(low: {Character}, high: {Character}) : {Character}
= if |low| 1 or |high| 1
then
else let l: Character = min low;
h: Character = min high
in if l h
then {l ... h}
else
action AcceptanceSet[ClassAtomd] : CharSetGenerator
AcceptanceSet[ClassAtomd ClassCharacterd](parenIndex: Integer) = {ClassCharacterd}
AcceptanceSet[ClassAtomd \ ClassEscape] = AcceptanceSet[ClassEscape]
action AcceptanceSet[ClassEscape] : CharSetGenerator
AcceptanceSet[ClassEscape DecimalOrOctalEscape](parenIndex: Integer)
= case EscapeValue[DecimalOrOctalEscape](parenIndex) of
octalCharacter(c: Character): {c};
backreference(n: Integer):
end
AcceptanceSet[ClassEscape b](parenIndex: Integer) = {‘«BS»’}
AcceptanceSet[ClassEscape CharacterEscape](parenIndex: Integer)
= {CharacterValue[CharacterEscape]}
AcceptanceSet[ClassEscape CharacterClassEscape](parenIndex: Integer)
= AcceptanceSet[CharacterClassEscape]