Expression simplifier.

Rasmus Anthin <e8rasmus@etek.chalmers.se>
29 Apr 2001 02:14:50 -0400

          From comp.compilers

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)
| List of all articles for this month |

From: Rasmus Anthin <e8rasmus@etek.chalmers.se>
Newsgroups: comp.compilers
Date: 29 Apr 2001 02:14:50 -0400
Organization: Chalmers University of Technology
Keywords: optimize, comment
Posted-Date: 29 Apr 2001 02:14:49 EDT

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 :(


Sincerely,
\ B. Rasmus Anthin
    / e8rasmus@etek.chalmers.se
  / www.etek.chalmers.se/~e8rasmus
[I'd have a set of tree rewriting patterns, e.g. X+0 -> X -John]


Post a followup to this message

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