GRIPS/PROLOG DEMONSTRATION MINI-COMPILER Contributed by Jocelyn 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. This entry consists of 10 files: COMPILER.PRE - this file. CODE_GENERATE.PL - the code-generator. COMPILE.PL - the master file. LEX.PL - the lexical analyser. LOAD.PL - the loader. MACHINE.PL - the machine-code interpreter. MAP.PL - one of the Edinburgh Tools files. Used to implement mappings. ORDSET.PL - another Tools file. Implements sets. PARSER.PL - the parser. PROGRAM. - a sample program. To run the compiler, you will need GRIPS. Consult GRIPS, and then (from Prolog; you needn't call the GRIPS TLI), do ?- grips_reconsult( 'compile.pl' ). This will load the other compiler files. Then do ?- demo. This predicate (defined in COMPILE.PL) will read tokens from the file PROGRAM. It will parse them, code-generate, load the code (fixing up labels), and interpret it. At each stage, it displays the structures produced (token list, parse tree, etc.); it also displays each cycle of the virtual machine. For the sample input supplied, you need not give any input: just type end-of-file when asked for some. Here is the output of this demo. ?- 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. CHECKED ON EDINBURGH-COMPATIBLE (POPLOG) PROLOG : yes. PORTABILITY : should be no problems. INTERNAL DOCUMENTATION : as program comments.