Antlr4直接右递归语法输入单个'a'报错问题咨询

问题重现 #

初始语法：

exp: 'a' exp | 'a';

输入单个'a'时，报错：

line 1:1 mismatched input '<EOF>' expecting 'a'

修改后的语法可正常匹配单'a'：

exp: 'a' exp 'a'| 'a';

原因解析 #

初始语法报错的核心原因 #

ANTLR4的LL(*)解析器采用贪婪匹配策略，会优先尝试匹配更长的语法分支。对于初始语法的右递归规则'a' exp，当输入单个'a'时：

1. 解析器先匹配第一个'a'；
2. 接着尝试递归调用exp规则，此时剩余输入是<EOF>；
3. exp的两个分支都要求以'a'开头，无法匹配<EOF>，因此抛出"期望'a'但遇到EOF"的错误。
   解析器不会主动回溯去尝试'a'这个基础分支，因为它优先选择了带递归的更长分支。

两种语法的差异 #

1. 初始语法：右递归分支'a' exp属于"前缀递归"——递归调用紧跟在匹配的'a'之后，没有后续终止符号约束。这种结构下，解析器匹配前缀'a'后，必须继续匹配exp的内容，而单'a'的剩余输入无法满足exp的起始要求，导致报错。
2. 修改后语法：递归分支'a' exp 'a'是"前后缀包裹的递归"——递归调用被两个'a'包裹。当输入单'a'时：
   • 解析器尝试匹配递归分支，匹配第一个'a'后，递归调用exp发现剩余输入是<EOF>，无法满足后续需要匹配'a'的要求；
   • 此时解析器会回溯，选择'a'这个基础分支，从而成功完成匹配。

内容的提问来源于stack exchange，提问作者Frank