DCGs can be faster than recursive descent

Nice to know
1

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
BUP 0.415142
Edinburgh 1.0
RecursiveDescent 1.008729
DCG 1.046898
2 Likes
2

You should also add that if you know BNF, you are more than half way done with writing a DCG and we know how understandable BNF can be.

1 Like
3

One problem I ran into with writing DCG grammars is that there’s no way (that I know of) to validate that the grammar is unambiguous. So, when I was writing the reference implementation for a decision-support language, I ended up writing the grammar in BNF and running through yacc/bison and then hand-translating to DCG. :frowning: