[REBOL] Expression evaluator (an example of parsing blocks)
From: g:santilli:tiscalinet:it at: 14-Oct-2000 13:12
Hi all!
Have you been sometimes annoyed by tha fact REBOL does not support
operator precedence? Here's the answer:
>> a: 2 b: 4 c: 3
== 3
>> eval [b ^ 2 - 4 * a * c]
== -8
The magic trick is:
>> eval/translate [b ^ 2 - 4 * a * c]
== [subtract power b 2 multiply multiply 4 a c]
Other examples:
>> eval/translate [1 / k !]
== [divide 1 factorial k]
>> eval/translate [a * - b]
== [multiply a negate b]
>> eval/translate [e ^ (i / h * (p * x - E * t))]
== [power e multiply divide i h subtract multiply p x multiply E t]
NOTE: it still needs improvements, such as error handling. They
are "left to the reader as an exercise". :-)
Enjoy!,
Gabriele.
--
Gabriele Santilli <[giesse--writeme--com]> - Amigan - REBOL programmer
Amiga Group Italia sez. L'Aquila -- http://www.amyresource.it/AGI/
REBOL [
Title: "Expression evaluator"
Author: "Gabriele Santilli <[giesse--writeme--com]>"
Comment: {
Evaluates expressions taking usual operator precedence
into account.
1. (...)
2. - [negation], ! [factorial]
3. ^ [power]
4. *, /
5. +, - [subtraction]
}
]
; A simple iterative implementation; returns 1 for negative
; numbers. FEEL FREE TO IMPROVE THIS!
factorial: func [n [integer!] /local res] [
if n < 2 [return 1]
res: 1
; should avoid doing the loop for i = 1...
repeat i n [res: res * i]
]
expression-parser: make object! [
slash: to-lit-word first [ / ]
expr-val:
expr-op: none
expression: [
term (expr-val: term-val)
any [
['+ (expr-op: 'add) | '- (expr-op: 'subtract)]
term (expr-val: compose [(expr-op) (expr-val) (term-val)])
]
]
term-val:
term-op: none
term: [
pow (term-val: power-val)
any [
['* (term-op: 'multiply) | slash (term-op: 'divide)]
pow (term-val: compose [(term-op) (term-val) (power-val)])
]
]
power-val: none
pow: [
unary (power-val: unary-val)
opt ['^ unary (power-val: compose [power (power-val) (unary-val)])]
]
unary-val:
pre-uop:
post-uop: none
unary: [
(post-uop: pre-uop: [])
opt ['- (pre-uop: 'negate)]
primary
opt ['! (post-uop: 'factorial)]
(unary-val: compose [(post-uop) (pre-uop) (prim-val)])
]
prim-val: none
; WARNING: uses recursion for parens.
primary: [
set prim-val [number! | word!]
| set prim-val paren! (prim-val: translate to-block :prim-val)
]
translate: func [expr [block!] /local res recursion] [
; to allow recursive calling, we need to preserve our state
recursion: reduce [
:expr-val :expr-op :term-val :term-op :power-val :unary-val
:pre-uop :post-uop :prim-val
]
res: if parse expr expression [expr-val]
set [
expr-val expr-op term-val term-op power-val unary-val
pre-uop post-uop prim-val
] recursion
res
]
set 'eval func [expr [block!] /translate] [
expr: self/translate expr
either translate [expr] [do expr]
]
]
