Rz3 compiler version 1.0
include eval3.c
This is a complete Rz compiler. It has a parser generator.
Any change (for example, add new syntax) can be made through Rz grammar
(file "rz-grammar9.txt in pgen-c). This compiler generates an explicit
parse-tree that can be used to generate machine specific code or to
"meta-interpret" (run) the program.
The function eval() is almost complete except "return" instruction.
Sample session
----------------------------
E:>rz3 quick.txt
inita
show
swap
partition
quicksort
main
(fun main (do (= N 10 )(call inita )(call swap 0 5 )(call swap 2 8
)(call show )(call quicksort 0 (- N 1 ))(call show )))
(fun inita (do (= #1 0 )(while (< #1 N )(do (= (vec a #1 )#1 )(= #1
(+ #1 1 ))))))
(fun show (do (= #1 0 )(while (< #1 N )(do (print (vec a #1 )" " )(=
#1 (+ #1 1))))(print "\n" )))
(fun swap (do (= #3 (vec a #1 ))(= (vec a #1 )(vec a #2 ))(= (vec a #2
)#3 )))
(fun partition (do (= #3 (vec a #1 ))(= #4 (- #1 1 ))(= #5 (+ #2 1 ))(=
#6 1 )(while #6 (do (= #5 (- #5 1 ))(while (> (vec a #5 )#3 )(= #5
(- #5 1 )))(= #4 (+ #4 1 ))(while (< (vec a #4 )#3 )(= #4 (+ #4 1
)))(else (< #4 #5 )(call swap #4 #5 )(= #6 0 ))))(return #5 )))
(fun quicksort (if (< #1 #2 )(do (= #3 (call partition #1 #2 ))(call
quicksort #1 #3 )(call quicksort (+ #3 1 )#2 ))))
N type 4 ref 1
a type 3 ref 2
5 1 8 3 4 0 6 7 2 9
0 1 2 3 4 5 6 7 8 9
-------------------------------
The compiler shows the parse-tree (in human readable form) and the
symbol table, global variables and functions. Then it calls
eval() to "run" this parse-tree.
State of eval3 in rz3
eval( ) works correctly except "return". It ran these benchmarks
correctly: bubble.txt, fac.txt, hanoi.txt, inc.txt, matmul2.txt,
perm.txt, queen.txt, quick.txt, sieve2.txt.
I modified "matmul.txt" to eliminate call to "index" which contains
"return". So, I can say, eval() is 95% correct. The problem of
"return" stems from its "jump out from the middle"
behaviour. That is, "return" must exit the function call.
Our meta-interpreter cannot do that. The control flow in the
meta-interpreter (the eval) works like this:
eval call fun
fun eval body
eval return -> exit from call fun
the stack frame can be create/delete properly. However, the flow of
control cannot be manipulate explicitly. The "command" that
affects the control flow are: if, while, do, call, return.
if eval cond is true
then
eval true-action
else
eval false-action
while eval cond is true
eval body
do
while arg is
not nil
eval head arg
arg = tail arg
call ...
These control flows are "implicit". We use the flow of
meta-interpreter. To be able to "return", we need to have an
explicit flow and to redirect the execution of "next instruction" of
"return" to match up to "call". To do that we need "choice
point". Before the call, we save the "choice point". At
"return" we restore the choice point.
How to represent "choice point"?
In a normal linear code, there is PC to do that. But we don't
have a PC. Compiling by continuation (a la callcc) is suitable
for this purpose. But it is complicate.
I try to use a global flag and have "return" to set this flag. In any
"loop" the interpreter will check this flag and determine whether it
will continue. But it is still difficult to "match up" with
"call". The solution will require me to spend more time. Because
of this, and because meta-interpreter is not my main goal (my goal is
to illustrate how to generate machine codes), I will stop my work on
eval now. And will prepare the code generator
instead.
15 Nov 2010