Andy Chu — 2018/6/7

Regex Tips, and Theory vs. Practice

Intro

What are regexes good for?

• Lexing programming languages
• "Big Data"
• System administration: server and network configuration

Quotes

I define UNIX as 30 definitions of regular expressions living under one roof.

— Donald Knuth

(Examples: grep, awk, Perl, Python, vim, emacs, ...)

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

— Jamie Zawinski

(related to tip #4: follow-on talk)

Tips

1. Use extended regular expressions (ERE) at the shell to minimize the amount of syntax you need to remember (grep/sed/awk vs. Perl/Python/JS/Ruby)

   • [demo]
   • grep -E (egrep)
   • sed -r or --regexp-extended (GNU)
   • awk (no flags necessary)
   • EREs are not exactly the same as Perl-style regexes, but they're closer than BREs (basic regexes).

2. Always write unit tests for your regular expressions.

   • Think of regular expressions as an alternate notation for a function. Either:
     1. myregex(s: str) -> bool
     2. myregex(s: str) -> (group1: str, group2: str, ...)
   • [demo]

3. Use re.VERBOSE in Python for readability (/x in Perl; JavaScript doesn't have this)

   • [demo]

4. Use regular expressions only to match regular languages (a mathematical idea).

   • More complex languages require more powerful parsing techniques (e.g. those based on grammars, PEGs, etc.)
   • Followup talk/seminar:
     • Learn what regex constructs to avoid.
     • Know when not to use regexes (or regular expressions).
     • Understand the potential for rare but severe performance bugs.
       • .. due to the algorithmic difference between different regex engines.

Intro

Q: What's good about both "regexes" and regular languages?

A: They are a compact notation for pattern matching on strings (e.g. without writing an if statement for every character). [example]

[A-Za-z_][A-Za-z0-9_]*                    # recognize a variable name
                                          # (programming language world)

^(http|https)://.*\.(png|gif|jpg|jpeg)$   # recognize certain URLs
                                          # ("big data" and system
                                          # administration worlds)

Excerpt from Crafting Interpreters

private boolean isDigit(char c) {
  return c >= '0' && c <= '9';
} 

private boolean isAlpha(char c) {
  return (c >= 'a' && c <= 'z') ||
         (c >= 'A' && c <= 'Z') ||
          c == '_';
}

private boolean isAlphaNumeric(char c) {
  return isAlpha(c) || isDigit(c);
}

private void identifier() {
  while (isAlphaNumeric(peek())) advance();

  addToken(IDENTIFIER);
}

  default:
    ...
    } else if (isAlpha(c)) {
      identifier();
    ...

Comparison

Recap: What's Good About Regular Languages (but NOT regexes)?

1. They have efficiency guarantees -- O(n) time, O(1) space.
2. They can represent nondeterminism
   • Compare with imperative code. Writing by hand isn't necessarily more efficient.
   • Trie Special Case
3. They can be translated to native code (re2c).
4. They can be checked for exhaustiveness by a compiler (re2c). Compare with ML/Haskell).

Links

• Regular Expression Denial-of-Service
  • Stack Overflow 2016 outage
  • Hotmail Migration 2006
• Guy Steele at ClojureConf 2017 on Computer Science Meta-Notation (YouTube video)
• Comprehensive / authoritative series of posts: Implementing Regular Expressions by Russ Cox
  • Addresses Perl-style vs. DFA/NFA, capturing.
  • Doesn't talk (much) about translation to native code (re2c, not re2).
  • Motivations: security, big data