为何修改Nearley语法分支后出现循环？请解析原因

我来帮你理清这个循环问题的根源，其实是Nearley处理左递归语法的逻辑导致的～

先看原来的语法为什么没问题 #

你最初的composition规则是：

composition -> _ expression _ {% nuller %}
| composition _ "," _ rank {% nuller %}

这里的递归分支是composition _ "," _ rank，其中rank是终端符号（直接匹配输入中的单个扑克牌点数字符）。当解析器处理递归时，每一次递归都需要消耗明确的输入（逗号+点数字符），解析器可以通过查看输入流的内容，判断什么时候停止递归（当没有逗号时，就会匹配基础情况_ expression _），所以不会出现无限循环。

修改后出现循环的原因 #

当你把递归分支里的rank改成expression后，规则变成了：

composition -> _ expression _ {% nuller %}
| composition _ "," _ expression {% nuller %}

这里的问题出在：递归分支的后续部分是非终结符expression，而Nearley在处理左递归规则时，会优先尝试展开左递归分支——也就是先假设已经有一个composition，然后再去匹配_ "," _ expression。但为了匹配前面的composition，解析器又需要再次展开composition的规则，如此循环往复，陷入无限递归，永远无法回到基础情况（_ expression _）。

再加上_规则允许匹配空空白（[\s]:*可以匹配0个空白字符），这让解析器更难判断递归的终止边界，进一步加剧了循环问题。

解决办法：用重复运算符替代显式左递归 #

Nearley支持用:*（零或多次重复）这类运算符来处理重复结构，这样可以避免手动写左递归带来的问题。修改后的语法如下：

@{% function nuller() { return null; } %}
main -> _ composition _ {% nuller %}
composition -> expression (_ "," _ expression):* {% nuller %}
expression -> _ rank _ {% nuller %}
rank -> [a, k, q, j, t, A, K, Q, J, T, 2-9] {% nuller %}
_ -> [\s]:* {% nuller %}

这个规则的逻辑是：先匹配一个基础的expression，然后匹配零个或多个逗号+expression的组合。解析器会按顺序处理输入，不会陷入无限递归，完美解决你的问题。

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