Fabian M. Suchanek
Regular Expressions
26
Regular Expressions
Regular expressions can detect strings of specific forms in text:
2
Regular expression: L[a-z]+
Text: The purpose of life is to Live, to Love, to Learn.
Finds: “Live”, “Love”, “Learn”
Regular expressions have applications in the detection of named entities
in text, syntax checking, and search in text.
They are a standard tool that is implemented in all reasonable text
editors and operating systems.
Def: Alphabet, Word
An
alphabet
is a set of symbols.
We will use as alphabet always implicitly the set of all unicode
characters.
3
A={a,b,c,d,e,f,0,1,2,3,4,5,6,7,8,9}
A={0,...9,a...,z,A...Z,!,?,...}
A
word
over an alphabet A is a sequence of symbols from A.
Since we use the alphabet of unicode characters, words are just strings.
hello!, 42, 3.141592, Rowan Atkinson
also with spaces!
Def: Language
A
language
over an alphabet S is a set of words over S.
4
Set of strings
we want to describe
L1 = {Andrei Sakharov, Shirin Ebadi, Rowan Atkinson, ...}
L2 = {1900, 1901, 1982, 2013, 2017, ...}
L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
L4 = {a, ab, abb, bbba, aaabbab, ababa, ...}
L5 = {a, b, aa, bb, aaa, bbb, ...}
L6 = {a, aa, aaa, ...}
L7 = {ab, abab, ababab, ...}
L8 = {c, ca, caa, caaa, ...}
L9 = { , a, aa, aaa, ...}
Def: Language
A language over an alphabet S is a set of words over S.
5
a*
Our description
(much shorter than the original set!)
Set of strings
we want to describe
L1 = {Andrei Sakharov, Shirin Ebadi, Rowan Atkinson, ...}
L2 = {1900, 1901, 1982, 2013, 2017, ...}
L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
L4 = {a, ab, abb, bbba, aaabbab, ababa, ...}
L5 = {a, b, aa, bb, aaa, bbb, ...}
L6 = {a, aa, aaa, ...}
L7 = {ab, abab, ababab, ...}
L8 = {c, ca, caa, caaa, ...}
L9 = { , a, aa, aaa, ...}
Def: Language
A language over an alphabet S is a set of words over S.
6
ca*
a*
L1 = {Andrei Sakharov, Shirin Ebadi, Rowan Atkinson, ...}
L2 = {1900, 1901, 1982, 2013, 2017, ...}
L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
L4 = {a, ab, abb, bbba, aaabbab, ababa, ...}
L5 = {a, b, aa, bb, aaa, bbb, ...}
L6 = {a, aa, aaa, ...}
L7 = { , ab, abab, ababab, ...}
L8 = {c, ca, caa, caaa, ...}
L9 = { , a, aa, aaa, ...}
Our description
(much shorter than the original set!)
Set of strings
we want to describe
Def: Language
A language over an alphabet S is a set of words over S.
7
ca*
a*
Our description
(much shorter than the original set!)
Set of strings
we want to describe
(ab)*
L1 = {Andrei Sakharov, Shirin Ebadi, Rowan Atkinson, ...}
L2 = {1900, 1901, 1982, 2013, 2017, ...}
L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
L4 = {a, ab, abb, bbba, aaabbab, ababa, ...}
L5 = {a, b, aa, bb, aaa, bbb, ...}
L6 = {a, aa, aaa, ...}
L7 = { , ab, abab, ababab, ...}
L8 = {c, ca, caa, caaa, ...}
L9 = { , a, aa, aaa, ...}
Def: Language
A language over an alphabet S is a set of words over S.
8
aa* = a+
ca*
a*
Our description
(much shorter than the original set!)
Set of strings
we want to describe
(ab)*
L1 = {Andrei Sakharov, Shirin Ebadi, Rowan Atkinson, ...}
L2 = {1900, 1901, 1982, 2013, 2017, ...}
L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
L4 = {a, ab, abb, bbba, aaabbab, ababa, ...}
L5 = {a, b, aa, bb, aaa, bbb, ...}
L6 = {a, aa, aaa, ...}
L7 = { , ab, abab, ababab, ...}
L8 = {c, ca, caa, caaa, ...}
L9 = { , a, aa, aaa, ...}
Def: Language
A language over an alphabet S is a set of words over S.
9
a+ | b+
aa* = a+
ca*
a*
Our description
(much shorter than the original set!)
Set of strings
we want to describe
(ab)*
L1 = {Andrei Sakharov, Shirin Ebadi, Rowan Atkinson, ...}
L2 = {1900, 1901, 1982, 2013, 2017, ...}
L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
L4 = {a, ab, abb, bbba, aaabbab, ababa, ...}
L5 = {a, b, aa, bb, aaa, bbb, ...}
L6 = {a, aa, aaa, ...}
L7 = { , ab, abab, ababab, ...}
L8 = {c, ca, caa, caaa, ...}
L9 = { , a, aa, aaa, ...}
Def: Language
A language over an alphabet S is a set of words over S.
10
aa* = a+
ca*
a*
Our description
(much shorter than the original set!)
Set of strings
we want to describe
(ab)*
(a | b)+
a+ | b+
L1 = {Andrei Sakharov, Shirin Ebadi, Rowan Atkinson, ...}
L2 = {1900, 1901, 1982, 2013, 2017, ...}
L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
L4 = {a, ab, abb, bbba, aaabbab, ababa, ...}
L5 = {a, b, aa, bb, aaa, bbb, ...}
L6 = {a, aa, aaa, ...}
L7 = { , ab, abab, ababab, ...}
L8 = {c, ca, caa, caaa, ...}
L9 = { , a, aa, aaa, ...}
Def: Language
A language over an alphabet S is a set of words over S.
11
(0 | 1 | ... | 9) = [0-9]
aa* = a+
ca*
a*
Our description
(much shorter than the original set!)
Set of strings
we want to describe
(ab)*
(a | b)+
a+ | b+
L1 = {Andrei Sakharov, Shirin Ebadi, Rowan Atkinson, ...}
L2 = {1900, 1901, 1982, 2013, 2017, ...}
L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
L4 = {a, ab, abb, bbba, aaabbab, ababa, ...}
L5 = {a, b, aa, bb, aaa, bbb, ...}
L6 = {a, aa, aaa, ...}
L7 = { , ab, abab, ababab, ...}
L8 = {c, ca, caa, caaa, ...}
L9 = { , a, aa, aaa, ...}
Def: Language
A language over an alphabet S is a set of words over S.
12
[0-9][0-9][0-9][0-9] = [0-9]{4}
(0 | 1 | ... | 9) = [0-9]
aa* = a+
ca*
a*
Our description
(much shorter than the original set!)
Set of strings
we want to describe
(ab)*
(a | b)+
a+ | b+
L1 = {Andrei Sakharov, Shirin Ebadi, Rowan Atkinson, ...}
L2 = {1900, 1901, 1982, 2013, 2017, ...}
L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
L4 = {a, ab, abb, bbba, aaabbab, ababa, ...}
L5 = {a, b, aa, bb, aaa, bbb, ...}
L6 = {a, aa, aaa, ...}
L7 = { , ab, abab, ababab, ...}
L8 = {c, ca, caa, caaa, ...}
L9 = { , a, aa, aaa, ...}
Def: Language
A language over an alphabet S is a set of words over S.
13
[A-Z][a-z]+ [A-Z][a-z]+
[0-9][0-9][0-9][0-9] = [0-9]{4}
(0 | 1 | ... | 9) = [0-9]
(a | b)+
a+ | b+
aa* = a+
ca*
a*
Our description
(much shorter than the original set!)
Set of strings
we want to describe
(ab)*
L1 = {Andrei Sakharov, Shirin Ebadi, ...}
L2 = {1900, 1901, 1982, 2013, 2017, ...}
L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
L4 = {a, ab, abb, bbba, aaabbab, ababa, ...}
L5 = {a, b, aa, bb, aaa, bbb, ...}
L6 = {a, aa, aaa, ...}
L7 = { , ab, abab, ababab, ...}
L8 = {c, ca, caa, caaa, ...}
L9 = { , a, aa, aaa, ...}
Regular expressions
A regular expression (regex) describes a language.
14
The language of a regular expression
[0-9][0-9][0-9][0-9] = [0-9]{4}
(0 | 1 | ... | 9) = [0-9]
(a | b)+
a+ | b+
aa* = a+
ca*
a*
[A-Z][a-z]+ [A-Z][a-z]+
*
for symbols
L1 = {Andrei Sakharov, Shirin Ebadi, ...}
L2 = {1900, 1901, 1982, 2013, 2017, ...}
L3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
L4 = {a, ab, abb, bbba, aaabbab, ababa, ...}
L5 = {a, b, aa, bb, aaa, bbb, ...}
L6 = {a, aa, aaa, ...}
L7 = { , ab, abab, ababab, ...}
L8 = {c, ca, caa, caaa, ...}
L9 = { , a, aa, aaa, ...}
Def: Regular expressions
A
regular expression
(regex) over an alphabet
is one of the following:
• the empty string
• an element of
• a string of the form XY
• a string of the form (X|Y)
• a string of the form (X)*
where X and Y are regexes
A regex is associated
to a language:
15
its language
the regular
expression
(0 is a special regex that cannot appear as part of other regexes. It represents the empty language and does not match any string.)
*
for symbols
->formal-grammars
Real-world example
16
Example from Wipolo via Dhouha Bouamor
Regular expressions cheat sheet
L(a) = {a}
L(ab) = {ab}
L(a | b) = {a, b}
L(a*) = {, a, aa, aaa, ...}
L(a+) := L(aa*)
L([a-z]) := L(a|b|...|z)
L(a{2,4}) := L(aa|aaa|aaaa)
L(a{3}) := L(aaa)
L(a?) := L( | a)
L(.) := {a|b|..|A|...|0|...|!|$|...}
L(\.) := {.}
17
Simple symbol
Concatenation
Disjunction
Kleene star
shorthand for “one or more”
shorthand for a range
shortand for a given number
shortand for a given number
shorthand for “optional”
shorthand for “any symbol”
escape sequence for special symbols
Task: Regexes
L(a) = {a}
L(ab) = {ab}
L(a | b) = {a, b}
L(a*) = {, a, aa, aaa, ...}
L(a+) := L(aa*)
L([a-z]) := L(a|b|...|z)
L(a{2,4}) := L(aa|aaa|aaaa)
L(a{3}) := L(aaa)
L(a?) := L( | a)
L(.) := {a|b|..|A|...|0|...|!|$|...}
L(\.) := {.}
18
Simple symbol
Concatenation
Disjunction
Kleene star
shorthand for “one or more”
shorthand for a range
shortand for a given number
shortand for a given number
shorthand for “optional”
shorthand for “any symbol”
escape sequence for special symbols
Define regexes for
• numbers
• phone numbers
Try it
• HTML tags
• Names of the form “Dr. Blah Blub”
Helpful Web page
19
https://regex101.com/
Named regexes
When using regular expressions in a
program, it is a good idea to name them:
digits = "[0-9]+"
separator = "( |-)"
pattern = digits+separator+digits
But: Human beings, who are almost unique in having the ability
to learn from the experience of others, are also remarkable for
their apparent disinclination to do so. (Douglas Adams)
20
Regex groups
21
A regex group is a sequence of the form (...) in a regex.
1st group
Groups are numbered by the order of their opening paranthesis.
no (([a-z]+) is below ([a-z]+))
Regex groups
22
A regex group is a sequence of the form (...) in a regex.
1st group
Groups are numbered by the order of their opening paranthesis.
no (([a-z]+) is below ([a-z]+))
2nd group
3rd group
Regex groups
No idea is above scrutiny, and no person is below dignity.
1st group: person is below dignity
2nd group: person
3rd group: dignity
Try it out!
23
no (([a-z]+) is below ([a-z]+))
Maajid Nawaz
Regexes in programming
Regex
Simplified regex
Finite State Machine
Matcher
It’s in my DNA, DNAAA !
your
programming
language
24
DN(A)+
DNA(A)*
D
N
A
A
you
>java
Example: Regexes in Java
Pattern pattern = Pattern.compile("DN(A)+");
Matcher matcher = pattern.matcher("It’s in my DNA, DNAAAA!");
while(matcher.find())
System.out.println(matcher.group());
25
DNA
DNAAA
It’s in my DNA, DNAAA !
Example: Regexes in Python
import re
pattern = re.compile("DN(A)+")
match = pattern.search(line)
if match!=None:
print(match.group())
26
It’s in my DNA, DNAAA !
DNA
DNAAA
Summary: Regular Expressions
A regular expression is a kind of “code” that matches a (possibly infinite)
set of strings.
Regexes are a standard facility in programming languages, and can be
used, e.g., for information extraction.
27
[A-Z][a-z]+ matches {Sakharov, Ebadi, Atkinson, ...}
->Formal-grammars
->Fact-extraction
->Nerc