Prolog 非常新,但我正在尝试实现上下文无关语法,并且我在通过带有我拥有的规则的测试用例时遇到了问题。
我尝试更改规则的顺序以使其在逻辑上更正确,但似乎无法获得一致的正确输出,并且继续出现相同的堆栈错误。我认为这与 vp --> vp, np.
递归有关,但如果是这样,那么为什么 np --> np, pp.
也不会给我一个错误?我的代码如下:
:- 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], []).
我都试过了,他们只是给了我同样的错误:
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)
任何反馈表示赞赏!
最佳答案
问题是你构造了一个 left recursive grammar .事实上,如果我们查看您定义的规则,我们会看到:
:- 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
,因此我们永远不会退出“循环”(直到调用堆栈溢出)。但是我们可以使用 tabling在这里,就像你对
s/2
所做的一样,这是不必要的,因为在 s
中没有左递归路径产生(直接或间接)s --> s, ...
.我们需要表 np/2
和 vp/2
, 喜欢::- 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].
那么我们确实可以得到预期的结果:
?- s([the,cop,chased,the,criminal], []).
true.
?- s([the, cop, the, criminal, chased], []).
false.
关于recursion - 超出堆栈限制 (0.2Gb)...可能无限递归(循环):,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56334823/