About five or six years ago I was reading O’Keefe’s The Craft of Prolog and was intrigued by his claims that DCGs could be fast (Chapter 8 Some Notes on Grammar Rules). I did some measurements and it turns out implementing a parser for Prolog with DCGs was just under 4% faster than any other method I could come up with. The DCG code was also amongst the most readable!
Here BUP is a Bottom-Up Parser, Edinburgh is the Edinburgh library parser, RecursiveDescent is a top down LL(k), and these are the results after giving the same largish Prolog source file as input to the different parsers:
|Parser||Speedup over Edinburgh|