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 是等效的）

等等。要在 Perl 中编写开关，您可以在源过滤器、given-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 回答