Finding duplicate sub-expressions in calculator grammar

[andrew]

i've written a parser in perl for a simple arithmetic grammar
{+,-,*,/,funtion ()} where each operation is potentially expensive to
evaluate. the parser outputs an AST tree that is stored for each of a set
of spreadsheet-like cells that can then be re-evaluated with different
inputs.

currently, if there are expressions like:

(A+B)+f(A+B)
A+B+A+B

the sub-expression A+B gets evaluated more than once when evaluating the
AST tree for that expression. i'd like them to be evaluated only once as
doing A+B can be expensive.

is there a clever way to pre-parse each expression with a regexp to make a
list of identical subexpressions (maybe making a list of expressions with
temporary variables, to be evaluated in succession, like C=A+B, C+f(C))?

can any compiler, like gcc, optimize for this?

andrew.

 

[John Bokma]

i've written a parser in perl for a simple arithmetic grammar
{+,-,*,/,funtion ()} where each operation is potentially expensive to
evaluate. the parser outputs an AST tree that is stored for each of a
set of spreadsheet-like cells that can then be re-evaluated with
different inputs.

currently, if there are expressions like:

(A+B)+f(A+B)
A+B+A+B

the sub-expression A+B gets evaluated more than once when evaluating
the AST tree for that expression. i'd like them to be evaluated only
once as doing A+B can be expensive.

is there a clever way to pre-parse each expression with a regexp to
make a list of identical subexpressions

if (A+B) == (B+A) holds, regexp is certainly not the way to go.

Parse the expression into a tree and read documentation on common sub
expression elimintation.