dfa-0.03 正規表現 → 構文木 → DFA、NFA (構文木経由版)

DFA と NFA を正規表現構文木からそれぞれ直接生成するように改訂しました。構文木を作るようにしたおかげで、正規表現の繰り返し指定に * へ加えて + が使えるようになりました。最初から、構文木にしておけば良かった。
ドラゴンブックの第三章の本文のアルゴリズムをこれで制覇したことになります。ということで、正規表現に絡んだオートマトンPerl コード作りは、これで一段落。次回から数回に分けて、備忘録を兼ねてコードの説明を書くかもしれません。
正規表現を扱う有限オートマトンアルゴリズムは集合演算を使うため、Perl 向きではなかったなと、今になって気が付いたのですが、後のまつり。ま、でも、C 言語にポートするには Perl の方が楽かも。

https://tociyuki.sakura.ne.jp/archive/dfa-0.03/index.html

以下は上のリンク先からのコピペです。

実装したアルゴリズム一覧

アルゴリズム3.1 DFA のシミュレーション p. 138
$DFA->match($string) -- DFA が文字列を受理するかどうかを調べます。
アルゴリズム3.2 NFA から DFAの構成 (部分集合構成法) p. 140
$DFA = $DFA2NFA->process($NFA) -- NFA から DFA を作成します。
アルゴリズム3.3 正規表現から NFA へ (Thomson の構成法) p. 145
$NFA = $Tree2NFA->process($regexp_tree) -- 正規表現構文木から NFA を作成します。このクラスは構文木のビジターになっています。
アルゴリズム3.4 NFAのシミュレーション p. 150
$NFA = $NFA->match($string) -- NFA が文字列を受理するかどうかを調べます。
アルゴリズム3.5 正規表現 r から DFA の作成 p. 167
$DFA = $Tree2DFA->process($regexp_tree) -- 正規表現構文木から NFA を作成します。このクラスは構文木のビジターになっています。
アルゴリズム3.6 DFA の状態数の最小化 p. 170
$DFA = $DFA->compact -- DFA の冗長な状態をまとめます。
アルゴリズム4.3 非再帰的な予測型構文解析 p. 224
$TopdownParser->process -- 構文解析表に基づくパーサのエンジンです。

ソース一覧

  1. dfa-sample.pl -- DFA のサンプル・コード。
  2. nfa-sample.pl -- NFA のサンプル・コード。
  3. compact.pl -- DFA 最小化のサンプル・コード。
  4. DFA.pm -- DFA の遷移表のコンテナ。
  5. NFA.pm -- NFA の遷移表のコンテナ。
  6. FATable.pm -- 上2つのベースクラス。
  7. Regexp2Tree.pm -- 正規表現構文木生成。
  8. Tree2DFA.pm -- 構文木から DFA を構成するビジター。
  9. Tree2NFA.pm -- 構文木から NFA を構成するビジター。
  10. NFA2DFA.pm -- NFAからDFAへ。
  11. Token.pm -- 正規表現スキャナ・パーサが使うトークンのクラス。
  12. TopdownParser.pm -- トップ・ダウン構文解析子のベースクラス。
  13. Regexp/Grammar.pm -- 正規表現構文解析表。
  14. Regexp/Scanner.pm -- 正規表現のスキャナ。
  15. Regexp/Char.pm -- 正規表現構文木の文字ノード。
  16. Regexp/Concat.pm -- 同上。連結ノード。
  17. Regexp/Select.pm -- 同上。選択ノード。
  18. Regexp/Repeat.pm -- 同上。繰り返しノード。
  19. Regexp/Epsilon.pm -- 同上。εノード。
  20. Regexp/Final.pm -- 同上。受理記号ノード。
  21. Regexp/Node.pm -- ノードのベースクラス。
  22. Regexp/Visitor.pm -- 構文木のビジターのベースクラス。