riddle@mathcs.emory.edu (Larry Riddle) (03/02/89)
Rather than spending the time to re-invent the wheel, I thought
I would check here first to see if anyone had some source or a
good reference on how to parse a function as input. I would like
to be able to have someone enter a function (say restricted to the
standard arithmetic operations and sin, cos, exp, sqr, log, etc)
while a program is running and then be able to evaluate that function
at however many points might be later specified.
Thanks for any assistance.
--
Larry Riddle | riddle@mathcs.emory.edu PREFERRED
Emory University | {decvax,gatech}!emory!riddle UUCP
Dept of Math and CS | riddle@emory NON-DOMAIN BITNET
Atlanta, GA 30322 | (404) 727-7922 AT&Tgalvinp@lafcol.UUCP (Pablo) (03/06/89)
I too would like code that parses mathematical functions. I have tried to code this before but failed. Commented code would be really nice but anything is better than what I have. You all may want to mail something like this to me as well, rather than posting it. Thanks, Paul J. Galvin (galvinp!lafcol)
milne@ics.uci.edu (Alastair Milne) (03/07/89)
In article <3764@emory.mathcs.emory.edu> riddle@mathcs.emory.edu (Larry Riddle) writes: >Rather than spending the time to re-invent the wheel, I thought >I would check here first to see if anyone had some source or a >good reference on how to parse a function as input. I would like >to be able to have someone enter a function (say restricted to the >standard arithmetic operations and sin, cos, exp, sqr, log, etc) >while a program is running and then be able to evaluate that function >at however many points might be later specified. I was going to reply privately to the first message asking for this, but it's starting to look as if a general follow-on would do more good. hp0p+@andrew.cmu.edu (Hokkun Pang) writes: > >... >so if I have: > value_of_expression('x^2+sin(x)',pi) >I should get 3.14^2+0 which is roughtly 9.8 > >Since the function will be used extensively in the program, the function must >be fast. If you have the actual codes, algorithm or ideas about the function, >please tell me. Thanks. Also, I use Turbo 5.0 Having just done something very similar in UCSD Pascal, I have a few points of advice. I won't submit code, both because it's not mine to submit, and because it would be far too big. I am not immediately aware of anything already available to do this, but you might try looking at the Numeric Toolbox, and Eureka, both from Borland, to see what they can contribute. 1. Define your grammar. How extensive and comprehensive you want to make it is rather up to you. I, for instance, arranged it to allow implicit multiplication in certain common cases, and to allow exponentiation of functions in such form as "sin^2(x)". I will confess to having started from the Pascal definition of expressions, but there are probably better algebraic grammars available if you look. Here you should also define the formats your constants can take -- important if you're going to handle reals. Also, decide on sensitivity to letter case. 2. Specify a unit to supply the evaluation service. Besides allowing you to develop it with its own global, permanent environment, this lets you export separate services, so that you can take one expression and parse it only once, followed by as many evaluations as you want. This will help your speed a lot. You also need to decide which of the many possible exceptional conditions, both in parsing and in evaluation, you will try to handle. I suggest something like UNIT AlgebraEval; INTERFACE TYPE Errors = ( { whatever error results the calling routine should know about } ); VarNameType = 'A' .. 'z'; { for user's algebraic variables} VarSetType = SET OF VarNameType; PROCEDURE InitExpression( Expression: STRING); { Parse Expression into an internal form which can be quickly evaluated. Be prepared to handle or return syntax errors from this stage. } PROCEDURE AssignVar( Variable: VarNameType; NewValue: REAL); { Assigns the NewValue to Variable in the parser's internal variable table, for use by EvalExpression. } PROCEDURE UndefineVars( VarsToRemove: VarSetType); { Removes from the internal variable table the definitions of all the variables named in VarsToRemove. Very useful for starting a new expression. } FUNCTION EvalExpression( VAR Result: REAL): Errors; { Returns the actual value of the expression, given that: - it had no syntax errors - all variables it uses have values - it has no semantic errors (e.g. sqrt(-3) ). The function return indicates whether evaluation succeeded, and if not, why not. } IMPLEMENTATION 3. Choose the internal representation your evaluator is to use, and write your parser to generate it. I like an explicit expression tree graph, built on the heap, which the evaluator will then traverse as often as needed; but other ways are possible, and you may find one you prefer. If, for instance, you wind up doing lots of different trees, and therefore having to dispose of old ones a lot, you might not want to trust Turbo's limited heap management, and instead try a prefix or postfix string format. For the parser itself: I like recursive descent, because it's pretty quick to write, and Pascal handles it very well. You might prefer table driven, if you have a parser generator handy. If you have your grammar written, the parser should emerge naturally from it. The internal variable table should be very simple: VAR VarTable: ARRAY[ VarNameType] OF RECORD CASE Defined: BOOLEAN OF TRUE: (Value: REAL) END; should do the job fine. Of course, if you don't need to handle algebraic expressions, this won't be needed. I could add quite a bit more, but this is already longer than I like to send on UseNet. If you need more, please mail to me directly, and I'll see what I can do. I don't entirely trust the address-processing, so here are my mail addresses, without threat of change: milne@ics.uci.edu -- for Internet OR AMILNE@UCI -- for bitnet Alastair Milne