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,!,?,...} 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 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 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