# Regular expression

In theoretical computer science, a regular expression ( English regular expression , abbreviation RegExp or Regex ) is a character string that is used to describe sets of character strings with the help of certain syntactic rules. Regular expressions are mainly used in software development . In addition to implementations in many programming languages , many text editors also process regular expressions in the " Find and Replace " function". Wildcards are a simple use case of regular expressions .

Regular expressions can be used as filter criteria in the text search by matching the text with the regular expression pattern. This process is also called pattern matching . For example, it is possible to search for all words from a word list that begin with S and end with D without having to explicitly specify the letters in between or their number.

The concept of the regular expression goes back essentially to the mathematician Stephen Kleene , who used the similar term regular set .

## Regular expressions in theoretical computer science

### Theoretical foundations

Regular expressions describe a family of formal languages and thus belong to theoretical computer science . These languages, the regular languages , are at the lowest and thus the weakest level of expression in the Chomsky hierarchy (type 3). They are generated by regular grammars .

For every regular expression there is a finite automaton that accepts the language specified by the expression. A corresponding (nondeterministic) finite automaton can be constructed from a regular expression with the Thompson construction . This makes regular expressions relatively easy to implement. Conversely, there is a regular expression for every finite automaton that describes the language accepted by the automaton. A corresponding regular expression can be constructed from a nondeterministic finite automaton using Kleene's algorithm . Kleene's algorithm usually produces very long regular expressions. The state elimination (German actually: "state elimination") usually provides shorter regular expressions in practice. In the highest case ("worst case"), however, both algorithms return regular expressions of the length , with the number of characters in the underlying alphabet and the number of states in the machine. ${\ displaystyle | \ Sigma | 4 ^ {| Q |}}$${\ displaystyle | \ Sigma |}$${\ displaystyle | Q |}$

#### syntax

The syntax precisely defines what regular expressions look like.

Regular expressions are always defined using a given set of characters , the so-called alphabet . Regular expressions are based on exactly three operations: alternative, concatenation and repetition. The formal definition looks like this: ${\ displaystyle \ Sigma}$

1. ${\ displaystyle \ varnothing}$(the special symbol for the empty set ) is a regular expression.
2. for all is (a character from the underlying alphabet representation) a regular expression.${\ displaystyle a_ {i} \ in \ Sigma}$${\ displaystyle \ mathbf {a} _ {i}}$
3. If and are regular expressions, then (alternative), ( concatenation ) and ( Kleene shell , Kleene star) are also regular expressions.${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x | y)}$${\ displaystyle (xy)}$${\ displaystyle (x ^ {*})}$

The symbol is used instead for alternative . Then you write . As an alternative, there is also an operator symbol for concatenation; one then writes . ${\ displaystyle |}$${\ displaystyle +}$${\ displaystyle (x + y)}$${\ displaystyle (x \ cdot y)}$

You can also allow additional constants and operations, provided that their effect can also be described using the basic rules mentioned above. In the literature one can find, among other things, the regular expression or the positive Kleenesche shell , which can be regarded as an abbreviation of . ${\ displaystyle \ epsilon}$${\ displaystyle x ^ {+}}$${\ displaystyle (x (x ^ {*}))}$

If you give a precedence of the operators , you can do without some brackets. The order of precedence is usually Kleene star over concatenation over alternative . Instead , the spelling is sufficient . ${\ displaystyle (((ab) | c) ^ {*})}$${\ displaystyle (ab | c) ^ {*}}$

The number of nested * operators is called the star height .

#### semantics

The semantics of regular expressions precisely define what formal meaning the syntax of regular expressions has.

A regular expression describes a formal language, i.e. a set of words (strings). The definition of the semantics can be described analogously to the syntax definition. It denotes the formal language that is specified by the regular expression . ${\ displaystyle {\ mathcal {L}} (regex)}$${\ displaystyle regex}$

1. ${\ displaystyle {\ mathcal {L}} (\ varnothing) = \ emptyset}$
The special symbol for the empty set specifies the empty language.
2. for all true${\ displaystyle a_ {i} \ in \ Sigma}$${\ displaystyle {\ mathcal {L}} (\ mathbf {a} _ {i}) = \ {a_ {i} \}}$
Each representative of a character from the alphabet specifies the language that contains only that character.
3. are and regular expressions, the following applies: ${\ displaystyle x}$${\ displaystyle y}$
• ${\ displaystyle {\ mathcal {L}} (x | y) = {\ mathcal {L}} (x) \ cup {\ mathcal {L}} (y)}$
The alternative between two terms describes the language that results from the union of the two languages ​​described by the two terms.
• ${\ displaystyle {\ mathcal {L}} (xy) = \ {\ alpha \ beta \; \ vert \; \ alpha \ in {\ mathcal {L}} (x) \ land \ beta \ in {\ mathcal { L}} (y) \}}$
The concatenation of two expressions describes the language that only contains the words that have a word from the language described by the first expression as a prefix and whose immediately following residual suffix is ​​a word from the language described by the second expression.
• ${\ displaystyle {\ mathcal {L}} (x ^ {*}) = \ cup _ {i \ geq 0} \; {\ mathcal {L}} ^ {i} (x)}$
The Kleen's shell of regular expressions describes the Kleen's shell of the language described by .${\ displaystyle x}$

If the syntax definition of regular expressions also contains the constant , then its meaning is defined as , i.e. the language that only contains the empty word . ${\ displaystyle \ epsilon}$${\ displaystyle {\ mathcal {L}} (\ epsilon) = \ {\ varepsilon \}}$ ${\ displaystyle \ varepsilon}$

The empty word is a word of a formal language ( ) and is therefore not a regular expression. The language contains only the empty word, but can also be without the constant by a regular expression to describe, for example: . However, a visual distinction is not always made between a regular expression and the associated language, so that instead of being used as a regular expression for the language , the distinction between and and between and can be omitted. ${\ displaystyle \ varepsilon \ in \ Sigma ^ {*}}$${\ displaystyle \ epsilon}$${\ displaystyle \ varnothing ^ {*}}$${\ displaystyle \ mathbf {a}}$${\ displaystyle a}$${\ displaystyle \ {a \}}$${\ displaystyle \ varnothing}$${\ displaystyle \ emptyset}$${\ displaystyle \ epsilon}$${\ displaystyle \ varepsilon}$

### Examples

If the alphabet from the letter , and is, therefore , then the following languages with the corresponding regular expressions can be described: ${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle c}$${\ displaystyle \ Sigma = \ {a, b, c \}}$

• The language of all words, which consists of any number or any number : ${\ displaystyle a}$${\ displaystyle b}$
Syntax: . Semantics:${\ displaystyle regex = \ mathbf {a} ^ {*} | \ mathbf {b} ^ {*}}$${\ displaystyle {\ mathcal {L}} (regex) = \ {a \} ^ {*} \ cup \ {b \} ^ {*}}$
• The language of all words that start with: ${\ displaystyle a}$
Syntax: . Semantics:${\ displaystyle regex = \ mathbf {a} (\ mathbf {a} | \ mathbf {b} | \ mathbf {c}) ^ {*}}$${\ displaystyle {\ mathcal {L}} (regex) = \ {a \ beta \; \ vert \; \ beta \ in \ Sigma ^ {*} \}}$
• The language of all words that begin and end with and only consist of any number in between : ${\ displaystyle a}$${\ displaystyle c}$
Syntax: . Semantics:${\ displaystyle \ mathbf {a} \ mathbf {c} ^ {*} \ mathbf {a}}$${\ displaystyle {\ mathcal {L}} (regex) = \ {a \ beta a \; \ vert \; \ beta \ in \ {c \} ^ {*} \}}$
• The language of all words that consist of two characters but do not contain any : ${\ displaystyle c}$
Syntax: . Semantics:${\ displaystyle (\ mathbf {a} | \ mathbf {b}) (\ mathbf {a} | \ mathbf {b})}$${\ displaystyle {\ mathcal {L}} (regex) = \ {\ alpha \ beta \; \ vert \; \ alpha, \ beta \ in \ {a, b \} \}}$

## Use of regular expressions

Ken Thompson used this notation in the 1960s to build qed (a previous version of the Unix editor ed ) and later to write the grep tool . Since then, very many programs and libraries of programming languages ​​have implemented functions to use regular expressions to search for and replace strings. Examples are the programs sed , grep, emacs , the programming languages Perl and Tcl and standard libraries for the programming languages C , C ++ , Java , JavaScript , Python , PHP , Ruby and the .NET framework. The word processor and the spreadsheet of the Office package OpenOffice.org offer the ability to search using regular expressions in the text.

There are differences in functionality and syntax between different Regexp implementations. In programming languages, the Perl Compatible Regular Expressions (PCRE) have prevailed, which are based on the implementation in Perl 5.0. Besides, in POSIX.2 between "basic" regular expressions (basic regular expressions) and "extended" regular expressions (extended regular expressions) distinguished.

Some programs, for example the text editor Vim , offer the possibility to switch back and forth between different regexp syntaxes.

Regular expressions play an important role in the lexical analysis of source texts , for example in compilers or for syntax highlighting in editors. A lexical scanner breaks the source text down into so-called tokens (keywords, operators, ...) using regular expressions . Since most programming languages are context-free languages , regular expressions are not powerful enough to describe their syntax. Therefore, the syntactic analysis that follows with compilers is usually done by a separate program, the parser .

Regular expressions also play a role in bioinformatics . They are used in protein databases to describe protein motifs. The regular expression

W-x{9,11}-[VFY]-[FYW]-x{6,7}-[GSTNE]-[GSTQCR]-[FYW]-R-S-A-P

describes, for example, a protein domain in PROSITE . The regular expression above says the following: At the beginning choose the amino acid tryptophan (one letter code W), then choose 9 to 11 amino acids freely, then choose either V, F or Y, then choose either F, Y or W, then again 6 to 7 Amino acids free, then either G, S, T, N or E, then either G, S, T, Q, C or R, then F, Y or W, then R then S then A then P.

## Regular Expressions in Practice

Most implementations today support extensions such as backreferences. These are no longer regular expressions in the sense of theoretical computer science, because the expressions expanded in this way no longer necessarily describe languages ​​of type 3 of the Chomsky hierarchy .

The following syntax descriptions relate to the syntax of common implementations with extensions, so they only partially correspond to the above definition from theoretical computer science.

### Quantifiers

Quantifiers (English quantifiers , also quantifiers or repetition factors ) allow the previous expression to be allowed in various multiples in the character string.

 ? The preceding expression is optional, it can occur once, but does not need it, that is, the expression occurs zero or once. (This corresponds to ) {0,1} + The preceding expression must appear at least once, but can also appear multiple times. (This corresponds to ) {1,} * The preceding expression can appear as often as you like (not even once). (This corresponds to ) {0,} {n} The preceding expression must appear exactly n times. (This corresponds to ) {n,n} {min,} The foregoing expression must at least min times occur. {min,max} The preceding expression must occur at least a minimum of and a maximum of a maximum of times. {0,max} The preceding expression may appear a maximum of times.

The quantifiers relate to the preceding regular expression, but not necessarily to the match it found. For example, a+an “a” or “aaaa” is used, but [0-9]+not only corresponds to repeated identical digits, but also to sequences of mixed digits, for example “072345”.

Further examples are:

• [ab]+ corresponds to "a", "b", "aa", "bbaab" etc.
• [0-9]{2,5}corresponds to two, three, four or five digits in a row, e.g. B. "42" or "54072", but not the character strings "0", "1.1" or "a1a1".

If a character string should only consist of the searched pattern (and not just contain it), in most implementations it must be explicitly defined that the pattern should extend from the beginning ( \Aor ^) QF1 to the end of the character string ( \Z, \zor $) QF1 . Otherwise, for example, [0-9]{2,5}also recognizes the substring “12345” for the character string “1234507”. For the same reason, for example a*, there would always be a hit, since every character string - even the empty word "" - contains at least 0 times the character "a". Quantifiers are (English by default "greedy" greedy implemented). That is, a regular expression is resolved to the closest possible match. However, since this behavior is not always wanted, quantifiers can be declared as "frugal" or "cautious" (English non-greedy , reluctant ) in many newer implementations . For example, a question mark is placed ?after the quantifier in Perl or tcl . The implementation of frugal quantifiers is comparatively complex and slow during the search process (requires backtracking ), which is why some implementations expressly avoid this e.g. B. sed. Example (Perl syntax) Assuming the regular expression is A.*Bapplied to the string "ABCDEB", it would find it as "ABCDEB". With the help of the “non-greedy” quantifier *?, the now modified expression - ie A.*?B - only the character string “AB”, thus aborts the search for the first “B” found. An equivalent regular expression for interpreters that do not support this quantifier would be A[^B]*B. QF1The characters ^and $match in multiline mode, i.e. if the m modifier is set, the beginnings and ends of lines also.

### Possessive behavior

A variant of the greedy behavior described above is possessive matching . However, since backtracking is prevented here, characters that match are not released again. Therefore, the synonymous terms atomic grouping , independent subexpression or non-backtracking subpattern can also be found in the literature . The syntax for these constructs varies with the different programming languages. Such partial expressions ("subpattern") were originally formulated in Perl . In addition, since Perl 5.10, there are the equivalent, already available in Java possessive quantifiers , , and . (?>Ausdruck)++*+?+{min,max}+

example
Assuming the regular expression is A.*+Bapplied to the string "ABCDEB" , it would not find a match. When processing the regular expression, the part would .*+match up to the end of the character string. However, in order to find the entire expression, one character - here the "B" - would have to be released again. The possessive quantifier forbids this due to the suppressed backtracking, which is why no successful match can be found.

### Groupings and backward references

Expressions can be summarized with round brackets (and : For example, an "abc" or an "abcabc" etc. ) (abc)+

Some implementations save the found matches of groupings and allow them to be reused in regular expressions or text replacement. These are backreferences (English back references called). The notation or is often used for this, where n corresponds to the nth grouping. A special position is n = 0, which usually stands for the match of the entire regular expression. \n$n example A search and replace with AA(.*?)BBas a regular search expression and \1as a replacement replaces all character strings enclosed by AA and BB with the text contained between AA and BB . That means AA and BB and the text in between are replaced by the text that was originally between AA and BB , so AA and BB are missing in the result. Regular expression interpreters that allow backward references no longer conform to type 3 of the Chomsky hierarchy . The pumping lemma can be used to show that a regular expression that determines whether 1the same number of 0is in a character string is not a regular language . There are also groupings that do not generate a backward reference (English non-capturing ). The syntax for this in most implementations is (?:) . Regexp documentation indicates that the creation of backward references should always be avoided if they are not later accessed. The creation of the references costs execution time and occupies space to store the match found. In addition, the implementations only allow a limited number of backward references (often only a maximum of 9). example The regular expression \d+(?:-\d+)*can be used to find sequences of number sequences separated by hyphens without receiving the last number sequence separated by a hyphen as a back reference. example A date in the format MM/DD/YYYYshould be converted into the format YYYY-MM-DD. 1. With the help of the expression ([0-1]?[0-9])\/([0-3]?[0-9])\/([0-9]{4}), the three groups of numbers are extracted. 2. The \3-\1-\2individual groups are converted into the correct format with the replacement expression . ### Alternatives You can |allow alternative expressions with the symbol. example ABC|abcmeans "ABC" or "abc", but z. B. not "Abc". ### More characters In order to support the applications on the computer that are often related to character strings, the following characters are usually defined in addition to those already mentioned:  ^ stands for the beginning of the line (not to be confused with ^the character selection using [and ]). $ can stand for the end of the line or the end of a character string, depending on the context, although in some implementations a “\ n” may follow. The actual ending matches \z. \ if necessary, cancels the meta-meaning of the next character (see masking characters ). For example, the expression (A\*)+allows the character strings "A *", "A * A *" and so on. In this way, a period “.” Can also be searched \.for while searching for \with \\. \b empty string at the beginning or at the end of a word \B empty string that does not form the beginning or the end of a word \< empty string at the beginning of the word \> empty string at the end of the word \n a line break in Unix format \r a line break in the (old, i.e. before 1999) Mac format \r\n a line break in DOS and Windows format \t a horizontal tab character
example
[^ ]\$ means: The character string must consist of at least one character and the last character cannot be a space.

### Look-around assertions

Perl Version 5 also introduced look-ahead and look-behind assertions in addition to the usual regular expressions (such as “forward-looking” or “backward-looking” assumptions or assertions), which are summarized under the term look-around assertions . These constructs extend the regular expressions by the possibility of formulating context-sensitive conditions without finding the context itself suitable. That is, you want to find all the strings "Sport", where the string "simplistic" follows, but without the string found "simplistic" contains the string itself, this would be a look-ahead assertion possible Sport(?=verein). In the example sentence “An athlete participates in sports in a sports club.”, The regular expression would therefore match the last occurrence of “Sport”, since only this is followed by the string “club”; however, it would not match the substring “sports club”.

Due to the property that the specified context (in the example “club”) is specified, but is not an explicit part of the appropriate character string (here “sport”), the zero-width attribute is usually also mentioned in connection with assertions . The full designations are thus - depending on whether a certain context is required (positive) or forbidden (negative) - zero-width positive / negative look-ahead / behind assertions. The names of the directions come from the fact that Regexp parsers always process a character string from left to right.

definition designation Explanation Notation
(?=Ausdruck) positive look-ahead assertion Expression mustfollow theabove expression Ausdruck(?=Ausdruck)
(?!Ausdruck) negative look-ahead assertion Expression must notfollow theabove expression Ausdruck(?!Ausdruck)
(?<=Ausdruck) positive look-behind assertion Expression mustprecede thefollowing expression (?<=Ausdruck)Ausdruck
(?<!Ausdruck) negative look-behind assertion Expression mustnot precede thefollowing expression (?<!Ausdruck)Ausdruck

Look-arounds are not only supported by Perl and PCRE , but also by Java , .NET and Python , among others . From version 1.5, JavaScript interprets positive and negative look-aheads.

example
\s(?=EUR)stands for a "whitespace" character (i.e., space or tab) followed by the string EUR. In contrast to \sEUR, here EURdoes not belong to a matching character string ("matched character string").

### Conditional expressions

Conditional expressions are relatively uncommon. These can be used in Perl, PCRE and the .NET framework, among others. Python offers only limited functionality for such expressions in connection with look-around assertions .

 (?(Bedingung)wahr-Ausdruck|falsch-Ausdruck) If the given expression “condition” is found, the “true expression” is used. If the search term cannot be found, the “wrong term” is used.

example

Expressing ($$)?\d+(?(1)$$)strings are like 1, (2), 34or (567), but not 3)`found.

## literature

Regular expressions

Regular expressions and natural languages

• Kenneth R. Beesley, Lauri Karttunen: Finite-State Morphology. Distributed for the Center for the Study of Language and Information. 2003. 2003 Series: (CSLI-SCL) Studies in Computational Linguistics.

Regular expressions and automata theory

Research literature

• Stephen C. Kleene: Representation of Events in Nerve Nets and Finite Automata. In: Claude E. Shannon, John McCarthy (Eds.): Automata Studies. Princeton University Press, 1956, pp. 3-42.

## Individual evidence

1. a b Stephen C. Kleene : Representation of Events in Nerve Nets and Finite Automata . In: Claude E. Shannon , John McCarthy (Eds.): Automata Studies . Princeton University Press, 1956, pp. 3-42 .
2. ^ Alfred V. Aho , Ravi Sethi, Jeffrey Ullman : Compilers: Principles, Techniques and Tools. Addison-Wesley, 1986
3. ^ A b c John E. Hopcroft , Jeffry D. Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . Addison-Wesley, Bonn 1994, ISBN 3-89319-744-3 .
4. Jacques Sakarovitch: The Language, the expression, and the (Small) Automaton . In: LNCS . 3845, 2006, pp. 15-30. doi : 10.1007 / 11605157_2 .
5. POSIX specifications
6. RE Bracket Expression , IEEE Std 1003.1, The Open Group Base Specifications, 2004
7. Look Ahead and Look Behind Zero-Width Assertions . Regular-Expressions.info
8. ^ Mozilla Developer Network: JavaScript Reference
9. If-Then-Else Conditionals in Regular Expressions . Regular-Expressions.info