1

一些语言语法在其规则中使用否定。例如，在 Dart 规范中使用了以下规则：

~('\'|'"'|'$'|NEWLINE)

这意味着匹配任何不是括号内规则之一的内容。现在，我知道在 flex 中我可以否定字符规则（例如： [^ab] ，但我想要否定的一些规则可能比单个字符更复杂，所以我认为我不能为此使用字符规则。例如，我可能需要为多行字符串否定序列 '"""' 但我不确定在 flex 中执行此操作的方法是什么。

4

1 回答 1

8

（TL；DR：跳到底部以获得实际答案。）

任何正则语言的逆都是正则语言。所以理论上可以把正则表达式的逆写成正则表达式。不幸的是，这并不总是那么容易。

至少，这个"""案子并不太难。

首先，让我们清楚我们要匹配的内容。

严格来说，“not """”意味着“除"""“之外的任何字符串。但这将包括，例如，x""".

所以说我们正在寻找“任何不包含"""”的字符串可能很诱人。（即 的倒数.*""".*）。但这也不完全正确。典型的用法是对输入进行标记，例如：

"""This string might contain " or ""."""

如果我们从初始字符串开始"""并寻找最长的不包含 的字符串"""，我们会发现：

This string might contain " or "".""

而我们想要的是：

This string might contain " or "".

所以事实证明，我们需要“任何不以结尾"且不包含"""”的字符串，这实际上是两个逆的合取：(~.*" ∧ ~.*""".*)

为此（相对）容易生成状态图：在此处输入图像描述

（请注意，上面与“任何不包含的字符串”的状态图之间的唯一区别"""是，在该状态图中，所有状态都将接受，而在此状态下，状态 1 和状态 2 不接受。）

现在，挑战是将其转回正则表达式。有一些自动化技术可以做到这一点，但它们产生的正则表达式通常又长又笨拙。但是，这种情况很简单，因为只有一个接受状态，我们只需要描述可以在该状态下结束的所有路径：

([^"]|\"([^"]|\"[^"]))*

此模型适用于任何简单的字符串，但当字符串不仅仅是相同字符的序列时，它会稍微复杂一些。例如，假设我们想要匹配以END而不是结尾的字符串"""。天真地修改上述模式将导致：

([^E]|E([^N]|N[^D]))*   <--- DON'T USE THIS

但该正则表达式将匹配字符串

ENENDstuff which shouldn't have been matched

我们正在寻找的真实状态图是在此处输入图像描述

作为正则表达式的一种写法是：

([^E]|E(E|NE)*([^EN]|N[^ED]))

再一次，我通过跟踪所有最终进入状态 0 的方式来产生它：

[^E] stays in state 0
E    in state 1:
     (E|NE)*: stay in state 1
     [^EN]: back to state 0
     N[^ED]:back to state 0 via state 2

这可能是很多工作，无论是制作还是阅读。并且结果容易出错。（使用状态图更容易进行正式验证，对于这类问题来说，状态图很小，而不是使用可能会变得很大的正则表达式）。

实用且可扩展的解决方案

Practical Flex 规则集使用开始条件来解决这类问题。例如，以下是您可能如何识别 python 三引号字符串：

%x TRIPLEQ
start \"\"\"
end   \"\"\"
%%

{start}        { BEGIN( TRIPLEQ ); /* Note: no return, flex continues */ }

<TRIPLEQ>.|\n  { /* Append the next token to yytext instead of
                  * replacing yytext with the next token
                  */
                 yymore();
                 /* No return yet, flex continues */
               }
<TRIPLEQ>{end} { /* We've found the end of the string, but
                  * we need to get rid of the terminating """
                  */
                 yylval.str = malloc(yyleng - 2);
                 memcpy(yylval.str, yytext, yyleng - 3);
                 yylval.str[yyleng - 3] = 0;
                 return STRING;
               }

之所以有效，是因为如果是与 ; 匹配的字符串的一部分，则.开始条件中的规则TRIPLEQ将不匹配。flex 总是选择最长的匹配。使用而不是可以提高效率，因为这会导致更长的匹配，从而减少对;的调用。为了清楚起见，我没有在上面这样写。""{end}[^"]+|\"|\n.|\nyymore()

这个模型更容易扩展。特别是，如果我们想<![CDATA[用作开始和]]>结束，我们只需要更改定义

start "<![CDATA["
end   "]]>"

（如果使用上面建议的优化，则可能是开始条件内的优化规则。）

于 2014-09-21T21:43:42.953 回答