プロローグで 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（何か）（予測）文法です。入力を左から右にウォークし、左端の派生を生成します。それらは簡単に作成できますが、文法はいくつかの制限に準拠している必要があります。
それらを左再帰にすることはできません。無限再帰が発生する可能性があります。これは、再帰パスをたどる前に、少なくとも1つのシンボル（トークン）を入力ストリームから削除する必要があることを意味します。文法をリファクタリングして左再帰を削除するのは、面倒ですが、かなり機械的な作業です。その方法については、まともなコンパイラの本を参照してください。
演算子の優先順位は通常、文法自体の構造に組み込まれています。単純な算術式の構文解析/評価のための再帰下降文法を定義する1つの方法を示す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 の歴史の中で私が観察した最も奇妙なことの 1 つです。つまり、間違った式の構文がすでに何年も前から示されています。誤った構文は 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 ではありません。しかし、たとえばプッシュバックによって、次の行に沿ってカットを排除することができます. プッシュバックは、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), [')'].