构建正则表达式

Question

我需要为 +/- 字符不能并排（必须由其他字符分隔）的字符串构建正则表达式。我得到了这个选项： (a*(+|-)a)* ，其中 a 是任何字符， * 是 Kleene 闭包， () 是为了清楚起见。但是这个表达式不识别以下形式的行：“+”、“-”、“+ a-”等。也许有人能把我从死点中解救出来。我需要规律性来构建有限自动机。

Answer 1

可能会：

^(\+(?![\+-])|-(?![\+-])|[^\+-])*?$

它将所有内容限制在一行中：^ 到 $。惰性量词 ()*? 确保不会识别超过一行。

括号内的3个拼接如下：

\+(?![\+-])如果字符是+下一个必须不是是+或 -
-(?![\+-])如果字符是-下一个必须不是是+或 -
前两个只有第二个字符向前看，可以组合成一个连接：[\+-](?![\+-]).
[^\+-] 任何不是 + 和 -

不过，你要知道，一个regex比一个regular expression更厉害。比起正则表达式，你更需要正则语法：

S = +T
S = -T
S = @S
S = ε

T = @S
T = ε

此文法是右正则的，@ 是任何不属于 + 或 - 的字符。 ε 是 epsilon = 无。

这是确定性有限自动机（其中 P=+ M=- @=not + and not -）：

  /---- @ ----\
  |           |
  |           v
(S = start/final)--- P,M -->(T = final)---- P,M --->(error)
      ^                          |         
      |                          |         
      \----------- @ ------------/

构建正则表达式

Build regular expression

finite-automata

regular-language