6
我想通過移植一個玩具NFA regexp matcher來學習一點clojure。顯然，我的主要問題是表示和操作圖形。我遇到了一個可行的解決方案，但是我的實現（基本上使用gensym來模擬指針）讓我在嘴裏感到一種難以忍受的味道。在clojure中表示圖形
爲了表示圖形和一般的可讀性以及習慣用法，謹慎地提出改進建議？ （原來的命令式解決方案比我現在的解決方案更具可讀性）。
乾杯！
; This is a port of Matt Might's toy regexp library described in
; http://matt.might.net/articles/implementation-of-nfas-and-regular-expressions-in-java/
; char_transitions is a map that associates a character with a set
; of target state names
; empty_transitions is a set of target state names
(defrecord NfaState [final char_transitions empty_transitions])
; 'entry' and 'exit' are state names
; 'states' is a map that associates state names with states
(defrecord Nfa [entry exit states])
(defn- add-empty-edge [nfa curr_state_name next_state_name]
(let [curr_state (curr_state_name (:states nfa))]
(Nfa. (:entry nfa) (:exit nfa) (assoc (:states nfa) curr_state_name (NfaState. (:final curr_state) (:char_transitions curr_state) (conj (:empty_transitions curr_state) next_state_name))))))
(defn- nfa-matches?
([nfa nfa_state_name string] (nfa-matches? nfa nfa_state_name string #{}))
([nfa nfa_state_name string visited]
(let [nfa_state (nfa_state_name (:states nfa))
new_visited (conj visited nfa_state_name)]
(cond
(contains? visited nfa_state_name) false
(empty? string) (or (:final nfa_state)
(some #(nfa-matches? nfa % string new_visited)
(:empty_transitions nfa_state)))
(not (empty? string)) (or
(some #(nfa-matches? nfa % (.substring string 1)) (get (:char_transitions nfa_state) (.charAt string 0) #{}))
(some #(nfa-matches? nfa % string new_visited) (:empty_transitions nfa_state)))
:else false))))
(defn matches? [nfa string]
"Matches a string against an NFA"
(nfa-matches? nfa (:entry nfa) string))
(defn c [ch]
"Creates an NFA which matches the character 'c'"
(let [in (gensym)
out (gensym)]
(Nfa. in out {in (NfaState. false {ch #{out}} #{}) out (NfaState. true {} #{})})))
(defn e []
"Creates an NFA which matches the empty string"
(let [in (gensym)
out (gensym)]
(Nfa. in out {in (NfaState. false {} #{out}) out (NfaState. true {} #{})})))
(defn rep [nfa]
"Creates an NFA which matches zero or more repetitions of the given NFA"
(add-empty-edge (add-empty-edge nfa (:entry nfa) (:exit nfa)) (:exit nfa) (:entry nfa)))
(defn- update-final [nfastate new_final]
(NfaState. new_final (:char_transitions nfastate) (:empty_transitions nfastate)))
(defn s [first second]
"Creates an NFA which matches a sequence of two provided NFAs"
(add-empty-edge (Nfa. (:entry first) (:exit second) (merge (update-in (:states first) [(:exit first)] update-final false) (update-in (:states second) [(:exit second)] update-final true))) (:exit first) (:entry second)))
(defn ou [first second]
"Creates an NFA which matches either provided NFA"
(let [in (gensym)
out (gensym)]
(add-empty-edge (add-empty-edge (Nfa. in out (assoc (merge (update-in (:states first) [(:exit first)] update-final false) (update-in (:states second) [(:exit second)] update-final false)) in (NfaState. false {} #{(:entry first) (:entry second)}) out (NfaState. true {} #{}))) (:exit first) out) (:exit second) out)))
; sugar
(defn st [string]
"Creates an NFA which matches the provided string"
(if (empty? string)
(e)
(s (c (.charAt string 0)) (st (.substring string 1)))))