Expression simplifier.

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]

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