Lex 对前瞻运算符的错误算法



在Andrew Appel的"Java中的现代编译器实现"中,他在一个练习中声称:

Lex有一个先行运算符/,因此正则表达式abc/def只有在后面跟着def时才与abc匹配(但def不是匹配字符串的一部分,而是下一个令牌的一部分)。Aho等人[1986]描述,Lex[Lesk 1975]使用了一种不正确的算法来实现前瞻性(它在(a|ab)/ba上失败,输入aba,在它应该匹配a的地方匹配ab)。Flex[Paxson 1995]使用了一种更好的机制,该机制对(a|ab)/ba正确工作,但失败了(在zx*/xy*上显示警告消息)。设计一个更好的前瞻机制。

有人知道他所描述的解决方案吗?

"不按我认为的方式工作"one_answers"不正确"并不总是一回事。给定输入

aba

和图案

(ab|a)/ab

(ab|a)贪婪地匹配然后单独应用/ab约束是有一定意义的。您认为它应该像以下正则表达式一样工作:

(ab|a)(ab)

具有不消耗由CCD_ 2匹配的部分的约束。这可能更好,因为它消除了一些限制,但由于在编写lex时没有任何外部要求,因此不能称行为正确或不正确。

这种天真的方式的优点是,添加尾随上下文不会改变令牌的含义,只是添加了一个完全独立的约束条件。但这确实会带来限制/惊喜:

 {IDENT}  /* original code */
 {IDENT}/ab   /* ident, only when followed by ab */

糟糕的是,它不会起作用,因为"ab"被IDENT吞噬,正是因为它的含义没有被后面的上下文改变。这变成了一种限制,但也许这是作者为了换取简单而愿意接受的限制。(无论如何,让它更有上下文的用例是什么?)

换个路怎么样?这也可能带来惊喜:

 {IDENT}/ab  /* input is bracadabra:123 */

假设用户希望它不匹配,因为bracadabra不是后面跟(或以)ab的标识符。但是{IDENT}/ab将匹配bracad,然后在输入中保留abra:123

无论你如何确定语义,用户的期望都可能被挫败。

lex现在是由单一Unix规范标准化的,它说:

r/x
只有当正则表达式r后面出现正则表达式x(x是尾随上下文的实例,在下文中进一步定义)时,才应匹配正则表达式r。yytext中返回的令牌只能与r匹配。如果r的尾部与x的开头匹配,则未指定结果。r表达式不能包含进一步的尾随上下文或"$"(匹配行尾)运算符;x不能包含"^"(匹配行首)运算符、尾部上下文或"$"运算符。也就是说,lex正则表达式中只允许出现一个尾随上下文,并且"^"运算符只能用于此类表达式的开头。

所以你可以看到这里有解释的空间。r和x可以被视为单独的正则表达式,以正常方式计算r的匹配,就好像它是单独的一样,然后x作为一个特殊约束应用。

规范也讨论了这个问题(你很幸运):

以下示例阐明了lex正则表达式与本卷IEEE Std 1003.1-2001中其他地方出现的正则表达式之间的差异。对于形式为"r/x"的正则表达式,总是返回与r匹配的字符串;当x的开头与r的尾部匹配时,可能会出现混淆。例如,给定正则表达式"a*b/cc"和输入"aaabcc",yytext将在此匹配中包含字符串"aaab"。但是,给定正则表达式"x*/xy"和输入"xxxy",某些实现会返回标记xxx,而不是xx,因为xxx与"x*"匹配。

在规则"ab*/bc"中,r末尾的"b*"将r的匹配扩展到尾部上下文的开头,因此未指定结果。但是,如果此规则为"ab/bc",则当文本"ab"后面跟着文本"bc"时,该规则将与文本"ab"匹配。在后一种情况下,r的匹配不能扩展到x的开头,因此指定了结果。正如您所看到的,这个功能有一些局限性。

未指定的行为意味着有一些关于行为应该是什么的选择,没有一个比其他选择更正确(如果你想让lex程序是可移植的,就不要写这样的模式)。"正如您所看到的,这个功能有一些局限性"。

最新更新