30 Apr 2001 00:53:16 -0400

Related articles |
---|

Expression simplifier. e8rasmus@etek.chalmers.se (Rasmus Anthin) (2001-04-29) |

Re: Expression simplifier. e8rasmus@etek.chalmers.se (Rasmus Anthin) (2001-04-30) |

Re: Expression simplifier. Brian.Inglis@SystematicSw.ab.ca (2001-04-30) |

Re: Expression simplifier. idbaxter@semdesigns.com (Ira D. Baxter) (2001-04-30) |

Re: Expression simplifier. e8rasmus@etek.chalmers.se (Rasmus Anthin) (2001-05-03) |

From: | "Ira D. Baxter" <idbaxter@semdesigns.com> |

Newsgroups: | comp.compilers |

Date: | 30 Apr 2001 00:53:16 -0400 |

Organization: | Posted via Supernews, http://www.supernews.com |

References: | 01-04-145 |

Keywords: | optimize |

Posted-Date: | 30 Apr 2001 00:53:16 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.