Erstellen eines Ausdrucksbaums in Prolog

dcg expression-trees prolog

Frage

Ich suche nach einer Möglichkeit, einen Expression Tree in Prolog zu erstellen. Ich habe bereits einige Experimente gemacht und den folgenden Arbeitscode entwickelt (der nur mit Konstanten und dem Plus-Ausdruck umgehen wird):

const(_).
plus(_, _).

eval(const(R), R).

eval(plus(A, B), R) :- number(A), number(B), R is A+B.
eval(plus(A, B), R) :- number(A), eval(B, B_R), R is A+B_R.
eval(plus(A, B), R) :- eval(A, A_R), number(B), R is A_R+B.
eval(plus(A, B), R) :- eval(A, A_R), eval(B, B_R), R is A_R+B_R.

Gibt es eine einfachere Alternative zu diesem Ansatz? Muss ich diese 4 Fälle für jeden der Operatoren definieren, die ich meinem Programm hinzufügen möchte?

Akzeptierte Antwort

Ich denke, das sollte es tun, obwohl ich das Konstrukt pred1(pred2(...)...) :- ... nicht pred1(pred2(...)...) :- ... (mein Prolog ist sehr rostig).

eval(A, A) :- number(A).
eval(plus(A, B), R) :- eval(A, A_R), eval(B, B_R), R is A_R+B_R.

Beliebte Antwort

Sehen Sie hier ein anderes Schema, das DCG und (eine Art) faule Auswertung ausnutzt:

/*
File:    dcg_calculator.pl
Author:  Carlo,,,
Created: Aug 16 2011
Purpose: associativity and precedences in calculator
*/

:- module(dcg_calculator, [dcg_calculator/2, expr//1]).
%- [library(http/dcg_basics)]. obsolete
:- [library(dcg/basics)].

/* usage

?- dcg_calculator("1+(-2-2)",S),V is S.
S = 1+ (-2-2),
V = -3 ;
false.

*/
dcg_calculator(Formula, IsEvaluable) :-
    phrase(expr(IsEvaluable), Formula, []).

expr(Evaluable) -->
    sum(Evaluable).

sum(S) -->
    product(P), sum_1(P, S).
sum_1(L, S) -->
    "+", product(P), sum_1(L + P, S);
    "-", product(P), sum_1(L - P, S);
    {L = S}.

product(P) -->
    value(V), product_1(V, P).
product_1(V, P) -->
    "*", value(U), product_1(V * U, P);
    "/", value(U), product_1(V / U, P);
    {V = P}.

% value(V) -->
%   {var(V)} -> {V=0 /* between(0, 9, V)*/ }, "0".

value(V) -->
    "(", expr(V), ")" ;
    number(V).

Mit Grammatiken zum Modellieren von Datenstrukturen ist es eine sehr nützliche Technik in Prolog. Die verwendete Grammatik ist eine Implementierung von PEGs . Abhängigkeit von SWI-Prolog ist sehr begrenzt, nur Nummer // 1.



Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum
Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum