\documentclass{howto} % TODO:% Document lookbehind assertions% Better way of displaying a RE, a string, and what it matches% Mention optional argument to match.groups()% Unicode (at least a reference) \title{Regular Expression HOWTO} \release{0.05} \author{A.M. Kuchling}\authoraddress{\email{amk@amk.ca}} \begin{document}\maketitle \begin{abstract}\noindentThis document is an introductory tutorial to using regular expressionsin Python with the \module{re} module. It provides a gentlerintroduction than the corresponding section in the Library Reference. This document is available from \url{http://www.amk.ca/python/howto}. \end{abstract} \tableofcontents \section{Introduction} The \module{re} module was added in Python 1.5, and providesPerl-style regular expression patterns. Earlier versions of Pythoncame with the \module{regex} module, which provided Emacs-stylepatterns. \module{regex} module was removed in Python 2.5. Regular expressions (or REs) are essentially a tiny, highlyspecialized programming language embedded inside Python and madeavailable through the \module{re} module. Using this little language,you specify the rules for the set of possible strings that you want tomatch; this set might contain English sentences, or e-mail addresses,or TeX commands, or anything you like. You can then ask questionssuch as ``Does this string match the pattern?'', or ``Is there a matchfor the pattern anywhere in this string?''. You can also use REs tomodify a string or to split it apart in various ways. Regular expression patterns are compiled into a series of bytecodeswhich are then executed by a matching engine written in C. Foradvanced use, it may be necessary to pay careful attention to how theengine will execute a given RE, and write the RE in a certain way inorder to produce bytecode that runs faster. Optimization isn'tcovered in this document, because it requires that you have a goodunderstanding of the matching engine's internals. The regular expression language is relatively small and restricted, sonot all possible string processing tasks can be done using regularexpressions. There are also tasks that \emph{can} be done withregular expressions, but the expressions turn out to be verycomplicated. In these cases, you may be better off writing Pythoncode to do the processing; while Python code will be slower than anelaborate regular expression, it will also probably be more understandable. \section{Simple Patterns} We'll start by learning about the simplest possible regularexpressions. Since regular expressions are used to operate onstrings, we'll begin with the most common task: matching characters. For a detailed explanation of the computer science underlying regularexpressions (deterministic and non-deterministic finite automata), youcan refer to almost any textbook on writing compilers. \subsection{Matching Characters} Most letters and characters will simply match themselves. Forexample, the regular expression \regexp{test} will match the string\samp{test} exactly. (You can enable a case-insensitive mode thatwould let this RE match \samp{Test} or \samp{TEST} as well; moreabout this later.) There are exceptions to this rule; some characters arespecial, and don't match themselves. Instead, they signal that someout-of-the-ordinary thing should be matched, or they affect otherportions of the RE by repeating them. Much of this document isdevoted to discussing various metacharacters and what they do. Here's a complete list of the metacharacters; their meanings will bediscussed in the rest of this HOWTO. \begin{verbatim}. ^ $ * + ? { [ ] \ | ( )\end{verbatim}% $ The first metacharacters we'll look at are \samp{[} and \samp{]}.They're used for specifying a character class, which is a set ofcharacters that you wish to match. Characters can be listedindividually, or a range of characters can be indicated by giving twocharacters and separating them by a \character{-}. For example,\regexp{[abc]} will match any of the characters \samp{a}, \samp{b}, or\samp{c}; this is the same as\regexp{[a-c]}, which uses a range to express the same set ofcharacters. If you wanted to match only lowercase letters, yourRE would be \regexp{[a-z]}. Metacharacters are not active inside classes. For example,\regexp{[akm\$]} will match any of the characters \character{a},\character{k}, \character{m}, or \character{\$}; \character{\$} isusually a metacharacter, but inside a character class it's stripped ofits special nature. You can match the characters not within a range by \dfn{complementing}the set. This is indicated by including a \character{\^} as the firstcharacter of the class; \character{\^} elsewhere will simply match the\character{\^} character. For example, \verb|[^5]| will match anycharacter except \character{5}. Perhaps the most important metacharacter is the backslash, \samp{\e}. As in Python string literals, the backslash can be followed by variouscharacters to signal various special sequences. It's also used to escapeall the metacharacters so you can still match them in patterns; forexample, if you need to match a \samp{[} or \samp{\e}, you can precede them with a backslash to remove theirspecial meaning: \regexp{\e[} or \regexp{\e\e}. Some of the special sequences beginning with \character{\e} representpredefined sets of characters that are often useful, such as the setof digits, the set of letters, or the set of anything that isn'twhitespace. The following predefined special sequences are available: \begin{itemize}\item[\code{\e d}]Matches any decimal digit; this isequivalent to the class \regexp{[0-9]}. \item[\code{\e D}]Matches any non-digit character; this isequivalent to the class \verb|[^0-9]|. \item[\code{\e s}]Matches any whitespace character; this isequivalent to the class \regexp{[ \e t\e n\e r\e f\e v]}. \item[\code{\e S}]Matches any non-whitespace character; this isequivalent to the class \verb|[^ \t\n\r\f\v]|. \item[\code{\e w}]Matches any alphanumeric character; this is equivalent to the class\regexp{[a-zA-Z0-9_]}. \item[\code{\e W}]Matches any non-alphanumeric character; this is equivalent to the class\verb|[^a-zA-Z0-9_]|. \end{itemize} These sequences can be included inside a character class. Forexample, \regexp{[\e s,.]} is a character class that will match anywhitespace character, or \character{,} or \character{.}. The final metacharacter in this section is \regexp{.}. It matchesanything except a newline character, and there's an alternate mode(\code{re.DOTALL}) where it will match even a newline. \character{.}is often used where you want to match ``any character''. \subsection{Repeating Things} Being able to match varying sets of characters is the first thingregular expressions can do that isn't already possible with themethods available on strings. However, if that was the onlyadditional capability of regexes, they wouldn't be much of an advance.Another capability is that you can specify that portions of the REmust be repeated a certain number of times. The first metacharacter for repeating things that we'll look at is\regexp{*}. \regexp{*} doesn't match the literal character \samp{*};instead, it specifies that the previous character can be matched zeroor more times, instead of exactly once. For example, \regexp{ca*t} will match \samp{ct} (0 \samp{a}characters), \samp{cat} (1 \samp{a}), \samp{caaat} (3 \samp{a}characters), and so forth. The RE engine has various internallimitations stemming from the size of C's \code{int} type, that willprevent it from matching over 2 billion \samp{a} characters; youprobably don't have enough memory to construct a string that large, soyou shouldn't run into that limit. Repetitions such as \regexp{*} are \dfn{greedy}; when repeating a RE,the matching engine will try to repeat it as many times as possible.If later portions of the pattern don't match, the matching engine willthen back up and try again with few repetitions. A step-by-step example will make this more obvious. Let's considerthe expression \regexp{a[bcd]*b}. This matches the letter\character{a}, zero or more letters from the class \code{[bcd]}, andfinally ends with a \character{b}. Now imagine matching this REagainst the string \samp{abcbd}. \begin{tableiii}{c|l|l}{}{Step}{Matched}{Explanation}\lineiii{1}{\code{a}}{The \regexp{a} in the RE matches.}\lineiii{2}{\code{abcbd}}{The engine matches \regexp{[bcd]*}, going as far asit can, which is to the end of the string.}\lineiii{3}{\emph{Failure}}{The engine tries to match \regexp{b}, but thecurrent position is at the end of the string, so it fails.}\lineiii{4}{\code{abcb}}{Back up, so that \regexp{[bcd]*} matchesone less character.}\lineiii{5}{\emph{Failure}}{Try \regexp{b} again, but thecurrent position is at the last character, which is a \character{d}.}\lineiii{6}{\code{abc}}{Back up again, so that \regexp{[bcd]*} isonly matching \samp{bc}.}\lineiii{6}{\code{abcb}}{Try \regexp{b} again. This time but the character at the current position is \character{b}, so it succeeds.}\end{tableiii} The end of the RE has now been reached, and it has matched\samp{abcb}. This demonstrates how the matching engine goes as far asit can at first, and if no match is found it will then progressivelyback up and retry the rest of the RE again and again. It will back upuntil it has tried zero matches for \regexp{[bcd]*}, and if thatsubsequently fails, the engine will conclude that the string doesn'tmatch the RE at all. Another repeating metacharacter is \regexp{+}, which matches one ormore times. Pay careful attention to the difference between\regexp{*} and \regexp{+}; \regexp{*} matches \emph{zero} or moretimes, so whatever's being repeated may not be present at all, while\regexp{+} requires at least \emph{one} occurrence. To use a similarexample, \regexp{ca+t} will match \samp{cat} (1 \samp{a}),\samp{caaat} (3 \samp{a}'s), but won't match \samp{ct}. There are two more repeating qualifiers. The question mark character,\regexp{?}, matches either once or zero times; you can think of it asmarking something as being optional. For example, \regexp{home-?brew}matches either \samp{homebrew} or \samp{home-brew}. The most complicated repeated qualifier is\regexp{\{\var{m},\var{n}\}}, where \var{m} and \var{n} are decimalintegers. This qualifier means there must be at least \var{m}repetitions, and at most \var{n}. For example, \regexp{a/\{1,3\}b}will match \samp{a/b}, \samp{a//b}, and \samp{a///b}. It won't match\samp{ab}, which has no slashes, or \samp{a////b}, which has four. You can omit either \var{m} or \var{n}; in that case, a reasonablevalue is assumed for the missing value. Omitting \var{m} isinterpreted as a lower limit of 0, while omitting \var{n} results in anupper bound of infinity --- actually, the 2 billion limit mentionedearlier, but that might as well be infinity. Readers of a reductionist bent may notice that the three other qualifierscan all be expressed using this notation. \regexp{\{0,\}} is the sameas \regexp{*}, \regexp{\{1,\}} is equivalent to \regexp{+}, and\regexp{\{0,1\}} is the same as \regexp{?}. It's better to use\regexp{*}, \regexp{+}, or \regexp{?} when you can, simply becausethey're shorter and easier to read. \section{Using Regular Expressions} Now that we've looked at some simple regular expressions, how do weactually use them in Python? The \module{re} module provides aninterface to the regular expression engine, allowing you to compileREs into objects and then perform matches with them. \subsection{Compiling Regular Expressions} Regular expressions are compiled into \class{RegexObject} instances,which have methods for various operations such as searching forpattern matches or performing string substitutions. \begin{verbatim}>>> import re>>> p = re.compile('ab*')>>> print p<re.RegexObject instance at 80b4150>\end{verbatim} \function{re.compile()} also accepts an optional \var{flags}argument, used to enable various special features and syntaxvariations. We'll go over the available settings later, but for now asingle example will do: \begin{verbatim}>>> p = re.compile('ab*', re.IGNORECASE)\end{verbatim} The RE is passed to \function{re.compile()} as a string. REs arehandled as strings because regular expressions aren't part of the corePython language, and no special syntax was created for expressingthem. (There are applications that don't need REs at all, so there'sno need to bloat the language specification by including them.)Instead, the \module{re} module is simply a C extension moduleincluded with Python, just like the \module{socket} or \module{zlib}module. Putting REs in strings keeps the Python language simpler, but has onedisadvantage which is the topic of the next section. \subsection{The Backslash Plague} As stated earlier, regular expressions use the backslashcharacter (\character{\e}) to indicate special forms or to allowspecial characters to be used without invoking their special meaning.This conflicts with Python's usage of the same character for the samepurpose in string literals. Let's say you want to write a RE that matches the string\samp{{\e}section}, which might be found in a \LaTeX\ file. To figureout what to write in the program code, start with the desired stringto be matched. Next, you must escape any backslashes and othermetacharacters by preceding them with a backslash, resulting in thestring \samp{\e\e section}. The resulting string that must be passedto \function{re.compile()} must be \verb|\\section|. However, toexpress this as a Python string literal, both backslashes must beescaped \emph{again}. \begin{tableii}{c|l}{code}{Characters}{Stage} \lineii{\e section}{Text string to be matched} \lineii{\e\e section}{Escaped backslash for \function{re.compile}} \lineii{"\e\e\e\e section"}{Escaped backslashes for a string literal}\end{tableii} In short, to match a literal backslash, one has to write\code{'\e\e\e\e'} as the RE string, because the regular expressionmust be \samp{\e\e}, and each backslash must be expressed as\samp{\e\e} inside a regular Python string literal. In REs thatfeature backslashes repeatedly, this leads to lots of repeatedbackslashes and makes the resulting strings difficult to understand. The solution is to use Python's raw string notation for regularexpressions; backslashes are not handled in any special way ina string literal prefixed with \character{r}, so \code{r"\e n"} is atwo-character string containing \character{\e} and \character{n},while \code{"\e n"} is a one-character string containing a newline.Frequently regular expressions will be expressed in Pythoncode using this raw string notation. \begin{tableii}{c|c}{code}{Regular String}{Raw string} \lineii{"ab*"}{\code{r"ab*"}} \lineii{"\e\e\e\e section"}{\code{r"\e\e section"}} \lineii{"\e\e w+\e\e s+\e\e 1"}{\code{r"\e w+\e s+\e 1"}}\end{tableii} \subsection{Performing Matches} Once you have an object representing a compiled regular expression,what do you do with it? \class{RegexObject} instances have severalmethods and attributes. Only the most significant ones will becovered here; consult \ulink{the LibraryReference}{http://www.python.org/doc/lib/module-re.html} for acomplete listing. \begin{tableii}{c|l}{code}{Method/Attribute}{Purpose} \lineii{match()}{Determine if the RE matches at the beginning of the string.} \lineii{search()}{Scan through a string, looking for any location where this RE matches.} \lineii{findall()}{Find all substrings where the RE matches,and returns them as a list.} \lineii{finditer()}{Find all substrings where the RE matches,and returns them as an iterator.}\end{tableii} \method{match()} and \method{search()} return \code{None} if no matchcan be found. If they're successful, a \code{MatchObject} instance isreturned, containing information about the match: where it starts andends, the substring it matched, and more. You can learn about this by interactively experimenting with the\module{re} module. If you have Tkinter available, you may also wantto look at \file{Tools/scripts/redemo.py}, a demonstration programincluded with the Python distribution. It allows you to enter REs andstrings, and displays whether the RE matches or fails.\file{redemo.py} can be quite useful when trying to debug acomplicated RE. Phil Schwartz's\ulink{Kodos}{http://kodos.sourceforge.net} is also an interactivetool for developing and testing RE patterns. This HOWTO will use thestandard Python interpreter for its examples. First, run the Python interpreter, import the \module{re} module, andcompile a RE: \begin{verbatim}Python 2.2.2 (#1, Feb 10 2003, 12:57:01)>>> import re>>> p = re.compile('[a-z]+')>>> p<_sre.SRE_Pattern object at 80c3c28>\end{verbatim} Now, you can try matching various strings against the RE\regexp{[a-z]+}. An empty string shouldn't match at all, since\regexp{+} means 'one or more repetitions'. \method{match()} shouldreturn \code{None} in this case, which will cause the interpreter toprint no output. You can explicitly print the result of\method{match()} to make this clear. \begin{verbatim}>>> p.match("")>>> print p.match("")None\end{verbatim} Now, let's try it on a string that it should match, such as\samp{tempo}. In this case, \method{match()} will return a\class{MatchObject}, so you should store the result in a variable forlater use. \begin{verbatim}>>> m = p.match( 'tempo')>>> print m<_sre.SRE_Match object at 80c4f68>\end{verbatim} Now you can query the \class{MatchObject} for information about thematching string. \class{MatchObject} instances also have severalmethods and attributes; the most important ones are: \begin{tableii}{c|l}{code}{Method/Attribute}{Purpose} \lineii{group()}{Return the string matched by the RE} \lineii{start()}{Return the starting position of the match} \lineii{end()}{Return the ending position of the match} \lineii{span()}{Return a tuple containing the (start, end) positions of the match}\end{tableii} Trying these methods will soon clarify their meaning: \begin{verbatim}>>> m.group()'tempo'>>> m.start(), m.end()(0, 5)>>> m.span()(0, 5)\end{verbatim} \method{group()} returns the substring that was matched by theRE. \method{start()} and \method{end()} return the starting andending index of the match. \method{span()} returns both start and endindexes in a single tuple. Since the \method{match} method onlychecks if the RE matches at the start of a string,\method{start()} will always be zero. However, the \method{search}method of \class{RegexObject} instances scans through the string, so the match may not start at zero in that case. \begin{verbatim}>>> print p.match('::: message')None>>> m = p.search('::: message') ; print m<re.MatchObject instance at 80c9650>>>> m.group()'message'>>> m.span()(4, 11)\end{verbatim} In actual programs, the most common style is to store the\class{MatchObject} in a variable, and then check if it was\code{None}. This usually looks like: \begin{verbatim}p = re.compile( ... )m = p.match( 'string goes here' )if m: print 'Match found: ', m.group()else: print 'No match'\end{verbatim} Two \class{RegexObject} methods return all of the matches for a pattern.\method{findall()} returns a list of matching strings: \begin{verbatim}>>> p = re.compile('\d+')>>> p.findall('12 drummers drumming, 11 pipers piping, 10 lords a-leaping')['12', '11', '10']\end{verbatim} \method{findall()} has to create the entire list before it can bereturned as the result. In Python 2.2, the \method{finditer()} methodis also available, returning a sequence of \class{MatchObject} instances as an iterator. \begin{verbatim}>>> iterator = p.finditer('12 drummers drumming, 11 ... 10 ...')>>> iterator<callable-iterator object at 0x401833ac>>>> for match in iterator:... print match.span()...(0, 2)(22, 24)(29, 31)\end{verbatim} \subsection{Module-Level Functions} You don't have to produce a \class{RegexObject} and call its methods;the \module{re} module also provides top-level functions called\function{match()}, \function{search()}, \function{sub()}, and soforth. These functions take the same arguments as the corresponding\class{RegexObject} method, with the RE string added as the firstargument, and still return either \code{None} or a \class{MatchObject}instance.Lines 1–500 of 1463. Load more
\documentclass{howto} % TODO: % Document lookbehind assertions % Better way of displaying a RE, a string, and what it matches % Mention optional argument to match.groups() % Unicode (at least a reference) \title{Regular Expression HOWTO} \release{0.05} \author{A.M. Kuchling} \authoraddress{\email{amk@amk.ca}} \begin{document} \maketitle \begin{abstract} \noindent This document is an introductory tutorial to using regular expressions in Python with the \module{re} module. It provides a gentler introduction than the corresponding section in the Library Reference. This document is available from \url{http://www.amk.ca/python/howto}. \end{abstract} \tableofcontents \section{Introduction} The \module{re} module was added in Python 1.5, and provides Perl-style regular expression patterns. Earlier versions of Python came with the \module{regex} module, which provided Emacs-style patterns. \module{regex} module was removed in Python 2.5. Regular expressions (or REs) are essentially a tiny, highly specialized programming language embedded inside Python and made available through the \module{re} module. Using this little language, you specify the rules for the set of possible strings that you want to match; this set might contain English sentences, or e-mail addresses, or TeX commands, or anything you like. You can then ask questions such as ``Does this string match the pattern?'', or ``Is there a match for the pattern anywhere in this string?''. You can also use REs to modify a string or to split it apart in various ways. Regular expression patterns are compiled into a series of bytecodes which are then executed by a matching engine written in C. For advanced use, it may be necessary to pay careful attention to how the engine will execute a given RE, and write the RE in a certain way in order to produce bytecode that runs faster. Optimization isn't covered in this document, because it requires that you have a good understanding of the matching engine's internals. The regular expression language is relatively small and restricted, so not all possible string processing tasks can be done using regular expressions. There are also tasks that \emph{can} be done with regular expressions, but the expressions turn out to be very complicated. In these cases, you may be better off writing Python code to do the processing; while Python code will be slower than an elaborate regular expression, it will also probably be more understandable. \section{Simple Patterns} We'll start by learning about the simplest possible regular expressions. Since regular expressions are used to operate on strings, we'll begin with the most common task: matching characters. For a detailed explanation of the computer science underlying regular expressions (deterministic and non-deterministic finite automata), you can refer to almost any textbook on writing compilers. \subsection{Matching Characters} Most letters and characters will simply match themselves. For example, the regular expression \regexp{test} will match the string \samp{test} exactly. (You can enable a case-insensitive mode that would let this RE match \samp{Test} or \samp{TEST} as well; more about this later.) There are exceptions to this rule; some characters are special, and don't match themselves. Instead, they signal that some out-of-the-ordinary thing should be matched, or they affect other portions of the RE by repeating them. Much of this document is devoted to discussing various metacharacters and what they do. Here's a complete list of the metacharacters; their meanings will be discussed in the rest of this HOWTO. \begin{verbatim} . ^ $ * + ? { [ ] \ | ( ) \end{verbatim} % $ The first metacharacters we'll look at are \samp{[} and \samp{]}. They're used for specifying a character class, which is a set of characters that you wish to match. Characters can be listed individually, or a range of characters can be indicated by giving two characters and separating them by a \character{-}. For example, \regexp{[abc]} will match any of the characters \samp{a}, \samp{b}, or \samp{c}; this is the same as \regexp{[a-c]}, which uses a range to express the same set of characters. If you wanted to match only lowercase letters, your RE would be \regexp{[a-z]}. Metacharacters are not active inside classes. For example, \regexp{[akm\$]} will match any of the characters \character{a}, \character{k}, \character{m}, or \character{\$}; \character{\$} is usually a metacharacter, but inside a character class it's stripped of its special nature. You can match the characters not within a range by \dfn{complementing} the set. This is indicated by including a \character{\^} as the first character of the class; \character{\^} elsewhere will simply match the \character{\^} character. For example, \verb|[^5]| will match any character except \character{5}. Perhaps the most important metacharacter is the backslash, \samp{\e}. As in Python string literals, the backslash can be followed by various characters to signal various special sequences. It's also used to escape all the metacharacters so you can still match them in patterns; for example, if you need to match a \samp{[} or \samp{\e}, you can precede them with a backslash to remove their special meaning: \regexp{\e[} or \regexp{\e\e}. Some of the special sequences beginning with \character{\e} represent predefined sets of characters that are often useful, such as the set of digits, the set of letters, or the set of anything that isn't whitespace. The following predefined special sequences are available: \begin{itemize} \item[\code{\e d}]Matches any decimal digit; this is equivalent to the class \regexp{[0-9]}. \item[\code{\e D}]Matches any non-digit character; this is equivalent to the class \verb|[^0-9]|. \item[\code{\e s}]Matches any whitespace character; this is equivalent to the class \regexp{[ \e t\e n\e r\e f\e v]}. \item[\code{\e S}]Matches any non-whitespace character; this is equivalent to the class \verb|[^ \t\n\r\f\v]|. \item[\code{\e w}]Matches any alphanumeric character; this is equivalent to the class \regexp{[a-zA-Z0-9_]}. \item[\code{\e W}]Matches any non-alphanumeric character; this is equivalent to the class \verb|[^a-zA-Z0-9_]|. \end{itemize} These sequences can be included inside a character class. For example, \regexp{[\e s,.]} is a character class that will match any whitespace character, or \character{,} or \character{.}. The final metacharacter in this section is \regexp{.}. It matches anything except a newline character, and there's an alternate mode (\code{re.DOTALL}) where it will match even a newline. \character{.} is often used where you want to match ``any character''. \subsection{Repeating Things} Being able to match varying sets of characters is the first thing regular expressions can do that isn't already possible with the methods available on strings. However, if that was the only additional capability of regexes, they wouldn't be much of an advance. Another capability is that you can specify that portions of the RE must be repeated a certain number of times. The first metacharacter for repeating things that we'll look at is \regexp{*}. \regexp{*} doesn't match the literal character \samp{*}; instead, it specifies that the previous character can be matched zero or more times, instead of exactly once. For example, \regexp{ca*t} will match \samp{ct} (0 \samp{a} characters), \samp{cat} (1 \samp{a}), \samp{caaat} (3 \samp{a} characters), and so forth. The RE engine has various internal limitations stemming from the size of C's \code{int} type, that will prevent it from matching over 2 billion \samp{a} characters; you probably don't have enough memory to construct a string that large, so you shouldn't run into that limit. Repetitions such as \regexp{*} are \dfn{greedy}; when repeating a RE, the matching engine will try to repeat it as many times as possible. If later portions of the pattern don't match, the matching engine will then back up and try again with few repetitions. A step-by-step example will make this more obvious. Let's consider the expression \regexp{a[bcd]*b}. This matches the letter \character{a}, zero or more letters from the class \code{[bcd]}, and finally ends with a \character{b}. Now imagine matching this RE against the string \samp{abcbd}. \begin{tableiii}{c|l|l}{}{Step}{Matched}{Explanation} \lineiii{1}{\code{a}}{The \regexp{a} in the RE matches.} \lineiii{2}{\code{abcbd}}{The engine matches \regexp{[bcd]*}, going as far as it can, which is to the end of the string.} \lineiii{3}{\emph{Failure}}{The engine tries to match \regexp{b}, but the current position is at the end of the string, so it fails.} \lineiii{4}{\code{abcb}}{Back up, so that \regexp{[bcd]*} matches one less character.} \lineiii{5}{\emph{Failure}}{Try \regexp{b} again, but the current position is at the last character, which is a \character{d}.} \lineiii{6}{\code{abc}}{Back up again, so that \regexp{[bcd]*} is only matching \samp{bc}.} \lineiii{6}{\code{abcb}}{Try \regexp{b} again. This time but the character at the current position is \character{b}, so it succeeds.} \end{tableiii} The end of the RE has now been reached, and it has matched \samp{abcb}. This demonstrates how the matching engine goes as far as it can at first, and if no match is found it will then progressively back up and retry the rest of the RE again and again. It will back up until it has tried zero matches for \regexp{[bcd]*}, and if that subsequently fails, the engine will conclude that the string doesn't match the RE at all. Another repeating metacharacter is \regexp{+}, which matches one or more times. Pay careful attention to the difference between \regexp{*} and \regexp{+}; \regexp{*} matches \emph{zero} or more times, so whatever's being repeated may not be present at all, while \regexp{+} requires at least \emph{one} occurrence. To use a similar example, \regexp{ca+t} will match \samp{cat} (1 \samp{a}), \samp{caaat} (3 \samp{a}'s), but won't match \samp{ct}. There are two more repeating qualifiers. The question mark character, \regexp{?}, matches either once or zero times; you can think of it as marking something as being optional. For example, \regexp{home-?brew} matches either \samp{homebrew} or \samp{home-brew}. The most complicated repeated qualifier is \regexp{\{\var{m},\var{n}\}}, where \var{m} and \var{n} are decimal integers. This qualifier means there must be at least \var{m} repetitions, and at most \var{n}. For example, \regexp{a/\{1,3\}b} will match \samp{a/b}, \samp{a//b}, and \samp{a///b}. It won't match \samp{ab}, which has no slashes, or \samp{a////b}, which has four. You can omit either \var{m} or \var{n}; in that case, a reasonable value is assumed for the missing value. Omitting \var{m} is interpreted as a lower limit of 0, while omitting \var{n} results in an upper bound of infinity --- actually, the 2 billion limit mentioned earlier, but that might as well be infinity. Readers of a reductionist bent may notice that the three other qualifiers can all be expressed using this notation. \regexp{\{0,\}} is the same as \regexp{*}, \regexp{\{1,\}} is equivalent to \regexp{+}, and \regexp{\{0,1\}} is the same as \regexp{?}. It's better to use \regexp{*}, \regexp{+}, or \regexp{?} when you can, simply because they're shorter and easier to read. \section{Using Regular Expressions} Now that we've looked at some simple regular expressions, how do we actually use them in Python? The \module{re} module provides an interface to the regular expression engine, allowing you to compile REs into objects and then perform matches with them. \subsection{Compiling Regular Expressions} Regular expressions are compiled into \class{RegexObject} instances, which have methods for various operations such as searching for pattern matches or performing string substitutions. \begin{verbatim} >>> import re >>> p = re.compile('ab*') >>> print p <re.RegexObject instance at 80b4150> \end{verbatim} \function{re.compile()} also accepts an optional \var{flags} argument, used to enable various special features and syntax variations. We'll go over the available settings later, but for now a single example will do: \begin{verbatim} >>> p = re.compile('ab*', re.IGNORECASE) \end{verbatim} The RE is passed to \function{re.compile()} as a string. REs are handled as strings because regular expressions aren't part of the core Python language, and no special syntax was created for expressing them. (There are applications that don't need REs at all, so there's no need to bloat the language specification by including them.) Instead, the \module{re} module is simply a C extension module included with Python, just like the \module{socket} or \module{zlib} module. Putting REs in strings keeps the Python language simpler, but has one disadvantage which is the topic of the next section. \subsection{The Backslash Plague} As stated earlier, regular expressions use the backslash character (\character{\e}) to indicate special forms or to allow special characters to be used without invoking their special meaning. This conflicts with Python's usage of the same character for the same purpose in string literals. Let's say you want to write a RE that matches the string \samp{{\e}section}, which might be found in a \LaTeX\ file. To figure out what to write in the program code, start with the desired string to be matched. Next, you must escape any backslashes and other metacharacters by preceding them with a backslash, resulting in the string \samp{\e\e section}. The resulting string that must be passed to \function{re.compile()} must be \verb|\\section|. However, to express this as a Python string literal, both backslashes must be escaped \emph{again}. \begin{tableii}{c|l}{code}{Characters}{Stage} \lineii{\e section}{Text string to be matched} \lineii{\e\e section}{Escaped backslash for \function{re.compile}} \lineii{"\e\e\e\e section"}{Escaped backslashes for a string literal} \end{tableii} In short, to match a literal backslash, one has to write \code{'\e\e\e\e'} as the RE string, because the regular expression must be \samp{\e\e}, and each backslash must be expressed as \samp{\e\e} inside a regular Python string literal. In REs that feature backslashes repeatedly, this leads to lots of repeated backslashes and makes the resulting strings difficult to understand. The solution is to use Python's raw string notation for regular expressions; backslashes are not handled in any special way in a string literal prefixed with \character{r}, so \code{r"\e n"} is a two-character string containing \character{\e} and \character{n}, while \code{"\e n"} is a one-character string containing a newline. Frequently regular expressions will be expressed in Python code using this raw string notation. \begin{tableii}{c|c}{code}{Regular String}{Raw string} \lineii{"ab*"}{\code{r"ab*"}} \lineii{"\e\e\e\e section"}{\code{r"\e\e section"}} \lineii{"\e\e w+\e\e s+\e\e 1"}{\code{r"\e w+\e s+\e 1"}} \end{tableii} \subsection{Performing Matches} Once you have an object representing a compiled regular expression, what do you do with it? \class{RegexObject} instances have several methods and attributes. Only the most significant ones will be covered here; consult \ulink{the Library Reference}{http://www.python.org/doc/lib/module-re.html} for a complete listing. \begin{tableii}{c|l}{code}{Method/Attribute}{Purpose} \lineii{match()}{Determine if the RE matches at the beginning of the string.} \lineii{search()}{Scan through a string, looking for any location where this RE matches.} \lineii{findall()}{Find all substrings where the RE matches, and returns them as a list.} \lineii{finditer()}{Find all substrings where the RE matches, and returns them as an iterator.} \end{tableii} \method{match()} and \method{search()} return \code{None} if no match can be found. If they're successful, a \code{MatchObject} instance is returned, containing information about the match: where it starts and ends, the substring it matched, and more. You can learn about this by interactively experimenting with the \module{re} module. If you have Tkinter available, you may also want to look at \file{Tools/scripts/redemo.py}, a demonstration program included with the Python distribution. It allows you to enter REs and strings, and displays whether the RE matches or fails. \file{redemo.py} can be quite useful when trying to debug a complicated RE. Phil Schwartz's \ulink{Kodos}{http://kodos.sourceforge.net} is also an interactive tool for developing and testing RE patterns. This HOWTO will use the standard Python interpreter for its examples. First, run the Python interpreter, import the \module{re} module, and compile a RE: \begin{verbatim} Python 2.2.2 (#1, Feb 10 2003, 12:57:01) >>> import re >>> p = re.compile('[a-z]+') >>> p <_sre.SRE_Pattern object at 80c3c28> \end{verbatim} Now, you can try matching various strings against the RE \regexp{[a-z]+}. An empty string shouldn't match at all, since \regexp{+} means 'one or more repetitions'. \method{match()} should return \code{None} in this case, which will cause the interpreter to print no output. You can explicitly print the result of \method{match()} to make this clear. \begin{verbatim} >>> p.match("") >>> print p.match("") None \end{verbatim} Now, let's try it on a string that it should match, such as \samp{tempo}. In this case, \method{match()} will return a \class{MatchObject}, so you should store the result in a variable for later use. \begin{verbatim} >>> m = p.match( 'tempo') >>> print m <_sre.SRE_Match object at 80c4f68> \end{verbatim} Now you can query the \class{MatchObject} for information about the matching string. \class{MatchObject} instances also have several methods and attributes; the most important ones are: \begin{tableii}{c|l}{code}{Method/Attribute}{Purpose} \lineii{group()}{Return the string matched by the RE} \lineii{start()}{Return the starting position of the match} \lineii{end()}{Return the ending position of the match} \lineii{span()}{Return a tuple containing the (start, end) positions of the match} \end{tableii} Trying these methods will soon clarify their meaning: \begin{verbatim} >>> m.group() 'tempo' >>> m.start(), m.end() (0, 5) >>> m.span() (0, 5) \end{verbatim} \method{group()} returns the substring that was matched by the RE. \method{start()} and \method{end()} return the starting and ending index of the match. \method{span()} returns both start and end indexes in a single tuple. Since the \method{match} method only checks if the RE matches at the start of a string, \method{start()} will always be zero. However, the \method{search} method of \class{RegexObject} instances scans through the string, so the match may not start at zero in that case. \begin{verbatim} >>> print p.match('::: message') None >>> m = p.search('::: message') ; print m <re.MatchObject instance at 80c9650> >>> m.group() 'message' >>> m.span() (4, 11) \end{verbatim} In actual programs, the most common style is to store the \class{MatchObject} in a variable, and then check if it was \code{None}. This usually looks like: \begin{verbatim} p = re.compile( ... ) m = p.match( 'string goes here' ) if m: print 'Match found: ', m.group() else: print 'No match' \end{verbatim} Two \class{RegexObject} methods return all of the matches for a pattern. \method{findall()} returns a list of matching strings: \begin{verbatim} >>> p = re.compile('\d+') >>> p.findall('12 drummers drumming, 11 pipers piping, 10 lords a-leaping') ['12', '11', '10'] \end{verbatim} \method{findall()} has to create the entire list before it can be returned as the result. In Python 2.2, the \method{finditer()} method is also available, returning a sequence of \class{MatchObject} instances as an iterator. \begin{verbatim} >>> iterator = p.finditer('12 drummers drumming, 11 ... 10 ...') >>> iterator <callable-iterator object at 0x401833ac> >>> for match in iterator: ... print match.span() ... (0, 2) (22, 24) (29, 31) \end{verbatim} \subsection{Module-Level Functions} You don't have to produce a \class{RegexObject} and call its methods; the \module{re} module also provides top-level functions called \function{match()}, \function{search()}, \function{sub()}, and so forth. These functions take the same arguments as the corresponding \class{RegexObject} method, with the RE string added as the first argument, and still return either \code{None} or a \class{MatchObject} instance.