Created
July 21, 2010 03:38
-
-
Save jl2/484022 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-- Convert an Nfa to a Dfa using the algorithms from section 3.7.1 of the "Dragon book" | |
toDfa :: Nfa -> Dfa | |
toDfa nfa = | |
let | |
dstrt = e_closure nfa (n_start nfa) | |
init = Map.fromList [(dstrt, genStates dstrt)] | |
dfa = getps init | |
stateNames = genStateMap dfa | |
partial = Map.mapKeys (\x -> lookupDefault x 0 stateNames) dfa | |
dfaTrans = Map.map (\x -> Map.map (\y -> (lookupDefault y 0 stateNames)) x) partial | |
accepting = Set.fromList | |
(Map.elems | |
(Map.filterWithKey | |
(\k x -> | |
(Set.size (Set.intersection (n_accepting nfa) k)) > 0 | |
) | |
stateNames | |
) | |
) | |
in | |
Dfa dfaTrans (n_start nfa) accepting (n_rgx nfa) | |
where | |
getps old = | |
if (new == old) | |
then new | |
else (getps new) | |
where | |
new = generateProductions old | |
generateProductions :: Map.Map (StateSet) (Map.Map NfaChar (StateSet)) | |
-> Map.Map (StateSet) (Map.Map NfaChar (StateSet)) | |
generateProductions fad = foldl | |
(\acc x -> | |
let | |
gt = (genStates x) | |
in | |
Map.insert x gt acc | |
) fad (getProductionStates fad) | |
genStateMap :: Map.Map (StateSet) (Map.Map NfaChar (StateSet)) | |
-> Map.Map (StateSet) Int | |
genStateMap dfa = foldl | |
(\acc x -> | |
let | |
(y, sm) = mapState acc x | |
in | |
sm | |
) Map.empty (Map.keys dfa) | |
getProductionStates fad = (concat | |
(map | |
(\x -> Map.elems x) | |
(Map.elems fad) | |
) | |
) | |
mapState sm set = case Map.lookup set sm of | |
Just y -> (y, sm) | |
Nothing -> let ms = Map.size sm | |
in (ms, Map.insert set ms sm) | |
genStates set = Map.fromList (filter (\(x,y) -> not (Set.null y)) | |
(Set.toList | |
(Set.map | |
(\ch -> (ch, e_closure_set nfa (nfa_move nfa set ch))) | |
inSyms | |
) | |
)) | |
inSyms = Set.delete Epsilon (Set.fromList (Map.fold (\x acc -> acc ++ Map.keys x) [] (n_transitions nfa))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment