Earley Parser in Clojure (Some helper functions are missing).

earley.clj

(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))))))