Превышен предел стека (0,2 Гб) ... Вероятна бесконечная рекурсия (цикл): - PullRequest
Новая
       52

Превышен предел стека (0,2 Гб) ... Вероятна бесконечная рекурсия (цикл):

2 голосов
/ 28 мая 2019

Довольно плохо знаком с Прологом, но я пытаюсь реализовать контекстно-свободную грамматику, и у меня возникла проблема при прохождении тестового примера с моими правилами.

Я пытался изменить порядокиз моих правил, чтобы казаться более логически правильными, но я не могу получить последовательные правильные результаты, и я продолжаю получать ту же ошибку стека.Я думаю, что это как-то связано с рекурсивностью 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)

Любые отзывы приветствуются!

1 Ответ

2 голосов
/ 28 мая 2019

Проблема в том, что вы создали левую рекурсивную грамматику . Действительно, если мы посмотрим на правила, которые вы определили, мы увидим: 

:- use_module(library(tabling)).
:- table s/2.

s --> np, vp.
np --> det, n.
<b>np</b> --> <b>np</b>, pp.
<b>vp</b> --> <b>vp</b>, 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, и, следовательно, мы никогда не выйдем из «цикла» (до стек вызовов переполняется).

Однако мы можем использовать табулирование здесь, как вы как-то сделали с s/2, что не является необходимым, поскольку в s нет левого рекурсивного пути, который дает (прямо или косвенно) s --> s, .... Нам нужно для таблицы np/2 и vp/2, например: 

:- use_module(library(tabling)).
<b>:- table np/2.</b>
<b>:- table vp/2.</b>

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.
...