Regex Parser

parse-regex.clj

(defn syntax-error []
  (throw (ex-info "Syntax Error" {})))
 
(declare alt then star prime)
 
(defn expect [s c]
  (if (not= (first s) c)
    (syntax-error)
    (rest s)))

(defn alt [s]
  (let [[a s] (then s)]
    (if (= (first s) "|")
      (let [[b s*] (alt (rest s))]
        [(list :alt a b) s*])
      [a s])))

(defn then [s]
  (let [[c s] (star s)]
    (if (or (= (first s) "(")
            (re-matches #"\w" (first s)))
      (let [[d s*] (then s)]
        [(list :then c d) s*])
      [c s])))
 
(defn star [s]
  (let [[p s] (prime s)
        P     [p]]
    (println p)
    (if (= (first s) "*")
      [(cons :star P) (rest s)]
      [(first P) s])))
 
(defn prime [s]
  (if (re-matches #"\w" (first s))
    (do
      [(list :literal (first s)) (rest s)])
    (do
      (let [s*      (expect s "(")
            [r s**] (alt s*)
            s***    (expect s** ")")]
        [r s***]))))
 
(defn parse-regex [s]
  (let [s         (map str (lazy-cat s "\x00"))
        [tree s*] (alt s)]
    (if-not (= (first s*) "\x00")
      (syntax-error)
      tree)))
 
(parse-regex "a")
(parse-regex "abc")
(parse-regex "(ab)")
(parse-regex "(ab)*")
(parse-regex "(ab)*(c|d)*(e|f)")