Added AMK's first cut at docs for re.py

5 files changed, 927 insertions, 1 deletions

diff --git a/Doc/Makefile b/Doc/Makefile
index 7fc78ae..58bb93e 100644
--- a/Doc/Makefile
+++ b/Doc/Makefile
@@ -112,7 +112,7 @@ LIBFILES = lib.tex \
     libuser.tex libanydbm.tex librandom.tex libsite.tex libwhichdb.tex \
     libbase64.tex libfnmatch.tex libquopri.tex libzlib.tex libsocksvr.tex \
     libmailbox.tex libcommands.tex libcmath.tex libni.tex libgzip.tex \
-    libpprint.tex libcode.tex libmimify.tex
+    libpprint.tex libcode.tex libmimify.tex libre.tex
 
 # Library document
 lib.dvi: $(LIBFILES)
diff --git a/Doc/lib.tex b/Doc/lib.tex
index 2980d64..442de74 100644
--- a/Doc/lib.tex
+++ b/Doc/lib.tex
@@ -97,6 +97,7 @@ to Python and how to embed it in other applications.
 \input{libstring}
 \input{libregex}
 \input{libregsub}
+\input{libre}
 \input{libstruct}
 \input{libstrio}
 \input{libsoundex}
diff --git a/Doc/lib/lib.tex b/Doc/lib/lib.tex
index 2980d64..442de74 100644
--- a/Doc/lib/lib.tex
+++ b/Doc/lib/lib.tex
@@ -97,6 +97,7 @@ to Python and how to embed it in other applications.
 \input{libstring}
 \input{libregex}
 \input{libregsub}
+\input{libre}
 \input{libstruct}
 \input{libstrio}
 \input{libsoundex}
diff --git a/Doc/lib/libre.tex b/Doc/lib/libre.tex
new file mode 100644
index 0000000..975bf38
--- /dev/null
+++ b/Doc/lib/libre.tex
@@ -0,0 +1,462 @@
+\section{Built-in Module \sectcode{re}}
+\label{module-re}
+
+\bimodindex{re}
+
+% XXX Remove before 1.5final release.
+{\large\bf The \code{re} module is still in the process of being
+developed, and more features will be added in future 1.5 alphas and
+betas.  This documentation is also preliminary and incomplete.  If you
+find a bug or documentation error, or just find something unclear,
+please send a message to
+\code{string-sig@python.org}, and we'll fix it.}
+
+This module provides regular expression matching operations similar to
+those found in Perl.  It's 8-bit
+clean: both patterns and strings may contain null bytes and characters
+whose high bit is set.  It is always available.  
+
+Regular expressions use the backslash character (\code{\e}) to
+indicate special forms or to allow special characters to be used
+without invoking their special meaning.  This collides with Python's
+usage of the same character for the same purpose in string literals;
+for example, to match a literal backslash, one might have to write
+\code{\e\e\e\e} as the pattern string, because the regular expression must be \code{\e\e}, and each backslash must be expressed as \code{\e\e} inside a regular Python string literal.
+
+The solution is to use Python's raw string notation for regular
+expression patterns; backslashes are not handled in any special way in
+a string literal prefixed with 'r'.  So \code{r"\e n"} is a two
+character string containing a backslash and the letter 'n', while
+\code{"\e n"} is a one-character string containing a newline.  Usually
+patterns will be expressed in Python code using this raw string notation.
+
+% XXX Can the following section be dropped, or should it be boiled down?
+
+%\strong{Please note:} There is a little-known fact about Python string
+%literals which means that you don't usually have to worry about
+%doubling backslashes, even though they are used to escape special
+%characters in string literals as well as in regular expressions.  This
+%is because Python doesn't remove backslashes from string literals if
+%they are followed by an unrecognized escape character.
+%\emph{However}, if you want to include a literal \dfn{backslash} in a
+%regular expression represented as a string literal, you have to
+%\emph{quadruple} it or enclose it in a singleton character class.
+%E.g.\  to extract \LaTeX\ \code{\e section\{{\rm
+%\ldots}\}} headers from a document, you can use this pattern:
+%\code{'[\e ] section\{\e (.*\e )\}'}.  \emph{Another exception:}
+%the escape sequence \code{\e b} is significant in string literals
+%(where it means the ASCII bell character) as well as in Emacs regular
+%expressions (where it stands for a word boundary), so in order to
+%search for a word boundary, you should use the pattern \code{'\e \e b'}.
+%Similarly, a backslash followed by a digit 0-7 should be doubled to
+%avoid interpretation as an octal escape.
+
+\subsection{Regular Expressions}
+
+A regular expression (or RE) specifies a set of strings that matches
+it; the functions in this module let you check if a particular string
+matches a given regular expression (or if a given regular expression
+matches a particular string, which comes down to the same thing).
+
+Regular expressions can be concatenated to form new regular
+expressions; if \emph{A} and \emph{B} are both regular expressions,
+then \emph{AB} is also an regular expression.  If a string \emph{p}
+matches A and another string \emph{q} matches B, the string \emph{pq}
+will match AB.  Thus, complex expressions can easily be constructed
+from simpler primitive expressions like the ones described here.  For
+details of the theory and implementation of regular expressions,
+consult the Friedl book referenced below, or almost any textbook about
+compiler construction.
+
+A brief explanation of the format of regular expressions follows.  For
+further information and a gentler presentation, consult XXX somewhere.
+
+Regular expressions can contain both special and ordinary characters.
+Most ordinary characters, like '\code{A}', '\code{a}', or '\code{0}',
+are the simplest regular expressions; they simply match themselves.  
+You can concatenate ordinary characters, so '\code{last}' matches the
+characters 'last'.  (In the rest of this section, we'll write RE's in
+\code{this special font}, usually without quotes, and strings to be
+matched 'in single quotes'.)
+
+Some characters, like \code{|} or \code{(}, are special.  Special
+characters either stand for classes of ordinary characters, or affect
+how the regular expressions around them are interpreted.
+
+The special characters are:
+\begin{itemize}
+\item[\code{.}] (Dot.)  In the default mode, this matches any
+character except a newline.  If the \code{DOTALL} flag has been
+specified, this matches any character including a newline.
+\item[\code{\^}] (Caret.)  Matches the start of the string, and in
+\code{MULTILINE} mode also immediately after each newline.
+\item[\code{\$}] Matches the end of the string.  
+\code{foo} matches both 'foo' and 'foobar', while the regular
+expression '\code{foo\$}' matches only 'foo'.
+%
+\item[\code{*}] Causes the resulting RE to
+match 0 or more repetitions of the preceding RE, as many repetitions
+as are possible.  \code{ab*} will
+match 'a', 'ab', or 'a' followed by any number of 'b's.
+%
+\item[\code{+}] Causes the
+resulting RE to match 1 or more repetitions of the preceding RE.
+\code{ab+} will match 'a' followed by any non-zero number of 'b's; it
+will not match just 'a'.
+%
+\item[\code{?}] Causes the resulting RE to
+match 0 or 1 repetitions of the preceding RE.  \code{ab?} will
+match either 'a' or 'ab'.
+\item[\code{*?}, \code{+?}, \code{??}] The \code{*}, \code{+}, and
+\code{?} qualifiers are all \dfn{greedy}; they match as much text as
+possible.  Sometimes this behaviour isn't desired; if the RE
+\code{<.*>} is matched against \code{<H1>title</H1>}, it will match the
+entire string, and not just \code{<H1>}.
+Adding \code{?} after the qualifier makes it perform the match in
+\dfn{non-greedy} or \dfn{minimal} fashion; as few characters as
+possible will be matched.  Using \code{.*?} in the previous
+expression, it will match only \code{<H1>}.
+%
+\item[\code{\e}] Either escapes special characters (permitting you to match
+characters like '*?+\&\$'), or signals a special sequence; special
+sequences are discussed below.  
+
+If you're not using a raw string to
+express the pattern, remember that Python also uses the
+backslash as an escape sequence in string literals; if the escape
+sequence isn't recognized by Python's parser, the backslash and
+subsequent character are included in the resulting string.  However,
+if Python would recognize the resulting sequence, the backslash should
+be repeated twice.   This is complicated and hard to understand, so
+it's highly recommended that you use raw strings.
+%
+\item[\code{[]}] Used to indicate a set of characters.  Characters can
+be listed individually, or a range is indicated by giving two
+characters and separating them by a '-'.  Special characters are not
+active inside sets.  For example, \code{[akm\$]} will match any of the
+characters 'a', 'k', 'm', or '\$'; \code{[a-z]} will match any
+lowercase letter and \code{[a-zA-Z0-9]} matches any letter or digit.
+Character classes of the form \code{\e \var{X}} defined below are also acceptable.
+If you want to include a \code{]} or a \code{-} inside a
+set, precede it with a backslash. 
+
+Characters \emph{not} within a range can be matched by including a
+\code{\^} as the first character of the set; \code{\^} elsewhere will
+simply match the '\code{\^}' character.  
+%
+\item[\code{|}]\code{A|B}, where A and B can be arbitrary REs,
+creates a regular expression that will match either A or B.  This can
+be used inside groups (see below) as well.  To match a literal '|', 
+use \code{\e|}, or enclose it inside a character class, like \code{[|]}.
+%
+\item[\code{( ... )}] Matches whatever regular expression is inside the parentheses, and indicates the start and end of a group; the
+contents of a group can be retrieved after a match has been performed,
+and can be matched later in the string with the
+\code{\e \var{number}} special sequence, described below.  To match the
+literals '(' or ')', 
+use \code{\e(} or \code{\e)}, or enclose them inside a character
+class: \code{[(] [)]}.
+%
+\item[\code{(?:...)}] A non-grouping version of regular parentheses.
+Matches whatever's inside the parentheses, but the text matched by the
+group \emph{cannot} be retrieved after performing a match or
+referenced later in the pattern. 
+%
+\item[\code{(?P<\var{name}>...)}] Similar to regular parentheses, but
+the text matched by the group is accessible via the symbolic group
+name \var{name}.  Group names must be valid Python identifiers.  A
+symbolic group is also a numbered group, just as if the group were not
+named.  So the group named 'id' in the example above can also be
+referenced as the numbered group 1.
+
+For example, if the pattern string is
+\code{r'(?P<id>[a-zA-Z_]\e w*)'}, the group can be referenced by its
+name in arguments to methods of match objects, such as \code{m.group('id')}
+or \code{m.end('id')}, and also by name in pattern text (e.g. \code{(?P=id)}) and
+replacement text (e.g. \code{\e g<id>}).
+%
+\item[\code{(?\#...)}] A comment; the contents of the parentheses are simply ignored.
+%
+\item[\code{(?=...)}] Matches if \code{RE} matches next.  This is not
+implemented as of  Python 1.5a3.
+%
+\item[\code{(?!...)}] Matches if \code{...} doesn't match next.  This is not
+implemented as of Python 1.5a3.
+\end{itemize}
+
+The special sequences consist of '\code{\e}' and a character from the
+list below.  If the ordinary character is not on the list, then the
+resulting RE will match the second character.  For example,
+\code{\e\$} matches the character '\$'.  Ones where the backslash
+should be doubled are indicated.
+
+\begin{itemize}
+
+%
+\item[\code{\e \var{number}}] Matches the contents of the group of the
+same number.  For example, \code{(.+) \e 1} matches 'the the' or '55
+55', but not 'the end' (note the space after the group).  This special
+sequence can only be used to match one of the first 99 groups.  If the
+first digit of \var{number} is 0, or \var{number} is 3 octal digits
+long, it will not interpreted as a group match, but as the character
+with octal value \var{number}.
+%
+\item[\code{\e A}] Matches only at the start of the string.
+%
+\item[\code{\e b}] Matches the empty string, but only at the
+beginning or end of a word.  A word is defined as a sequence of
+alphanumeric characters, so the end of a word is indicated by
+whitespace or a non-alphanumeric character.
+%
+\item[\code{\e B}] Matches the empty string, but only when it is \emph{not} at the
+beginning or end of a word.
+%
+\item[\code{\e d}]Matches any decimal digit; this is
+equivalent to the set \code{[0-9]}.
+%
+\item[\code{\e D}]Matches any non-digit character; this is
+equivalent to the set \code{[\^0-9]}.
+%
+\item[\code{\e s}]Matches any whitespace character; this is
+equivalent to the set \code{[ \e t\e n\e r\e f\e v]}.
+%
+\item[\code{\e S}]Matches any non-whitespace character; this is
+equivalent to the set \code{[\^ \e t\e n\e r\e f\e v]}.
+%
+\item[\code{\e w}]Matches any alphanumeric character; this is
+equivalent to the set \code{[a-zA-Z0-9_]}.
+%
+\item[\code{\e W}] Matches any non-alphanumeric character; this is
+equivalent to the set \code{[\^a-zA-Z0-9_]}.
+
+\item[\code{\e Z}]Matches only at the end of the string.
+%
+
+\item[\code{\e \e}] Matches a literal backslash.
+
+\end{itemize}
+
+\subsection{Module Contents}
+
+The module defines the following functions and constants, and an exception:
+
+\renewcommand{\indexsubitem}{(in module re)}
+
+\begin{funcdesc}{compile}{pattern\optional{\, flags}}
+  Compile a regular expression pattern into a regular expression
+  object, which can be used for matching using its \code{match} and
+  \code{search} methods, described below.  
+
+  The sequence
+%
+\bcode\begin{verbatim}
+prog = re.compile(pat)
+result = prog.match(str)
+\end{verbatim}\ecode
+%
+is equivalent to
+%
+\bcode\begin{verbatim}
+result = re.match(pat, str)
+\end{verbatim}\ecode
+%
+but the version using \code{compile()} is more efficient when multiple
+regular expressions are used concurrently in a single program.  
+%(The compiled version of the last pattern passed to \code{regex.match()} or
+%\code{regex.search()} is cached, so programs that use only a single
+%regular expression at a time needn't worry about compiling regular
+%expressions.)
+\end{funcdesc}
+
+\begin{funcdesc}{escape}{string}
+Return \var{string} with all non-alphanumerics backslashed; this is
+useful if you want to match some variable string which may have
+regular expression metacharacters in it.
+\end{funcdesc}
+
+\begin{funcdesc}{match}{pattern\, string\optional{\, flags}}
+  If zero or more characters at the beginning of \var{string} match
+  the regular expression \var{pattern}, return a corresponding
+  \code{Match} object.  Return \code{None} if the string does not
+  match the pattern; note that this is different from a zero-length
+  match.
+\end{funcdesc}
+
+\begin{funcdesc}{search}{pattern\, string\optional{\, flags}}
+  Scan through \var{string} looking for a location where the regular
+  expression \var{pattern} produces a match.  Return \code{None} if no
+  position in the string matches the pattern; note that this is
+  different from finding a zero-length match at some point in the string.
+\end{funcdesc}
+
+\begin{funcdesc}{split}{pattern\, string\, \optional{, maxsplit=0}}
+  Split \var{string} by the occurrences of \var{pattern}.  If
+  capturing parentheses are used in pattern, then occurrences of
+  patterns or subpatterns are also returned.
+%
+\bcode\begin{verbatim}
+>>> re.split('[\W]+', 'Words, words, words.')
+['Words', 'words', 'words', '']
+>>> re.split('([\W]+)', 'Words, words, words.')
+['Words', ', ', 'words', ', ', 'words', '.', '']
+\end{verbatim}\ecode
+%
+  This function combines and extends the functionality of
+  \code{regex.split()} and \code{regex.splitx()}.
+\end{funcdesc}
+
+\begin{funcdesc}{sub}{pattern\, repl\, string\optional{, count=0}}
+Return the string obtained by replacing the leftmost non-overlapping
+occurrences of \var{pattern} in \var{string} by the replacement
+\var{repl}, which can be a string or the function that returns a string.  If the pattern isn't found, \var{string} is returned unchanged. The
+pattern may be a string or a regexp object; if you need to specify
+regular expression flags, you must use a regexp object, or use
+embedded modifiers in a pattern string; e.g.
+%
+\bcode\begin{verbatim}
+sub("(?i)b+", "x", "bbbb BBBB") returns 'x x'.
+\end{verbatim}\ecode
+%
+The optional argument \var{count} is the maximum number of pattern
+occurrences to be replaced; count must be a non-negative integer, and
+the default value of 0 means to replace all occurrences.
+
+Empty matches for the pattern are replaced only when not adjacent to a
+previous match, so \code{sub('x*', '-', 'abc')} returns '-a-b-c-'.
+\end{funcdesc}
+
+\begin{funcdesc}{subn}{pattern\, repl\, string\optional{, count=0}}
+Perform the same operation as \code{sub()}, but return a tuple
+\code{(new_string, number_of_subs_made)}.
+\end{funcdesc}
+
+\begin{excdesc}{error}
+  Exception raised when a string passed to one of the functions here
+  is not a valid regular expression (e.g., unmatched parentheses) or
+  when some other error occurs during compilation or matching.  (It is
+  never an error if a string contains no match for a pattern.)
+\end{excdesc}
+
+\subsection{Regular Expression Objects}
+Compiled regular expression objects support the following methods and
+attributes:
+
+\renewcommand{\indexsubitem}{(regex method)}
+\begin{funcdesc}{match}{string\optional{\, pos}}
+  Return how many characters at the beginning of \var{string} match
+  the compiled regular expression.  Return \code{-1} if the string
+  does not match the pattern (this is different from a zero-length
+  match!).
+  
+  The optional second parameter \var{pos} gives an index in the string
+  where the search is to start; it defaults to \code{0}.  This is not
+  completely equivalent to slicing the string; the \code{'\^'} pattern
+  character matches at the real begin of the string and at positions
+  just after a newline, not necessarily at the index where the search
+  is to start.
+\end{funcdesc}
+
+\begin{funcdesc}{search}{string\optional{\, pos}}
+  Return the first position in \var{string} that matches the regular
+  expression \code{pattern}.  Return \code{-1} if no position in the
+  string matches the pattern (this is different from a zero-length
+  match anywhere!).
+  
+  The optional second parameter has the same meaning as for the
+  \code{match} method.
+\end{funcdesc}
+
+\begin{funcdesc}{split}{string\, \optional{, maxsplit=0}}
+Identical to the \code{split} function, using the compiled pattern.
+\end{funcdesc}
+
+\begin{funcdesc}{sub}{repl\, string\optional{, count=0}}
+Identical to the \code{sub} function, using the compiled pattern.
+\end{funcdesc}
+
+\begin{funcdesc}{subn}{repl\, string\optional{, count=0}}
+Identical to the \code{subn} function, using the compiled pattern.
+\end{funcdesc}
+
+\renewcommand{\indexsubitem}{(regex attribute)}
+
+\begin{datadesc}{flags}
+The flags argument used when the regex object was compiled, or 0 if no
+flags were provided.
+\end{datadesc}
+
+\begin{datadesc}{groupindex}
+A dictionary mapping any symbolic group names (defined by 
+\code{?P<\var{id}>}) to group numbers.  The dictionary is empty if no
+symbolic groups were used in the pattern.
+\end{datadesc}
+
+\begin{datadesc}{pattern}
+The pattern string from which the regex object was compiled.
+\end{datadesc}
+
+\subsection{Match Objects}
+Match objects support the following methods and attributes:
+
+\begin{funcdesc}{span}{group}
+Return the 2-tuple \code{(start(\var{group}), end(\var{group}))}.
+Note that if \var{group} did not contribute to the match, this is \code{(None,
+None)}.
+\end{funcdesc}
+
+\begin{funcdesc}{start}{group}
+\end{funcdesc}
+
+\begin{funcdesc}{end}{group}
+Return the indices of the start and end of the substring matched by
+\var{group}.  Return \code{None} if \var{group} exists but did not contribute to
+the match.  Note that for a match object \code{m}, and a group \code{g}
+that did contribute to the match, the substring matched by group \code{g} is
+\bcode\begin{verbatim}
+    m.string[m.start(g):m.end(g)]
+\end{verbatim}\ecode
+%
+Note too that \code{m.start(\var{group})} will equal
+\code{m.end(\var{group})} if \var{group} matched a null string.  For example,
+after \code{m = re.search('b(c?)', 'cba')}, \code{m.start(0)} is 1,
+\code{m.end(0)} is 2, \code{m.start(1)} and \code{m.end(1)} are both
+2, and \code{m.start(2)} raises an 
+\code{IndexError} exception.
+\end{funcdesc}
+
+\begin{funcdesc}{group}{\optional{g1, g2, ...})}
+This method is only valid when the last call to the \code{match}
+or \code{search} method found a match.  It returns one or more
+groups of the match.  If there is a single \var{index} argument,
+the result is a single string; if there are multiple arguments, the
+result is a tuple with one item per argument.  If the \var{index} is
+zero, the corresponding return value is the entire matching string; if
+it is in the inclusive range [1..99], it is the string matching the
+the corresponding parenthesized group (using the default syntax,
+groups are parenthesized using \code{\e (} and \code{\e )}).  If no
+such group exists, the corresponding result is \code{None}.
+
+If the regular expression was compiled by \code{symcomp} instead of
+\code{compile}, the \var{index} arguments may also be strings
+identifying groups by their group name.
+\end{funcdesc}
+
+\begin{datadesc}{pos}
+The index at which the search or match began.
+\end{datadesc}
+
+\begin{datadesc}{re}
+The regular expression object whose match() or search() method
+produced this match object. 
+\end{datadesc}
+
+\begin{datadesc}{string}
+The string passed to \code{match()} or \code{search()}.
+\end{datadesc}
+
+
+
+\begin{seealso}
+\seetext Jeffrey Friedl, \emph{Mastering Regular Expressions}.
+\end{seealso}
+
diff --git a/Doc/libre.tex b/Doc/libre.tex
new file mode 100644
index 0000000..975bf38
--- /dev/null
+++ b/Doc/libre.tex
@@ -0,0 +1,462 @@
+\section{Built-in Module \sectcode{re}}
+\label{module-re}
+
+\bimodindex{re}
+
+% XXX Remove before 1.5final release.
+{\large\bf The \code{re} module is still in the process of being
+developed, and more features will be added in future 1.5 alphas and
+betas.  This documentation is also preliminary and incomplete.  If you
+find a bug or documentation error, or just find something unclear,
+please send a message to
+\code{string-sig@python.org}, and we'll fix it.}
+
+This module provides regular expression matching operations similar to
+those found in Perl.  It's 8-bit
+clean: both patterns and strings may contain null bytes and characters
+whose high bit is set.  It is always available.  
+
+Regular expressions use the backslash character (\code{\e}) to
+indicate special forms or to allow special characters to be used
+without invoking their special meaning.  This collides with Python's
+usage of the same character for the same purpose in string literals;
+for example, to match a literal backslash, one might have to write
+\code{\e\e\e\e} as the pattern string, because the regular expression must be \code{\e\e}, and each backslash must be expressed as \code{\e\e} inside a regular Python string literal.
+
+The solution is to use Python's raw string notation for regular
+expression patterns; backslashes are not handled in any special way in
+a string literal prefixed with 'r'.  So \code{r"\e n"} is a two
+character string containing a backslash and the letter 'n', while
+\code{"\e n"} is a one-character string containing a newline.  Usually
+patterns will be expressed in Python code using this raw string notation.
+
+% XXX Can the following section be dropped, or should it be boiled down?
+
+%\strong{Please note:} There is a little-known fact about Python string
+%literals which means that you don't usually have to worry about
+%doubling backslashes, even though they are used to escape special
+%characters in string literals as well as in regular expressions.  This
+%is because Python doesn't remove backslashes from string literals if
+%they are followed by an unrecognized escape character.
+%\emph{However}, if you want to include a literal \dfn{backslash} in a
+%regular expression represented as a string literal, you have to
+%\emph{quadruple} it or enclose it in a singleton character class.
+%E.g.\  to extract \LaTeX\ \code{\e section\{{\rm
+%\ldots}\}} headers from a document, you can use this pattern:
+%\code{'[\e ] section\{\e (.*\e )\}'}.  \emph{Another exception:}
+%the escape sequence \code{\e b} is significant in string literals
+%(where it means the ASCII bell character) as well as in Emacs regular
+%expressions (where it stands for a word boundary), so in order to
+%search for a word boundary, you should use the pattern \code{'\e \e b'}.
+%Similarly, a backslash followed by a digit 0-7 should be doubled to
+%avoid interpretation as an octal escape.
+
+\subsection{Regular Expressions}
+
+A regular expression (or RE) specifies a set of strings that matches
+it; the functions in this module let you check if a particular string
+matches a given regular expression (or if a given regular expression
+matches a particular string, which comes down to the same thing).
+
+Regular expressions can be concatenated to form new regular
+expressions; if \emph{A} and \emph{B} are both regular expressions,
+then \emph{AB} is also an regular expression.  If a string \emph{p}
+matches A and another string \emph{q} matches B, the string \emph{pq}
+will match AB.  Thus, complex expressions can easily be constructed
+from simpler primitive expressions like the ones described here.  For
+details of the theory and implementation of regular expressions,
+consult the Friedl book referenced below, or almost any textbook about
+compiler construction.
+
+A brief explanation of the format of regular expressions follows.  For
+further information and a gentler presentation, consult XXX somewhere.
+
+Regular expressions can contain both special and ordinary characters.
+Most ordinary characters, like '\code{A}', '\code{a}', or '\code{0}',
+are the simplest regular expressions; they simply match themselves.  
+You can concatenate ordinary characters, so '\code{last}' matches the
+characters 'last'.  (In the rest of this section, we'll write RE's in
+\code{this special font}, usually without quotes, and strings to be
+matched 'in single quotes'.)
+
+Some characters, like \code{|} or \code{(}, are special.  Special
+characters either stand for classes of ordinary characters, or affect
+how the regular expressions around them are interpreted.
+
+The special characters are:
+\begin{itemize}
+\item[\code{.}] (Dot.)  In the default mode, this matches any
+character except a newline.  If the \code{DOTALL} flag has been
+specified, this matches any character including a newline.
+\item[\code{\^}] (Caret.)  Matches the start of the string, and in
+\code{MULTILINE} mode also immediately after each newline.
+\item[\code{\$}] Matches the end of the string.  
+\code{foo} matches both 'foo' and 'foobar', while the regular
+expression '\code{foo\$}' matches only 'foo'.
+%
+\item[\code{*}] Causes the resulting RE to
+match 0 or more repetitions of the preceding RE, as many repetitions
+as are possible.  \code{ab*} will
+match 'a', 'ab', or 'a' followed by any number of 'b's.
+%
+\item[\code{+}] Causes the
+resulting RE to match 1 or more repetitions of the preceding RE.
+\code{ab+} will match 'a' followed by any non-zero number of 'b's; it
+will not match just 'a'.
+%
+\item[\code{?}] Causes the resulting RE to
+match 0 or 1 repetitions of the preceding RE.  \code{ab?} will
+match either 'a' or 'ab'.
+\item[\code{*?}, \code{+?}, \code{??}] The \code{*}, \code{+}, and
+\code{?} qualifiers are all \dfn{greedy}; they match as much text as
+possible.  Sometimes this behaviour isn't desired; if the RE
+\code{<.*>} is matched against \code{<H1>title</H1>}, it will match the
+entire string, and not just \code{<H1>}.
+Adding \code{?} after the qualifier makes it perform the match in
+\dfn{non-greedy} or \dfn{minimal} fashion; as few characters as
+possible will be matched.  Using \code{.*?} in the previous
+expression, it will match only \code{<H1>}.
+%
+\item[\code{\e}] Either escapes special characters (permitting you to match
+characters like '*?+\&\$'), or signals a special sequence; special
+sequences are discussed below.  
+
+If you're not using a raw string to
+express the pattern, remember that Python also uses the
+backslash as an escape sequence in string literals; if the escape
+sequence isn't recognized by Python's parser, the backslash and
+subsequent character are included in the resulting string.  However,
+if Python would recognize the resulting sequence, the backslash should
+be repeated twice.   This is complicated and hard to understand, so
+it's highly recommended that you use raw strings.
+%
+\item[\code{[]}] Used to indicate a set of characters.  Characters can
+be listed individually, or a range is indicated by giving two
+characters and separating them by a '-'.  Special characters are not
+active inside sets.  For example, \code{[akm\$]} will match any of the
+characters 'a', 'k', 'm', or '\$'; \code{[a-z]} will match any
+lowercase letter and \code{[a-zA-Z0-9]} matches any letter or digit.
+Character classes of the form \code{\e \var{X}} defined below are also acceptable.
+If you want to include a \code{]} or a \code{-} inside a
+set, precede it with a backslash. 
+
+Characters \emph{not} within a range can be matched by including a
+\code{\^} as the first character of the set; \code{\^} elsewhere will
+simply match the '\code{\^}' character.  
+%
+\item[\code{|}]\code{A|B}, where A and B can be arbitrary REs,
+creates a regular expression that will match either A or B.  This can
+be used inside groups (see below) as well.  To match a literal '|', 
+use \code{\e|}, or enclose it inside a character class, like \code{[|]}.
+%
+\item[\code{( ... )}] Matches whatever regular expression is inside the parentheses, and indicates the start and end of a group; the
+contents of a group can be retrieved after a match has been performed,
+and can be matched later in the string with the
+\code{\e \var{number}} special sequence, described below.  To match the
+literals '(' or ')', 
+use \code{\e(} or \code{\e)}, or enclose them inside a character
+class: \code{[(] [)]}.
+%
+\item[\code{(?:...)}] A non-grouping version of regular parentheses.
+Matches whatever's inside the parentheses, but the text matched by the
+group \emph{cannot} be retrieved after performing a match or
+referenced later in the pattern. 
+%
+\item[\code{(?P<\var{name}>...)}] Similar to regular parentheses, but
+the text matched by the group is accessible via the symbolic group
+name \var{name}.  Group names must be valid Python identifiers.  A
+symbolic group is also a numbered group, just as if the group were not
+named.  So the group named 'id' in the example above can also be
+referenced as the numbered group 1.
+
+For example, if the pattern string is
+\code{r'(?P<id>[a-zA-Z_]\e w*)'}, the group can be referenced by its
+name in arguments to methods of match objects, such as \code{m.group('id')}
+or \code{m.end('id')}, and also by name in pattern text (e.g. \code{(?P=id)}) and
+replacement text (e.g. \code{\e g<id>}).
+%
+\item[\code{(?\#...)}] A comment; the contents of the parentheses are simply ignored.
+%
+\item[\code{(?=...)}] Matches if \code{RE} matches next.  This is not
+implemented as of  Python 1.5a3.
+%
+\item[\code{(?!...)}] Matches if \code{...} doesn't match next.  This is not
+implemented as of Python 1.5a3.
+\end{itemize}
+
+The special sequences consist of '\code{\e}' and a character from the
+list below.  If the ordinary character is not on the list, then the
+resulting RE will match the second character.  For example,
+\code{\e\$} matches the character '\$'.  Ones where the backslash
+should be doubled are indicated.
+
+\begin{itemize}
+
+%
+\item[\code{\e \var{number}}] Matches the contents of the group of the
+same number.  For example, \code{(.+) \e 1} matches 'the the' or '55
+55', but not 'the end' (note the space after the group).  This special
+sequence can only be used to match one of the first 99 groups.  If the
+first digit of \var{number} is 0, or \var{number} is 3 octal digits
+long, it will not interpreted as a group match, but as the character
+with octal value \var{number}.
+%
+\item[\code{\e A}] Matches only at the start of the string.
+%
+\item[\code{\e b}] Matches the empty string, but only at the
+beginning or end of a word.  A word is defined as a sequence of
+alphanumeric characters, so the end of a word is indicated by
+whitespace or a non-alphanumeric character.
+%
+\item[\code{\e B}] Matches the empty string, but only when it is \emph{not} at the
+beginning or end of a word.
+%
+\item[\code{\e d}]Matches any decimal digit; this is
+equivalent to the set \code{[0-9]}.
+%
+\item[\code{\e D}]Matches any non-digit character; this is
+equivalent to the set \code{[\^0-9]}.
+%
+\item[\code{\e s}]Matches any whitespace character; this is
+equivalent to the set \code{[ \e t\e n\e r\e f\e v]}.
+%
+\item[\code{\e S}]Matches any non-whitespace character; this is
+equivalent to the set \code{[\^ \e t\e n\e r\e f\e v]}.
+%
+\item[\code{\e w}]Matches any alphanumeric character; this is
+equivalent to the set \code{[a-zA-Z0-9_]}.
+%
+\item[\code{\e W}] Matches any non-alphanumeric character; this is
+equivalent to the set \code{[\^a-zA-Z0-9_]}.
+
+\item[\code{\e Z}]Matches only at the end of the string.
+%
+
+\item[\code{\e \e}] Matches a literal backslash.
+
+\end{itemize}
+
+\subsection{Module Contents}
+
+The module defines the following functions and constants, and an exception:
+
+\renewcommand{\indexsubitem}{(in module re)}
+
+\begin{funcdesc}{compile}{pattern\optional{\, flags}}
+  Compile a regular expression pattern into a regular expression
+  object, which can be used for matching using its \code{match} and
+  \code{search} methods, described below.  
+
+  The sequence
+%
+\bcode\begin{verbatim}
+prog = re.compile(pat)
+result = prog.match(str)
+\end{verbatim}\ecode
+%
+is equivalent to
+%
+\bcode\begin{verbatim}
+result = re.match(pat, str)
+\end{verbatim}\ecode
+%
+but the version using \code{compile()} is more efficient when multiple
+regular expressions are used concurrently in a single program.  
+%(The compiled version of the last pattern passed to \code{regex.match()} or
+%\code{regex.search()} is cached, so programs that use only a single
+%regular expression at a time needn't worry about compiling regular
+%expressions.)
+\end{funcdesc}
+
+\begin{funcdesc}{escape}{string}
+Return \var{string} with all non-alphanumerics backslashed; this is
+useful if you want to match some variable string which may have
+regular expression metacharacters in it.
+\end{funcdesc}
+
+\begin{funcdesc}{match}{pattern\, string\optional{\, flags}}
+  If zero or more characters at the beginning of \var{string} match
+  the regular expression \var{pattern}, return a corresponding
+  \code{Match} object.  Return \code{None} if the string does not
+  match the pattern; note that this is different from a zero-length
+  match.
+\end{funcdesc}
+
+\begin{funcdesc}{search}{pattern\, string\optional{\, flags}}
+  Scan through \var{string} looking for a location where the regular
+  expression \var{pattern} produces a match.  Return \code{None} if no
+  position in the string matches the pattern; note that this is
+  different from finding a zero-length match at some point in the string.
+\end{funcdesc}
+
+\begin{funcdesc}{split}{pattern\, string\, \optional{, maxsplit=0}}
+  Split \var{string} by the occurrences of \var{pattern}.  If
+  capturing parentheses are used in pattern, then occurrences of
+  patterns or subpatterns are also returned.
+%
+\bcode\begin{verbatim}
+>>> re.split('[\W]+', 'Words, words, words.')
+['Words', 'words', 'words', '']
+>>> re.split('([\W]+)', 'Words, words, words.')
+['Words', ', ', 'words', ', ', 'words', '.', '']
+\end{verbatim}\ecode
+%
+  This function combines and extends the functionality of
+  \code{regex.split()} and \code{regex.splitx()}.
+\end{funcdesc}
+
+\begin{funcdesc}{sub}{pattern\, repl\, string\optional{, count=0}}
+Return the string obtained by replacing the leftmost non-overlapping
+occurrences of \var{pattern} in \var{string} by the replacement
+\var{repl}, which can be a string or the function that returns a string.  If the pattern isn't found, \var{string} is returned unchanged. The
+pattern may be a string or a regexp object; if you need to specify
+regular expression flags, you must use a regexp object, or use
+embedded modifiers in a pattern string; e.g.
+%
+\bcode\begin{verbatim}
+sub("(?i)b+", "x", "bbbb BBBB") returns 'x x'.
+\end{verbatim}\ecode
+%
+The optional argument \var{count} is the maximum number of pattern
+occurrences to be replaced; count must be a non-negative integer, and
+the default value of 0 means to replace all occurrences.
+
+Empty matches for the pattern are replaced only when not adjacent to a
+previous match, so \code{sub('x*', '-', 'abc')} returns '-a-b-c-'.
+\end{funcdesc}
+
+\begin{funcdesc}{subn}{pattern\, repl\, string\optional{, count=0}}
+Perform the same operation as \code{sub()}, but return a tuple
+\code{(new_string, number_of_subs_made)}.
+\end{funcdesc}
+
+\begin{excdesc}{error}
+  Exception raised when a string passed to one of the functions here
+  is not a valid regular expression (e.g., unmatched parentheses) or
+  when some other error occurs during compilation or matching.  (It is
+  never an error if a string contains no match for a pattern.)
+\end{excdesc}
+
+\subsection{Regular Expression Objects}
+Compiled regular expression objects support the following methods and
+attributes:
+
+\renewcommand{\indexsubitem}{(regex method)}
+\begin{funcdesc}{match}{string\optional{\, pos}}
+  Return how many characters at the beginning of \var{string} match
+  the compiled regular expression.  Return \code{-1} if the string
+  does not match the pattern (this is different from a zero-length
+  match!).
+  
+  The optional second parameter \var{pos} gives an index in the string
+  where the search is to start; it defaults to \code{0}.  This is not
+  completely equivalent to slicing the string; the \code{'\^'} pattern
+  character matches at the real begin of the string and at positions
+  just after a newline, not necessarily at the index where the search
+  is to start.
+\end{funcdesc}
+
+\begin{funcdesc}{search}{string\optional{\, pos}}
+  Return the first position in \var{string} that matches the regular
+  expression \code{pattern}.  Return \code{-1} if no position in the
+  string matches the pattern (this is different from a zero-length
+  match anywhere!).
+  
+  The optional second parameter has the same meaning as for the
+  \code{match} method.
+\end{funcdesc}
+
+\begin{funcdesc}{split}{string\, \optional{, maxsplit=0}}
+Identical to the \code{split} function, using the compiled pattern.
+\end{funcdesc}
+
+\begin{funcdesc}{sub}{repl\, string\optional{, count=0}}
+Identical to the \code{sub} function, using the compiled pattern.
+\end{funcdesc}
+
+\begin{funcdesc}{subn}{repl\, string\optional{, count=0}}
+Identical to the \code{subn} function, using the compiled pattern.
+\end{funcdesc}
+
+\renewcommand{\indexsubitem}{(regex attribute)}
+
+\begin{datadesc}{flags}
+The flags argument used when the regex object was compiled, or 0 if no
+flags were provided.
+\end{datadesc}
+
+\begin{datadesc}{groupindex}
+A dictionary mapping any symbolic group names (defined by 
+\code{?P<\var{id}>}) to group numbers.  The dictionary is empty if no
+symbolic groups were used in the pattern.
+\end{datadesc}
+
+\begin{datadesc}{pattern}
+The pattern string from which the regex object was compiled.
+\end{datadesc}
+
+\subsection{Match Objects}
+Match objects support the following methods and attributes:
+
+\begin{funcdesc}{span}{group}
+Return the 2-tuple \code{(start(\var{group}), end(\var{group}))}.
+Note that if \var{group} did not contribute to the match, this is \code{(None,
+None)}.
+\end{funcdesc}
+
+\begin{funcdesc}{start}{group}
+\end{funcdesc}
+
+\begin{funcdesc}{end}{group}
+Return the indices of the start and end of the substring matched by
+\var{group}.  Return \code{None} if \var{group} exists but did not contribute to
+the match.  Note that for a match object \code{m}, and a group \code{g}
+that did contribute to the match, the substring matched by group \code{g} is
+\bcode\begin{verbatim}
+    m.string[m.start(g):m.end(g)]
+\end{verbatim}\ecode
+%
+Note too that \code{m.start(\var{group})} will equal
+\code{m.end(\var{group})} if \var{group} matched a null string.  For example,
+after \code{m = re.search('b(c?)', 'cba')}, \code{m.start(0)} is 1,
+\code{m.end(0)} is 2, \code{m.start(1)} and \code{m.end(1)} are both
+2, and \code{m.start(2)} raises an 
+\code{IndexError} exception.
+\end{funcdesc}
+
+\begin{funcdesc}{group}{\optional{g1, g2, ...})}
+This method is only valid when the last call to the \code{match}
+or \code{search} method found a match.  It returns one or more
+groups of the match.  If there is a single \var{index} argument,
+the result is a single string; if there are multiple arguments, the
+result is a tuple with one item per argument.  If the \var{index} is
+zero, the corresponding return value is the entire matching string; if
+it is in the inclusive range [1..99], it is the string matching the
+the corresponding parenthesized group (using the default syntax,
+groups are parenthesized using \code{\e (} and \code{\e )}).  If no
+such group exists, the corresponding result is \code{None}.
+
+If the regular expression was compiled by \code{symcomp} instead of
+\code{compile}, the \var{index} arguments may also be strings
+identifying groups by their group name.
+\end{funcdesc}
+
+\begin{datadesc}{pos}
+The index at which the search or match began.
+\end{datadesc}
+
+\begin{datadesc}{re}
+The regular expression object whose match() or search() method
+produced this match object. 
+\end{datadesc}
+
+\begin{datadesc}{string}
+The string passed to \code{match()} or \code{search()}.
+\end{datadesc}
+
+
+
+\begin{seealso}
+\seetext Jeffrey Friedl, \emph{Mastering Regular Expressions}.
+\end{seealso}
+