Expression simplifier.

Rasmus Anthin <>
29 Apr 2001 02:14:50 -0400

          From comp.compilers

Related articles
Expression simplifier. (Rasmus Anthin) (2001-04-29)
Re: Expression simplifier. (Rasmus Anthin) (2001-04-30)
Re: Expression simplifier. (2001-04-30)
Re: Expression simplifier. (Ira D. Baxter) (2001-04-30)
Re: Expression simplifier. (Rasmus Anthin) (2001-05-03)
| List of all articles for this month |

From: Rasmus Anthin <>
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

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:



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

\ B. Rasmus Anthin
[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.