Regular Expressions

Introduction

• How to count the blank lines in a file?
  • Most people consider a line with just spaces and tabs to be blank
  • But examining characters one by one is tedious
  • More complex patterns (like telephone numbers or email addresses) are hard to describe in code
• Use regular expressions (REs) instead
  • Represent patterns as strings
  • Just like the "*" in the shell's *.txt
• Warning: the notation is ugly
  • Have to use what's on the keyboard, instead of inventing new symbols the way mathematicians do

You Can Skip This Lecture If...

• You know what a regular expression is
• You understand the difference between «*» and «+»
• You know how and why to compile an RE
• You know how to find out which part of a string matched which part of an RE
• You know how to get all of an RE's matches with one method call

A Simple Example

• The simplest kind of RE matches a fixed string of characters
  • Similar to the in operator

Download fixed_match.py
  1   import re
  2   
  3   dragons = [
  4       ['CTAGGTGTACTGATG',    'Antipodean Opaleye'],
  5       ['AAGATGCGTCCGTAT',    'Common Welsh Green'],
  6       ['AGTCGTGCTCGTTATATC', 'Hebridean Black'],
  7       ['ATGCGTCGTCGATTATCT', 'Hungarian Horntail'],
  8       ['CCGTTAGGGCTAAATGCT', 'Norwegian Ridgeback']
  9   ]
 10   
 11   for (dna, name) in dragons:
 12       if re.search('ATGCGT', dna):
 13           print name

Download fixed_match.out
  1   Common Welsh Green
  2   Hungarian Horntail

This or That

• Modify the regular expression a little

  • Download or_match.py
      1   import re
      2   
      3   dragons = [
      4       ['CTAGGTGTACTGATG',    'Antipodean Opaleye'],
      5       ['AAGATGCGTCCGTAT',    'Common Welsh Green'],
      6       ['AGTCGTGCTCGTTATATC', 'Hebridean Black'],
      7       ['ATGCGTCGTCGATTATCT', 'Hungarian Horntail'],
      8       ['CCGTTAGGGCTAAATGCT', 'Norwegian Ridgeback']
      9   ]
     10   
     11   for (dna, name) in dragons:
     12       if re.search('ATGCGT|GCT', dna):
     13           print name
    

    Download or_match.out
      1   Common Welsh Green
      2   Hebridean Black
      3   Hungarian Horntail
      4   Norwegian Ridgeback
    

• The vertical bar «|» means “or”
  • So this RE matches any string containing either "ATGCGT" or "GCT"

Precedence

• What about matching either "ATA" or "ATC" (both of which code for isoleucine)?
  • «ATA|C» will not work: it matches either "ATA" or "C"
  • «ATA|ATC» will work, but it's a bit redundant
• Solution: use parentheses, just as in math

  Download precedence.py
    1   import re
    2   
    3   tests = [
    4       ['ATA',   True],
    5       ['xATCx', True],
    6       ['ATG',   False],
    7       ['AT',    False],
    8       ['ATAC',  True]
    9   ]
   10   
   11   for (dna, expected) in tests:
   12       actual = re.search('AT(A|C)', dna) is not None
   13       assert actual == expected
  

  • Note that there's no output: the asserts will crash the program if any of the tests fail

Escaping Special Characters

• How to match an actual "|", "(", or ")"?
• Solution is to use «\|», «\(», or «\)» in the RE
  • And of course «\\» to match a backslash
• But in order to put a backslash in a Python string, you have to escape it
  • So the written form of the RE is "\\|", "\\(", "\\)", or "\\\\"
• What you type in is being compiled twice:
  • Once by Python to create a string
  • Once by the regular expression library to create the RE
  • 

    Figure 10.1: Double Compilation of Regular Expressions

Raw Strings

• To help keep things readable, Python supports raw strings
  • Written as r'abc' or r"this\nand\nthat"
  • Inside a raw string, a backslash is just a backslash
  • So r'\n' is a string containing the two characters "\" and "n", not a newline
• Raw strings are not automatically converted into REs
  • But that is their most common use

Sequences

• In the shell, "*" matches zero or more characters
• In an RE, «*» is an operator that means, “match zero or more occurrences of a pattern”
  • Comes after the pattern, not before
• Example: match any strand of DNA in which "TTA" and "CTA" are separated by any number of "G"

  Download star.py
    1   tests = [
    2       ['TTACTA',    True],  # separated by zero G's
    3       ['TTAGCTA',   True],  # separated by one G
    4       ['TTAGGGCTA', True],  # separated by three G's
    5       ['TTAXCTA',   False], # an X in the way
    6       ['TTAGCGCTA', False], # an embedded X in the way
    7   ]
    8   
    9   for (dna, expected) in tests:
   10       actual = re.search('TTAG*CTA', dna) is not None
   11       assert actual == expected
  

  • Note that the RE matches "TTACTA" because «G*» can match zero occurrences of "G"
  • 

    Figure 10.2: Zero or More

• «+» matches one or more (i.e., won't match the empty string)

  Download plus.py
    1   assert re.search('TTAG*CTA', 'TTACTA')
    2   assert not re.search('TTAG+CTA', 'TTACTA')
  

  • 

    Figure 10.3: One or More

Making Something Optional

• The «?» operator means “optional”
  • I.e., zero or one occurrences, but no more

Download optional.py
  1   assert re.search('AC?T', 'AT')
  2   assert re.search('AC?T', 'ACT')
  3   assert not re.search('AC?T', 'ACCT')



Figure 10.4: Zero or One

Character Sets

• Use «[]» to match sets of characters
  • The expression «[abcd]» matches exactly one "a", "b", "c", or "d"
  • Can be abbreviated as «[a-d]»
• Often combined with «*», «+», or «?»
  • «[aeiou]+» matches any non-empty sequence of vowels
• Example: find lines containing numbers

  • Download find_numbers.py
      1   import re
      2   
      3   lines = [
      4       "Charles Darwin (1809-82)",
      5       "Darwin's principal works, The Origin of Species (1859)",
      6       "and The Descent of Man (1871) marked a new epoch in our",
      7       "understanding of our world and ourselves.  His ideas",
      8       "were shaped by the Beagle's voyage around the world in",
      9       "1831-36."
     10   ]
     11   
     12   for line in lines:
     13       if re.search('[0-9]+', line):
     14           print line
    

    Download find_numbers.out
      1   Charles Darwin (1809-82)
      2   Darwin's principal works, The Origin of Species (1859)
      3   and The Descent of Man (1871) marked a new epoch in our
      4   1831-36.
    

  • Try writing this without using regular expressions…

Abbreviations

• Some character sets occur so often that they have abbreviations

  • Sequence	Equivalent	Explanation
    «\d»	«[0-9]»	Digits
    «\s»	«[ \t\r\n]»	Whitespace
    «\w»	«[a-zA-Z0-9_]»	Word characters (i.e., those allowed in variable names)
    Table 10.1: Regular Expression Escapes in Python

Special Cases

• «[^abc]» means “anything except the characters in this set”
• «.» means “any character except the end of line”
  • Equivalent to «[^\n]»
• «\b» matchs the break between word and non-word characters
  • Doesn't consume any actual characters
  • 

    Figure 10.5: Word/Non-Word Breaks

• Example: find words that end in a vowel
  • Use string.split to break on spaces and newlines before applying RE

  • Download end_in_vowel.py
      1   import re
      2   
      3   words = '''Born in New York City in 1918, Richard Feynman earned a
      4   bachelor's degree at MIT in 1939, and a doctorate from Princeton in
      5   1942. After working on the Manhattan Project in Los Alamos during
      6   World War II, he became a professor at CalTech in 1951.  Feynman won
      7   the 1965 Nobel Prize in Physics for his work on quantum
      8   electrodynamics, and served on the commission investigating the
      9   Challenger disaster in 1986.'''.split()
     10   
     11   end_in_vowel = set()
     12   for w in words:
     13       if re.search(r'[aeiou]\b', w):
     14           end_in_vowel.add(w)
     15   for w in end_in_vowel:
     16       print w
    

    Download end_in_vowel.out
      1   a
      2   Prize
      3   degree
      4   became
      5   doctorate
      6   the
      7   he
    

Anchoring

• How to find blank lines?
  • re.search(r'\s*', line) will match "start end"
• Use anchors
  • «^» matches the beginning of the string
  • «$» matches the end
  • Neither consumes any characters
  • 

    Figure 10.6: Anchoring Matches

• Examples:

  • Pattern	Text	Result
    «b+»	"abbc"	Matches
    «^b+»	"abbc"	Fails (string doesn't start with b)
    «c$»	"abbc"	Matches (string ends with c)
    «^a*$»	aabaa	Fails (something other than "a" between start and end of string)
    Table 10.2: Regular Expression Anchors in Python

Extracting Matches

• Problem: want to find comments in a data file
  • A comment starts with a "#", and extends to the end of the line
• First try: If the RE matches, split on the "#"

  • Download comment_err.py
      1   import sys, re
      2   
      3   lines = '''Date: 2006-03-07
      4   On duty: HP # 01:30 - 03:00
      5   Observed: Common Welsh Green
      6   On duty: RW #03:00-04:30
      7   Observed: none
      8   On duty: HG # 04:30-06:00
      9   Observed: Hebridean Black
     10   '''.split('\n')
     11   
     12   for line in lines:
     13       if re.search('#', line):
     14           comment = line.split('#')[1]
     15           print comment
    

    Download comment_err.out
      1    01:30 - 03:00
      2   03:00-04:30
      3    04:30-06:00
    

  • Output is inconsistent
  • split followed by strip seems clumsy

Match Objects

• Result of re.search is actually a match object that records what what matched, and where
  • mo.group() returns the whole string that matched the RE
  • mo.start() and mo.end() are the indices of the match's location

  • Download match_object.py
      1   import re
      2   
      3   text = 'abbcb'
      4   for pattern in ['b+', 'bc*', 'b+c+']:
      5       match = re.search(pattern, text)
      6       print '%s / %s => "%s" (%d, %d)' % \
      7             (pattern, text, match.group(), match.start(), match.end())
    

    Download match_object.out
      1   b+ / abbcb => "bb" (1, 3)
      2   bc* / abbcb => "b" (1, 2)
      3   b+c+ / abbcb => "bbc" (1, 4)
    

Match Groups

• Every parenthesized subexpression in the RE is a group
  • Group 0 is the entire match
  • Text that matched N^th parentheses (counting from left) is group N
  • mo.group(3) is the text that matched the third subexpression, m.start(3) is where it started
• Extracting comments is now easy:

  • Download comment.py
      1   import sys, re
      2   
      3   lines = '''Date: 2006-03-07
      4   On duty: HP # 01:30 - 03:00
      5   Observed: Common Welsh Green
      6   On duty: RW #03:00-04:30
      7   Observed: none
      8   On duty: HG # 04:30-06:00
      9   Observed: Hebridean Black
     10   '''.split('\n')
     11   
     12   for line in lines:
     13       match = re.search(r'#\s*(.+)', line)
     14       if match:
     15           comment = match.group(1)
     16           print comment
    

    Download comment.out
      1   01:30 - 03:00
      2   03:00-04:30
      3   04:30-06:00
    

Reversing Columns

• REs are the power tools of text processing
  • Can do things in one line that would otherwise take many lines of code
• Example: reverse two-column data

  • Download reverse_cols.py
      1   import re
      2   
      3   def reverse_columns(line):
      4       match = re.search(r'^\s*(\d+)\s+(\d+)\s*$', line)
      5       if not match:
      6           return line
      7       return match.group(2) + ' ' + match.group(1)
      8   
      9   tests = [
     10       ['10 20',    'easy case'],
     11       [' 30  40 ', 'padding'],
     12       ['60 70 80', 'too many columns'],
     13       ['90 end',   'non-numeric']
     14   ]
     15   
     16   for (fixture, title) in tests:
     17       actual = reverse_columns(fixture)
     18       print '%s: "%s" => "%s"' % (title, fixture, actual)
    

    Download reverse_cols.out
      1   easy case: "10 20" => "20 10"
      2   padding: " 30  40 " => "40 30"
      3   too many columns: "60 70 80" => "60 70 80"
      4   non-numeric: "90 end" => "90 end"
    

Compiling

• The RE library compiles patterns into a more concise form for matching
  • Each regular expression becomes a finite state machine
  • Library follows the arcs in the FSM as it reads characters
  • Drawing FSMs is a good way to debug REs
  • 

    Figure 10.7: Regular Expressions as Finite State Machines

• You can improve a program's performance by compiling the RE once, and re-using the compiled form
  • Use re.compile(pattern) to get the compiled RE
  • Its methods have the same names and behavior as the functions in the re module
  • E.g., matcher.search(text) searches text for matches to the RE that was compiled to create matcher

Finding Title Case Words

• Example: find all Title Case words in a document

  • Download title_case.py
      1   import re
      2   
      3   # Put pattern outside 'find_all' so that it's only compiled once.
      4   pattern = re.compile(r'\b([A-Z][a-z]*)\b(.*)')
      5   
      6   def find_all(line):
      7       result = []
      8       match = pattern.search(line)
      9       while match:
     10           result.append(match.group(1))
     11           match = pattern.search(match.group(2))
     12       return result
     13   
     14   lines = [
     15       'This has several Title Case words',
     16       'on Each Line (Some in parentheses).'
     17   ]
     18   for line in lines:
     19       print line
     20       for word in find_all(line):
     21           print '\t', word
    

    Download title_case.out
      1   This has several Title Case words
      2   	This
      3   	Title
      4   	Case
      5   on Each Line (Some in parentheses).
      6   	Each
      7   	Line
      8   	Some
    

Finding All Matches

• Notice how the function gets all matches:
  • Pattern captures what we want in group 1, and everything else on the line in group 2
  • Each time there's a match, continue the search in the remainder captured in group 2
• Much easier to use the findall method

  • Download findall.py
      1   import re
      2   
      3   lines = [
      4       'This has several Title Case words',
      5       'on Each Line (Some in parentheses).'
      6   ]
      7   pattern = re.compile(r'\b([A-Z][a-z]*)\b')
      8   for line in lines:
      9       print line
     10       for word in pattern.findall(line):
     11           print '\t', word
    

    Download findall.out
      1   This has several Title Case words
      2   	This
      3   	Title
      4   	Case
      5   on Each Line (Some in parentheses).
      6   	Each
      7   	Line
      8   	Some
    

Reference Material

Pattern	Matches	Doesn't Match	Explanation
«a*»	"", "a", "aa", …	"A", "b"	«*» means “zero or more” matching is case sensitive
«b+»	"b", "bb", …	""	«+» means “one or more”
«ab?c»	"ac", "abc"	"a", "abbc"	«?» means “optional” (zero or one)
«[abc]»	"a", "b", or "c"	"ab", "d"	«[…]» means “one character from a set”
«[a-c]»	"a", "b", or "c"	Character ranges can be abbreviated
«[abc]*»	"", "ac", "baabcab", …	Operators can be combined: zero or more choices from "a", "b", or "c"
Table 10.3: Regular Expression Operators

Method	Purpose	Example	Result
split	Split a string on a pattern.	re.split('\\s*,\\s*', 'a, b ,c , d')	['a', 'b', 'c', 'd']
findall	Find all matches for a pattern.	re.findall('\\b[A-Z][a-z]*', 'Some words in Title Case.')	['Some', 'Title', 'Case']
sub	Replace matches with new text.	re.sub('\\d+', 'NUM', 'If 123 is 456')	"If NUM is NUM"
Table 10.4: Regular Expression Object Methods

But Wait, There's More

• We've only scratched the surface
  • Regular expressions have proved to be too useful to remain clean and elegant
• For example, use «pat{N}» to match exactly N occurrences of a pattern
  • More generally, «pat{M,N}» matches between M and N occurrences
• Most important thing is to build up complex REs one step at a time
  • Write something that matches part of what you're looking for
  • Test it
  • Add to it

Summary

• Regular expressions are available in almost every language
  • As a library: C/C++, Java, …
  • Built into the language: Perl, Ruby, …
  • Syntax varies slightly, but the ideas are the same
• For a broader tutorial, see [Wilson 2005]
  • And if you're going to be doing serious work, check out [Good 2005] or [Friedl 2002]

Exercises