Understanding Computation (14 page)

• hello
, which only matches the string
  'hello'


• hello|goodbye
, which matches the strings
  'hello'
and
  'goodbye'


• (hello)*
, which matches the strings
  'hello'
,
  'hellohello'
,
  'hellohellohello'
, and so on, as well as the empty
  string
  

In this chapter, we’ll always think of a regular expression as matching an
entire
string. Real-world implementations of regular expressions
typically use them for matching
parts
of strings, with extra syntax
needed if we want to specify that an entire string should be matched.

For example, our regular expression
hello|goodbye
would be written in Ruby as
/\A(hello|goodbye)\z/
to make sure
that any match is anchored to the beginning (
\A
) and end (
\z
) of the string.

Let’s be precise
about what we mean by “regular expression.” To get us off
the ground, here are two kinds of extremely simple regular expression
that are not built out of anything simpler:

Once we have these simple kinds of pattern, there are three ways
we can combine them to build more complex expressions:

To implement this syntax in Ruby, we can define a class for each kind of regular
expression and use instances of those classes to represent the abstract syntax tree of any
regular expression, just as we did for
Simple
expressions
in
Chapter 2
:

module
Pattern
def
bracket
(
outer_precedence
)
if
precedence
<
outer_precedence
'('
+
to_s
+
')'
else
to_s
end
end
def
inspect
"/
#{
self
}
/"
end
end
class
Empty
include
Pattern
def
to_s
''
end
def
precedence
3
end
end
class
Literal
<
Struct
.
new
(
:character
)
include
Pattern
def
to_s
character
end
def
precedence
3
end
end
class
Concatenate
<
Struct
.
new
(
:first
,
:second
)
include
Pattern
def
to_s
[
first
,
second
].
map
{
|
pattern
|
pattern
.
bracket
(
precedence
)
}
.
join
end
def
precedence
1
end
end
class
Choose
<
Struct
.
new
(
:first
,
:second
)
include
Pattern
def
to_s
[
first
,
second
].
map
{
|
pattern
|
pattern
.
bracket
(
precedence
)
}
.
join
(
'|'
)
end
def
precedence
0
end
end
class
Repeat
<
Struct
.
new
(
:pattern
)
include
Pattern
def
to_s
pattern
.
bracket
(
precedence
)
+
'*'
end
def
precedence
2
end
end

These classes let us
manually build trees to represent regular
expressions:

>>
pattern
=
Repeat
.
new
(
Choose
.
new
(
Concatenate
.
new
(
Literal
.
new
(
'a'
),
Literal
.
new
(
'b'
)),
Literal
.
new
(
'a'
)
)
)
=> /(ab|a)*/

Of course, in a real implementation, we’d use a parser to build these trees instead of
constructing them by hand; see
Parsing
for instructions
on how to do
this.

Now that we
have a way of representing the syntax of a regular
expression as a tree of Ruby objects, how can we convert that syntax
into an NFA?

We need to decide how instances of each syntax class should be
turned into NFAs. The easiest class to convert is
Empty
, which we should always turn into the
one-state NFA that only accepts the empty string:

Similarly, we should turn any literal, single-character pattern
into the NFA that only accepts the single-character string containing
that character. Here’s the NFA for the pattern
a
:

It’s easy enough to implement
#to_nfa_design
methods for
Empty
and
Literal
to generate these NFAs:

class
Empty
def
to_nfa_design
start_state
=
Object
.
new
accept_states
=
[
start_state
]
rulebook
=
NFARulebook
.
new
(
[]
)
NFADesign
.
new
(
start_state
,
accept_states
,
rulebook
)
end
end
class
Literal
def
to_nfa_design
start_state
=
Object
.
new
accept_state
=
Object
.
new
rule
=
FARule
.
new
(
start_state
,
character
,
accept_state
)
rulebook
=
NFARulebook
.
new
(
[
rule
]
)
NFADesign
.
new
(
start_state
,
[
accept_state
]
,
rulebook
)
end
end

We can check that the
NFAs generated from
Empty
and
Literal
regular expressions accept the strings
we want them to:

>>
nfa_design
=
Empty
.
new
.
to_nfa_design
=> #
>>
nfa_design
.
accepts?
(
''
)
=> true
>>
nfa_design
.
accepts?
(
'a'
)
=> false
>>
nfa_design
=
Literal
.
new
(
'a'
)
.
to_nfa_design
=> #
>>
nfa_design
.
accepts?
(
''
)
=> false
>>
nfa_design
.
accepts?
(
'a'
)
=> true
>>
nfa_design
.
accepts?
(
'b'
)
=> false

There’s an opportunity here to wrap
#to_nfa_design
in a
#matches?
method to give patterns a nicer
interface:

module
Pattern
def
matches?
(
string
)
to_nfa_design
.
accepts?
(
string
)
end
end

This lets us match patterns directly against strings:

>>
Empty
.
new
.
matches?
(
'a'
)
=> false
>>
Literal
.
new
(
'a'
)
.
matches?
(
'a'
)
=> true

Now that we know how to turn simple
Empty
and
Literal
regular expressions into NFAs, we need
a similar setup for
Concatenate
,
Choose
, and
Repeat
.

Let’s begin with
Concatenate
:
if we have two regular expressions that we already know how to turn into
NFAs, how can we build an NFA to represent the concatenation of those
regular expressions? For example, given that we can turn
the single-character regular expressions
a
and
b
into NFAs, how do we turn
ab
into
one?

In the
ab
case, we can connect the two NFAs in
sequence, joining them together with a free move, and keeping the second NFA’s accept
state:

This technique works in other cases too. Any two NFAs can be concatenated by turning
every accept state from the first NFA into a nonaccept state and connecting it to the start
state of the second NFA with a free move. Once the concatenated machine has read a sequence
of inputs that would have put the first NFA into an accept state, it can spontaneously move
into a state corresponding to the start state of the second NFA, and then reach an accept
state by reading a sequence of inputs that the second NFA would have accepted.

So, the raw ingredients for the combined machine are:

We can turn this idea into an implementation of
Concatenate#to_nfa_design
:

class
Concatenate
def
to_nfa_design
first_nfa_design
=
first
.
to_nfa_design
second_nfa_design
=
second
.
to_nfa_design
start_state
=
first_nfa_design
.
start_state
accept_states
=
second_nfa_design
.
accept_states
rules
=
first_nfa_design
.
rulebook
.
rules
+
second_nfa_design
.
rulebook
.
rules
extra_rules
=
first_nfa_design
.
accept_states
.
map
{
|
state
|
FARule
.
new
(
state
,
nil
,
second_nfa_design
.
start_state
)
}
rulebook
=
NFARulebook
.
new
(
rules
+
extra_rules
)
NFADesign
.
new
(
start_state
,
accept_states
,
rulebook
)
end
end

This code first converts the first and second regular expressions
into
NFADesign
s, then combines their
states and rules in the appropriate way to make a new
NFADesign
. It works as expected for the simple
ab
case: