April 2002 Draft
JavaScript 2.0
Formal Description
Regular Expression Semantics
 previousupnext

Thursday, February 7, 2002

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.

Semantics

tag syntaxError;
SemanticException = {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

tuple REInput
str: String,
ignoreCase: Boolean,
multiline: Boolean,
span: Boolean
end tuple;

Field str is the input string. ignoreCase, multiline, and span are the corresponding regular expression flags.

tag undefined;
Capture = String  {undefined};
tuple REMatch
endIndex: Integer,
captures: Capture[]
end tuple;
tag failure;
REResult = REMatch  {failure};

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.

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 REMatch result that contains the final state; if no match is possible, it returns a failure result.

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.

A Integer Matcher 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.

proc characterSetMatcher(acceptanceSet: Character{}, invert: Boolean): Matcher
proc m(t: REInput, x: REMatch, c: Continuation): REResult
i: Integer  x.endIndex;
s: String  t.str;
if i = |s| then return failure
elsif s[i]  acceptanceSet xor invert then
return c(REMatchendIndex: i + 1, captures: x.captures)
else return failure
end if
end proc;
return m
end proc;

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).

proc characterMatcher(ch: Character): Matcher
return characterSetMatcher({ch}, false)
end proc;

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

Execute[RegularExpressionPattern  Disjunction]: REInput  Integer  REResult
begin
m1: Matcher  GenMatcher[Disjunction](0);
proc e(t: REInput, index: Integer): REResult
x: REMatch  REMatchendIndex: index, captures: fillCapture(CountParens[Disjunction]);
return m1(t, x, successContinuation)
end proc;
return e
end;
proc successContinuation(x: REMatch): REResult
return x
end proc;
proc fillCapture(i: Integer): Capture[]
if i = 0 then return [] else return fillCapture(i – 1)  [undefined] end if
end proc;

Disjunctions

Syntax

Disjunction 
   Alternative
|  Alternative | Disjunction

Semantics

proc GenMatcher[Disjunction] (parenIndex: Integer): Matcher
[Disjunction  Alternative] do return GenMatcher[Alternative](parenIndex);
[Disjunction0  Alternative | Disjunction1] do
m1: Matcher  GenMatcher[Alternative](parenIndex);
m2: Matcher  GenMatcher[Disjunction1](parenIndex + CountParens[Alternative]);
proc m3(t: REInput, x: REMatch, c: Continuation): REResult
y: REResult  m1(t, x, c);
case y of
REMatch do return y;
{failure} do return m2(t, x, c)
end case
end proc;
return m3
end proc;
CountParens[Disjunction]: Integer;
CountParens[Disjunction  Alternative] = CountParens[Alternative];
CountParens[Disjunction0  Alternative | Disjunction1] = CountParens[Alternative] + CountParens[Disjunction1];

Alternatives

Syntax

Alternative 
   «empty»
|  Alternative Term

Semantics

proc GenMatcher[Alternative] (parenIndex: Integer): Matcher
[Alternative  «empty»] do
proc m(t: REInput, x: REMatch, c: Continuation): REResult
return c(x)
end proc;
return m;
[Alternative0  Alternative1 Term] do
m1: Matcher  GenMatcher[Alternative1](parenIndex);
m2: Matcher  GenMatcher[Term](parenIndex + CountParens[Alternative1]);
proc m3(t: REInput, x: REMatch, c: Continuation): REResult
proc d(y: REMatch): REResult
return m2(t, y, c)
end proc;
return m1(t, x, d)
end proc;
return m3
end proc;
CountParens[Alternative]: Integer;
CountParens[Alternative  «empty»] = 0;
CountParens[Alternative0  Alternative1 Term] = CountParens[Alternative1] + CountParens[Term];

Terms

Syntax

Term 
   Assertion
|  Atom
|  Atom Quantifier

Semantics

proc GenMatcher[Term] (parenIndex: Integer): Matcher
[Term  Assertion] do
proc m(t: REInput, x: REMatch, c: Continuation): REResult
if TestAssertion[Assertion](t, x) then return c(x) else return failure end if
end proc;
return m;
[Term  Atom] do return GenMatcher[Atom](parenIndex);
[Term  Atom Quantifier] do
m: Matcher  GenMatcher[Atom](parenIndex);
min: Integer  Minimum[Quantifier];
max: Limit  Maximum[Quantifier];
greedy: Boolean  Greedy[Quantifier];
if max  + then if max < min then throw syntaxError end if end if;
return repeatMatcher(m, min, max, greedy, parenIndex, CountParens[Atom])
end proc;
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

Limit = Integer  {+};
proc resetParens(x: REMatch, p: Integer, nParens: Integer): REMatch
captures: Capture[]  x.captures;
i: Integer  p;
while i < p + nParens do captures  captures[i \ undefined]; i  i + 1 end while;
return REMatchendIndex: x.endIndex, captures: captures
end proc;
proc repeatMatcher(body: Matcher, min: Integer, max: Limit, greedy: Boolean, parenIndex: Integer, nBodyParens: Integer): Matcher
proc m(t: REInput, x: REMatch, c: Continuation): REResult
if max = 0 then return c(x) end if;
proc d(y: REMatch): REResult
if min = 0 and y.endIndex = x.endIndex then return failure end if;
newMin: Integer  min;
if min  0 then newMin  min – 1 end if;
newMax: Limit  max;
if max  + then newMax  max – 1 end if;
m2: Matcher  repeatMatcher(body, newMin, newMax, greedy, parenIndex, nBodyParens);
return m2(t, y, c)
end proc;
xr: REMatch  resetParens(x, parenIndex, nBodyParens);
if min  0 then return body(t, xr, d)
elsif greedy then
z: REResult  body(t, xr, d);
case z of
REMatch do return z;
{failure} do return c(x)
end case
else
z: REResult  c(x);
case z of
REMatch do return z;
{failure} do return body(t, xr, d)
end case
end if
end proc;
return m
end proc;
Minimum[Quantifier]: Integer;
Minimum[Quantifier  QuantifierPrefix] = Minimum[QuantifierPrefix];
Minimum[Quantifier  QuantifierPrefix ?] = Minimum[QuantifierPrefix];
Maximum[Quantifier]: Limit;
Maximum[Quantifier  QuantifierPrefix] = Maximum[QuantifierPrefix];
Maximum[Quantifier  QuantifierPrefix ?] = Maximum[QuantifierPrefix];
Greedy[Quantifier]: Boolean;
Greedy[Quantifier  QuantifierPrefix] = true;
Greedy[Quantifier  QuantifierPrefix ?] = false;
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];
Maximum[QuantifierPrefix]: Limit;
Maximum[QuantifierPrefix  *] = +;
Maximum[QuantifierPrefix  +] = +;
Maximum[QuantifierPrefix  ?] = 1;
Maximum[QuantifierPrefix  { DecimalDigits }] = IntegerValue[DecimalDigits];
Maximum[QuantifierPrefix  { DecimalDigits , }] = +;
Maximum[QuantifierPrefix  { DecimalDigits1 , DecimalDigits2 }] = IntegerValue[DecimalDigits2];
IntegerValue[DecimalDigits]: Integer;
IntegerValue[DecimalDigits  DecimalDigit] = DecimalValue[DecimalDigit];
IntegerValue[DecimalDigits0  DecimalDigits1 DecimalDigit] = 10IntegerValue[DecimalDigits1] + DecimalValue[DecimalDigit];
DecimalValue[DecimalDigit]: Integer = digitValue(DecimalDigit);

Assertions

Syntax

Assertion 
   ^
|  $
|  \ b
|  \ B

Semantics

proc TestAssertion[Assertion] (t: REInput, x: REMatch): Boolean
[Assertion  ^] do
return x.endIndex = 0 or (t.multiline and t.str[x.endIndex – 1]  lineTerminators);
[Assertion  $] do
return x.endIndex = |t.str| or (t.multiline and t.str[x.endIndex]  lineTerminators);
[Assertion  \ b] do return atWordBoundary(x.endIndex, t.str);
[Assertion  \ B] do return not atWordBoundary(x.endIndex, t.str)
end proc;
proc atWordBoundary(i: Integer, s: String): Boolean
return inWord(i – 1, s) xor inWord(i, s)
end proc;
proc inWord(i: Integer, s: String): Boolean
if i = –1 or i = |s| then return false else return s[i]  reWordCharacters end if
end proc;

Atoms

Syntax

Atom 
   PatternCharacter
|  .
|  NullEscape
|  \ AtomEscape
|  CharacterClass
|  ( Disjunction )
|  ( ? : Disjunction )
|  ( ? = Disjunction )
|  ( ? ! Disjunction )
PatternCharacter  UnicodeCharacter except ^ | $ | \ | . | * | + | ? | ( | ) | [ | ] | { | } | |

Semantics

proc GenMatcher[Atom] (parenIndex: Integer): Matcher
[Atom  PatternCharacter] do return characterMatcher(PatternCharacter);
[Atom  .] do
proc m1(t: REInput, x: REMatch, c: Continuation): REResult
a: Character{}  t.span ? {} : lineTerminators;
m2: Matcher  characterSetMatcher(a, true);
return m2(t, x, c)
end proc;
return m1;
[Atom  NullEscape] do
proc m(t: REInput, x: REMatch, c: Continuation): REResult
return c(x)
end proc;
return m;
[Atom  \ AtomEscape] do return GenMatcher[AtomEscape](parenIndex);
[Atom  CharacterClass] do
a: Character{}  AcceptanceSet[CharacterClass];
return characterSetMatcher(a, Invert[CharacterClass]);
[Atom  ( Disjunction )] do
m1: Matcher  GenMatcher[Disjunction](parenIndex + 1);
proc m2(t: REInput, x: REMatch, c: Continuation): REResult
proc d(y: REMatch): REResult
ref: Capture  t.str[x.endIndex ... y.endIndex – 1];
updatedCaptures: Capture[]  y.captures[parenIndex \ ref];
return c(REMatchendIndex: y.endIndex, captures: updatedCaptures)
end proc;
return m1(t, x, d)
end proc;
return m2;
[Atom  ( ? : Disjunction )] do return GenMatcher[Disjunction](parenIndex);
[Atom  ( ? = Disjunction )] do
m1: Matcher  GenMatcher[Disjunction](parenIndex);
proc m2(t: REInput, x: REMatch, c: Continuation): REResult
y: REResult  m1(t, x, successContinuation);
case y of
REMatch do return c(REMatchendIndex: x.endIndex, captures: y.captures);
{failure} do return failure
end case
end proc;
return m2;
[Atom  ( ? ! Disjunction )] do
m1: Matcher  GenMatcher[Disjunction](parenIndex);
proc m2(t: REInput, x: REMatch, c: Continuation): REResult
case m1(t, x, successContinuation) of
REMatch do return failure;
{failure} do return c(x)
end case
end proc;
return m2
end proc;
CountParens[Atom]: Integer;
CountParens[Atom  PatternCharacter] = 0;
CountParens[Atom  .] = 0;
CountParens[Atom  NullEscape] = 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

NullEscape  \ _
AtomEscape 
   DecimalEscape
|  CharacterEscape
|  CharacterClassEscape

Semantics

proc GenMatcher[AtomEscape] (parenIndex: Integer): Matcher
[AtomEscape  DecimalEscape] do
n: Integer  EscapeValue[DecimalEscape];
if n = 0 then return characterMatcher(‘«NUL»’)
elsif n > parenIndex then throw syntaxError
else return backreferenceMatcher(n)
end if;
[AtomEscape  CharacterEscape] do
return characterMatcher(CharacterValue[CharacterEscape]);
[AtomEscape  CharacterClassEscape] do
return characterSetMatcher(AcceptanceSet[CharacterClassEscape], false)
end proc;
proc backreferenceMatcher(n: Integer): Matcher
proc m(t: REInput, x: REMatch, c: Continuation): REResult
ref: Capture  nthBackreference(x, n);
case ref of
String do
i: Integer  x.endIndex;
s: String  t.str;
j: Integer  i + |ref|;
if j  |s| and s[i ... j – 1] = ref then
return c(REMatchendIndex: j, captures: x.captures)
else return failure
end if;
{undefined} do return c(x)
end case
end proc;
return m
end proc;
proc nthBackreference(x: REMatch, n: Integer): Capture
return x.captures[n – 1]
end proc;

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

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;
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

EscapeValue[DecimalEscape  DecimalIntegerLiteral [lookahead{DecimalDigit}]]: Integer = IntegerValue[DecimalIntegerLiteral];
IntegerValue[DecimalIntegerLiteral]: Integer;
IntegerValue[DecimalIntegerLiteral  0] = 0;
IntegerValue[DecimalIntegerLiteral  NonZeroDecimalDigits] = IntegerValue[NonZeroDecimalDigits];
IntegerValue[NonZeroDecimalDigits]: Integer;
IntegerValue[NonZeroDecimalDigits  NonZeroDigit] = DecimalValue[NonZeroDigit];
IntegerValue[NonZeroDecimalDigits0  NonZeroDecimalDigits1 DecimalDigit] = 10IntegerValue[NonZeroDecimalDigits1] + DecimalValue[DecimalDigit];
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

CharacterValue[HexEscape]: Character;
CharacterValue[HexEscape  x HexDigit1 HexDigit2] = codeToCharacter(16HexValue[HexDigit1] + HexValue[HexDigit2]);
CharacterValue[HexEscape  u HexDigit1 HexDigit2 HexDigit3 HexDigit4] = codeToCharacter(4096HexValue[HexDigit1] + 256HexValue[HexDigit2] + 16HexValue[HexDigit3] + HexValue[HexDigit4]);
HexValue[HexDigit]: Integer = digitValue(HexDigit);

Character Class Escapes

Syntax

CharacterClassEscape 
   s
|  S
|  d
|  D
|  w
|  W

Semantics

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
|  NullEscape ClassRanges

Semantics

AcceptanceSet[CharacterClass]: Character{};
AcceptanceSet[CharacterClass  [ [lookahead{^}] ClassRanges ]] = AcceptanceSet[ClassRanges];
AcceptanceSet[CharacterClass  [ ^ ClassRanges ]] = AcceptanceSet[ClassRanges];
Invert[CharacterClass]: Boolean;
Invert[CharacterClass  [ [lookahead{^}] ClassRanges ]] = false;
Invert[CharacterClass  [ ^ ClassRanges ]] = true;
AcceptanceSet[ClassRanges]: Character{};
AcceptanceSet[ClassRanges  «empty»] = {};
AcceptanceSet[ClassRanges  NonemptyClassRangesdash] = AcceptanceSet[NonemptyClassRangesdash];
AcceptanceSet[NonemptyClassRanges]: Character{};
AcceptanceSet[NonemptyClassRanges  ClassAtomdash] = AcceptanceSet[ClassAtomdash];
AcceptanceSet[NonemptyClassRanges0  ClassAtom NonemptyClassRangesnoDash1] = AcceptanceSet[ClassAtom]  AcceptanceSet[NonemptyClassRangesnoDash1];
AcceptanceSet[NonemptyClassRanges  ClassAtom1 - ClassAtomdash2 ClassRanges] = characterRange(AcceptanceSet[ClassAtom1], AcceptanceSet[ClassAtomdash2])  AcceptanceSet[ClassRanges];
AcceptanceSet[NonemptyClassRanges  NullEscape ClassRanges] = AcceptanceSet[ClassRanges];
proc characterRange(low: Character{}, high: Character{}): Character{}
if |low|  1 or |high|  1 then throw syntaxError end if;
l: Character  min low;
h: Character  min high;
if l  h then return {l ... h} else throw syntaxError end if
end proc;

Character Class Range Atoms

Syntax

ClassAtom 
   ClassCharacter
|  \ ClassEscape
ClassCharacterdash  UnicodeCharacter except \ | ]
ClassCharacternoDash  ClassCharacterdash except -
ClassEscape 
   DecimalEscape
|  b
|  CharacterEscape
|  CharacterClassEscape

Semantics

AcceptanceSet[ClassAtom]: Character{};
AcceptanceSet[ClassAtom  ClassCharacter] = {ClassCharacter};
AcceptanceSet[ClassAtom  \ ClassEscape] = AcceptanceSet[ClassEscape];
AcceptanceSet[ClassEscape]: Character{};
AcceptanceSet[ClassEscape  DecimalEscape]
begin
if EscapeValue[DecimalEscape] = 0 then return {‘«NUL»’}
else throw syntaxError
end if
end;
AcceptanceSet[ClassEscape  b] = {‘«BS»’};
AcceptanceSet[ClassEscape  CharacterEscape] = {CharacterValue[CharacterEscape]};
AcceptanceSet[ClassEscape  CharacterClassEscape] = AcceptanceSet[CharacterClassEscape];
Waldemar Horwat
Last modified Thursday, February 7, 2002
 previousupnext