One of the benefits of functional languages, compared to other languages, is the routineness of correctness proofs at each step of program development. The authors have used this property of Scheme to construct a recursive ascent general LR parser, which is then transformed using offline partial evaluation (also proven correct) into generators of efficient parsers. This last step uses Bondorf’s Similix and Thiemann’s PGG systems, both of which are publicly available on the Internet. The efficiency of the authors’ system matches or exceeds that of stack implemented recursive descent parser generators, and their system has the advantage of understandability and guaranteed correctness.

The performance of the generated parsers, including an imperative version, on three different grammars with inputs whose sizes range from 2 to 983 words, are compared to existing Yacc-based implementations: Mossin’s general parser, a direct-style LR parser, a continuation-based parser, and Bison-generated parsers. The differences in the performance times range from a trivial difference between the system presented here and the Bison-generated parsers, to more than a seven-times improvement over the LR parser. I would have liked to see a column reporting statistical confidence levels for these differences added to the run-time tables.

After detailed descriptions of each of the general parsers considered, the paper ends with pointers to the parser code on the Internet. The 58 references include an address for the PGG system as well.