正規表現 → 非決定性有限オートマトン

プログラム

http://members.jcom.home.ne.jp/j-klein/src-box/reg2nfa.y

正規表現から非決定性有限オートマトン（NFA）を構築するプログラムを作ってみた。yaccの練習がてら作ってみたのだけれど、かなりばかなやり方をしてると思う。やってみて思ったのは、解析木から状態遷移テーブルを作る作業は構文解析自体を再起下降法でやるのとまったく同じ手順になるということ。だったらはじめから再起下降法で構文解析すれば解析木を作らずに状態遷移テーブルを作れそう。

ちなみに、NFAを構築したらそれをgraphvizを使って照合機械自体を見ることが出来る。三つほどサンプルを作ってみたのでどうぞ。なお、辺についているラベルは入力を表していて、入力”*”（アスタリスク）はε遷移（空遷移）を意味する。

そうそう、正規表現の仕様はいたってシンプル。使用出来るのは"a|b"のような論理和（OR）、"ab"のような連接（Concatenation）、"a*"のような閉包（Closure）、優先度を表す括弧"()"のみ。よって[0-9]のようなことは出来ず、数字を表す時は(0|1|2|3|4|5|6|7|8|9)とするしかない。