;; This file requires common lisp.


;;; ############################
;;; Demonstration:
;;; A simple grammar of English.
;;; ############################

(defun random-elt (list)
  "This function takes a random element from a list."
  (nth (random (length list)) list))

;; DET -> a, the, this, these
(defun det ()
  "This function chooses a random element from a list of determiners."
  (list 'det (random-elt '("a" "the" "this" "these"))))

;; N -> boy, cat, dog, women
(defun n ()
  "This function takes a random element from a list of nouns."
  (list 'n (random-elt '("boy" "cat" "dog" "women"))))

;; V -> sneezed, looked, shouted
(defun v ()
  "This function takes a random element from a list of verbs."
  (list 'v (random-elt '("sneezed" "looked" "shouted"))))

;; NP -> Det N
(defun np ()
  "This function calls the functions #'det and #'n."
  (list 'np (det) (n)))

;; VP -> V
(defun vp ()
  "This function calls the function #'v."
  (list 'vp (v)))

;; S -> NP VP
(defun generate-sentence ()
  "This function calls the rewrite-rules that generate a sentence."
  (list 's (np) (vp)))

(defun get-sentence-from-tree (list)
  "This function returns only the sentence itself without the tree."
  (cond
    ((null list) nil)
    ((stringp (first list)) (list (first list)))
    ((symbolp (first list)) (get-sentence-from-tree (rest list)))
    (t
     (append (get-sentence-from-tree (first list)) 
	     (get-sentence-from-tree (rest list))))))

(defun produce-sentence ()
  "This function produces a tree and returns its sentence."
  (let ((tree (generate-sentence)))
    (format t "~%Generated tree: ~a~%" tree)
    (get-sentence-from-tree tree)))

;; Examples of applying the function #'produce-sentence:
;; -----------------------------------------------------
;;
;; > (produce-sentence)
;; 
;; Generated tree: (S (NP (DET a) (N women)) (VP (V looked)))
;; ("a" "women" "looked")x
;;
;;
;; > (produce-sentence)
;;
;; Generated tree: (S (NP (DET the) (N cat)) (VP (V sneezed)))
;; ("the" "cat" "sneezed")
;;
;;
;; > (produce-sentence)
;;
;; Generated tree: (S (NP (DET this) (N women)) (VP (V sneezed)))
;; ("this" "women" "sneezed")