parser-combinators.clj

;; parser combinators

(defn pred->parser
  [pred]
  (fn [[x & remaining :as input]]
    (if (pred x)
      [x remaining]
      [::invalid input])))

(defn alt
  [& parsers]
  (fn [input]
    (loop [[parser & parsers] parsers]
      (if parser
        (let [[results remaining] (parser input)]
          (if (= results ::invalid)
            (recur parsers)
            [results remaining]))
        [::invalid input]))))

(defn many*
  [parser]
  (fn [input]
    (loop [results [], remaining input]
      (if (seq remaining)
        (let [[result remaining] (parser remaining)]
          (if (= result ::invalid)
            [results remaining]
            (recur (conj results result) remaining)))
        [results remaining]))))

(defn many+
  [parser]
  (let [parser (many* parser)]
    (fn [input]
      (let [[results remaining] (parser input)]
        (if (empty? results)
          [::invalid input]
          [results remaining])))))

(defn optional
  [parser]
  (fn [input]
    (let [[results remaining] (parser input)]
      (if (= results ::invalid)
        [nil input]
        [results remaining]))))

(defn sequence
  [reduction-fn & parsers]
  (fn [input]
    (loop [[parser & parsers] parsers
           remaining          input
           results            []]
      (if parser
        (let [[results' remaining] (parser remaining)]
          (if (= results' ::invalid)
            [::invalid input]
            (recur parsers remaining (reduction-fn results results'))))
        [results remaining]))))

(defn transform
  [f parser]
  (fn [input]
    (let [[results remaining] (parser input)]
      (if (= results ::invalid)
        [::invalid remaining]
        [(f results) remaining]))))

(defn descend
  [parser]
  (fn [input]
    (let [[sub-input & remaining] input
          [result sub-remaining] (parser sub-input)]
      (if (seq sub-remaining)
        [::invalid input]
        [result remaining]))))