parser-combinator.clj

(ns rabscuttle.parser-combinator)

(comment
  "Working through http://www.cs.nott.ac.uk/~gmh//parsing.ps"
  "parser is a function that takes in input and returns [[v, inp]]")

;; Primitive Parsers
(defn succeed [v] (fn [inp] [[v inp]]))

(defn fail [inp] [])

(defn satisfy [pred]
  (fn [inp]
    (let [h (first inp)]
      (if (pred h) 
	((succeed h) (rest inp))
	(fail [])))))

(defn literal [x]
  (satisfy #(= x %)))

;; Combinators
(defn alt [p1 p2]
  (fn [inp]
    (lazy-cat (p1 inp)
	      (p2 inp))))

(defn then [p1 p2]
  (fn [inp]
    (for [[v1 out1] (p1 inp)
	  [v2 out2] (p2 out1)]
      [[v1 v2] out2])))

;; Manipulating values
(defn using [p f]
  (fn [inp]
    (for [[v out] (p inp)]
      [(f v) out])))

(defn my-cons [args] 
  (cons (first args) (second args)))

(defn many [p]
  (fn [inp]
    (let [manyp (alt (using (then p (many p)) my-cons)
		     (succeed []))]
      (manyp inp))))

(defn some-p [p]
  (fn [inp]
    (let [somep (using (then p (many p)) my-cons)]
      (somep inp))))