我试图在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在左递归规则上确实有问题。的开场白解释器就会进入一个无限循环重复调用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
注:除了去掉左递归，我们还可以使用某种形式的表格。
它只是工作。但这并不比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)].