GRIPS/PROLOG DEMONSTRATION MINI-COMPILER Contributed by Jocelyn Ireson-Paine, Oxford University. Shelved on the 11th of January 1991 This is a demonstration compiler, written in a functional language (GRIPS) that can be translated into Prolog. The GRIPS translator is available as another library entry. The compiler takes programs in a (very small) subset of Pascal. It lexically analyses them into tokens, parses the token list into a tree, generates code from the tree, fixes up references in the code, and then interprets the code on a stack virtual machine. It displays the output of each stage, and the interpreter displays the machine state as each instruction is obeyed. The compiler is written in a functional style, using functions (sometimes represented as sets of domain->codomain pairs) to represent well-known concepts in programming language semantics, such as the store and the environment. I wrote it to explain in his own idiom, compiling to a mathematician starting a computer science M.Sc. Here is an example program that it can compile and run. program p; label 99, 100; const five = 5; var v : integer; w : integer; begin write('Hello.'); v := 1; w := 1; 99: if v=five then goto 100; v := v + 1; w := w * v; goto 99; 100: write('v = '); write(v); write('v! = '); write(w) end. Here is the result of compiling and running this program: ?- demo. Tokens : [program, p, ;, label, 99, ,, 100, ;, const, five, =, 5, ;, var, v, :, integer, ;, w, :, integer, ;, begin, write, (, string(Hello.), ), ;, v, :=, 1, ;, w, :=, 1, ;, 99, :, if, v, =, five, then, goto, 100, ;, v, :=, v, +, 1, ;, w, :=, w, *, v, ;, goto, 99, ;, 100, :, write, (, string(v = ), ), ;, write, (, v, ), ;, write, (, string(v! = ), ), ;, write, (, w, ), end, .] Tree : PROG(p, DECLARATIONS([99, 100], [C(five, 5)], [V(v, integer), V(w, integer)]), [WRITE(STR(Hello.)), ASSIGN(v, 1), ASSIGN(w, 1), LABELLED(99, IF(E(=, v, five), [GOTO(100)])), ASSIGN(v , E(+, v, 1)), ASSIGN(w, E(*, w, v)), GOTO(99), LABELLED(100, WRITE(STR(v = ))), WRITE(v), WRITE(STR(v! = )), WRITE(w)]) Environment : 0 map{five->5} map{v->LOC(1000, 2), w->LOC(1002, 2)} Unfixedup code : [OP(loadconst, 46), OP(loadconst, 111), OP(loadconst, 108), OP(loadconst, 108), OP(loadconst, 101), OP(loadconst, 72), OP(loadconst, 6), OP(writestring), OP(loadconst, 1), OP(store, 1000), OP(loadconst, 1), OP(store, 1002), LABEL(99), OP(load, 1000), OP(loadconst, 5), OP(eq), OP(jump_if_false, -1), OP(goto, 100), LABEL(-1), OP(load, 1000), OP(loadconst, 1), OP(add), OP(store , 1000), OP(load, 1002), OP(load, 1000), OP(mult), OP(store, 1002), OP(goto, 99), LABEL(100), OP(loadconst, 32), OP(loadconst, 61), OP(loadconst, 32), OP(loadconst, 118), OP(loadconst, 4), OP(writestr ing), OP(load, 1000), OP(write), OP(loadconst, 32), OP(loadconst, 61), OP(loadconst, 32), OP(loadconst, 33), OP(loadconst, 118), OP(loadconst, 5), OP(writestring), OP(load, 1002), OP(write)] Code : [OP(loadconst, 46), OP(loadconst, 111), OP(loadconst, 108), OP(loadconst, 108), OP(loadconst, 101), OP(loadconst, 72), OP(loadconst, 6), OP(writestring), OP(loadconst, 1), OP(store, 1000), OP(loadconst, 1), OP(store, 1002), LABEL(46), OP(load, 1000), OP(loadconst, 5), OP(eq), OP(jump_if_false, 64), OP(goto, 96), LABEL(64), OP(load, 1000), OP(loadconst, 1), OP(add), OP(store, 1000), OP(load, 1002), OP(load, 1000), OP(mult), OP(store, 1002), OP(goto, 46), LABEL(96), OP(loadconst, 32), OP(loadconst, 61), OP(loadconst, 32), OP(loadconst, 118), OP(loadconst, 4), OP(writestr ing), OP(load, 1000), OP(write), OP(loadconst, 32), OP(loadconst, 61), OP(loadconst, 32), OP(loadconst, 33), OP(loadconst, 118), OP(loadconst, 5), OP(writestring), OP(load, 1002), OP(write)] Loaded code : map{0->OP(loadconst, 46), 4->OP(loadconst, 111), 8->OP(loa dconst, 108), 12->OP(loadconst, 108), 16->OP(loadconst, 101), 20->OP(loadconst, 72), 24->OP(loadconst, 6), 28->OP(writestring), 30->OP(loadconst, 1), 34->OP(store, 1000), 38->OP(loadconst, 1), 42->OP(store, 1002), 46->OP(load, 1000), 50->OP(loadconst, 5), 54->OP(eq), 56->OP(jump_if_false, 64), 60->OP(goto, 96), 64->OP(load, 1000), 68->OP(loadconst, 1), 72->OP(add), 74->OP(store, 1000), 78->OP(load, 1002), 82->OP(load, 1000), 86->OP(mult), 88->OP(store, 1002), 92->OP(goto, 46), 96->OP(loadconst, 32), 100->OP(loadconst, 61), 104->OP(loadconst, 32), 108->OP(loadconst, 118), 112->OP(loadconst, 4), 116->OP(writestring), 118->OP(load, 1000), 122->OP(write), 124->OP(loadconst, 32), 128->OP(loadconst, 61), 132->OP(loadconst, 32), 136->OP(loadconst, 33), 140->OP(loadcon st, 118), 144->OP(loadconst, 5), 148->OP(writestring), 150->OP(load, 1002), 154->OP(write)} Initial store : map{1000->255, 1001->255, 1002->255, 1003->255} Input? |: Stack: [] Store: map{1000->255, 1001->255, 1002->255, 1003->255} PC : 0 In : [] Out : [] About to do OP(loadconst, 46) Stack: [46] Store: map{1000->255, 1001->255, 1002->255, 1003->255} PC : 4 In : [] Out : [] ... etc ... About to do OP(write) Stack: [] Store: map{1000->5, 1001->0, 1002->120, 1003->0} PC : 156 In : [] Out : [Hello., v = , 5, v! = , 120] Finished. SIZE : 55 kilobytes. CHECKED ON EDINBURGH-COMPATIBLE (POPLOG) PROLOG : yes. PORTABILITY : should be no problems. INTERNAL DOCUMENTATION : as program comments.