piclist 1998\10\07\153939a >
Thread: FORTH / Expression parsing
www.piclist.com/techref/index.htm?key=forth+expression
flavicon
face BY : John Payson email (remove spam text)

part 0 3213 bytes

|        I haven't used FORTH in a while, but am constantly using my HP
|15C and HP35 calculators, both of which operate very in a FORTH manner.
|FORTH and RPN calculators really DO make sense...  You give the machine
|the numbers, then tell it what to do with them.  This is also called post
|fix notation, as opposed to the in fix notation we're more familiar with.

|        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.

<01BDF1FF.9ACAD320@JOHN_WKST1>

See also: www.piclist.com/techref/index.htm?key=forth+expression
Reply You must be a member of the piclist mailing list (not only a www.piclist.com member) to post to the piclist. This form requires JavaScript and a browser/email client that can handle form mailto: posts.
Subject (change) FORTH / Expression parsing

month overview.

new search...