Compilers Written in Prolog

Appeared in Volume 8/1, February 1995

marechal@reseau.onecert.fr
Christophe Marechal
25th January 1994

I am looking for a compiler source, written in Prolog, (preferably a Pascal compiler), with comments if possible, and with detailed parts: Lexical analyser; Syntaxic analyser; Semantic analyser; Code generator; Optimizer, etc.

popx@vax.oxford.ac.uk
Jocelyn Paine
26th January 1994

My library of public-domain Prolog software contains a small compiler which I wrote to demonstrate to a mathematician friend of mine how compilers work. It takes programs in a tiny subset of Pascal, 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.

It's 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.

Warning: because I was coding for a mathematician, I decided to write in functions. I have a pre-processor which transforms functional definitions into Prolog, and you'll also need that.

You can get the code from my Prolog library of public-domain software, via anonymous FTP from the Imperial College archive at:
ftp://src.doc.ic.ac.uk/packages/prolog-pd-software/
The compiler is in compiler.tar.Z. The functional-to-Prolog translator is in grips.tar.Z.

bowen@comlab.ox.ac.uk
Jonathan Bowen
27th January 1994

The classic original article on this subject is:

D.H.D. Warren, Logic programming and compiler writing, Software Practice and Experience, Vol. 10, pp. 97-125, 1980

Another important paper is:

J. Cohen and T. Hickey, Parsing and Compiling using Prolog, ACM Transactions on Programming Languages and Systems (TOPLAS), Vol. 9, No. 2, pp.125-163, 1987

You could also read:

J. Paakki, Prolog in practical compiler writing, The Computer Journal, Vol. 34, No. 1, pp.64-72, 1991

If you are interested in a rapid prototyping approach implementing a proven correct compiling specification try:

J.P. Bowen, From Programs to Object Code using Logic and Logic Programming, R. Giegerich and S.L. Graham (eds.), In Concepts, Tools, Techniques, Dagstuhl, Germany, 20--24 May 1991, Springer-Verlag, Workshops in Computing, pp.173-192, 1992

And if decompilation is of interest as well, look at:

J.P. Bowen, From Programs to Object Code and Back Again Using Logic Programming: Compilation and Decompilation, Journal of Software Maintenance: Research and Practice, Vol. 5, No. 4, pp.205-234, December, 1993

feliks@carlstedt.se
Feliks Kluzniak
28th January 1994

People who read the Paakki paper cited above, should also read the follow-up letter to the editor in The Computer Journal, vol. 35, no. 3 (1992), p. 313