Re: Expression simplifier.

Full algebraic expression simplification actually takes quite a lot of
mechanism above and beyond a parse tree. You also need a way to
prettyprint the result, ways to write down pattern-base rewriting
rules (usually augmented by procedural transforms to handle things
patterns don't do well), and metaprogramming methods to control when,
how, and where such rules are applied. (The useful rule ?x+?y ->
?y+?x can cause looping behavior if indiscrimately applied) More
complications come from trying to match expressions in the face of
associative and/or commutative operators. (e.g., x+5+-x "should" be
matched by ?p+-?p -> 0, but won't be if you are doing pure tree
matches).


If you only want to do very simple "simplfications", you can probably
implement enough by hand. If you want to anything sophisticated,
you're in for a lot of work to replicate all the required machinery.
*Then* you get to encode enough rules about mathematics to carry of
your desired task.


I don't know if Matlab offers symbolic rewriting, but my suspicion is
that you wouldn't have asked if it did. Mathematica (which I have
nothing to do with except being a heavy-duty user once), has much of
the mechanism you need already built it. However, Mathematica makes
you adopt *their* lisp-like expression syntax.


If you want a tool which can accept arbitrary grammars, and which has
all the other machinery needed to accept simplification rules written
in the target syntax, you should look at the DMS Software
Reengineering Toolkit. See
http://www.semdesigns.com/Products/DMS/DMSToolkit.html.


Your particular example could be handled by DMS with the following rules:
        rule normalize_subtract(p1:product,p2:product):sum->sum = "\p1-\p2" =
"\p1+(-1*\p2)"
          rule remove_add_zero(e:sum): sum -> sum = "\e+0" -> "\e".
          rule remove_multiply_one(e:product): product -> product = "\e*1" ->
"\e".
          rule combine_coefficients(p:product,t:term,):sum->sum = "\p*\t+\t" ->
"(\p+1)*\t".
          rule constant_add(n1:NUMBER,n2:NUMBER):sum->sum ="\n1+\n2" ->
"\sum(\n1,\n2)".
and an auxuilary procedure sum that takes two numbers and adds them.


--
Ira D. Baxter, Ph.D. CTO Semantic Designs, Inc.
http://www.semdesigns.com


"Rasmus Anthin" <e8rasmus@etek.chalmers.se> wrote in message
> I need to simplify expressions in strings using matlab


> Now to the problem: I have implemented the scanner and parser and the
> parser tree is of the matlab type cell-array


> Now, generating the tree was easy and it seems to work correctly. The
> result I want to get is a simplification of an expression like:
>
> » simplify('(sin(x+y+0)/(1*1*r))-4*x+x')
>
> sin(x+y)/r-3*x
>
> But how can I minimize the parser tree in order to establish such a
> result as the example above? Should I use some form of intermediate
> expressions? What methods should I use etc...

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