4 ms·
Prolog DCGs have pitfalls that aren’t immediately evident to someone only familiar with BNF, mainly that you have to specify your grammar in Greibach normal for
by irdc 3y ago
Prolog DCGs have pitfalls that aren’t immediately evident to someone only familiar with BNF, mainly that you have to specify your grammar in Greibach normal form (every nonterminal production starts with a terminal) to get any sort of performance out of them.
- YeGoblynQueenne 3y agoWoa, blast from the past! :D I used Greibach normal form grammars in my Master's, in 2014, when I was doing some grammar induction stuff with DCGs. Now, Greibach normal form is useful, but its use is to avoid left-recursions. That's not to say it improves performance: Prolog's SLDNF-Resolution just can't handle left-recursion and it will often "go infinite" with it (although many staple Prolog programs like member/2, append/3, reverse/2 etc. are left-recursive). DCGs are not the pinnacle of performance, sure, but that's not because of left-recursion. It's because a Definite Clause Grammar evaluated by SLDNF-Resolution is a left-right descent parser, and those are just not very efficient. I think it's O(n^3) to parse a CFG with an LR descent parser? So if you want better performance out of a DCG, parse it with a chart parser.