Skip to content

Instantly share code, notes, and snippets.

@amnn

amnn/earley.clj

Created Oct 9, 2014
Embed
What would you like to do?
Earley Parser in Clojure (Some helper functions are missing).
(defn recogniser
"Returns the recogniser function for the grammar `g`."
[g]
(let [nullable? (nullable g)
g (null-free g)
init (initial-state (nullable? :S))]
(letfn [(consume-token [{:keys [index items] :as state} tok]
(loop [processed? #{}
items items
state (reset-state state)]
(if (seq items)
(let [item (peek items)]
(if (processed? item)
(recur processed? (pop items) state)
(case (classify item)
:shift
(recur (conj processed? item)
(pop items)
(if (= tok (next-sym item))
(update-in state [:items]
conj (shift item))
state))
:reduce
(let [r-key (redux-key item)]
(recur (conj processed? item)
(->> (get-in state [:redux r-key])
(map shift)
(into (pop items)))
(update-in state [:complete] conj r-key)))
:predict
(let [nt (next-sym item)
r-key [index nt]
predicted? (contains? (:redux state) r-key)
state (if predicted?
state
(assoc-in state [:redux r-key] #{}))
items (pop (if (nullable? nt)
(conj items (shift item))
items))]
(recur
(conj processed? item)
(if predicted?
items
(into items
(->> (rule-seq g nt)
(map #(->Item % index 0)))))
(update-in state [:redux r-key] conj item))))))
state)))]
(fn [toks]
(-> (->> (conj (vec toks) nil)
(reduce consume-token init)
:complete)
(contains? success-key))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.