2.1.6 Regular Expression Substitution, Memory, and ELIZA

An important use of regular expressions is in substitutions. For example, the Perl substitution operator s/regexpl/pattern/ allows a string characterized by a regular expression to be replaced by another string:

It is often useful to be able to refer to a particular subpart of the string matching the first pattern. For example, suppose we wanted to put angle brackets around all integers in a text, changing e.g., the 35 boxes to the <35> boxes. We'd like a way to refer back to the integer we've found so that we can easily add the brackets. To do this, we put parentheses ( and ) around the first pattern, and use the number operator \1 in the second pattern to refer back. Here's how it looks:

s/([0-9]+)/\<1>/

The parenthesis and number operators can also be used to specify that a certain string or expression must occur twice in the text. For example, suppose we are looking for the pattern “the Xer they were, the Xer they will be”, where we want to constrain the two X’s to be the same string. We do this by surrounding the first X with the parenthesis operator, and replacing the second X with the number operator \1, as follows:

/the (.*)er they were, the \ler they will be/

Here the \1 will be replaced by whatever string matched the first item in parentheses. So this will match The bigger they were, the bigger they will be but not The bigger they were, the faster they will be.

The number operator can be used with other numbers: if you match two different sets of parenthesis, \2 means whatever matched the second set. For example

/the (.*)er they (.*), the \ler they \2/

will match The bigger they were, the bigger they were but not The bigger they were, the bigger they will be. These numbered memories are called registers (e.g. register 1, register 2, register 3, etc). This memory feature is not part of every regular expression language and is often considered an “extended” feature of regular expressions.

Substitutions using memory are very useful in implementing a simple natural-language understanding program like ELIZA (Weizenbaum, 1966). Recall that ELIZA simulated a Rogerian psychologist and could carry on conversations with the user like the following:

User $ _{1} $: Men are all alike.

ELIZA $ _{1} $: IN WHAT WAY

User2: They're always bugging us about something or other.

ELIZA $ _{2} $: CAN YOU THINK OF A SPECIFIC EXAMPLE

User $ _{3} $: Well, my boyfriend made me come here.

ELIZA $ _{3} $: YOUR BOYFRIEND MADE YOU COME HERE

User $ _{4} $: He says I'm depressed much of the time.

ELIZA $ _{4} $: I AM SORRY TO HEAR YOU ARE DEPRESSED.

Eliza worked by having a cascade of regular expression substitutions that each matched some part of the input lines and changed them. The first substitutions changed all instances of my to YOUR, and I'm to YOU ARE, and so on. The next set of substitutions looked for relevant patterns in the input and created an appropriate output; here are some examples:

s/.* YOU ARE (depressed|sad) .*/I AM SORRY TO HEAR YOU ARE \1/

s/.* YOU ARE (depressed|sad) .*/WHY DO YOU THINK YOU ARE \1/

s/.* all .*/IN WHAT WAY/

s/.* always .*/CAN YOU THINK OF A SPECIFIC EXAMPLE/

Since multiple substitutions could apply to a given input, substitutions were assigned a rank and were applied in order. Creation of such patterns is addressed in Exercise 2.2.

2.2 FINITE-STATE AUTOMATA

The regular expression is more than just a convenient metalanguage for text searching. First, a regular expression is one way of describing a finite-state automaton (FSA). Finite-state automata are the theoretical foundation of a good deal of the computational work we will describe in this book. Any regular expression can be implemented as a finite-state automaton (except regular expressions that use the memory feature; more on this later). Symmetrically, any finite-state automaton can be described with a regular expression. Second, a regular expression is one way of characterizing a particular kind of formal language called a regular language. Both regular expressions and finite-state automata can be used to describe regular languages. A third equivalent method of characterizing the regular languages, the regular grammar, will be introduced in Ch. 15. The relation among these four theoretical constructions is sketched out in Fig. 2.9.

This section will begin by introducing finite-state automata for some of the regular expressions from the last section, and then suggest how the mapping from regular expressions to automata proceeds in general. Although we begin with their use for implementing regular expressions, FSAs have a wide variety of other uses that we will explore in this chapter and the next.