30 Apr 2001 00:52:36 -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: | Brian.Inglis@SystematicSw.ab.ca |

Newsgroups: | comp.compilers |

Date: | 30 Apr 2001 00:52:36 -0400 |

Organization: | Systematic Software |

References: | 01-04-145 |

Keywords: | optimize |

Posted-Date: | 30 Apr 2001 00:52:36 EDT |

On 29 Apr 2001 02:14:50 -0400, Rasmus Anthin

<e8rasmus@etek.chalmers.se> wrote:

*>I need to simplify expressions in strings using matlab. I must say*

*>that programming scanners and parsers in matlab is very time saving*

*>and the code becomes very compact ideed (the scanner is only 14 lines*

*>long!).*

*>*

*>Now to the problem: I have implemented the scanner and parser and the*

*>parser tree is of the matlab type cell-array. The nonterminals/productions*

*>used are:*

*><expression> ::= [<add_op>] <term> {<add_op> <term>}*

*><term> ::= <factor> {<mul_op> [<add_op>] <factor>}*

*><factor> ::= <primary> {<pow_op> [<add_op>] <primary>}*

*><primary> ::= "(" <expression> ")" | <func_call> | <id>*

*><func_call> ::= <id> "(" <expressions> ")"*

*><expressions> ::= <expression> {"," <expression>}*

*><id> := a letter followed by letters and/or numbers*

*><add_op> := "+" | "-"*

*><mul_op> := "*" | "/" | "\"*

*><pow_op> := "^"*

*>*

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

*>*

*>Any ideas?*

*>*

*>Please help, I have really struck into the wall on this one :(*

*>*

*>[I'd have a set of tree rewriting patterns, e.g. X+0 -> X -John]*

Expanding on John's comment, you have to identify common

variables in terms and factors, use identities e.g. +0, *1, x/x,

etc. to allow combination, recognize and evaluate constant

expressions, recognize identities and remove them:

-4*x+x -> -4*x+1*x -> (-4+1)*x -> -3*x

add identity common factor evaluate

1*1*r -> 1*r -> r

evaluate or remove identity

remove identity

y+0 -> 0

remove identity

Specifying rewrite rules using a little language will make

experiments easier.

Thanks. Take care, Brian Inglis Calgary, Alberta, Canada

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.