Subtitle of this talk

I define UNIX as 30 definitions of regular expressions living under one roof.
—Donald Ervin Knuth

RegEx in practice

Predecessor talk RegEx in practice

Recap

Recap

• RegEx is a domain-specific language (DSL).
• It is typically embedded into more general languages like C++, python, perl, ruby, Scala, …
• One string specifies several strings.
• Metacharacters have special meanings like quantities.
• RegEx is a required tool for every programmer. Why? Because we write algorithms for data processing. Data processing requires matching, extracting, replacing, … data.

Advanced regular expressions

And who are we going to do discuss that?

Let's talk about APIs 😇

Programming languages

Data provided by TIOBE Index

Programming languages

What to discuss

• Java, Go, Python and Perl analyzed.
• No libraries like XDuce, CDuce and HaRP.
• No parsers like ANTLR, bison, Yacc and flex.

Rationale: I'm not aware of applications of XDuce and CDuce. HaRP features a broken link to the homepage. In general too commercial or too theoretical to be discussed here.

Parser generators feature CFG-based approaches (context-free grammar), require unambiguous grammars (regex isn't unambiguous) and structural persistency is more important than performance. Hence uninteresting.

Parsing expression grammars (PEG) have different semantics (greedy, non-backtracking), seem to be a super set and sorry, I didn't look into them thoroughly. Might be interesting; theory seems to be in progress.

Java

Pattern

compile(String regex[, int flags] )
matcher([String regex,] CharSequence input)
quote(String s)
split(CharSequence input[, int limit])

Matcher

find([int start])
group([int|String group])
matches()
replaceAll(String replacement)
replaceFirst(String replacement)

Links: Oracle's regex documentation, Source code

Java

• Lookaheads or lookbehinds must be strings of fixed length.

• If you want to escape metacharacters, you have to do it with two backslashes.

  \[harlo\]

  \\[harlo\\]

• Java is old and stable. Different implementations of the JVM like SunJDK and OpenJDK exist.

Go

API described by a regex:

Find(All)?(String)?(Submatch)?(Index)?

The regexp implementation provided by this package is guaranteed to run in time linear in the size of the input. (This is a property not guaranteed by most open source implementations of regular expressions.)

The implementation is written natively in Go. Russ Cox is the regex expert who has written this engine.

re2 is another engine by Russ Cox which was ported to several languages: RE2/J, pyre2, re::engine::RE2

Links: Go regexp documentation Source code

Python

re.search(pattern, string, flags=0)
re.match(pattern, string, flags=0)
re.fullmatch(pattern, string, flags=0)
re.split(pattern, string, maxsplit=0, flags=0)
re.findall(pattern, string, flags=0)
re.sub(pattern, repl, string, count=0, flags=0)
re.escape(string)

Links: Python's re module, Source code

Perl

$string =~ /regex/

$string !~ /regex/

• A lot of modifiers
• Inspired the famous PCRE library
• perl was famous for its text processing capabilities. Nowadays it lacks activity (AFAICS).
• String interpolation as a performance problem.

my $e = "Hello";
my $p = /$e World/;
print "Hello World" =~ $p, "\n";

Links: perlre, Source code

Engines

Differences on engines:

• What can be extracted? Only fixed number of arguments? Can you access structural information?
• Embedding into host language? Syntactic sugar? String interpolation? Applicable to pattern matching?
• Different modifiers but they are mostly the same. Local modifiers?
• Ambiguities get resolved?
• Configurability of greediness?
• Word boundaries
• Caching
• Memory requirements
• Runtime guarantees / efficiency

Understanding leftmost

leftmost-longest

POSIX ERE (egrep) syntax

leftmost-first

Non-POSIX engines (perl, python, go, java)

Leftmost-longest means when matching against text, the regexp returns a match that begins as early as possible in the input (leftmost), and among those it chooses a match that is as long as possible.

Leftmost first

==============================================
Mode                ⇒ Leftmost first anyone
Regular expression  ⇒ .*(ham|and ham and spam)
Input               ⇒ eggs and ham and spam
Groups              ⇒ Yes, 1

Match               ⇒ eggs and ham and spam
                      ╰──────────╯  ↦ 'eggs and ham' [0–12]

                    ⇒ eggs and ham and spam - group 1
                               ╰─╯

Leftmost longest

================================================================
Mode                ⇒ Leftmost longest anyone
Regular expression  ⇒ .*(ham|and ham and spam)
Input               ⇒ eggs and ham and spam
Groups              ⇒ Yes, 1

Match               ⇒ eggs and ham and spam
                      ╰───────────────────╯  ↦ 'eggs and ham and spam' [0–21]

                    ⇒ eggs and ham and spam - group 1
                           ╰──────────────╯

Exercise NOT string

Specification

Match an arbitrary except one string.

Exercise

Match any string except '01234'

Example testcases

ab
{empty string}
4
0
02
11
0123
01234
012345

Exercise NOT string

(^01234)

^[^01234]$

^[^0][^1][^2][^3][^4]$

^[^0]?[^1]?[^2]?[^3]?[^4]?$

^[^0]?[^1]?[^2]?[^3]?[^4]?.*$

Exercise NOT string

^([^0]?([^1]?([^2]?([^3]?([^4]?.*)))))$

^([^0]([^1]([^2]([^3]([^4].*)?)?)?)?)?$

^([^0]([^1]([^2]([^3]([^4].*)?|0123)?|012)?|01)?|0)?$

^([^0]([^1]([^2]([^3]([^4].*)|...3)|..2)|.1)|0|)$

Exercise NOT string

They all fail, because …

1. Matches string starting with 01234; 01234 fails
2. Matches only strings of length 1; 0 fails
3. Matches only strings of length 5; 0 fails
4. Matches only strings of length up to 5; 012345 fails
5. 01234 skips square bracket expr and matches .*; 01234 fails
6. Same as previous, just groups added
7. Next character must not correspond to 01234, but if current character does not correspond, anything is allowed; 11 fails
8. Fixes previous for some cases, but 11 still fails
9. Fixes previous for some cases, but 02 still fails

Exercise NOT string

Exercise NOT string

^(|.|..|...|....|[^0]....|.[^1]...|..[^2]..|...[^3].|....[^4]|......+)$

To the best of my knowledge, a correct solution to our problem 😙

Exercise NOT string

But we know negative lookaheads, right?

^(?!01234).*$

^(?!01234$).*$

^(?!01234$)(.|\n)*$

Exercise NOT string performance

1. |.|..|...|....|…

2. .?.?.?…

For excluding a string of length 1389 (1…500), I computed a regex with (1) 2,914,158 or (2) 1,947,413 characters and 123,761 test strings.

Usecase variadic matches

Usecase: A text file contains edges of a graph. It stores several numbers in a line:

4 42 1337

The first number defines the identifier of the base vertex. All consecutive numbers/vertices are connected to the base vertex.

Task: Match all integers and store them in a list.

Usecase variadic matches

So …

1. define a regex to match integers separated by a space
2. retrieve those integers as groups

… right?

>>> import re
>>> regex = r"^(\d+(?: |$))+"
>>> reg = re.compile(regex)
>>> match = reg.search("4 42 1337")

>>> match.groups()
('1337',)

('4', '42', '1337')

Usecase variadic matches

Case distinction:

RegEx match do not overlap

go: re.FindAllString, py: re.findall,
perl: @matches = $input =~ /regex/g;
java: while (matcher_object.find()) { matcher_object.group(0) }

RegEx match overlaps with next possible match

Last match started at index i? Start search at i+1.

Usecase variadic matches

Let's do it:

>>> import re
>>> regex = r"^(\d+(?: |$))+"
>>> reg = re.compile(regex)
>>> reg.findall("4 42 1337")
['1337']

What went wrong here?

>>> import re
>>> regex = r"\d+"
>>> reg = re.compile(regex)
>>> reg.findall("4 42 1337")
['4', '42', '1337']

Usecase recursive structures

Backreferences allow context-free specifications. What about XML?

>>> import re
>>> re.findall(r'<(\w+)>(.*)</\1>', '<svg><text></text></svg>')
[('svg', '<text></text>')]
>>> re.findall(r'<(\w+)>(.*)</\1>', '<svg><text></text></svg>'[5:])
[('text', '')]
>>> re.findall(r'<(\w+)>(.*)</\1>', '<svg><text>Hello World</text></svg>'[5:])
[('text', 'Hello World')]
        
        

          Backreferences, lookaheads and lookbehinds as features are the main reason,
          why regex engines are working inefficiently. They need to store a lot of information about the current parsing state which makes memory management kind of difficult.
        
      

Unicode

Q: How do you match a newline?

\r?\n

(\r|\n|\r\n)

\r?\n|\n?\r

\u000D\u000A|[\u000A\u000B\u000C\u000D\u0085\u2028\u2029]

Parsing email addresses

Thomas Limoncelli's email parsing regex

[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x 80-\xff\n\015()]*)*\)[\040\t]*)*(?:(?:[^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff]+(?![^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff])|"[^\\\x80 -\xff\n\015"]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015"]*)*")[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\01 5()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*(?:\.[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(? :\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*(?:[^(\040) <>@,;:".\\\[\]\000-\037\x80-\xff]+(?![^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff])|"[^\\\x80-\xff\n\015"]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\ 015"]*)*")[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\ ))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*)*@[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x8 0-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*(?:[^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff]+(?![^(\040)<>@,;:" .\\\[\]\000-\037\x80-\xff])|\[(?:[^\\\x80-\xff\n\015\[\]]|\\[^\x80-\xff])*\])[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\ ([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*(?:\.[\040\t]*(?:\([^\\\x80-\x ff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t ]*)*(?:[^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff]+(?![^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff])|\[(?:[^\\\x80-\xff\n\015\[\]]|\\[^\x80-\xf f])*\])[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^ \\\x80-\xff\n\015()]*)*\)[\040\t]*)*)*|(?:[^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff]+(?![^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff])|"[^\\\x 80-\xff\n\015"]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015"]*)*")[^()<>@,;:".\\\[\]\x80-\xff\000-\010\012-\037]*(?:(?:\([^\\\x80-\xff\n\015()]* (?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)|"[^\\\x80-\xff\n\0 15"]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015"]*)*")[^()<>@,;:".\\\[\]\x80-\xff\000-\010\012-\037]*)*<[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(? :(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*(?:@[\040\ t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n \015()]*)*\)[\040\t]*)*(?:[^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff]+(?![^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff])|\[(?:[^\\\x80-\xff\n\01 5\[\]]|\\[^\x80-\xff])*\])[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\x ff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*(?:\.[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\0 15()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*(?:[^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff]+(?! [^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff])|\[(?:[^\\\x80-\xff\n\015\[\]]|\\[^\x80-\xff])*\])[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\ [^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*)*(?:,[\040\t]*( ?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015 ()]*)*\)[\040\t]*)*@[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\0 15()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*(?:[^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff]+(?![^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff ])|\[(?:[^\\\x80-\xff\n\015\[\]]|\\[^\x80-\xff])*\])[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(? :\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*(?:\.[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80 -\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*(?:[^(\040)<>@,;:".\\\ [\]\000-\037\x80-\xff]+(?![^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff])|\[(?:[^\\\x80-\xff\n\015\[\]]|\\[^\x80-\xff])*\])[\040\t]*(?:\([^\\\ x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[ \040\t]*)*)*)*:[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()] *)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*)?(?:[^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff]+(?![^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff])| "[^\\\x80-\xff\n\015"]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015"]*)*")[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\x ff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*(?:\.[\040\t]*(?:\([^\\\x80-\xff\n\015()]* (?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*(?:[^(\0 40)<>@,;:".\\\[\]\000-\037\x80-\xff]+(?![^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff])|"[^\\\x80-\xff\n\015"]*(?:\\[^\x80-\xff][^\\\x80-\xff\ n\015"]*)*")[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)* \))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*)*@[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x8 0-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*(?:[^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff]+(?![^(\040)<>@,;:". \\\[\]\000-\037\x80-\xff])|\[(?:[^\\\x80-\xff\n\015\[\]]|\\[^\x80-\xff])*\])[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([ ^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]*)*(?:\.[\040\t]*(?:\([^\\\x80-\xff \n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\\x80-\xff\n\015()]*)*\)[\040\t]* )*(?:[^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff]+(?![^(\040)<>@,;:".\\\[\]\000-\037\x80-\xff])|\[(?:[^\\\x80-\xff\n\015\[\]]|\\[^\x80-\xff] )*\])[\040\t]*(?:\([^\\\x80-\xff\n\015()]*(?:(?:\\[^\x80-\xff]|\([^\\\x80-\xff\n\015()]*(?:\\[^\x80-\xff][^\\\x80-\xff\n\015()]*)*\))[^\\ \x80-\xff\n\015()]*)*\)[\040\t]*)*)*>)

Parsing email addresses

Mail::RFC822::Address

• In general, email address parsing is difficult and broken.
• But take this with a grain of salt. This is just IMHO.
• Check whether @ is included and verify with a verification link.

whois grml.solutions

mikagrml@twitter

RegViz

regviz.org

Regex Crossword

regexcrossword.com

RegHex

rampion.github.io/RegHex

RegEx to parse regex?

/^((?:(?:[^?+*{}()[\]\\|]+|\\.|\[(?:\^?\\.|\^[^\\]|[^\\^])(?:[^\]\\]+|\\.)*\]|\((?:\?[:=!]|\?<[=!]|\?>)?(?1)??\)|\(\?(?:R|[+-]?\d+)\))(?:(?:[?+*]|\{\d+(?:,\d*)?\})[?+]?)?|\|)*)$/

StackOverflow: Is there a regular expression to detect a valid regular expression?

Interesting reading material

Russ Cox

“Implementing regular expressions”

Unicode Consortium

“Unicode Regular Expressions”

Nick Patch

“Unicode Regular Expression Engines”

Claus Brabrand, Jakob G. Thomsen

“Typed and Unambiguous Pattern Matching on Strings using Regular Expressions”

Conclusion

• Do not use too powerful tools for simple jobs!
• Do not let user specify and execute regular expressions!
  We are not there yet!
• I think there will be something going on in the next years.
• I also think DSLs are a good idea, but we need standards.