(F)Lex,我如何匹配否定？

Question

一些语言语法在规则中使用否定.例如,在Dart规范中使用以下规则:

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

这意味着匹配任何不是括号内的规则之一的东西.现在,我知道在flex中我可以否定字符规则(例如:[^ ab],但是我想要否定的一些规则可能比单个字符更复杂,所以我认为我不能使用字符规则.例如,我可能需要否定多行字符串的序列'"""',但我不确定在flex中这样做的方法是什么.

Answer 1

(TL; DR:跳到底部以获得实际答案.)

任何常规语言的反面都是常规语言.因此理论上可以将正则表达式的反转写为正则表达式.不幸的是,这并不容易.

"""至少,这个案子并不太难.

首先,让我们清楚一下我们想要匹配的东西.

严格来说,"不""""意味着"除了"""" 以外的任何字符串.但那将包括,例如,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

这可能是很多工作,无论是制作还是阅读.结果很容易出错.(使用状态图更容易进行形式验证,状态图对于这类问题而言较小,而不是使用可能变得非常大的正则表达式).

实用且可扩展的解决方案

实用的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   "]]>"

(如果使用上面建议的优化,可能是启动条件内的优化规则.)