ANTLRv4:非贪婪的规则

Question

我正在阅读明确的ANTLR4参考文献,并对其中一个例子有疑问(第76页):

STRING: '"' (ESC|.)*? '"';
fragment 
ESC: '\\"' | '\\\\' ;

该规则匹配典型的C++字符串 - 包含的char序列"",也可以包含\".

在我的期望中,规则STRING应该匹配可能的最小字符串,因为非贪婪的构造.所以,如果它看到\"它会映射\到.,并"以"在规则的结束,因为这会导致在最小的字符串可能.而不是这个,a \"映射到ESC.我有一个理解问题,因为它不是我所期望的.

这到底发生了什么？是这样的,分离的DFA (ESC|.)首先匹配,而另一个DFA匹配STRING使用已经匹配的(ESC|.)构造字符串？我不得不承认我还没读过这本书.

Answer 1

ANTLR 4词法分析器通常以最长匹配获胜行为运行,而不考虑备选在语法中出现的顺序.如果两个词法分析器规则匹配相同的最长输入序列,则只有这些规则的相对顺序进行比较才能确定如何分配令牌类型.

一旦词法分析器到达非贪婪的可选或闭包,规则内的行为就会发生变化.从该时刻到规则结束,该规则中的所有备选方案都将被视为有序,而具有最低备选方案的路径将获胜.这种看似奇怪的行为实际上是由于我们在底层ATN表示中订购替代方式而导致的非贪婪处理.当词法分析器处于此模式并到达块时(ESC|.),排序约束要求ESC尽可能使用它.