An experiment to assess the suitability of using Prolog’s definite clause grammar (DCG) formalism to write a compiler for moderate-sized languages is reported. The experiment consisted of implementing a compiler for the EDISON language using three approaches: DCG, recursive descent in Pascal, and parser generation by an LALR(1) parser generator.
The first third of the paper describes the architecture of the compilers. Each compiler consists of four passes: a scanner, a parser that generates an abstract syntax tree, a semantic analyzer that transforms the syntax tree, and a code generator that outputs abstract EDISON code suitable for interpretation. Examples show how EDISON statements are represented and transformed in the Prolog implementation.
Next, the paper compares the development effort and performance of the three implementations. Surprisingly, each implementation took roughly the same amount of time to produce, although the DCG version was half the size of the other two. For the scanner and parser, the DCG implementation was spectacularly slow, in the worst case taking more than 1800 times longer than the Pascal version. (This figure is for compiled Prolog; when run interpretively, it could not finish, due to lack of space on a VAX/8800.)
In the last section, the author gives a long-winded assessment of DCG. Basically, he likes the conceptual approach of DCG, especially for semantic analysis and code generation. He feels that the poor performance of the DCG version is not inherent, but a reflection of the Prolog systems he used. He is working on a compiler-writing system based on Prolog with special support for DCG and symbol-table management.