regexp->list->nfa

正規表現を文字列で考えていて頭がいたくなってきたので、一旦リストにしてからNFAにするようにしてみる。

;;regexp->list
(defun regexp->list (reg)
  (let* ((top nil)
	 (stack (list top)))
    (loop :for ch across reg
       :do
       (case ch
	 ((#\()
	  (push top stack)
	  (setf top nil))
	 ((#\))
	  (let ((prev (pop stack)))
	    (push top prev)
	    (setf top prev)))
	 ((#\|)
	   (setf top
		 (list top :or)))
	 ((#\*)
	  (let ((tmp (list (pop top) :loop)))
	    (push tmp top)))
	 ((#\.)
	  (push :all top))
	 (T
	  (push ch top)))
       :finally (return-from regexp->list
       (reverse-tree top)))))

(defun reverse-tree (tree)
  (if (listp tree)
      (reverse (mapcar #'reverse-tree tree))
      tree))

(defun list->nfa (lst)
  (reduce
   #'merge-nfa-concat
   (remove
    nil
    (mapcar
    #'(lambda (obj)
	(typecase obj
	  (character
	   (make-nfa-char obj))
	  (list
	   (case (car obj)
	     ((:loop)
	      (make-nfa-loop
	       (list->nfa (cdr obj))))
	     ((:or)
	      (merge-nfa-or
	       (list->nfa (list (second obj)))
	       (list->nfa (cddr obj))))
	     (T
	      (list->nfa obj))))
	   (symbol
	    (case obj
	      ((:all)
	       (make-nfa-all))
	      (T (error "Unexpected symbol:~A" obj))))
	   (T (error "Unexpected type:~A" obj))))
     lst))))

>(match (list->nfa (regexp->list "(hoge|fuga|piyo)*"))
	"foobarhogefugapiyofizzbuzz")
"hogefugapiyo"
6
18
>(match (list->nfa (regexp->list "'.*(hoge|fuga|piyo).*'"))
		"this is 'test hoge.'")
"'test hoge.'"
8
20