Searching \ for 'FORTH / Expression parsing' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/index.htm?key=forth+expression
Search entire site for: 'FORTH / Expression parsing'.

Truncated match.
PICList Thread
'FORTH / Expression parsing'
1998\10\07@153939 by John Payson

flavicon
face
part 0 2843 bytes
|        Finally, years and years ago I licensed a 6800 Basic interpreter
|from Microsoft.  It's interesting to see how it evaluates an expression.
|It actually scans the line left to right, interpreting as it goes along.
|When it sees some sort of two argument operator (like + ), it goes on and
|evaluates the second argument, which may involve recursive function
|calls.  It's pretty neat.  When it finds a function call, it calls the
|function evaluator, which then looks at the argument and calls the
|function evaluator again to evaluate the argument to the function.  This
|continues until there is actually some number that is returned, then  all
|the functions return.

For a PICbasic-style interpreter, a postfix representation of expressions
is generally far superior to an infix one (prefix can sometimes be okay,
but the execution stack can get a little complicated).  Conversion of an
infix expression to prefix, postfix, or result (i.e. evaluation of the
expression) isn't too hard to write but a lot of the code ends up looking
a bit redundant.  Assuming you have routines to 'peek' at and 'munch' the
next token in the input stream, things proceed pretty straightforwardly:

to parse an expression:
 parse a logicterm
 while the next token is 'or':
   munch it and parse another logterm. Then perform the 'or'.

to parse a logicterm:
 read a logicfactor
 while the next token is 'and':
   munch it and parse another logicfactor.  Then do the 'and'.

to parse a logicfactor:
 if the next token is 'not':
   munch it and parse the next logicfactor.  Then negate it.
 otherwise
   munch the next relational

to parse a relational:
 parse a numeric
 while the next token is '>', '>=', '<', '<=', '<>', or '=':
   munch it and parse the next numeric.  Then do the comparison.

to parse a numeric:
 parse a term
 while the next token is '+' or '-':
   munch it and parse the next term.  Then add/subtract.

to parse a term:
 parse a factor
 while the next token is '*' or '/':
   munch it and parse the next factor.  Then add/subtract.

to parse a factor:
 parse an atom
 if the next token is '^':
   munch it and parse the next factor.  Then take the exponent.

to parse an atom:
 if the next token is '-'    ; Unary '-'
   munch it and parse the next atom.  Then negate it.
 otherwise if the next token is a '('
   munch it, parse the next expression [back to top], and munch a ')'
 otherwise if the next token is a variable
   munch it and evaluate it
 otherwise if the next token is a number
   munch it and evaluate it
 otherwise
   report an error

Nothing terribly complicated, but quite long and cumbersome.  Although it
is certainly possible for small micros to deal with that sort of thing,
it's much easier to simply use a postfix-based expression evaluator at
runtime.

1998\10\07@170104 by Scott Dattalo

face
flavicon
face
John Payson wrote:

> For a PICbasic-style interpreter, a postfix representation of expressions
> is generally far superior to an infix one (prefix can sometimes be okay,
> but the execution stack can get a little complicated).  Conversion of an
> infix expression to prefix, postfix, or result (i.e. evaluation of the
> expression) isn't too hard to write but a lot of the code ends up looking
> a bit redundant.  Assuming you have routines to 'peek' at and 'munch' the
> next token in the input stream, things proceed pretty straightforwardly:

<algorithm snipped>

I've written an RPN type equation parser in CPP (for Borland) that does
what you describe - except it doesn't spew pic code.

http://interstice.com/~sdattalo/technical/parser/parser.html

Maybe this be could be the basis for gpforth?

Scott

PS - Several people have told their inability to compile my parser.
That's because I (foolishly) used Borland's non-standard containers.
Perhaps after gpsim settles I'll fix that design bug.

More... (looser matching)
- Last day of these posts
- In 1998 , 1999 only
- Today
- New search...