Proposed Update Unicode Technical Standard #18

Unicode Regular Expressions

Summary

This document describes guidelines for how to adapt regular expression engines to use Unicode.

This is the last call version, so please send feedback as soon as possible.

Status

This document is a proposed update of a previously approved Unicode Technical Report. Publication does not imply endorsement by the Unicode Consortium. This is a draft document which may be updated, replaced, or superseded by other documents at any time. This is not a stable document; it is inappropriate to cite this document as other than a work in progress.

A Unicode Technical Standard (UTS) is an independent specification. Conformance to the Unicode Standard does not imply conformance to any UTS. Each UTS specifies a base version of the Unicode Standard. Conformance to the UTS requires conformance to that version or higher.

Please submit corrigenda and other comments with the online reporting form [Feedback]. Related information that is useful in understanding this document is found in [References]. For the latest version of the Unicode Standard see [Unicode]. For a list of current Unicode Technical Reports see [Reports]. For more information about versions of the Unicode Standard, see [Versions].

Contents

0 Introduction

0.1 Notation

0.2 Conformance

1 Basic Unicode Support: Level 1

1.1 Hex notation

1.2 Properties

1.3 Subtraction and Intersection

1.4 Simple Word Boundaries

1.5 Simple Loose Matches

1.6 End Of Line

1.7 Supplementary Characters

2 Extended Unicode Support: Level 2

2.1 Canonical Equivalents

2.2 Default Grapheme Clusters

2.3 Default Words

2.4 Default Loose Matches

2.5 Name Properties

3 Tailored Support: Level 3

3.1 Tailored Punctuation

3.2 Tailored Grapheme Clusters

3.3 Tailored Words

3.4 Tailored Loose Matches

3.5 Tailored Ranges

3.6 Context Matching

3.7 Incremental Matches

3.8 Unicode Set Sharing

3.9 Possible Match Sets

3.10 Folded Matching

3.11 Submatchers

Annex A. Character Blocks

Annex B. Sample Collation Character Code

Annex C. Compatibly Properties

References

Acknowledgments

Modifications

0 Introduction

The following describes general guidelines for extending regular expression engines to handle Unicode. The following issues are involved in such extensions.

• Unicode is a large character set—regular expression engines that are only adapted to handle small character sets will not scale well.
• Unicode encompasses a wide variety of languages which can have very different characteristics than English or other western European text.

There are three fundamental levels of Unicode support that can be offered by regular expression engines:

• Level 1: Basic Unicode Support. At this level, the regular expression engine provides support for Unicode characters as basic logical units. (This is independent of the actual serialization of Unicode as UTF-8, UTF-16BE, UTF-16LE, UTF-32BE, or UTF-32LE.) This is a minimal level for useful Unicode support. It does not account for end-user expectations for character support, but does satisfy most low-level programmer requirements. The results of regular expression matching at this level is independent of country or language. At this level, the user of the regular expression engine would need to write more complicated regular expressions to do full Unicode processing.
• Level 2: Extended Unicode Support. At this level, the regular expression engine also accounts for default grapheme clusters (what the end-user generally thinks of as a character), better word-break, and canonical equivalence. This is still a default level—independent of country or language—but provides much better support for end-user expectations than the raw level 1, without the regular-expression writer needing to know about some of the complications of Unicode encoding structure.
• Level 3: Tailored Support. At this level, the regular expression engine also provides for tailored treatment of characters (including country- or language-specific behavior), for example, whereby the characters ch can behave as a single character (in Slovak or traditional Spanish). The results of a particular regular expression reflect the end-users expectations of what constitutes a character in their language, and what order the characters are in. However, there is a performance impact to support at this level.

One of the most important requirements for a regular expression engine is to document clearly what Unicode features are and are not supported. Even if higher-level support is not currently offered, provision should be made for the syntax to be extended in the future to encompass those features.

Note: Unicode is a constantly evolving standard: new characters will be added in the future. This means that a regular expression that tests for, say, currency symbols will have different results in Unicode 2.0 than in Unicode 2.1 (where the Euro currency symbol was added.)

At any level, efficiently handling properties or conditions based on a large character set can take a lot of memory. A common mechanism for reducing the memory requirements — while still maintaining performance — is the two-stage table, discussed in Chapter 5 of The Unicode Standard [Unicode]. For example, the Unicode character properties required in RL1.2 Properties can be stored in memory in a two-stage table with only 7 or 8Kbytes. Accessing those properties only takes a small amount of bit-twiddling and two array accesses.

Note: For ease of reference, the section ordering for this document is intended to be as stable as possible over successive versions. That may lead, in some cases, to the ordering of the sections being less than optimal.

0.1 Notation

In order to describe regular expression syntax, we will use an extended BNF form:

The following syntax for character ranges will be used in successive examples.

Note: This is only a sample syntax for the purposes of examples in this document. (Regular expression syntax varies widely: the issues discussed here would need to be adapted to the syntax of the particular implementation. However, it is important to have a concrete syntax to correctly illustrate the different issues.

In general, the syntax here is similar to that of Perl Regular Expressions [Perl].) In some cases, this gives multiple syntactic constructs that provide for the same functionality.

LIST := "[" NEGATION? ITEM (SEP? ITEM)* "]"
ITEM := CODE_POINT2
     := CODE_POINT2 "-" CODE_POINT2 // range

CODE_POINT2 := ESCAPE CODE_POINT
            := CODE_POINT

NEGATION := "^"
SEP := ""  // no separator = union 
    := "|" // union
ESCAPE := "\"

Code_point refers to any Unicode code point from U+0000 to U+10FFFF, although typically the only ones of interest will be those representing characters. Whitespace is allowed between any elements, but to simplify the presentation the many occurrences of " "* are omitted.

Code points that are syntax characters or whitespace are typically escaped. For more information see [Syntax].

Examples:

Where string offsets are used in examples, they are from zero to n (the length of the string), and indicate positions between characters. Thus in "abcde", the substring from 2 to 4 includes the two characters "cd".

0.2 Conformance

The following describes the possible ways that an implementation can claim conformance to this technical standard.

All syntax and API presented in this document is only for the purpose of illustration; there is absolutely no requirement to follow such syntax or API. Regular expression syntax varies widely: the features discussed here would need to be adapted to the syntax of the particular implementation. In general, the syntax in examples is similar to that of Perl Regular Expressions [Perl], but it may not be exactly the same. While the API examples generally follow Java style, it is again only for illustration.

RL1.1 Hex Notation

RL1.2 Properties

RL1.3 Subtraction and Intersection

RL1.4 Simple Word Boundaries

RL1.5 Simple Loose Matches

RL1.6 End Of Line

RL1.7 Supplementary Characters

RL2.1 Canonical Equivalents

RL2.2 Default Grapheme Clusters

RL2.3 Default Words

RL2.4 Default Loose Matches

RL2.5 Name Properties

RL3.1 Tailored Punctuation

RL3.2 Tailored Grapheme Clusters

RL3.3 Tailored Words

RL3.4 Tailored Loose Matches

RL3.5 Tailored Ranges

RL3.6 Context Matching

RL3.7 Incremental Matches

RL3.8 Unicode Set Sharing

RL3.9 Possible Match Sets

RL3.10 Folded Matching

RL3.11 Submatchers

For example, an implementation may claim conformance to Level 1, plus Context Matching, and Incremental Matches. Another implementation may claim conformance to Level 1, except for Subtraction and Intersection.

Notes:

• A regular expression engine may be operating in the context of a larger system. In that case some of the requirements may be met by the overall system. For example, the requirements of section 2.1 might be best met by making normalization available as a part of the larger system, and requiring users of the system to normalize strings where desired before supplying them to the regular-expression engine. Such usage is conformant, as long as the situation is clearly documented.

• A conformance claim may also include capabilities added by an optional add-on, such as an optional library module, as long as this is clearly documented.

• For backwards compatibility, some of the functionality may only be available if some special setting is turned on. None of the conformance requirements require the functionality to be available by default.

1 Basic Unicode Support: Level 1

Regular expression syntax usually allows for an expression to denote a set of single characters, such as [a-z A-Z 0-9]. Since there are a very large number of characters in the Unicode standard, simple list expressions do not suffice.

1.1 Hex notation

The character set used by the regular expression writer may not be Unicode, or may not have the ability to input all Unicode code points from a keyboard.

A sample notation for listing hex Unicode characters within strings is by prefixing four hex digits with "\u" and prefixing eight hex digits with "\U". This would provide for the following addition:

<codepoint> := <character>
<codepoint> := ESCAPE U_SHORT_MARK
               HEX_CHAR HEX_CHAR HEX_CHAR HEX_CHAR

<codepoint> := ESCAPE U_LONG_MARK
               HEX_CHAR HEX_CHAR HEX_CHAR HEX_CHAR
               HEX_CHAR HEX_CHAR HEX_CHAR HEX_CHAR

U_SHORT_MARK := "u"
U_LONG_MARK := "U"

Examples:

• Note: instead of [...\u3040...], an alternate syntax is [...\x{3040}...], as in Perl 5.6 and later.
• Note: more advanced regular expression engines can also offer the ability to use the Unicode character name for readability. See 2.5 Name Properties.

1.2 Properties

Since Unicode is a large character set, a regular expression engine needs to provide for the recognition of whole categories of characters as well as simply ranges of characters; otherwise the listing of characters becomes impractical and error-prone. This is done by providing syntax for sets of characters based on the Unicode character properties, and allowing them to be mixed with lists and ranges of individual code points.

There are a large number of Unicode Character Database properties. The official data mapping Unicode characters (and code points) to properties is the Unicode Character Database [UCD]. See also Chapter 4 in The Unicode Standard [Unicode].

The recommended names for UCD properties and property values are in PropertyAliases.txt [Prop] and PropertyValueAliases.txt [PropValue]. There are both abbreviated names and longer, more descriptive names. It is strongly recommended that both names be recognized, and that loose matching of property names be used, whereby the case distinctions, whitespace, hyphens, and underbar are ignored.

Note: it may be a useful implementation technique to load the Unicode tables that support properties and other features on demand, to avoid unnecessary memory overhead for simple regular expressions that don't use those properties.

Where a regular expression is expressed as much as possible in terms of higher-level semantic constructs such as Letter, it makes it practical to work with the different alphabets and languages in Unicode. Here is an example of a syntax addition that permits properties.

Notice that following Perl Syntax, the p is lowercase to indicate a positive match, and uppercase to indicate a negative match.

Examples:

Some properties are binary: they are either true or false for a given code point. In that case, only the property name is required. Others have multiple values, so for uniqueness both the property name and the property value need to be included. For example, Alphabetic is both a binary property and a value of the Line_Break enumeration, so \p{Alphabetic} would mean the binary property, and \p{Line Break:Alphabetic} or \p{Line_Break=Alphabetic} would mean the enumerated property. There are two exceptions to this: the properties Script and General Category commonly have the property name omitted. Thus \p{Not_Assigned} is equivalent to \p{General_Category = Not_Assigned}, and \p{Greek} is equivalent to \p{Script:Greek}.

Of these, only General Category and Script are not binary. An implementation that does not support non-binary enumerated properties can essentially "flatten" the enumerated type. Thus, for example, instead of \p{script=latin} the syntax could be \p{script_latin}.

General Category Property

The most basic overall character property is the General Category, which is a basic categorization of Unicode characters into: Letters, Punctuation, Symbols, Marks, Numbers, Separators, and Other. These property values each have a single letter abbreviation, which is the uppercase first character except for separators, which use Z. The official data mapping Unicode characters to the General Category value is in UnicodeData.txt [UData].

Each of these categories has different subcategories. For example, the subcategories for Letter are uppercase, lowercase, titlecase, modifier, and other (in this case, other includes uncased letters such as Chinese). By convention, the subcategory is abbreviated by the category letter (in uppercase), followed by the first character of the subcategory in lowercase. For example, Lu stands for Uppercase Letter.

Note: Since it is recommended that the property syntax be lenient as to spaces, casing, hyphens and underbars, any of the following should be equivalent: \p{Lu}, \p{lu}, \p{uppercase letter}, \p{uppercase letter}, \p{Uppercase_Letter}, and \p{uppercaseletter}

The General Category property values are listed below. For more information on the meaning of these values, see UCD.html [UDataDoc].

Script Property

A regular-expression mechanism may choose to offer the ability to identify characters on the basis of other Unicode properties besides the General Category. In particular, Unicode characters are also divided into scripts as described in UTR #24: Script Names [ScriptDoc] (for the data file, see Scripts.txt [ScriptData]). Using a property such as \p{Greek} allows people test letters for whether they are Greek or not.

Note, however, that the usage model for the script property normally requires that people construct somewhat more complex regular expressions, because a great many characters are shared between scripts. Documentation should point users to the description in UTR #24.

Other Properties

Other useful properties are described in the documentation for the Unicode Character Database, cited above. The binary properties include:

• Bidi_Control, Join_Control

• ASCII_Hex_Digit, Hex_Digit

• ID_Start, ID_Continue, XID_Start, XID_Continue

• NF*_NO, NF*_MAYBE

The enumerated non-binary properties include:

• Decomposition_Type

• Numeric_Type

• East_Asian_Width

• Line_Break

The numeric properties include:

• Numeric_Value

The string properties include:

• Name

  • For details on the implementation of the name property, see

• Age

  • Caution: the DerivedAge data file in the UCD provides the deltas between versions, for compactness. However, when using the property all characters included in that version are include. Thus \p{age=3.0} includes the letter a, which was included in Unicode 1.0. To get characters that are new in a particular version, subtract off the previous version as described in 1.3 Subtraction and Intersection. E.g. [\p{age=3.1} - \p{age=3.0]

A full list of the available properties is on UCD Properties. See also 2.5 Extended Properties.

Blocks

Unicode blocks can sometimes also be a useful enumerated property. However, there are some very significant caveats to the use of Unicode blocks for the identification of characters: see Annex A. Character Blocks. If blocks are used, some of the names can collide with Script names, so they should be distinguished, such as with syntax like \p{Greek Block} or \p{Block=Greek}.

1.3 Subtraction and Intersection

As discussed above, character properties are essential with a large character set. In addition, there needs to be a way to "subtract" characters from what is already in the list. For example, one may want to include all non-ASCII letters without having to list every character in \p{letter} that is not one of those 52.

ITEM := "[" ITEM "]" // for grouping
SEP := ""            // no separator = union 
    := "|"           // union
    := "&"           // intersection
    := "-"           // removal = set difference

Implementations may also choose to offer other set operations, such as symmetric difference: [\p{letter} ⊖ \p{ascii}]

Note: In the sample syntax used here:

1. The symbol "-" between two characters still means a range, not a set-difference. That is:

   • [\p{ascii} - aeiouy] is equivalent to [\p{ascii} - [aeiouy]]

   • [aeiouy & \p{ascii}] is equivalent to [[aeiouy] & \p{ascii}]

2. Union binds more closely than intersection, which binds more closely than removal. Otherwise items bind from the left. (However, such binding or precedence may vary by regular expression engine.)

   For example, we get the following, where A..E stand for expressions, not characters:

   • [A|B|C-D|E] is the same as [[A|B|C] - [D|E]]

     • That is, it means form the union of A, B, and C, and then subtract the union of D and E.

   • [A - B - C - D & E] is the same as [[[A - B] - C] - [D & E]]

     • That is, take A, then remove all Bs, then all Cs, then remove the intersection of D and E.

Examples:

1.4 Simple Word Boundaries

Most regular expression engines allow a test for word boundaries (such as by "\b" in Perl). They generally use a very simple mechanism for determining word boundaries: one example of that would be having word boundaries between any pair of characters where one is a <word_character> and the other is not, or at the start and end of a string. This is not adequate for Unicode regular expressions.

Level 2 provides more general support for word boundaries between arbitrary Unicode characters which may override this behavior.

1.5 Simple Loose Matches

The only loose matches that most regular expression engines offer is caseless matching. If the engine does offers this, then it needs to account for the large range of cased Unicode characters outside of ASCII.

In addition, because of the vagaries of natural language, there are situations where two different Unicode characters have the same uppercase or lowercase. To meet this requirement, implementations must implement these in accordance with the Unicode Standard. For example, the Greek U+03C3 "σ" small sigma, U+03C2 "ς" small final sigma, and U+03A3 "Σ" capital sigma all match.

Some caseless matches may match one character against two: for example, U+00DF "ß" matches the two characters "SS". And case matching may vary by locale. However, because many implementations are not set up to handle this, at Level 1 only simple case matches are necessary. To correctly implement a caseless match, see Chapter 3 of the Unicode Standard [Unicode]. The data file supporting caseless matching is CaseFolding.txt [CaseData].

To meet this requirement, where an implementation also offers case conversions, then these must also follow Chapter 3 of the Unicode Standard [Unicode]. The relevant data files are SpecialCasing.txt [SpecialCasing] and UnicodeData.txt [UData].

1.6 End Of Line

Most regular expression engines also allow a test for line boundaries: end-of-line or start-of-line. This presumes that lines of text are separated by line (or paragraph) separators.

Formfeed (U+000C) also normally indicates an end-of-line. For more information, see Chapter 3 of The Unicode Standard [Unicode].

These characters should be uniformly handled in determining logical line numbers, start-of-line, end-of-line, and arbitrary-character implementations. Logical line number is useful for compiler error messages and the like. Regular expressions often allow for SOL and EOL patterns, which match certain boundaries. Often there is also a "non-line-separator" arbitrary character pattern that excludes line separator characters.

1. Logical line number
   • The line number is increased by one for each occurrence of:
     \u2028 | \u2029 | \u000D\u000A | \u000A | \u000C | \u000D | \u0085
2. Logical beginning of line (often "^")
   • SOL is at the start of a file or string, and also immediately following any occurrence of:
     \u2028 | \u2029 | \u000D\u000A | \u000A | \u000C | \u000D | \u0085
   • Note that there is no empty line within the sequence \u000D\u000A.
3. Logical end of line (often "$")
   • EOL at the end of a file or string, and also immediately preceding any occurrence of:
     \u2028 | \u2029 | \u000D\u000A | \u000A | \u000C | \u000D | \u0085
   • Note that there is no empty line within the sequence \u000D\u000A.
4. Arbitrary character pattern (often ".")
   • should not match any of
     \u2028 | \u2029 | \u000A | \u000C | \u000D | \u0085

   • In "multiline mode", these would match, and \u000D\u000A matches as if it were a single character.

   • Note that ^.*$ (an empty line pattern) should not match the empty string within the sequence \u000D\u000A, but should match the empty string within the sequence \u000A\u000D.

It is strongly recommended that there be a regular expression meta-character, such as "\R", for matching all line ending characters and sequences listed above (e.g. in #1). It would thus be shorthand for (\u000D\u000A | [\u2028\u2029\u000A\u000C\u000D\u0085]).

1.7 Code Points

A fundamental requirement is that Unicode text be interpreted semantically by code point, not code units.

UTF-16 uses pairs of Unicode code units to express code points above FFFF₁₆. Surrogate pairs (or their equivalents in other encoding forms) are be handled internally as single code point values. In particular, [\u0000-\U0010000] will match all the following sequence of code units:

2 Extended Unicode Support: Level 2

Level 1 support works well in many circumstances. However, it does not handle more complex languages or extensions to the Unicode Standard very well. Particularly important cases are canonical equivalence, word boundaries, default grapheme cluster boundaries, and loose matches. (For more information about boundary conditions, see The Unicode Standard, Section 5-15.)

Level 2 support matches much more what user expectations are for sequences of Unicode characters. It is still locale-independent and easily implementable. However, the implementation may be slower when supporting Level 2, and some expressions may require Level 1 matches. Thus it is often useful to have some sort of syntax that will turn Level 2 support on and off.

2.1 Canonical Equivalents

There are many instances where a character can be equivalently expressed by two different sequences of Unicode characters. For example, [ä] should match both "ä" and "a\u0308". (See UAX #15: Unicode Normalization [Norm] and Sections 2.5 and 3.9 of The Unicode Standard for more information.)

There are two main options for implementing this:

1. Before (or during) processing, translate text (and pattern) into a normalized form. This is the simplest to implement, since there are available code libraries for doing normalization

2. Expand the regular expression internally into a more generalized regular expression that takes canonical equivalence into account. For example, the expression [a-z ä] can be internally turned into [a-z ä] | (a \u0308). While this can be faster, it may also be substantially more difficult to generate expressions capturing all of the possible equivalent sequences.

Note: Combining characters are required for many characters. Even when text is in Normalization Form C, there may be combining characters in the text.

2.2 Default Grapheme Clusters

One or more Unicode characters may make up what the user thinks of as a character. To avoid ambiguity with the computer use of the term character, this is called a grapheme cluster. For example, "G" + acute-accent is a grapheme cluster: it is thought of as a single character by users, yet is actually represented by two Unicode characters.

Note: default grapheme clusters were previously referred to as "locale-independent graphemes". The term cluster has been added to emphasize that the term grapheme as used differently in linguistics. For simplicity and to align with UTS #10: Unicode Collation Algorithm [Collation], the terms "locale-independent" and "locale-dependent" been also changed to "default" and "tailored" respectively.

Essentially, the default grapheme clusters do only two things: they keep Hangul syllables together, and they don't break before non-spacing marks.

These default grapheme clusters are not the same as tailored grapheme clusters, which are covered in Level 3, Tailored Grapheme Clusters. The default grapheme clusters are determined according to the rules in UTR #29: Text Boundaries [Boundaries].

For example, an implementation could interpret "\X" as matching any default grapheme cluster, while interpreting "." as matching any single code point. It could interpret "\h" as a zero-width match against any grapheme cluster boundary, and "\H" as the negation of that.

Regular expression engines should also provide some mechanism for easily matching against literal clusters, since they are more likely to match user expectations for many languages. One mechanism for doing that is to have explicit syntax for literal clusters, as in the following. This syntax can also be used for tailored grapheme clusters (Tailored Grapheme Clusters).

Examples:

These can be expressed syntactically by breaking them into combinations of code point sets and other constructs: [a-z ñ \q{ch} \q{ll} \q{rr}] is equivalent to ([a-z ñ] | ch | ll | rr), but that is not as convenient when other options are added, as in Level 3.

A typical implementation of the inverse of a set containing literal clusters simply removes those strings, thus [^a-z ñ \q{ch} \q{ll} \q{rr}] is equivalent to [^a-z ñ]. Without literal clusters, intersection and set-difference can be expressed simply as a combination of the other with inverse. However, this is not the case if the implementation of inverse simply removes the strings. Thus:

• [\p{letter} - \p{ascii}] is equivalent to [\p{letter} & [^\p{ascii}]]

• [\p{letter} & \p{ascii}] is equivalent to [\p{letter} - [^\p{ascii}]]

• [[a\q{rr}] - [a\q{rr}]] is not equivalent to [[a\q{rr}] & [^a\q{rr}]]

2.3 Default Words

The simple Level 1 support using simple <word_character> classes is only a very rough approximation of user word boundaries. A much better method takes into account more context than just a single pair of letters. A general algorithm can take care of character and word boundaries for most of the world's languages. For more information, see UTR #29: Text Boundaries [Boundaries].

Note: Word-break boundaries and line-break boundaries are not generally the same; line breaking has a much more complex set of requirements to meet the typographic requirements of different languages. See UAX #14: Line Breaking Properties [LineBreak] for more information. However, line breaks are not generally relevant to general regular expression engines.

A fine-grained approach to languages such as Chinese or Thai, languages that do not have spaces, requires information that is beyond the bounds of what a Level 2 algorithm can provide.

2.4 Default Loose Matches

At Level 1, caseless matches do not need to handle cases where one character matches against two. Level 2 includes caseless matches where one character may match against two (or more) characters. For example, 00DF "ß" will match against the two characters "SS".

To correctly implement a caseless match and case conversions, see UAX #21: Case Mappings [Case]. For ease of implementation, a complete case folding file is supplied at CaseFolding.txt [CaseData].

If the implementation containing the regular expression engine also offers case conversions, then these should also be done in accordance with UAX #21, with the full mappings. The relevant data files are SpecialCasing.txt [SpecialCasing] and UnicodeData.txt [UData].

2.5 Name Properties

When using names in regular expressions, the main data is supplied in the Name property in the UCD, as described in [UDataDoc], or computed as in the case of CJK Ideographs or Hangul Syllables. Certain code points are not assigned names in the standard. These should be given names based on the General_Category:

The ISO names for the control characters may be unfamiliar, especially since the names at some point, so it is recommended that they be supplemented with other aliases. For example, for U+0009 the implementation could accept the official name CHARACTER TABULATION, and also HORIZONTAL TABULATION, HT, and TAB.

Individually Named Characters

This facility provides syntax for specifying a code point by supplying the precise name, such as the following. This syntax specifies a single code point, which can thus be used in ranges.

As with other property values, names should use a loose match, disregarding spaces and "-" (the character "_" cannot occur in Unicode character names). An implementation may also choose to allow namespaces, where some prefix like "LATIN LETTER" is set globally and used if there is no match otherwise.

There are, however, three instances that require special-casing with loose matching, where an extra test must be made for the presence or absence of a hyphen.

• U+0F68 TIBETAN LETTER A and
  U+0F60 TIBETAN LETTER -A

• U+0FB8 TIBETAN SUBJOINED LETTER A and
  U+0FB0 TIBETAN SUBJOINED LETTER -A

• U+116C HANGUL JUNGSEONG OE and
  U+1180 HANGUL JUNGSEONG O-E

 Examples:

• \N{WHITE SMILING FACE} is equivalent to \u263A

• \N{GREEK SMALL LETTER ALPHA} is equivalent to \u03B1

• \N{FORM FEED} is equivalent to \u000C

• \N{SHAVIAN LETTER PEEP} is equivalent to \U00010450

• [\N{GREEK SMALL LETTER ALPHA}-\N{GREEK SMALL LETTER BETA}] is equivalent to [\u03B1-\u03B2]

Unicode Name Property

The Unicode Name Property with wildcards is slightly different. Instead of a single code point, it represents a set, and thus cannot be used in character ranges. The value to be matched is assumed to be a regular expression. The regular expression must support at least wild-cards; other regular expressions features are recommended but optional.

Note: Because regular-expressions are using in matching, spaces and '-' are significant; it is presumed that people will use regular-expression features to ignore these if desired.

Examples, where ".*" matches any character:

3 Tailored Support: Level 3

All of the above deals with a default specification for a regular expression. However, a regular expression engine also may want to support tailored specifications, typically tailored for a particular language or locale. This may be important when the regular expression engine is being used by end-users instead of programmers, such as in a word-processor allowing some level of regular expressions in searching.

For example, the order of Unicode characters may differ substantially from the order expected by users of a particular language. The regular expression engine has to decide, for example, whether the list [a-ä] means:

• the Unicode characters in binary order between 006116 and 00E516 (including 'z', 'Z', '[', and '¼'), or
• the letters in that order in the users' locale (which does not include 'z' in English, but does include it in Swedish).

If both tailored and default regular expressions are supported, then a number of different mechanism are affected. There are a two main alternatives for control of tailored support:

• coarse-grained support: the whole regular expression (or the whole script in which the regular expression occurs) can be marked as being tailored.
• fine-grained support: any part of the regular expression can be marked in some way as being tailored.

For example, fine-grained support could use some syntax like the following indicate tailoring to a locale within a certain range. (Marking locales is generally specified by means of the common ISO 639 and 3166 tags, such as "en_US". For more information on these tags, see the online data in [Online].)

\T{<locale>}..\E

Level 3 support may be considerably slower than Level 2, and some scripts may require either Level 1 or Level 2 matches instead. Thus there must be some sort of syntax that will allow Level 3 support to be turned on and off. Because tailored regular expression patterns are usually quite specific to the locale, and will generally not work across different locales, the syntax should also specify the particular locale or other tailoring customization that the pattern was designed for.

Sections 3.6 and following describe some additional capabilities of regular expression engines that are very useful in a Unicode environment, especially in dealing with the complexities of the large number of writing systems and languages expressible in Unicode.

3.1. Tailored Punctuation

The Unicode character properties for punctuation may vary from language to language or from country to country. In most cases, the effects of such changes will be apparent in other operations, such as a determination of word breaks. But there are other circumstances where the effects should be apparent in the general APIs, such as when testing whether a curly quotation mark is opening or closing punctuation may vary.

As described in 3.0, there must be the capability of turning this support on or off.

3.2 Tailored Grapheme Clusters

Tailored grapheme clusters may be somewhat different than the default grapheme clusters discussed in Level 2. They are coordinated with the collation ordering for a given language in the following way. A collation ordering determines a collation grapheme cluster, which is a sequence of characters that is treated as a unit by the ordering. For example, ch is a collation character for a traditional Spanish ordering. More specifically, a collation character is the longest sequence of characters that maps to a sequence of one or more collation elements where the first collation element has a primary weight and subsequent elements do not, and no completely ignorable characters are included.

The tailored grapheme clusters for a particular locale are the collation characters for the collation ordering for that locale. The determination of tailored grapheme clusters requires the regular expression engine to either draw upon the platform's collation data, or incorporate its own tailored data for each supported locale.

See UTS #10: Unicode Collation Algorithm [Collation] for more information about collation, and Annex B. Sample Collation Character Code for sample code.

3.3 Tailored Words

Semantic analysis may be required for correct word-break in languages that don't require spaces, such as Thai, Japanese, Chinese or Korean. This can require fairly sophisticated support if Level 3 word boundary detection is required, and usually requires drawing on platform OS services.

3.4 Tailored Loose Matches

In Level 1 and 2, caseless matches are described, but there are other interesting linguistic features that users may want to match. For example, V and W are considered equivalent in Swedish collations, and so [V] should match W in Swedish. In line with the UTS #10: Unicode Collation Algorithm [Collation], at the following four levels of equivalences are recommended:

• exact match: bit-for-bit identity
• tertiary match: disregard 4th level differences (language tailorings)
• secondary match: disregard 3rd level differences such as upper/lowercase and compatibility variation (e.g. matching both half-width and full-width katakana).
• primary match: disregard accents, case and compatibility variation; also disregard differences between katakana and hiragana.

If users are to have control over these equivalence classes, here is an example of how the sample syntax could be modified to account for this. The syntax for switching the strength or type of matching varies widely. Note that these tags switch behavior on and off in the middle of a regular expression; they do not match a character.

ITEM := \v{PRIMARY}   // match primary only
ITEM := \v{SECONDARY} // match primary & secondary only
ITEM := \v{TERTIARY}  // match primary, secondary, tertiary
ITEM := \v{EXACT}     // match all levels, normal state

Examples:

Basic information for these equivalence classes can be derived from the data tables referenced by UTS #10: Unicode Collation Algorithm [Collation].

3.5. Tailored Ranges

Tailored character ranges will include tailored grapheme clusters, as discussed above. This broadens the set of grapheme clusters — in traditional Spanish, for example, [b-d] would match against "ch".

Note: this is another reason why a property for all characters \p{Any} is needed—it is possible for a locale's collation to not have [\u0000-\U0010FFFF] encompass all characters.

Languages may also vary whether they consider lowercase below uppercase or the reverse. This can have some surprising results: [a-Z] may not match anything if Z < a in that locale!

3.6 Context Matching

For parallel, filtered transformations, such as involved in script transliteration, it is important to restrict the matching of a regular expression to a substring of a given string, and yet allow for context before and after the affected area. Here is a sample API that implements such functionality, where m is an extension of a Regex Matcher.

  if (m.matches(text, contextStart, targetStart, targetLimit, contextLimit)) {
    int end = p.getMatchEnd();
  }

The range of characters between contextStart and targetStart define a precontext; the characters between targetStart and targetLimit define a target, and the offsets between targetLimit and contextLimit define a postcontext. Thus contextStart ≤ targetStart ≤ targetLimit ≤ contextLimit. The meaning of this function is that

• a match is attempted beginning at targetStart.

• the match will only succeed with an endpoint at or less than targetLimit.

• any zero-width look-arounds (look-aheads or look-behinds) can match characters inside or outside of the target, but cannot match characters outside of the context.

Examples:

In these examples, the text in the pre- and postcontext is italicized and the target is underlined. In the output column, the text in bold is the matched portion. The pattern syntax "(←x)" means a backwards match for x (without moving the cursor) This would be (?<=x) in Perl. The pattern "(→x)" means a forwards match for x (without moving the cursor). This would be (?=x) in Perl.

While it would be possible to simulate this API call with other regular expression calls, it would require subdividing the string and making multiple regular expression engine calls, significantly affecting performance.

There should also be pattern syntax for matches (like ^ and $) for the contextStart and contextLimit positions.

Internally, this can be implemented by modifying the regular expression engine so that all matches are limited to characters between contextStart and contextLimit, and that all matches that are not zero-width look-arounds are limited to the characters between targetStart and targetLimit.

3.7 Incremental Matches

For buffered matching, one needs to be able to return whether there is a partial match; that is, whether there would be a match if additional characters were added after the targetLimit. This can be done with a separate method having an enumerated return value: match, no_match, or partial_match.

  if (m.incrementalmatches(text, cs, ts, tl, cl) == Matcher.MATCH) {
    ...
  }

Thus performing an incremental match of /bcbce(→d)/ against "1abcbcd2" would return a partial_match because the addition of an e to the end of the target would allow it to match. Note that /(bc)*(→d)/ would also return a partial match, because if bc were added at the end of the target, it would match.

Here is the above table, when an incremental match method is called:

The typical usage of incremental match is to make a series of incremental match calls, marching through a buffer with each successful match. At the end, if there is a partial match, one loads another buffer (or waits for other input). When the process terminates (no more buffers/input available), then a regular match call is made.

Internally, incremental matching can be implemented in the regular expression engine by detecting whether the matching process ever fails when the current position is at or after targetLimit, and setting a flag if so. If the overall match fails, and this flag is set, then the return value is set to partial_match. Otherwise, either match or no_match is returned, as appropriate.

The return value partial_match indicates that there was a partial match: if further characters were added there could be a match to the resulting string. It may be useful to divide this return value into two, instead:

• extendable_match: in addition to there being a partial match, there was also a match somewhere in the string. For example, when matching /(ab)*/ against "aba", there is a match, and if other characters were added ("a", "aba",...) there could also be another match.

• only_partial_match: there was no other match in the string. For example, when matching /abcd/ against "abc", there is only a partial match; there would be no match unless additional characters were added.

3.8 Unicode Set Sharing

For script transliteration and similar applications, there may be a hundreds of regular expressions, sharing a number of Unicode sets in common. These Unicode sets, such as [\p{Alphabetic} - \p{Latin}], could take a fair amount of memory, since they would typically be expanded into an internal memory representation that allows for fast lookup. If these sets separately stored, this means an excessive memory burden.

To reduce the storage requirements, an API may allow regular expressions to share storage of these and other constructs, by having a 'pool' of data associated with a set of compiled regular expressions.

rules.registerSet("$lglow", "[\p{lowercase}&[\p{latin}\p{greek}]] ");
rules.registerSet("$mark", "[\p{Mark}]");
...
rules.add("θ", "th");
rules.add("Θ(→$mark*$lglow)", "Th");
rules.add("Θ", "TH");
...
rules.add("φ", "th");
rules.add("Ψ(→$mark*$lglow)", "Ps");
rules.add("Ψ", "PS");
...

3.9 Possible Match Sets

There are a number of circumstances where additional functions on regular expression patterns can be useful for performance or analysis of those patterns. These are functions that return information about the sets of characters that a regular expression can match.

When applying a list of regular expressions (with replacements) against a given piece of text, one can do that either serially or in parallel. With a serial application, each regular expression is applied the text, repeatedly from start to end. With parallel application, each position in the text is checked against the entire list, with the first match winning. After the replacement, the next position in the text is checked, and so on.

For such a parallel process to be efficient, one needs to be able to winnow out the regular expressions that simply could not match text starting with a given code point. For that, it is very useful to have a function on a regular expression pattern that returns a set of all the code points that the pattern would partially or fully match.

   myFirstMatchingSet = pattern.getFirstMatchSet(Regex.POSSIBLE_FIRST_CODEPOINT);

For example, the pattern /[[\u0000-\u00FF] & [:Latin:]] * [0-9]/ would return the set {0..9, A..Z, a..z}. Logically, this is the set of all code points that would be at least partial matches (if considered in isolation).

The second useful case is the set of all code points that could be matched in any particular group, that is, that could be set in the standard $0, $1, $2, etc. variables.

   myAllMatchingSet = pattern.getAllMatchSet(Regex.POSSIBLE_IN$0);

Internally, this can be implemented by analysing the regular expression (or parts of it) recursively to determine which characters match. For example, the first match set of an alternation (a | b) is the union of the first match sets of the terms a and b.

The set that is returned is only guaranteed to include all possible first characters; if an expression gets too complicated it could be a proper superset of all the possible characters.

3.10 Folded Matching

Regular expressions typically provide for case-sensitive or case-insensitive matching. This accounts for the fact that in English and many other languages, users quite often want to disregard the differences between characters that are solely due to case. It would be quite awkward to do this without manually: for example, to do a caseless match against the last name in /Mark\sDavis/, one would have to use the pattern /Mark\s[Dd][Aa][Vv][Ii][Ss]/, instead of some syntax that can indicate that the target text is to be matched after folding case, such as /Mark\s\CDavis\E/.

For many languages and writing systems, there are other differences besides case where users want to allow a loose match. Once such way to do this is given above in the discussion of matching according to collation strength. There are others: for example, for Ethiopic one may need to match characters independent of their inherent vowel, or match certain types of vowels. It is difficult to tell exactly which ways people might want to match text for different languages, so the most flexible way to provide such support is to provide a general mechanism for overriding the way that regular expressions match literals.

One way to do this is to use folding functions. These are functions that map strings to strings, and are idempotent (applying a function more than once produces the same result: f(f(x)) = f(x). There are two parts to this: (a) allow folding functions to be registered, and (b) extend patterns so that registered folding functions can be activated. During the span of text in which a folding function is activated, both the pattern literals and the input text will be processed according to the folding before comparing. For example:

// Folds katakana and hiragana together
class KanaFolder implements RegExFolder {
  // from RegExFolder, must be overridden in subclasses
  String fold(String source) {...}

  // from RegExFolder, may be overridden for efficiency
  RegExFolder clone(String parameter, Locale locale) {...}
  int fold(int source) {...}
  UnicodeSet fold(UnicodeSet source) {...}
}
  ...

  RegExFolder.registerFolding("k_h", new KanaFolder());

  ...

  p = Pattern.compile("(\F{k_h=argument}マルク (\s)* ダ (ヸ | ビ) ス \E : \s+)*");

In the above example, the Kana folding is in force until terminated with \E. Within the scope of the folding, all text in the target would be folded before matching (the literal text in the pattern would also be folded). This only affects literals; regular expression syntax such as '(' or '*' are unaffected.

While it is sufficient to provide a folding function for strings, for efficiency one can also provide functions for folding single code points and Unicode sets (e.g. [a-z...]).

3.11 Submatchers

There are over 70 properties in the Unicode character database, yet there are many other sequences of characters that people may want to match, many of them specific to given languages. For example, characters that are used as vowels may vary by language. This goes beyond single-character properties, since certain sequences of characters may need to be matched; such sequences may not be easy themselves to express using regular expressions. Extending the regular expression syntax to provide for registration of arbitrary properties of characters allows these requirements to be handled.

The following provides an example of this. The actual function is just for illustration.

class MultipleMatcher implements RegExSubmatcher {
  // from RegExFolder, must be overridden in subclasses
  /**
   * Returns -1 if there is no match; otherwise returns the endpoint;
   * an offset indicating how far the match got.
   * The endpoint is always between targetStart and targetLimit, inclusive.
   * Note that there may be zero-width matches.
   */
  int match(String text, int contextStart, int targetStart, int targetLimit, int contextLimit) {
    // code for matching numbers according to numeric value.
  }

  // from RegExFolder, may be overridden for efficiency
  /**
   * The parameter is a number. The match will match any numeric value that is a multiple.
   * Example: for "2.3", it will match "0002.3000", "4.6", "11.5", and any non-Western
   * script variants, like Indic numbers.
   */
  RegExSubmatcher clone(String parameter, Locale locale) {...}
}
  ...

  RegExSubmatcher.registerMatcher("multiple", new MultipleMatcher());

  ...

  p = Pattern.compile("xxx\M{multiple=2.3}xxx");

In this example, the match function can be written to parse numbers according to the conventions of different locales, based on OS functions available for doing such parsing. If there are mechanisms for setting a locale for a portion of a regular expression, then that locale would be used; otherwise the default locale would be used.

Note: It might be advantageous to make the Submatcher API identical to the Matcher API; that is, only have one base class "Matcher", and have user extensions derive from the base class. The base class itself can allow for nested matchers.

Annex A. Character Blocks

The Block property from the Unicode Character Database can be a useful property for quickly describing a set of Unicode characters. It assigns a name to segments of the Unicode codepoint space; for example, [\u0370-\u03FF] is the Greek block.

However, block names need to be used with discretion; they are very easy to misuse since they only supply a very coarse view of the Unicode character allocation. For example:

• Blocks are not at all exclusive. There are many mathematical operators that are not in the Mathematical Operators block; there are many currency symbols not in Currency Symbols, etc.
• Blocks may include characters not assigned in the current version of Unicode. This can be both an advantage and disadvantage. Like the General Property, this allows an implementation to handle characters correctly that are not defined at the time the implementation is released. However, it also means that depending on the current properties of assigned characters in a block may fail. For example, all characters in a block may currently be letters, but this may not be true in the future.
• Writing systems may use characters from multiple blocks: English uses characters from Basic Latin and General Punctuation, Syriac uses characters from both the Syriac and Arabic blocks, various languages use Cyrillic plus a few letters from Latin, etc.
• Characters from a single writing system may be split across multiple blocks. See the table below. Moreover, presentation forms for a number of different scripts may be collected in blocks like Alphabetic Presentation Forms or Halfwidth and Fullwidth Forms.

The following table illustrates the mismatch between writing systems and blocks. These are only examples; this table is not a complete analysis. It also doesn't include common punctuation used with all of these writing systems.

For the above reasons, Script values are generally preferred to Block values. Even there, they should be used in accordance with the guidelines in UTR #24: Script Names [ScriptDoc].

Annex B: Sample Collation Character Code

The following provides sample code for doing Level 3 collation character detection. This code is meant to be illustrative, and has not been optimized. Although written in Java, it could be easily expressed in any programming language that allows access to the Unicode Collation Algorithm mappings.

/**
 * Return the end of a collation character.
 * @param s         the source string
 * @param start     the position in the string to search
 *                  forward from
 * @param collator  the collator used to produce collation elements.
 * This can either be a custom-built one, or produced from
 * the factory method Collator.getInstance(someLocale).
 * @return          the end position of the collation character
 */

static int getLocaleCharacterEnd(String s,
  int start, RuleBasedCollator collator) {
    int lastPosition = start;
    CollationElementIterator it 
      = collator.getCollationElementIterator(
          s.substring(start, s.length()));
    it.next(); // discard first collation element
    int primary;
        
    // accumulate characters until we get to a non-zero primary
        
    do {
        lastPosition = it.getOffset();
        int ce = it.next();
        if (ce == CollationElementIterator.NULLORDER) break;
        primary = CollationElementIterator.primaryOrder(ce);
    } while (primary == 0);
    return lastPosition;
}

Annex C: Compatibility Properties

The following are recommended assignments for compatibility property names, for use in Regular Expressions. These are informative recommendations only.

References

Acknowledgments

Thanks to Jeffrey Friedl, Andy Heninger, Alan Liu, Karlsson Kent, Jarkko Hietaniemi, Gurusamy Sarathy, Tom Watson and Kento Tamura for their feedback on the document.

Modifications

The following summarizes modifications from the previous version of this document.

Copyright © 2000-2002 Unicode, Inc. All Rights Reserved. The Unicode Consortium makes no expressed or implied warranty of any kind, and assumes no liability for errors or omissions. No liability is assumed for incidental and consequential damages in connection with or arising out of the use of the information or programs contained or accompanying this technical report.

Unicode and the Unicode logo are trademarks of Unicode, Inc., and are registered in some jurisdictions.