FORTH / Expression parsing
John Payson email (remove spam text)
part 0 3213 bytes<01BDF1FF.9ACAD320@JOHN_WKST1>
| 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.
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
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
See also: www.piclist.com/techref/index.htm?key=forth+expression
You must be a member of the
piclist mailing list
(not only a www.piclist.com member) to post to the