Understanding Computation (15 page)

>>
pattern
=
Concatenate
.
new
(
Literal
.
new
(
'a'
),
Literal
.
new
(
'b'
))
=> /ab/
>>
pattern
.
matches?
(
'a'
)
=> false
>>
pattern
.
matches?
(
'ab'
)
=> true
>>
pattern
.
matches?
(
'abc'
)
=> false

This conversion process is recursive—
Concatenate#to_nfa_design
calls
#to_nfa_design
on other objects—so it also
works for more deeply nested cases like the regular expression
abc
, which contains two concatenations
(
a
concatenated with
b
concatenated with
c
):

>>
pattern
=
Concatenate
.
new
(
Literal
.
new
(
'a'
),
Concatenate
.
new
(
Literal
.
new
(
'b'
),
Literal
.
new
(
'c'
))
)
=> /abc/
>>
pattern
.
matches?
(
'a'
)
=> false
>>
pattern
.
matches?
(
'ab'
)
=> false
>>
pattern
.
matches?
(
'abc'
)
=> true

We can use a similar strategy to convert a
Choose
expression into an NFA. In the simplest
case, the NFAs for the regular expressions
a
and
b
can
be combined to build an NFA for the regular expression
a|b
by adding a new start state and using free
moves to connect it to the previous start states of the two original
machines:

Before the
a|b
NFA has read any input, it can use a
free move to go into either of the original machines’ start states, from which point it can
read either
'a'
or
'b'
to reach an accept state. Again, it’s just as easy to glue together any two machines by
adding a new start state and two free moves:

In this case, the ingredients for the combined machine are:

Again, this is easy to implement as
Choose#to_nfa_design
:

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

The implementation works nicely:

>>
pattern
=
Choose
.
new
(
Literal
.
new
(
'a'
),
Literal
.
new
(
'b'
))
=> /a|b/
>>
pattern
.
matches?
(
'a'
)
=> true
>>
pattern
.
matches?
(
'b'
)
=> true
>>
pattern
.
matches?
(
'c'
)
=> false

And finally, repetition: how can we turn an NFA that matches a
string exactly once into an NFA that matches the same string zero or
more times? We can build an NFA for
a*
by starting with the NFA for
a
and making two additions:

Here’s how that looks:

The free move from the old accept state to the old start state allows the machine to
match several times instead of just once (
'aa'
,
'aaa'
, etc.), and the new start state allows it to match the
empty string without affecting what
other strings it can accept.
^[
24
]
We can do the same for any NFA as long as we connect each old accept state to
the old start state with a free move:

This time we need:

Let’s turn that into code:

class
Repeat
def
to_nfa_design
pattern_nfa_design
=
pattern
.
to_nfa_design
start_state
=
Object
.
new
accept_states
=
pattern_nfa_design
.
accept_states
+
[
start_state
]
rules
=
pattern_nfa_design
.
rulebook
.
rules
extra_rules
=
pattern_nfa_design
.
accept_states
.
map
{
|
accept_state
|
FARule
.
new
(
accept_state
,
nil
,
pattern_nfa_design
.
start_state
)
}
+
[
FARule
.
new
(
start_state
,
nil
,
pattern_nfa_design
.
start_state
)
]
rulebook
=
NFARulebook
.
new
(
rules
+
extra_rules
)
NFADesign
.
new
(
start_state
,
accept_states
,
rulebook
)
end
end