java - 如何为 ANTLR 中的模糊输入生成多个解析树

Question

我面临一个模棱两可的情况，输入字符串可以使用不同的规则进行解析，我需要考虑这两个选项并为它们生成多个解析树。

为简单起见，考虑像“Alber Johanson”这样的人名，这个名字可以解析为

(fullName (firstName Alber) (lastName Johanson)) 

或解析为

(fullName (firstName Alber) (lastName Johan) (relation son)) 

首先，如何配置规则来处理第二种情况？因为它是第二个字符串的一部分，而不是单独的标记。

其次，如何为输入字符串的所有可能选项生成解析树？

更新

这是我的语法示例，它只能用于解析第一种情况而不能用于第二种情况

fullName: firstName lastName | firstName lastName relation;
firstName: NAME;
lastName: NAME;
relation: REL;

NAME: ('a'..'z'|'A'..'Z')+;
REL: 'son';

WHITESPACE : ('\t' | ' ' | '\r' | '\n'| '\u0020' | '\u000C' )+ -> skip ;

Answer 1

ANTLR 不允许您按照自己的方式进行操作。然而，原因不是歧义，而是分词器。

由于 ANTLR 的词法分析策略，“Johanson”这个词总是被词法分析为 NAME:

• 返回匹配最长的Token
• 如果两个标记匹配的长度相同，则首选第一个定义的

token REL 永远不会出现，因为

• 任何带有后缀“son”的单词都是NAME(最长匹配)
• 任何前缀为“son”的词都是NAME(最长匹配)
• 然而，一个孤立的单词 'son' 是一个 NAME(REL 匹配但未首先定义)

第一个问题的答案: 它不能由 ANTLR 解析器处理，因为它依赖于解析前的标记化。您有两个选择:

• 使用解析器生成器允许您对解析器进行标记化(PEG 解析器就像半熟的，老鼠应该这样做)
• 丢弃标记 REL，并在访问解析树时重新解析姓氏

第二个问题的答案:

上述两种选择都很难解决打印同一字符序列的可能解释的问题。

PEG-Parsers 被设计为优先选择第一个替代方案，如果找到有效的解释，它不会进一步探索。

ANTLR 还没有被设计用来驱动由解析器引导的词法分析器。如果您决定重新解析姓氏，使用纯 Java 查找解释可能比编写新的词法分析器/解析器来查找它们更容易。