ANTLRv4 : non-greedy rules

Question

我正在阅读明确的 ANTLR4 引用资料，并对其中一个示例(第 76 页)有疑问:

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

该规则匹配典型的 C++ 字符串——包含在 "" 中的字符序列。 , 可以包含 \"也。

在我的期望中，规则 STRING由于非贪婪结构，应该匹配可能的最小字符串。所以如果它看到 \"它会映射 \至 .和 "至 "在规则的末尾，因为这将导致可能的最小字符串。取而代之的是 \"映射到 ESC .我有一个理解问题，因为这不是我所期望的。

这里究竟发生了什么？是不是这样，一个分离的DFA匹配 (ESC|.)第一个，另一个 DFA 匹配 STRING使用已经匹配的字符串 (ESC|.)构造？我不得不承认我还没有读完这本书。

Answer 1

ANTLR 4 词法分析器通常以最长匹配获胜行为运行，不考虑替代项在语法中出现的顺序。如果两个词法分析器规则匹配相同的最长输入序列，则只有比较这些规则的相对顺序才能确定如何分配标记类型。

一旦词法分析器达到非贪婪的可选或闭包，规则中的行为就会改变。从那一刻开始到规则结束，该规则内的所有替代方案都将被视为有序，具有最低替代方案的路径获胜。由于the way we order alternatives in the underlying ATN representation，这种看似奇怪的行为实际上是造成非贪婪处理的原因。 .当词法分析器处于此模式并到达块 (ESC|.) 时，排序约束要求它使用 ESC如果可能的话。