2

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

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

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

4

1 回答 1

1

“不按我认为的方式工作”和“不正确”并不总是相同的。给定输入

aba

和图案

(ab|a)/ab

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

(ab|a)(ab)

(ab)具有不消耗与之匹配的部分的约束。这可能会更好,因为它消除了一些限制,但由于在编写它时没有任何外部要求lex应该做什么,你不能称行为正确或不正确。

天真的方法的优点是添加尾随上下文不会改变标记的含义,而只是添加一个完全独立的约束来限制它后面的内容。但这确实会导致限制/惊喜:

 {IDENT}  /* original code */

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

糟糕,它不起作用,因为“ab”被吞入 IDENT 正是因为它的含义没有被尾随上下文改变。这变成了一个限制,但也许这是作者为了简单而愿意忍受的限制。(无论如何,使它更具上下文的用例是什么?)

另一种方式呢?这也可能有惊喜:

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

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

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

lex现在由 The Single Unix 规范标准化,它说:

r/x
正则表达式 r 仅在其后出现正则表达式 x 时才应匹配(x 是尾随上下文的实例,下面将进一步定义)。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”,则该规则在其后跟文本“bc”时匹配文本“ab”。在后一种情况下,r 的匹配不能扩展到 x 的开头,因此指定了结果。如您所见,此功能存在一些限制。

未指定的行为意味着有一些关于行为应该是什么的选择,其中没有一个比其他的更正确(如果您希望您的 lex 程序可移植,请不要编写这样的模式)。“如您所见,此功能存在一些限制”。

于 2012-03-19T21:50:15.050 回答