Scanning—Theory and Practice - Crafting a Compiler - page 95

function M ake D eterministic ( N ) returns DFA

D . StartState ← R ecord S tate ( { N . StartState } )

foreach S ∈ WorkList do
WorkList ← WorkList −{ S }
foreach c ∈Σ (

s ∈ S

do D . T ( S , c ) ← R ecord S tate

N . T ( s , c ))

D . AcceptStates ←{ S ∈ D . States | S ∩ N . AcceptStates ∅}
end

function C lose ( S , T ) returns Set

ans ← S
repeat
changed ←

false
foreach s ∈ ans do
foreach t ∈ T ( s ,λ ) do

if t ans
then
ans ← ans ∪{ t }
changed ← true

until not changed
return ( ans )
end

function R ecord S tate ( s ) returns Set

( s , N . T )
if s D . States
then
D . States ← D . States ∪{ s }
WorkList ← WorkList ∪{ s }
return ( s )
end

s ← C lose

Figure 3.23: Construction of a DFA D from an NFA N .