Perl有限状态机,用于快速解析,正则表达式生成

Question

我需要匹配非常短的文本段(1到7个字母),并且我知道如何在有限状态机中指定可接受的字符串.我认为为这个应用程序构建一个正则表达式会变得太乱,难以维护.我需要一个易于使用的模块,我可以编写一个FSM,如果模块可以生成一个正则表达式供我使用,那将是一个很大的好处.有没有人知道一个可以做到这一点的模块？

Answer 1

即使没有模块,编写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时,您应该只进行尾递归.