;;; --------------------------------------------------------------
;;; CMSC723: Natural Language Processing
;;;
;;;   Assignment 2
;;;
;;;
;;; Remark: nil = epsilon
;;;
;;; This is the NFSA recognition.  The algorithm is the same as the
;;; algorithm of Jurafsky and Martin on p.44 of the textbook.
;;; A number of example is also given.  It works on both sheep talk
;;; and date expression.
;;; 
;;; --------------------------------------------------------------

;;; --------------------------------------------------------------
;;; Global variable
;;; --------------------------------------------------------------

(defvar *verbose* nil)   ;; boolean value that toggle the verbose mode

;;; --------------------------------------------------------------
;;; Structure declaration
;;; --------------------------------------------------------------

(defstruct NFSA-state
  transition
  (is-accept-state nil))

(defstruct NFSA
  name
  states    ;; optional
  symbols   ;; optional
  initial-state)

;;; --------------------------------------------------------------
;;; Functions
;;; --------------------------------------------------------------

(defun ND-Recognize (machine tape)
  (if *verbose*
      (format t "--- NFSA start ---~%"))
  (format t "NFSA = ~A~%" (NFSA-name machine))
  (format t "Input string = ~A~%" tape)
  (let ((agenda)
	(s-state)
	(m-state)
	(m-tape)
	(m-symbol)
	(tmp-agenda))
    (push (cons tape (NFSA-initial-state machine)) agenda)
    (loop (if (null agenda)
	      (progn (format t "String rejected~%")
		     (return)))
          (setf s-state (pop agenda))
	  (setf m-tape (car s-state))
	  (setf m-state (cdr s-state))
	  (setf m-symbol (car m-tape))
	  (if *verbose*
	      (progn (format t "State = ~A~%" m-state)
		     (format t "Tape  = ~A~%" m-tape)))
	  (if (and (null m-symbol)
		   (NFSA-state-is-accept-state (eval m-state)))
	      (progn (format t "String accepted~%")
		     (return))
	      (progn (setf tmp-agenda (generate-new-state
				       m-state m-tape m-symbol))
		     (if (and *verbose* (null tmp-agenda))
			 (format t "Backtrack~%"))
		     (setf agenda (append tmp-agenda agenda))))))  
  (format t "~%"))


(defun generate-new-state (m-state m-tape m-symbol)
  (let ((tmp-agenda nil))
    (dolist (edge (NFSA-state-transition (eval m-state)))
	    (if (member nil (cdr edge))
		(push (cons m-tape (car edge)) tmp-agenda)))
    (dolist (edge (NFSA-state-transition (eval m-state)))
	    (if (member m-symbol (cdr edge))
		(push (cons (cdr m-tape) (car edge)) tmp-agenda)))
    tmp-agenda))


;;; --------------------------------------------------------------
;;; Test Case 1: Sheep talk 1
;;; --------------------------------------------------------------

(setf Q0 (make-NFSA-state
	  :transition '((Q1 B))))

(setf Q1 (make-NFSA-state
	  :transition '((Q2 A))))

(setf Q2 (make-NFSA-state
	  :transition '((Q2 A) (Q3 A))))

(setf Q3 (make-NFSA-state
	  :transition '((Q4 !))))

(setf Q4 (make-NFSA-state
	  :is-accept-state t
	  :transition nil))

(setf sheep-talk-NFSA-1 (make-NFSA
			 :name "Sheep Talk NFSA 1"
;;		         :states '(Q0 Q1 Q2 Q3)
;;		         :symbols '(B A !)
			 :initial-state 'Q0))

(setf tape '(B A A A A !))

(ND-Recognize sheep-talk-NFSA-1 tape)

;;; --------------------------------------------------------------
;;; Test Case 2: Sheep talk 2
;;; --------------------------------------------------------------

(setf Q0 (make-NFSA-state
	  :transition '((Q1 B))))

(setf Q1 (make-NFSA-state
	  :transition '((Q2 A))))

(setf Q2 (make-NFSA-state
	  :transition '((Q3 A))))

(setf Q3 (make-NFSA-state
	  :transition '((Q4 !) (Q2 nil))))

(setf Q4 (make-NFSA-state
	  :is-accept-state t
	  :transition nil))

(setf sheep-talk-NFSA-2 (make-NFSA
			 :name "Sheep Talk NFSA 2"
;;		         :states '(Q0 Q1 Q2 Q3)
;;		         :symbols '(B A !)
			 :initial-state 'Q0))

(setf tape '(B A A A A !))

(ND-Recognize sheep-talk-NFSA-2 tape)

;;; --------------------------------------------------------------
;;; Test Case 3: Date expression
;;; --------------------------------------------------------------

(setf Q0 (make-NFSA-state
	  :transition '((E1 nil) (E2 nil) (E3 nil) (E4 nil) (E5 nil))))

(setf Qf (make-NFSA-state
	  :is-accept-state t
	  :transition nil))

(setf E1 (make-NFSA-state
  :transition '((E1-mon-31 Jan Mar May Jul Aug Oct Dec)
		(E1-mon-30 Apr Jun Sep Nov)
		(E1-mon-29 Feb))))

(setf E1-mon-31 (make-NFSA-state
  :transition '((E1-day 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
	                16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31))))

(setf E1-mon-30 (make-NFSA-state
  :transition '((E1-day 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
	                16 17 18 19 20 21 22 23 24 25 26 27 28 29 30))))

(setf E1-mon-29 (make-NFSA-state
  :transition '((E1-day 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
	                16 17 18 19 20 21 22 23 24 25 26 27 28 29))))

(setf E1-day (make-NFSA-state
  :transition '((Qf nil)
		(E1-year 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989
			 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999
			 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009
			 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019
			 2020))))

(setf E1-year (make-NFSA-state
  :transition '((Qf nil))))


(setf E2 (make-NFSA-state
  :transition '((E1-mon-31 January March May July August October December)
		(E1-mon-30 April June September November)
		(E1-mon-29 February))))


(setf E3 (make-NFSA-state
  :transition '((E3-the the))))

(setf E3-the (make-NFSA-state
  :transition '((E3-day-1to29
		 1st  2nd  3rd  4th  5th  6th  7th  8th  9th 10th
		 11th 12th 13th 14th 15th 16th 17th 18th 19th 20th
		 21st 22nd 23rd 24th 25th 26th 27th 28th 29th)
		(E3-day-1to30
		 1st  2nd  3rd  4th  5th  6th  7th  8th  9th 10th
		 11th 12th 13th 14th 15th 16th 17th 18th 19th 20th
		 21st 22nd 23rd 24th 25th 26th 27th 28th 29th 30th)
		(E3-day-1to31
		 1st  2nd  3rd  4th  5th  6th  7th  8th  9th 10th
		 11th 12th 13th 14th 15th 16th 17th 18th 19th 20th
		 21st 22nd 23rd 24th 25th 26th 27th 28th 29th 30th 31st))))


(setf E3-day-1to29 (make-NFSA-state
  :transition '((E3-day-1to29-of of))

))

(setf E3-day-1to30 (make-NFSA-state
  :transition '((E3-day-1to30-of of))

))

(setf E3-day-1to31 (make-NFSA-state
  :transition '((E3-day-1to31-of of))

))

(setf E3-day-1to29-of (make-NFSA-state
  :transition '((E3-mon February))))

(setf E3-day-1to30-of (make-NFSA-state
  :transition '((E3-mon April June September November))))

(setf E3-day-1to31-of (make-NFSA-state
  :transition '((E3-mon January March May July August October December))))

(setf E3-mon (make-NFSA-state
  :transition '((Qf nil))))

(setf E4 (make-NFSA-state
  :transition '((Qf New-Year New-Year-Eve Martin-Lurther-King-Day
		    Valentine-Day Mother-Day Father-Day Independence-Day
		    Labor-Day Halloween Thanksgiving-Day Christmas
		    New-Year-Eve))))

(setf E5 (make-NFSA-state
  :transition '((E5-mon-31 1 3 5 7 8 10 12)
		(E5-mon-30 4 6 9 11)
		(E5-mon-29 2))))

(setf E5-mon-31 (make-NFSA-state
  :transition '((E5-mon-31-s /))))

(setf E5-mon-30 (make-NFSA-state
  :transition '((E5-mon-30-s /))))

(setf E5-mon-29 (make-NFSA-state
  :transition '((E5-mon-29-s /))))


(setf E5-mon-31-s (make-NFSA-state
  :transition '((E5-day  1  2  3  4  5  6  7  8  9 10
			11 12 13 14 15 16 17 18 19 20
			21 22 23 24 25 26 27 28 29 30 31))))

(setf E5-mon-30-s (make-NFSA-state
  :transition '((E5-day  1  2  3  4  5  6  7  8  9 10
			11 12 13 14 15 16 17 18 19 20
			21 22 23 24 25 26 27 28 29 30))))

(setf E5-mon-29-s (make-NFSA-state
  :transition '((E5-day  1  2  3  4  5  6  7  8  9 10
			11 12 13 14 15 16 17 18 19 20
			21 22 23 24 25 26 27 28 29))))

(setf E5-day (make-NFSA-state
  :transition '((E5-day-s /))))

(setf E5-day-s (make-NFSA-state
  :transition '((E5-year 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989
			 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999
			 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009
			 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019
			 2020))))

(setf E5-year (make-NFSA-state
  :transition '((Qf nil))))

(setf date-expression-NFSA (make-NFSA
  :name "Date Expression NFSA"
  :initial-state 'Q0))

(ND-Recognize date-expression-NFSA '(Mar 15))
(ND-Recognize date-expression-NFSA '(January 1 2000))
(ND-Recognize date-expression-NFSA '(Dec 31))
(ND-Recognize date-expression-NFSA '(February 29))
(ND-Recognize date-expression-NFSA '(Apr 31))
(ND-Recognize date-expression-NFSA '(Feb 30))
(ND-Recognize date-expression-NFSA '(the 22nd of November))
(ND-Recognize date-expression-NFSA '(the 31st of December))
(ND-Recognize date-expression-NFSA '(the 31st of February))
(ND-Recognize date-expression-NFSA '(the 31st of September))
(ND-Recognize date-expression-NFSA '(Christmas))
(ND-Recognize date-expression-NFSA '(Mother-Day))
(ND-Recognize date-expression-NFSA '(10 / 31 / 2010))
(ND-Recognize date-expression-NFSA '(4 / 30 / 2000))
(ND-Recognize date-expression-NFSA '(4 / 31 / 1999))


;;; --------------------------------------------------------------
;;; The end
;;; --------------------------------------------------------------