我正在尝试在 prolog 中解决 DCG 语法并成功了，我一直在评估涉及这些大括号的表达式。
expr( T, [’(’, 5, +, 4, ’)’, *, 7], []),
expr(Z) --> num(Z).
expr(Z) --> num(X), [+], expr(Y), {Z is X+Y}.
expr(Z) --> num(X), [-], expr(Y), {Z is X-Y}.
expr(Z) --> num(X), [*], expr(Y), {Z is X*Y}.
num(D) --> [D], {number(D)}.
eval(L, V, []) :- expr(V, L, []).
Prolog 的 DCG 语法实现的解析器是递归下降 LL( something )（预测）语法。它从左到右遍历输入，并在执行过程中产生最左侧的推导。它们很容易制作，但语法必须符合一些限制：
它们不能是左递归的。无限递归可以/将产生。这意味着在遵循递归路径之前，必须从输入流中删除至少一个符号（令牌）。重构语法以删除左递归是一项相当机械的练习，尽管很乏味。有关如何做到这一点，请参阅任何体面的编译器书籍。
运算符优先级通常内置于语法本身的结构中。这是 BNF 表示法，显示了一种定义递归下降语法以解析/评估简单算术表达式的方法：
ArithmeticExpression : AdditiveExpression
;
AdditiveExpression : MultiplicativeExpression
| MultiplicativeExpression '+' AdditiveExpression
| MultiplicativeExpression '-' AdditiveExpression
;
MultiplicativeExpression : ExponentialExpression
| ExponentialExpression '*' MultiplicativeExpression
| ExponentialExpression '/' MultiplicativeExpression
| ExponentialExpression '%' MultiplicativeExpression
;
ExponentialExpression : UnaryExpression
| UnaryExpression '^' ExponentialExpression
;
UnaryExpression : '-' UnaryExpression
| AtomicExpression
;
AtomicExpression : '(' ArithmeticExpression ')'
| ['0'..'9']+
;
每个运算符优先级的术语是从下一个更高优先级的表达式构建的。因此，任意算术表达式只是一个加法表达式。
每个加法表达式是 1 个或多个乘法表达式，由加法和减法运算符连接。
每个乘法表达式是 1 个或多个指数表达式，由乘法、除法和余数运算符连接。
每个指数表达式都是一个一元表达式，带有一个选项指数运算符，后跟另一个一元表达式。
每个一元表达式要么是一个原子表达式，要么是一个一元减号，后跟另一个一元表达式。
每个原子表达式要么是括在括号中的任意算术表达式，要么是无符号整数标记。
将上述内容转换为 Prolog 的 DCG 语法应该很简单。如何评价语法中每个子句所代表的术语应该是不言而喻的。
这是我在 Prolog 历史上观察到的最奇怪的事情之一。也就是说，错误的表达式语法已经出现了很长时间。在 DEC10 Prolog 文档中已经发现了错误的语法，当我们查看规则时可以看到不合适的语法：
expr(Z) --> num(X), "/", expr(Y), {Z is X/Y}.
etc..
这使得除法运算符 xfy，但它应该是 yfx。因此，根据上述规则，表达式 10/2/5 被读取为 10/(2/5) 并导致 25 作为结果。但事实上，这个例子应该被解读为 (10/2)/5 产生 1 作为结果。
问题是正确的语法将是递归的。DCG 确实存在左递归规则的问题。Prolog 解释器会通过重复调用 expr/3 进入左递归规则的无限循环：
expr(Z) --> expr(X), "/", num(Y), {Z is X/Y}
etc..
所以解决方案是通过引入累加器和附加规则来消除左递归。我不知道这种方法是否普遍有效，但在目前的情况下它肯定有效。因此，正确且深度优先的可执行规则应为：
expr(Y) --> num(X), expr_rest(X,Y).
expr_rest(X,T) --> "/", !, num(Y), {Z is X/Y}, expr_rest(Z,T).
etc..
expr_rest(X,X).
上面的语法是有点难度的DCG。它不再是纯 Prolog，因为它使用了 cut (!)。但是我们可以消除削减，例如通过后推，类似于以下几行。在 DCG 介绍中，推回再次是一个复杂的问题，我们需要在表达式的末尾引入一个停止字符以使其工作：
etc..
expr_rest(X,X), [C] --> [C], {not_operator(C)}.
或者我们既不能进入剪切或推回的长度，也不能忍受在回溯时解析器会做额外的工作，在目前的情况下是不必要的工作。所以底线可能是，虽然这个例子不正确，但解释 DCG 很简单，不需要太多高级的 DCG 东西。
有趣的是，缺少的括号语法几乎不受左递归消除的影响。只需添加：
num(X) --> "(", !, expr(X), ")".
哎呀，又砍了！
最好的祝福
完整代码可以在这里看到：http: //www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/06_bench/09_programs/10_calculator/01_calculator.p.html
PS：除了消除左递归之外，我们还可以使用某种形式的表格。
它只是工作。然而，它并不比 yacc/bison 容易。
%?-eval('11*(7+5-2)^2*(11+8)').
eval(A) :- lex(A,L), evallist(L).
%?-evallist([11,*,'(',7,+,5,-,2,')',^,2,*,'(',11,+,8,')']).
evallist(L) :- e(R,L,[]),write(R),!.
e(N) --> t(N1), erest(N1,N).
erest(N1,N) --> [+], !, t(N2), {N3 is N1+N2}, erest(N3,N);
[-], !, t(N2), {N3 is N1-N2}, erest(N3,N).
erest(N,N) --> [].
t(N) --> f(N1), trest(N1,N).
trest(N1,N) --> [*], !, f(N2), {N3 is N1*N2}, trest(N3,N);
[/], !, f(N2), {N3 is N1/N2}, trest(N3,N).
trest(N,N) --> [].
f(N) --> n(N);
n(N1), [^], f(N2), {N is N1**N2}.
n(N) --> ['('], !, e(N), [')'];
[-], !, e(N1), {N is -N1};
num(N).
num(N) --> [N], {number(N)}.
lex(A,NL) :-
atom_chars(A,L), lex0(_,L,NL).
lex0(S,L,NL) :-
L=[], (number(S), NL=[S], !; NL=[]), !;
L=[E|R], (d(E,N), (number(S), !; S=0), S1 is S*10+N, lex0(S1, R, NL), !;
lex0(_,R,NR), (number(S), NL=[S|[E|NR]], !;
NL=[E|NR])).
d(I,N) :-
char_code(I,C), C > 47, C < 58, N is C - 48.
添加此子句似乎有效：num(D) --> ['('], expr(D), [')'].
感谢@vladimir lidovski 并基于 BNF 表示法（并根据我的需要），我将其扩展为还包括逻辑表达式。这是我的代码（要查看完整的解释器，请查看我的git repo）：
cond_expre(T) --> and_expre(E1), or_rest(E1,T).
or_rest(E1,T) --> [punct('|'),punct('|')],!, and_expre(E2), {V = (\/,E1,E2)}, or_rest(V,T).
or_rest(T,T) --> [].
and_expre(T) --> equality_expre(E1), and_rest(E1,T).
and_rest(E1,T) --> [punct(&),punct(&)], !, equality_expre(E2), {V = (/\,E1,E2)}, and_rest(V,T).
and_rest(T,T) --> [].
equality_expre(T) --> relat_expre(E1), equality_rest(E1,T).
equality_rest(E1,T) --> equality_op(Op) ,!, relat_expre(E2), { V=(Op,E1,E2)}, equality_rest(V,T).
equality_rest(T,T) --> [].
relat_expre(T) --> atomic_texpre(E1), relat_rest(E1,T).
relat_rest(E1,T) --> relat_op(Op) ,!, atomic_texpre(E2) , { V=(Op,E1,E2) },relat_rest(V,T).
relat_rest(T,T) --> [].
atomic_texpre(T) --> arith_expre(T); [punct('(')], !, cond_expre(T), [punct(')')] .
arith_expre(V) --> expre(V).
equality_op(==) --> [punct(=),punct(=)].
equality_op(\=) --> [punct(!),punct(=)].
relat_op(>=) --> [punct(>),punct(=)].
relat_op(>) --> [punct(>)].
relat_op('=<') --> [punct(<),punct(=)].
relat_op(<) --> [punct(<)].
expre(N) --> multiplicative(N1), additive_rest(N1,N).
additive_rest(N1,N) --> [punct('+')], !, multiplicative(N2), {N3 = (+,N1,N2)}, additive_rest(N3,N);
[punct('-')], !, multiplicative(N2), {N3 = (-,N1,N2)}, additive_rest(N3,N).
additive_rest(N,N) --> [].
multiplicative(N) --> atomic(N1), multiplicative_rest(N1,N).
multiplicative_rest(N1,N) --> [punct('*')], !, atomic(N2), {N3 = (*,N1,N2)}, multiplicative_rest(N3,N);
[punct('/')], !, atomic(N2), {N3 = (/,N1,N2)}, multiplicative_rest(N3,N);
[punct('%')], !, atomic(N2), {N3 = (mod,N1,N2)}, multiplicative_rest(N3,N).
multiplicative_rest(N,N) --> [].
atomic(N) --> [punct('(')], !, expre(N), [punct(')')]; num(N).
num(N) --> pl_constant(N).
pl_constant(num(N)) --> pl_integer(N), !.
pl_constant(id(X)) --> identifier(X), {call(id(X,_)) }. %Not sure if I remember what it does but I think, the right most call I wrote to assure that the variable is already registered in the cache so that a value can later be retrieved from it
pl_integer(X) --> [number(X)]. %the value on the right works together with a tokenizer library -> :- use_module(library(tokenize)). It's basically a token labled as a number. Same with the next line.
identifier(X) --> [word(X)].