1   Appendix: Regular Expressions

1.1.1   The Wildcard

The "." symbol is called a wildcard: it matches any single character. For example, the regular expression «s.ng» matches the following English words: sang, sing, song, and sung. Note that «.» will match not only alphabetic characters, but also numeric and whitespace characters. Consequently, «s.ng» will also match non-words such as s3ng.

We can also use the wildcard symbol for counting characters. For instance «....zy» matches six-letter strings that end in zy. The pattern «....berry» finds words like cranberry. In our text from Wall Street Journal below, the pattern «t...» will match the words that and term, and will also match the word sequence to a (since the third "." in the pattern can match the space character):

Paragraph 12 from wsj_0034:
It's probably worth paying a premium for funds that invest in markets
that are partially closed to foreign investors, such as South Korea,
some specialists say.  But some European funds recently have
skyrocketed; Spain Fund has surged to a startling 120% premium.  It has
been targeted by Japanese investors as a good long-term play tied to
1992's European economic integration.  And several new funds that aren't
even fully invested yet have jumped to trade at big premiums.

"I'm very alarmed to see these rich valuations," says Smith Barney's
Mr. Porter.

We can see exactly where a regular expression matches against a string using NLTK's re_show function. Readers are encouraged to use re_show to explore the behavior of regular expressions.

>>> string = """
... It's probably worth paying a premium for funds that invest in markets
... that are partially closed to foreign investors, such as South Korea, ...
... """
>>> nltk.re_show('t...', string)
I{t's }probably wor{th p}aying a premium for funds {that} inves{t in} markets
{that} are par{tial}ly closed {to f}oreign inves{tors}, such as Sou{th K}orea, ...

1.1.2   Optionality and Repeatability

The "?" symbol indicates that the immediately preceding regular expression is optional. The regular expression «colou?r» matches both British and American spellings, colour and color. The expression that precedes the ? may be punctuation, such as an optional hyphen. For instance «e-?mail» matches both e-mail and email.

The "+" symbol indicates that the immediately preceding expression is repeatable, up to an arbitrary number of times. For example, the regular expression «coo+l» matches cool, coool, and so on. This symbol is particularly effective when combined with the . symbol. For example, «f.+f» matches all strings of length greater than two, that begin and end with the letter f (e.g. foolproof). The expression «.+ed» finds strings that potentially have the past-tense -ed suffix.

The "*" symbol indicates that the immediately preceding expression is both optional and repeatable. For example «.*gnt.*» matches all strings that contain gnt.

Occasionally we need to match material that spans a line-break. For example, we may want to strip out the HTML markup from a document. To do this we must delete material between angle brackets. The most obvious expression is: «<.*>». However, this has two problems: it will not match an HTML tag that contains a line-break, and the «.*» will consume as much material as possible (including the > character). To permit matching over a line-break we must use Python's DOTALL flag, and to ensure that the > matches against the first instance of the character we must do non-greedy matching using *?:

>>> text = """one two three <font
...           color="red">four</font> five"""
>>> re.sub(r'<.*?>', ' ', text, re.DOTALL)

1.1.3   Choices

Patterns using the wildcard symbol are very effective, but there are many instances where we want to limit the set of characters that the wildcard can match. In such cases we can use the [] notation, which enumerates the set of characters to be matched - this is called a character class. For example, we can match any English vowel, but no consonant, using «[aeiou]». Note that this pattern can be interpreted as saying "match a or e or ... or u"; that is, the pattern resembles the wildcard in only matching a string of length one; unlike the wildcard, it restricts the characters matched to a specific class (in this case, the vowels). Note that the order of vowels in the regular expression is insignificant, and we would have had the same result with the expression «[uoiea]». As a second example, the expression «p[aeiou]t» matches the words: pat, pet, pit, pot, and put.

We can combine the [] notation with our notation for repeatability. For example, expression «p[aeiou]+t» matches the words listed above, along with: peat, poet, and pout.

Often the choices we want to describe cannot be expressed at the level of individual characters. As discussed in the tagging tutorial, different parts of speech are often tagged using labels from a tagset. In the Brown tagset, for example, singular nouns have the tag NN1, while plural nouns have the tag NN2, while nouns which are unspecified for number (e.g., aircraft) are tagged NN0. So we might use «NN.*» as a pattern which will match any nominal tag. Now, suppose we were processing the output of a tagger to extract string of tokens corresponding to noun phrases, we might want to find all nouns (NN.*), adjectives (JJ.*) and determiners (DT), while excluding all other word types (e.g. verbs VB.*). It is possible, using a single regular expression, to search for this set of candidates using the choice operator "|" as follows: «NN.*|JJ.*|DT». This says: match NN.* or JJ.* or DT.

As another example of multi-character choices, suppose that we wanted to create a program to simplify English prose, replacing rare words (like abode) with a more frequent, synonymous word (like home). In this situation, we need to map from a potentially large set of words to an individual word. We can match the set of words using the choice operator. In the case of the word home, we would want to match the regular expression «dwelling|domicile|abode».

1.2.1   Ranges

Earlier we saw how the [] notation could be used to express a set of choices between individual characters. Instead of listing each character, it is also possible to express a range of characters, using the - operator. For example, «[a-z]» matches any lowercase letter. This allows us to avoid the over-permissive matching we noted above with the pattern «t...». If we were to use the pattern «t[a-z][a-z][a-z]», then we would no longer match the two word sequence to a.

As expected, ranges can be combined with other operators. For example «[A-Z][a-z]*» matches words that have an initial capital letter followed by any number of lowercase letters. The pattern «20[0-4][0-9]» matches year expressions in the range 2000 to 2049.

Ranges can be combined, e.g. «[a-zA-Z]» which matches any lowercase or uppercase letter. The expression «[b-df-hj-np-tv-z]+» matches words consisting only of consonants (e.g. pygmy).

1.2.2   Complementation

We just saw that the character class «[b-df-hj-np-tv-z]+» allows us to match sequences of consonants. However, this expression is quite cumbersome. A better alternative is to say: let's match anything which isn't a vowel. To do this, we need a way of expressing complementation. We do this using the symbol "^" as the first character inside a class expression []. Let's look at an example. The regular expression « [^aeiou] » is just like our earlier character class «[aeiou]», except now the set of vowels is preceded by ^. The expression as a whole is interpreted as matching anything which fails to match «[aeiou]». In other words, it matches all lowercase consonants (plus all uppercase letters and non-alphabetic characters).

As another example, suppose we want to match any string which is enclosed by the HTML tags for boldface, namely <B> and </B>. We might try something like this: «<B>.*</B>». This would successfully match <B>important</B>, but would also match <B>important</B> and <B>urgent</B>, since the «.*» sub-pattern will happily match all the characters from the end of important to the end of urgent. One way of ensuring that we only look at matched pairs of tags would be to use the expression «<B>[^<]*</B>», where the character class matches anything other than a left angle bracket.

Finally, note that character class complementation also works with ranges. Thus «[^a-z]» matches anything other than the lower case alphabetic characters a through z.

1.2.3   Common Special Symbols

So far, we have only looked at patterns which match with the content of character strings. However, it is also useful to be able to refer to formatting properties of texts. Two important symbols in this regard are "^" and "$" which are used to anchor matches to the beginnings or ends of lines in a file.

For example, suppose we wanted to find all the words that occur at the beginning of lines in the WSJ text above. Our first attempt might look like «^[A-Za-z]+». This says: starting at the beginning of a line, look for one or more alphabetic characters (upper or lower case), followed by a space. This will match the words that, some, been, and even. However, it fails to match It's, since ' isn't an alphabetic character. A second attempt might be «^[^ ]+», which says to match any string starting at the beginning of a line, followed by one or more characters which are not the space character, followed by a space. This matches all the previous words, together with It's, skyrocketed, 1992s, I'm and "Mr.. As a second example, «[a-z]*s$» will match words ending in s that occur at the end of a line. Finally, consider the pattern «^$»; this matches strings where no character occurs between the beginning and the end of a line - in other words, empty lines!

As we have seen, special characters like ".", "*", "+" and "$" give us powerful means to generalize over character strings. But suppose we wanted to match against a string which itself contains one or more special characters? An example would be the arithmetic statement $5.00 * ($3.05 + $0.85). In this case, we need to resort to the so-called escape character "\" ("backslash"). For example, to match a dollar amount, we might use «\$[1-9][0-9]*\.[0-9][0-9]». The same goes for matching other special characters.

Table 1.1

1.3.1   Exercises

2. Pig Latin is a simple transliteration of English: words starting with a vowel have way appended (e.g. is becomes isway); words beginning with a consonant have all consonants up to the first vowel moved to the end of the word, and then ay is appended (e.g. start becomes artstay).
   1. Write a program to convert English text to Pig Latin.
   2. Extend the program to convert text, instead of individual words.
   3. Extend it further to preserve capitalization, to keep qu together (i.e. so that quiet becomes ietquay), and to detect when y is used as a consonant (e.g. yellow) vs a vowel (e.g. style).
3. An interesting challenge for tokenization is words that have been split across a line-break. E.g. if long-term is split, then we have the string long-\nterm.
   1. Write a regular expression that identifies words that are hyphenated at a line-break. The expression will need to include the \n character.
   2. Use re.sub() to remove the \n character from these words.
4. Write a utility function that takes a URL as its argument, and returns the contents of the URL, with all HTML markup removed. Use urllib.urlopen to access the contents of the URL, e.g. raw_contents = urllib.urlopen('http://nltk.org/').read().
5. Write a program to guess the number of syllables from the orthographic representation of words (e.g. English text).
6. Download some text from a language that has vowel harmony (e.g. Hungarian), extract the vowel sequences of words, and create a vowel bigram table.
7. Obtain a pronunciation lexicon, and try generating nonsense rhymes.