>  トップ  >  d:tociyuki別館 >  dfa-0.02

d:tociyuki別館

dfa-0.02

限定版の正規表現から決定性有限オートマトン遷移表を作る Perl スクリプトの習作集です。正規表現から NFA を作り、NFA から DFA を作るやりかたをしています。

エイホ他「コンパイラ I 原理・技法・ツール」の「3.6 有限オートマトン」と「3.7 正規表現から NFA へ」の 2 節で説明されているアルゴリズムを perl で実装してみました。

※本版で「3.9 DFA によるパターン照合の最適化」の「DFAの状態数の最小化」を実装しました。DFA->compose($RE) は状態数を圧縮した DFA を返すようになりました。

ソース

  1. compact.pl -- DFA 最小化のサンプル・コード。
  2. sample.pl -- サンプル・コード。
  3. DFA.pm -- DFA の遷移表のコンテナ。
  4. NFA.pm -- NFA の遷移表のコンテナ。
  5. FATable.pm -- 上2つのベースクラス。
  6. NFA2DFA.pm -- NFAからDFAへ。部分集合構成法を使用。
  7. Regexp2NFA.pm -- 正規表現のBNFでNFAへ変換。
  8. RegexpScanner.pm -- 正規表現のスキャナ。
  9. Token.pm -- 同上の生成するトークンのクラス。
  10. TopdownParser.pm -- トップ・ダウン構文解析子のベースクラス。

改訂履歴

dfa-0.03 2007年2月22日
正規表現 → 構文木 → DFA、正規表現 → 構文木 → NFA に改訂。繰り返し記号 + を使えるようにした。NFA → DFA は残す。Regexp2NFA パッケージを削除。構文木用のノード・クラスを追加。
dfa-0.02 2007年2月21日
DFA 最小化を実装。FATable から push メソッドを削除。
dfa-0.01 2007年2月20日
初出。正規表現 → NFA → DFA 変換機能。

COPYRIGHT AND LICENSE

Copyright (C) 2004 by MIZUTANI Tociyuki

This library is free software . You can redistribute it and/or modify it under the same terms as perl itself.

MIZUTANI Tociyuki at Kanagawa-Ku, Yokohama-City, Japan