11 Nov 2006 15:50:04 -0500

Related articles |
---|

Fastening the run-time interpretation of mathematical expressions paolopantaleo@gmail.com (PAolo) (2006-11-11) |

Re: Fastening the run-time interpretation of mathematical expressions haberg@math.su.se (2006-11-11) |

Re: Fastening the run-time interpretation of mathematical expressions mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2006-11-13) |

Re: Fastening the run-time interpretation of mathematical expressions akk@privat.de (Andreas Kochenburger) (2006-11-13) |

Re: Fastening the run-time interpretation of mathematical expressions martin@gkc.org.uk (Martin Ward) (2006-11-13) |

Re: Fastening the run-time interpretation of mathematical expressions tommy.thorn@gmail.com (Tommy Thorn) (2006-11-13) |

Re: Fastening the run-time interpretation of mathematical expressions 148f3wg02@sneakemail.com (Karsten Nyblad) (2006-11-15) |

[4 later articles] |

From: | "PAolo" <paolopantaleo@gmail.com> |

Newsgroups: | comp.compilers |

Date: | 11 Nov 2006 15:50:04 -0500 |

Organization: | Compilers Central |

Keywords: | interpreter, question, comment |

Posted-Date: | 11 Nov 2006 15:50:04 EST |

I am writing a piece of software that accept in input the definition

of a mathematical function and a list of points in which evaluate the

function and puts the result in output. The main feature of the progam

is that once the function definition is read, the program evaluates

the function very fast [Well this isn't done already...]. I was

thinking to build a pair of stacks, one containig the operands

(floats) and the other containig the operators (function pointers).

For each evaluation the following steps should be done:

Duplicate the operands stack

Do the operations (modifying the duplicated stack)

The operations are as simple as a function call (through a pointer),

the matheatical operation itself and the stack update (that is moving

the pointer and writing the resulting data).

Question 1: Is this a fast method to do the stuff (given that the

function is known at run time and I do not want to generate the

assebler code for portability sake).

Parsing the function definitions (using Bison) gives the RPN

representation of the expression, that is near the two stack

representation, but it is not exactly that. The gramar is:

%token <val> NUM /*float representation*/

%token <name> ID /*name starting with [a-zA-Z_] */

%left '-' '+'

%left '*' '/'

%left NEG /* negation--unary minus */

%right '^' /* exponentiation */

exp: NUM {printf(" %g",$1);}

| ID {printf(" #%s",$1);}

| ID '(' exp ')' {printf(" @%s",$1);}

| exp '+' exp {printf(" +");}

| exp '-' exp {printf(" -");}

| exp '*' exp {printf(" *");}

| exp '/' exp {printf(" /");}

| '-' exp %prec NEG {printf(" neg");}

| exp '^' exp {printf(" ^");}

| '(' exp ')'

;

Given the RPN expression

1 2 + 3 *

in the two stack forms is (the left of the string is the top of the

stack):

|1 2 3| |+ *|

which can also mean RPN

1 2 3 + *

Things would be much easier if all the RPN would be in a form that in

every step of the evaluation would be true the following:

On the top of the stack there are n operand followed by the operator

(taking n operands) that conusumes them.

For example 1 2 3 + * could be rewritten 2 3 + 1 *

Question 2: Is always possible to rewrite the expression in the form I

said? How could I do it automatically?

Some more examples:

2^(3+4) -> 2 3 4 + ^ -> 3 4 + 2 commutate^

where commutate-operator is an operator that swaps its operands [ a

commutate^ b = b^a]

4+3*(2+1) -> 4 3 2 1 + * + -> 2 1 + 3 * 4 +

I didn't find any case in which the conversion is impossble.

Thnx for reading this message,

any help is wellcome

Paolo Pantaleo

[This seems much more complicated than it needs to be. The usual way to

do an RPN interpreter is to make the RPN a string of tokens, and then

for the interpreter to run through the set of tokens, popping arguments

and pushing results for each operator, with the result left on the top

of the stack. Only one stack needed, no stack copying, and no RPN

rewriting. -John]

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.