问题描述
Prolog相当新,但是我正在尝试实现无上下文语法,并且在通过具有我自己的规则的测试用例时遇到了问题.
Pretty new to Prolog, but I'm trying to implement a context-free grammar and I'm having an issue passing a test case with the rules I have.
我尝试将规则的顺序更改为看起来更符合逻辑,但是我似乎无法获得一致的正确输出,并且继续遇到相同的堆栈错误.我认为这与 vp->有关.vp,np.
是递归的,但是如果是这种情况,那么为什么 np->np,pp.
也给我一个错误?我的代码如下:
I've tried changing the order of my rules to seem more logically correct, but I can't seem to get consistent correct outputs and I continue to get the same stack error. I think it has something to do with vp --> vp, np.
being recursive, but if that's the case, then why doesn't np --> np, pp.
give me an error as well? My code is below:
:- use_module(library(tabling)).
:- table s/2.
s --> np, vp.
np --> det, n.
np --> np, pp.
vp --> vp, pp.
vp --> v, np.
pp --> p, np.
det --> [the].
n --> [cop].
n --> [criminal].
n --> [street].
v --> [chased].
p --> [in].
p --> [by].
将此查询理想地返回 true :
$- s([the,cop,chased,the,criminal], []).
并要求其返回 false :
$- s([the, cop, the, criminal, chased], []).
我都尝试过,但它们都给了我相同的错误:
I've tried both and they just give me the same error:
Stack limit (0.2Gb) exceeded
Stack sizes: local: 0.2Gb, global: 22Kb, trail: 5Kb
Stack depth: 1,561,893, last-call: 0%, Choice points: 1,561,869
Probable infinite recursion (cycle):
[1,561,893] vp([length:3], _1424)
[1,561,892] vp([length:3], _1456)
任何反馈表示赞赏!
推荐答案
问题是您构建了 左递归语法.实际上,如果我们查看您定义的规则,就会看到:
The problem is that you have constructed a left recursive grammar. Indeed if we look at the rules you defined, we see:
:- use_module(library(tabling)).
:- table s/2.
s --> np, vp.
np --> det, n.
np --> np, pp.
vp --> vp, pp.
vp --> v, np.
pp --> p, np.
det --> [the].
n --> [cop].
n --> [criminal].
n --> [street].
v --> [chased].
p --> [in].
p --> [by].
现在基于Prolog实现谓词的方式,它无法使用这种左递归语法,因为如果您调用 np/2
,它将首先调用 np/2
,因此我们永远都无法摆脱循环"(直到调用堆栈溢出).
Now based on how Prolog implements predicates, it can not work with such left recursive grammar, since if you call np/2
, it will first call np/2
, and hence we never get out of the "loop" (until the call stack overflows).
不过,我们可以在此处使用 tabling ,例如您以某种方式使用了 s/2
,这是不必要的,因为在 s
中没有左递归路径可以(直接或间接)产生 s->s,...
.我们需要表 np/2
和 vp/2
,例如:
We can however use tabling here, like you somehow did with s/2
, which is not necessary, since there is no left-recursive path in s
that yields (directly or indirectly) s --> s, ...
. We need to table np/2
and vp/2
, like:
:- use_module(library(tabling)).
:- table np/2.
:- table vp/2.
s --> np, vp.
np --> det, n.
np --> np, pp.
vp --> vp, pp.
vp --> v, np.
pp --> p, np.
det --> [the].
n --> [cop].
n --> [criminal].
n --> [street].
v --> [chased].
p --> [in].
p --> [by].
我们确实可以得到预期的结果:
We then indeed can obtain the expected results:
?- s([the,cop,chased,the,criminal], []).
true.
?- s([the, cop, the, criminal, chased], []).
false.
这篇关于超出堆栈限制(0.2Gb)...可能的无限递归(周期):的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!