dfa-0.01 正規表現から DFA へ(NFA 経由版)

機能限定版の正規表現トップダウン構文解析して非決定性有限オートマトン(NFA)を生成し、それから部分集合構成法で決定性有限オートマトン(DFA)を生成するコードを Perl で書いてみました。
扱う正規表現は、総称文字(.)や文字クラス([][…][])が使えず、1文字そのものしか扱えず、繰り返し指定は ?* しか使えません。括弧 (…)Perl(?:…) に相当し、パターンの記憶はできません。複数選択の | は使えます。
ネタ元のドラゴンブックの字句解析部の説明で使われているプログラミング言語の断片の字句を Perl 風にちょっと変更した正規表現DFA にして字句それぞれにマッチさせるサンプルを書くと次のようになります。
(追記) このパッケージの DFA と NFA の match メソッドは m/\A…\z/ の動作をします。

#!/bin/env perl
use strict;
use warnings;

use DFA;

my $RE = '<(=>?)?|>=?|==?|!=?|w(w|1)*|11*(\\.11*)?(e(+|-)?11*)?';
my $dfa = DFA->compose($RE);
print $dfa->inspect;
for ('<', '<=', '<=>', '<<', 'ww111ww1', '1.1e+1', '1e+1', '1.1', '11') {
    printf "%-8s %s\n", $_, $dfa->match($_) || 'no';
}

Perl正規表現は高速かつ強力ですので、このコードをパターンマッチングに使うことはありませんが、仕組みを復習したいという、ただそれだけの動機で作ってみました。なお、このパッケージ集には、まだ DFA を使ったスキャナを含めてません。


DFA の遷移状態を最小化させる改訂版https://tociyuki.sakura.ne.jp/archive/dfa-0.02/ (説明のエントリ)


https://tociyuki.sakura.ne.jp/archive/dfa-0.01/

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

(追記) 勘違いを発見。NFA2DFA->process のある状態集合 T から文字 c_i ごとの遷移先の状態集合 U(c_i) を求めるときの文字集合は、T からその都度探すのが正しいはずです。ところが、私のコードでは NFA の全状態の集合の文字を最初に求めて、それを使っています。私の誤ったやりかたですと文字集合 [][…][] が扱いにくくなります。改訂版を作らなくては……。
ネタ元は、ドラゴンブックの「3.6 有限オートマトン」と「3.7 正規表現から NFA へ」の 2 節です。この教科書ではこれに続いて 3.8 節で正規表現から DFA を直接生成するアルゴリズムを扱っていまして、続いてそっちもやってみたいと思っています。

コンパイラ―原理・技法・ツール〈1〉 (Information & Computing)

コンパイラ―原理・技法・ツール〈1〉 (Information & Computing)