在Prolog的DCG语法规则堆栈溢出：如何有效地或懒洋洋地处理大名单(Stack overflow

我解析由一系列线的一个相当简单的文件格式，有一些空格分隔的字段的每一行，看起来像这样：

l 0x9823 1
s 0x1111 3
l 0x1111 12
⋮

我使用的是SWI-Prolog的。这是DCG我到目前为止有：

:- consult(library(pure_input)).

load_trace(Filename, Traces) :-
    phrase_from_file(trace_file_phrase(Traces), Filename).

trace_file_phrase([]) --> [].
trace_file_phrase([T|Ts]) --> trace_phrase(T), trace_file_phrase(Ts).

trace_phrase(access(Type, Address, SinceLast)) -->
    access_type(Type), space,
    address(Address),  space,
    nat(SinceLast),    newline.

access_type(load)  --> "l".
access_type(store) --> "s".

address(Number) --> "0x", hexnum(Number).

hexdigit(N)  --> digit(N).
hexdigit(10) --> "a". hexdigit(11) --> "b". hexdigit(12) --> "c".
hexdigit(13) --> "d". hexdigit(14) --> "e". hexdigit(15) --> "f".
hexnum(N) --> hexdigit(D), hexnum(D, N).
hexnum(N, N) --> [].
hexnum(A, N) --> hexdigit(D), { A1 is A*16 + D }, hexnum(A1, N).

newline --> "\n".
space --> " ".

%% the following two productions are courtesy of Lars Mans at
%% https://stackoverflow.com/questions/3279822/parsing-numbers-with-multiple-digits-in-prolog
digit(0) --> "0". digit(1) --> "1". digit(2) --> "2".
digit(3) --> "3". digit(4) --> "4". digit(5) --> "5".
digit(6) --> "6". digit(7) --> "7". digit(8) --> "8".
digit(9) --> "9".

nat(N)   --> digit(D), nat(D,N).
nat(N,N) --> [].
nat(A,N) --> digit(D), { A1 is A*10 + D }, nat(A1, N).

正如评论所说，我从那儿剽窃处理数字解析数与Prolog的多个数字。

我遇到的问题是一些文件都很大，比如，5-10 MB的顺序。在SWI-Prolog的默认堆栈不足这一点，并解析这些文件正在采取大量的时间，5-15秒左右。我对这个情况的几个问题：

凡在此代码的效率问题？我认为这是无论是在trace_file_phrase//1或nat//1 ，但这些都只是预感。
如果问题清单，有没有更好的方式来处理列表与DCG中比这个？
一个人如何，一般来说，诊断和治疗的性能问题DCG中像这样的？

Answer 1:

作为一般的话，你会发现名下更多的SO关于它的library(pio) 还使用更清洁的方式比较：

:- use_module(library(pio)).

你举的例子是太复杂了，所以我只会考虑一个稍微简单的情况下，换行分隔的数字列表：

nats([]) --> [].
nats([N|Ns]) --> nat(N), newline, nats(Ns).

那么，如何才能有效地测试这个？（这是你的问题3）的基本点library(pio)是可以使用普通的DCG中进行文件处理。但在小测试，你仍然可以使用简单的phrase/2 。所以，我做的：

?- phrase(nats(Ns),"1\n").
Ns = [1] ;
false.

你看到的; 提示？这意味着：序言无法决定下一步的答案是否会计算 - 所以给人们留下一个或更多的选择点开放。 而这仅适用于单个数字你能想象事情会如何堆积起来。

让你更深入：

?- phrase(digit(D),"1").
D = 1 ;
false.

再次邪恶的; ！为了使这项工作，一切都必须是确定的。有三种方法可以这样：

使用切割（和失去你的灵魂）

我祝你好运 - 最好的似乎只是重复元素后：

trace_file_phrase([]) --> [].
trace_file_phrase([T|Ts]) -->
   trace_phrase(T),
   !, % ugly, but...
   trace_file_phrase(Ts).

（这应该回答问题1）

但是，保持一分钟！什么是坏对这个! ？只要，因为恰好有一个答案trace_phrase//1东西是完美的。它只是，如果有更多的答案（或实际的解决方案），该切口可能会删除珍贵的答案。你怎么知道，如果有更多的解决方案？好了，你不知道。你不会看到他们，因为他们已经被切去。

`call_semidet/1`

这里有一个方法，以确保不会发生这种情况。这仅适用于无副作用的目标，可以两次无任何影响被称为：

call_semidet(Goal) :-
   (  call_nth(Goal, 2)
   -> throw(error(mode_error(semidet,Goal),_))
   ;  once(Goal)
   ).

这使用call_nth/2 ，如在另一篇文章中定义。（作为一种优化，实现可能避免调用Goal的两倍时，没有选择的余地，点开...）只是为了清楚，它是如何工作：

?- phrase(nat(N),"1234").
N = 1234 ;
false.

?- call_semidet(phrase(nat(N),"1234")).
N = 1234.

?- call_semidet((X=1;X=2)).
ERROR: Unknown error term: mode_error(semidet, (2=1;2=2))

因此，它使你的小语法有效定！因此，没有必要重新制定任何东西！

目前缺乏的是现在一些集成到这个语法。你可以做到这一点非常低的水平，或者说利用干净library(lambda) 。

phrase_semidet(NT) -->
   call(S0^S^call_semidet(phrase(NT,S0,S))).

注意，在这个非常特殊的情况下，我们不使用\重命名。

trace_file_phrase([]) --> [].
trace_file_phrase([T|Ts]) -->
   phrase_semidet(trace_phrase(T)),
   trace_file_phrase(Ts).

利用索引

最后，很辛苦，但干净的方法是将改写一切受益于更好的索引（也许有助于改善通用编制索引...）但是，这是一条漫长的道路。刚入手：

digit(D) --> [C],
   {c_digit(C,D)}.

c_digit(0'0,0).
c_digit(0'1,1).
c_digit(0'2,2).
c_digit(0'3,3).
c_digit(0'4,4).
c_digit(0'5,5).
c_digit(0'6,6).
c_digit(0'7,7).
c_digit(0'8,8).
c_digit(0'9,9).

现在，这为您提供：

?- phrase(digit(D),"1").
D = 1.

但是，你有确定性的另一个来源是相当因为你的方法定义的语法。在nat//2你看到它：

nat(N,N) --> [].
nat(A,N) --> digit(D), ... .

第一条规则始终适用，那就是"1234\n"会被解析为"1" "12" "123" "1234"只有以下newline//0意识到它就够走过去-然后坚持给它。

你可以重写的东西了，只那么，代码不再是你喜欢的纯小规格的，不是吗？好吧，也许事情会改善未来。

例如索引是SWI明显优于它曾经是，也许还东西太多演变这里....

的意图library(pio)是让这个过程开始。与此相比，哈斯克尔-我们远离interact效率明智的！但是没有内在的成本：

... --> [] | [_], ... .

?- phrase_from_file((...,"searchstring",...),fichier).

是一样的grep高效 - 空间明智的。也就是说，它运行在恒定的空间。所以希望更多的代码将运行在更好的未来。

编辑：BTW， library(pio)也已经有一定影响效率的明智：作为Wadler的固定部分空间泄漏GC相显著改善，以同样的方式非常多- 25年前的纸张。事情演变...

Answer 2:

我已经验证了上一个2MB的文件中的计算器。然后我重写使用库（DCG /基础）的语法，现在正在工作。

:- [library(dcg/basics)].

load_trace_0(Filename, Ls) :-
    phrase_from_file(lines(Ls), Filename).

lines([s(H,I)|R]) -->
    "s 0x", xinteger(H), " ",
    integer(I), blanks,
    !, lines(R).
lines([l(H,I)|R]) -->
    "l 0x", xinteger(H), " ",
    integer(I), blanks,
    !, lines(R).
lines([]) --> [].

但后来我试图把切你的语法，并正在为好。所以从@gusbro（+1）的答案解决您的问题。

Answer 3:

关于效率问题：

如果输入通常是良好的，那么我认为你应该换的条款nat/4和hexnum/4 ，所以他们会读：

nat(A,N) --> digit(D), { A1 is A*10 + D }, nat(A1, N).
nat(N,N) --> [].

hexnum(A, N) --> hexdigit(D), { A1 is A*16 + D }, hexnum(A1, N).
hexnum(N, N) --> [].

因为你只想停止解析数时，有没有更多的数字消费。

如果使用得当，切（ ! ）可以帮助你的性能代价，也关于堆栈溢出，因为它修剪序言中评价树。例如，你可以提交（ ! ）在结束trace_file_phrase/3 （也就是后newline ），因为你并不需要再次重新分析输入的那部分找到其他的解决方案。

文章来源: Stack overflow in Prolog DCG grammar rule: how to handle large lists efficiently or lazily