1

テキストの非常に短いセグメント (1 ～ 7 文字) を照合する必要があり、有限状態マシンで許容可能な文字列を指定する方法を知っています。このアプリケーションの正規表現を構築すると、面倒で保守が難しくなると思います。FSM を記述できる使いやすいモジュールが必要です。そのモジュールで正規表現を生成して使用できるようになれば、大きなメリットになります。これを簡単に実行できるモジュールを知っている人はいますか?

4

1 に答える 1

10

FSM の作成は、モジュールがなくても非常に簡単です。

my $state = 0;
while (my $token = shift @input) {
  $state = $state_table{$state}->($token);
}

ここで、状態テーブルは、状態をキーとして、匿名サブを値として持つハッシュです。

0 => sub {
  my $nextstate;
  given (shift) {
    when ('a') {print "its an a"; $nextstate = 2}
    default    {$nextstate = 1}
  }
 return $nextstate;
},
1 => sub {
  my $token = shift;
  my $nextstate = ({
    a => sub {print "Its an a"; 2}
  }->{$token} // sub {1})->();
  return $nextstate;
},
2 => ...

(この場合、状態 0 と 1 は同等であることに注意してください)

givenPerl でスイッチを作成するには、ソース フィルター、 -コンストラクト、ハッシュのいずれかを選択できるwhenため、タスクが簡単になります。特にハッシュ (ハッシュのハッシュ ... サブルーチンのハッシュ) は、テーブル駆動型プログラミングを非常に簡単にします。

ただし、問題が正規表現で簡単に表現できる場合は、代わりにそうする価値があるかもしれません。Perl 正規表現は正規表現に限定されないことに注意してください。そのため、使用する機能に注意する必要があります。正規表現エンジンは高度に最適化されているため、ステート マシンに対する正規表現の主な利点は実行速度です。構文も非常に簡潔であるため、記述が容易になります。/x修飾子に非意味的な空白を含めることができることを忘れないでください:

m{
   .*?    # match anything
   (?:
       a  # followed by an a
     | b  # or a b
   )
}x

と完全に同等です（ただし、より読みやすい）

/.*?(?:a|b)/

したがって、手書きの正規表現は潜在的にはるかに短くなるだけでなく (優れたプログラマーはすべて怠け者です)、多くの楽しみもあります。

次のように状態を定義できます。

my $state_machine = qr{
   ^(?&STATESTART)$

   (?(DEFINE)
     (?<STATESTART> (?&STATE0)    )
     (?<STATE0>     a (?&STATE2)
              |     . (?&STATE1) )
     (?<STATE1>     a (?&STATE2)
              |     . (?&STATE1) )
     (?<STATE2>     ...  )
   )
}x;
print "->$x<- is part of the language" if $x =~ $state_machine;

これは、ハッシュを使用したステート マシンの上記のスケッチに対応します。名前付き正規表現パターンを使用して FSM をモデル化する場合は、末尾再帰のみを使用する必要があることに注意してください。

于 2012-09-13T00:51:31.083 に答える