Prolog中数学表达式DCG实现的循环与重复匹配问题排查

问题1：匹配时的递归循环原因 #

你的DCG存在左递归和交叉递归的双重问题：

• 左递归：addsubexpr --> addsubexpr, restaddsubexpr和divmulexpr --> divmulexpr, restdivmulexpr都是左递归规则。Prolog采用深度优先搜索，左递归会让解释器不断展开同一个规则，无法终止。
• 交叉递归：divmulexpr里的operator(lparen), addsubexpr, operator(rparen)规则，让divmulexpr依赖addsubexpr，而addsubexpr又依赖divmulexpr，形成了循环依赖路径：addsubexpr → divmulexpr → addsubexpr → ...，匹配时会不断进入这个循环分支，无法退出。

问题2：无限返回true的原因 #

你的规则中大量存在空匹配分支（比如restaddsubexpr --> []、restdivmulexpr --> []），加上左递归的存在，导致Prolog回溯时会不断尝试“匹配空+展开左递归”的无效路径：
当第一次匹配成功后，解释器会回溯寻找其他可能的匹配方式，此时会选择restaddsubexpr的空分支，然后再次触发addsubexpr的左递归展开，而因为空匹配不需要消耗输入，这个过程可以无限重复，最终返回无限个true。

修复方案 #

核心是消除左递归，同时调整规则顺序避免无效回溯，把左递归改成右递归结构，让规则优先匹配非空分支，再处理空情况：

修改后的DCG代码：

lex(add, '+').
lex(sub, '-').
lex(mul, '*').
lex(div, '/').
lex(lparen, '(').
lex(rparen, ')').
lex(num, X) :- number(X).

expr --> addsubexpr.
expr --> [].  % 保持空表达式，但放在非空规则之后

% 把addsubexpr的左递归改成右递归：先匹配divmulexpr，再处理后续的加减操作
addsubexpr --> divmulexpr, rest_addsub.

rest_addsub --> operator(Op), divmulexpr, { Op = add; Op = sub }, rest_addsub.
rest_addsub --> [].  % 空分支放在最后

% 同理修改divmulexpr的左递归
divmulexpr --> primary, rest_divmul.

primary --> [Num], { lex(num, Num) }.
primary --> operator(lparen), addsubexpr, operator(rparen).

rest_divmul --> operator(Op), primary, { Op = mul; Op = div }, rest_divmul.
rest_divmul --> [].

operator(Op) --> [X], { lex(Op, X) }.

修改要点说明： #

1. 消除左递归：将addsubexpr --> addsubexpr, restaddsubexpr改为addsubexpr --> divmulexpr, rest_addsub，让规则从基础表达式开始，再递归处理后续操作，避免无限展开。
2. 拆分primary规则：把原divmulexpr里的数字和括号表达式拆成独立的primary规则，切断divmulexpr和addsubexpr的直接交叉递归，让依赖链变成addsubexpr → divmulexpr → primary → addsubexpr，但此时primary的括号分支只会在遇到(时触发，不会无差别进入循环。
3. 调整空分支顺序：把空匹配规则放在对应递归规则的最后，让解释器优先尝试非空的有效匹配，减少无效回溯。
4. 简化条件判断：把操作符的判断移到rest_addsub和rest_divmul的头部，避免在递归末尾做条件检查导致的回溯浪费。

现在测试addsubexpr([1, '+', 2], [])，只会返回一次true，且不会出现递归循环。

内容的提问来源于stack exchange，提问作者Agustín Nieto García