Re: Algorithm

  "Amit M. Rao" <arao@ececs.uc.edu> writes:
> I am looking for an algorithm that enumerates all possible expression
> trees obtained by applying the commutative law to an expresssion tree.


A natural application of Prolog. Here's the program:


tree_com(A=B,A1=B1):- tree_com(A,A1), tree_com(B,B1).
tree_com(A+B,A1+B1):- tree_com(A,A1), tree_com(B,B1).
tree_com(A+B,B1+A1):- tree_com(A,A1), tree_com(B,B1).
tree_com(A*B,A1*B1):- tree_com(A,A1), tree_com(B,B1).
tree_com(A*B,B1*A1):- tree_com(A,A1), tree_com(B,B1).
tree_com(T,T):-atom(T).


And here's the query and its solutions for your example:


?- tree_com(a = b * c + d, X).


X = a=b*c+d ? ;


X = a=c*b+d ? ;


X = a=d+b*c ? ;


X = a=d+c*b ? ;


no


- anton
--
M. Anton Ertl Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html
--

Return to the comp.compilers page.
Search the comp.compilers archives again.