Re: Expression simplifier.

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

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