parser-combinator.clj

(ns rabscuttle.parser-combinator)

(comment
  "Working through http://www.cs.nott.ac.uk/~gmh//parsing.ps"
  "A parser is a function that takes in input and returns lazy list of list of parsed value, and remaining input pairs")

(def letters (map char (lazy-cat (range (int \a) (inc (int \z)))
				(range (int \A) (inc (int \Z))))))

(def digits (map char (lazy-cat (range (int \0) (inc (int \9))))))

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

(defn char-in-range? [start end c]
  (and c
       (>= (int c) (int start))
       (<= (int c) (int end))))

(defn digit? [c]
  (char-in-range? \0 \9 c))

(defn number [inp]
  ((some-p (satisfy digit?)) inp))

(defn letter? [c]
  (or (char-in-range? \a \z c)
      (char-in-range? \A \Z c)))

(defn word [inp]
  ((some-p (satisfy letter?)) inp))

(defn string [xs]
  (if xs
    (using (then (literal (first xs)) (string (rest xs)))
	   my-cons)
    (succeed [])))

(defn thenx [p1 p2]
  (using (then p1 p2) first))

(defn xthen [p1 p2]
  (using (then p1 p2) second))

(defn return [p v]
  (let [const (fn [x] (fn [y] x))]
    (using p (const v))))

(defn str-first [parse-results]
  (apply str (ffirst parse-results)))