Geek Answers Handbook

Creating an expression tree in Prolog

I am looking for a way to create an expression tree in Prolog. I have already done some experiments and came up with the following working code (which will only process constants and the plus expression):

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.

Is there a simpler alternative to this approach? Should I identify these 4 cases for each of the operators that I plan to add to my program?

+3
prolog dcg expression-trees
source share
2 answers

I think this should do it, although I am not familiar with the pred1(pred2(...)...) :- ... construct pred1(pred2(...)...) :- ... (my Prolog is very rusty).

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

See here another diagram using DCG and a (kind of) lazy rating:

 /* 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).

Using grammars to model data structures is a very useful method in Prolog. The grammar used the implementation of PEG . Dependence on SWI-Prolog is very limited, just the number // 1.

+5
source share

More articles:


All Articles