CC-BY    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/ -> Python
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 >groups -> Python
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