Prolog 循环中的数学表达式 DCG

Question

我正在尝试在 Prolog 中实现数学表达式的 DCG，因为我想做用该语言实现计算器的基本练习，这是我的代码：

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

expr --> [].
expr --> addsubexpr.

addsubexpr --> divmulexpr.
addsubexpr --> addsubexpr, restaddsubexpr.

restaddsubexpr --> [].
restaddsubexpr --> operator(Op), addsubexpr, restaddsubexpr, { Op = add; Op = sub }.

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

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

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

我现在有两个问题：

1. 当我针对简单的示例调用它时，它会循环：

   addsubexpr([1, '+', 2], []).

   。它循环的语句是这样的：

   divmulexpr --> operator(lparen), addsubexpr, operator(rparen).

   ——基本上它正在做

   expr -> addsubexpr -> divmulexpr -> addsubexpr -> ...

   ，或者这就是我通过跟踪它所理解的。
2. 对于像

   addsubexpr([1, '+', 2], []).

   这样的表达式，它会给出无限的

   true

   ，而它应该只返回

   true

   一次，因为我没有给它任何可以使用的变量。

我真的不知道是什么可能导致这些问题，因为据我所知语法写得正确。如果有人可以告诉我其中的原因，我将不胜感激。特别是第二个问题在我的序言程序中很常见。

Answer 1

我搞砸了，也许是因为太累了。

addsubexpr --> addsubexpr, restaddsubexpr.

和

divmulexpr --> divmulexpr, restdivmulexpr.

中明显存在左递归。

这是更正后的语法：

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

expr --> [].
expr --> addsubexpr.

addsubexpr --> divmulexpr, restaddsubexpr.

restaddsubexpr --> [].
restaddsubexpr --> operator(Op), addsubexpr, restaddsubexpr, { Op = add; Op = sub }.

divmulexpr --> num, restdivmulexpr.
divmulexpr --> operator(lparen), addsubexpr, operator(rparen).

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

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