Advanced expression simplification (Igor Chudov)
11 Jul 2005 07:03:35 -0400

          From comp.compilers

Related articles
Advanced expression simplification (2005-07-11)
Re: Advanced expression simplification (Marco van de Voort) (2005-07-11)
Re: Advanced expression simplification (2005-07-12)
Re: Advanced expression simplification (Gene) (2005-07-17)
Advanced expression simplification (Evangelos Drikos) (2005-07-17)
Re: Advanced expression simplification (F. Liekweg) (2005-07-17)
| List of all articles for this month |

From: (Igor Chudov)
Newsgroups: comp.compilers
Date: 11 Jul 2005 07:03:35 -0400
Organization: Compilers Central
Keywords: optimize, code, question
Posted-Date: 11 Jul 2005 07:03:35 EDT

I am writing an algebra expression simplifier. It parses an expression
and then applies various rules to the parsed tree. It also produces
"work shown". Much of it already works (reduction of constants,
similar terms, similar factors, etc). It works with expressions of
arbitrary complexity, powers etc.


Now I am approaching more difficult areas.

Specifically, in simplification, some approaches can be tried and
abandoned. For example:

(x^2-1)/(x-1) simplifies to x+1. GOOD

(1^100-1)/(x-1) "simplifies" to x^99+x^98+...+x+1. NOT GOOD.

If I do such things, I need to make sure that simplification does not
loop with endless tries, and that it takes a reasonable amount of
time. Some approaches can initially lead to bigger expressions, and
then to smaller ones. The typical example is use of associative

I cannot expect all simplification approaches to always reduce the
size of expressions. And yet, I need to know "where to stop".

Are there any good treatises on expression simplification.




Post a followup to this message

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