2010年3月17日水曜日

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

0 件のコメント:

コメントを投稿