The time complexity of a look ahead
parser with one word token look ahead and
one character look ahead, and Prolog code
that is optimized towards clauses that
use first argument indexing, you can view
it as a kind of table driven parser with
push down, althought its Prolog, should be only
O(N+M), where N=number of characters and M=number of
words. It has linear complexity and not
something else. In 1965 Donald Knuth proposed
LR(k) parser, which are bottom up, but the idea
here is LL(k) parser, which are top down.
Both parsing algorithms run in linear time.
Mild Shock schrieb:
I can make a case of such a comparison,
DCG pipe dream versus proper look-ahead:
/* Scryer Prolog 0.9.4-135 */
?- time((between(1,1000,_), data(X), json_chars(Y,X,[]), fail; true)).
% CPU time: 0.283s, 2_506_022 inferences
true.
/* SWI-Prolog 9.3.8 */
?- time((between(1,1000,_), data(X), atom_json_term(X,Y,[]), fail; true)).
% 44,998 inferences, 0.016 CPU in 0.006 seconds (281% CPU, 2879872 Lips) true.
I think the speed difference of a factor
20x is not because of native float parsing.
The example doesn’t have much float:
data("{ \"a\":123 }").
So whats the bug in the DCG parser by
Scryer Prolog? Why does the parser written by
Jan W. not have the same defect?
Why does the number of inferences differ so much?
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)