Definite Clause Grammars with core.logic (aka Logos) in Clojure http://en.wikipedia.org/wiki/Definite_clause_grammar

dcg.clj

(ns dcg
  (:refer-clojure :exclude [reify == inc])
  (:use (clojure.core.logic minikanren prelude)))

(declare sentence noun-phrase verb-phrase det noun verb)

(defn sentence [s1 s3]
  (exist [s2]
    (noun-phrase s1 s2)
    (verb-phrase s2 s3)))

(defn noun-phrase [s1 s3]
  (exist [s2]
    (det s1 s2)
    (noun s2 s3)))

(defn verb-phrase [s1 s3]
  (exist [s2]
    (verb s1 s2)
    (noun-phrase s2 s3)))

(defne det [s1 s2]
  ([['the . ?x] ?x])
  ([['a . ?x] ?x]))

(defne noun [s1 s2]
  ([['cat . ?x] ?x])
  ([['bat . ?x] ?x]))

(defne verb [s1 s2]
  ([['eats . ?x] ?x]))

(comment
  
  (run* [q] (sentence q ()))
  ((the cat eats the cat)
   (the cat eats the bat)
   (the cat eats a cat)
   (the cat eats a bat)
   (the bat eats the cat)
   (the bat eats the bat)
   (the bat eats a cat)
   (the bat eats a bat)
   (a cat eats the cat)
   (a bat eats the cat)
   (a cat eats the bat)
   (a cat eats a cat)
   (a bat eats the bat)
   (a cat eats a bat)
   (a bat eats a cat)
   (a bat eats a bat))

  (run* [q] (sentence '(the cat eats a bat) ()))
  (_.0)

  (run* [q] (sentence '(the cat a bat eats) ()))
  ()

  )



(declare sentance pronoun verb-phrase verb)

(defn sentence [s1 s3]
  (exist [s2]
    (pronoun :subject s1 s2)
    (verb-phrase s2 s3)))

(defn verb-phrase [s1 s3]
  (exist [s2]
    (verb s1 s2)
    (pronoun :object s2 s3)))

(defne pronoun [case s1 s2]
  ([:subject ['he . ?x]  ?x])
  ([:subject ['she . ?x] ?x])
  ([:object  ['him . ?x] ?x])
  ([:object  ['her . ?x] ?x]))

(defne verb [s1 s2]
  ([['likes . ?x] ?x]))

(comment
  
  (run* [q] (sentence q []))
  ((he likes him) (he likes her) (she likes him) (she likes her))

  (run* [q] (sentence '(she likes him) ()))
  (_.0)

  (run* [q] (sentence '(her likes he) ()))
  ()

  )



(declare make-sen make-np make-vp make-d make-n make-v
         sentence noun-phrase verb-phrase det noun verb)

(defn make-sen [np vp]
  (list 'S np vp))

(defn make-np [d n]
  (list 'NP d n))

(defn make-vp [v np]
  (list 'VP v np))

(defn make-d [d]
  (list 'D d))

(defn make-n [n]
  (list 'N n))

(defn make-v [v]
  (list 'V  v))

(defn sentence [s s1 s3]
  (exist [np vp s2]
    (noun-phrase np s1 s2)
    (verb-phrase vp s2 s3)
    (== s (make-sen np vp))))

(defn noun-phrase [np s1 s3]
  (exist [d n s2]
    (det d s1 s2)
    (noun n s2 s3)
    (== np (make-np d n))))

(defn verb-phrase [vp s1 s3]
  (exist [v np s2]
    (verb v s1 s2)
    (noun-phrase np s2 s3)
    (== vp (make-vp v np))))

(defne det [d s1 s2]
  ([_ ['the . ?x] ?x] (== d (make-d 'the)))
  ([_ ['a   . ?x] ?x] (== d (make-d 'a))))

(defne noun [n s1 s2]
  ([_ ['bat . ?x] ?x] (== n (make-n 'bat)))
  ([_ ['cat . ?x] ?x] (== n (make-n 'cat))))

(defne verb [v s1 s2]
  ([_ ['eats . ?x] ?x] (== v (make-v 'eats))))

(comment

  (run* [parse-tree] (sentence parse-tree '(the bat eats a cat) ()))
  ((S (NP (D the)
          (N bat))
      (VP (V eats)
          (NP (D a)
              (N cat)))))
  
  )