Разбор пролога исчерпан

У меня есть этот код

s(W) :- append(W1,W2,W), np(W1), vp(W2).

vp(W) :- append(W1,W2,W), v(W1), np(W2).

np(W) :-
   (  append(W1,W2,W), pn(W1), ph(W2)
   ;  append(W1,W2,W), det(W1), n(W2)
   ).

pn([hans]).

ph([]).

v([beobachtet]).

n([mann]).
n([fernrohr]).

p([mit]).

det([den]).
det([dem]).

когда я снимаю что-то вроде np(X).vp(X). или же pp(X) получить один возможный анализ, а затем ошибку вне стека. когда я снимаю s(X). Я даже не получаю разбор. Я знаю, что это потому, что работает какой-то бесконечный цикл, но я просто не могу указать, в какой момент он зацикливается. Я подумал, что это может произойти из-за использования одинаковых имен для всех моих переменных, но потом я изменил их на отдельные, и это ничего не изменило.

кто-нибудь получил подсказку?

заранее спасибо!

2 ответа

Решение

Причина выхода из стека

Давайте посмотрим на следующую строку из вашего кода:

vp(W) :- append(W1,W2,W), v(W1), np(W2).

Бег append(W1, W2, W) в отрыве дает следующее:

?- append(W1, W2, W).
W1 = [],
W2 = W ;
W1 = [_G1108],
W = [_G1108|W2] ;
W1 = [_G1108, _G1114],
W = [_G1108, _G1114|W2] ;
W1 = [_G1108, _G1114, _G1120],
W = [_G1108, _G1114, _G1120|W2] .

Как вы видете, W1 список увеличивающейся длины. Только для длины 1 это дает решение (так как v(W1)). После этого первого экземпляра, W1 становится все дольше и дольше и дольше и..., но v(W1) не удастся для списков большей длины.

DCG грамматика

В Прологе вы можете использовать нотацию DCG для создания грамматики. Ваша грамматика будет выглядеть следующим образом:

s --> np, vp.
np --> pn.
np --> det, n.
vp --> v, np.

det --> [den].
det --> [dem].

n --> [mann].
n --> [fernrohr].

pn --> [hans].

v --> [beobachtet].

Пример использования

?- phrase(s, S).
S = [hans, beobachtet, hans] ;
S = [hans, beobachtet, den, mann] ;
S = [hans, beobachtet, den, fernrohr] ;
S = [hans, beobachtet, dem, mann] ;
S = [hans, beobachtet, dem, fernrohr] ;
S = [den, mann, beobachtet, hans] ;
S = [den, mann, beobachtet, den, mann] ;
S = [den, mann, beobachtet, den, fernrohr] ;
S = [den, mann, beobachtet, dem, mann] ;
S = [den, mann, beobachtet, dem, fernrohr] ;
S = [den, fernrohr, beobachtet, hans] ;
S = [den, fernrohr, beobachtet, den, mann] ;
S = [den, fernrohr, beobachtet, den, fernrohr] ;
S = [den, fernrohr, beobachtet, dem, mann] ;
S = [den, fernrohr, beobachtet, dem, fernrohr] ;
S = [dem, mann, beobachtet, hans] ;
S = [dem, mann, beobachtet, den, mann] ;
S = [dem, mann, beobachtet, den, fernrohr] ;
S = [dem, mann, beobachtet, dem, mann] ;
S = [dem, mann, beobachtet, dem, fernrohr] ;
S = [dem, fernrohr, beobachtet, hans] ;
S = [dem, fernrohr, beobachtet, den, mann] ;
S = [dem, fernrohr, beobachtet, den, fernrohr] ;
S = [dem, fernrohr, beobachtet, dem, mann] ;
S = [dem, fernrohr, beobachtet, dem, fernrohr].

Непрекращение часто трудно понять в Прологе. Возьмите в качестве примера запрос pn(X), Очевидно, должно быть:

W = [hans] ;
W = [den, mann] ;
W = [den, fernrohr] ;
W = [dem, mann] ;
W = [dem, fernrohr].

в качестве решения, (независимо от [den, fernrohr] не будучи немцем). Но Пролог находит только один, а затем циклы. В некотором смысле вы можете считать себя счастливым, потому что вы обнаружили эту проблему на ранней стадии. Но представьте себе ситуацию, когда перед циклом есть много ответов. Так что у вас сложилось впечатление, что все в порядке, но это не так.

Чтобы найти эти проблемы немного быстрее, спросите pn(X), false вместо. Хотя этот запрос никогда не будет истинным, он будет завершен точно так же, как pn(X) но он не будет производить все эти раздражающие решения.

Вы можете пойти еще дальше, вставив false в вашей программе результирующая программа называется срезом сбоев. С чистой, монотонной программой, как ваша, справедливо следующее:

Если срез ошибки не завершается (для определенного запроса), то исходная программа не завершается для этого запроса.

Отрезанные фрагменты, как правило, намного короче, поэтому они быстрее читаются и понимаются. В случае np(X)

?- НП (Х), ложь.

НП (Ш):-
   (добавить (W1,W2,W), false, pn (W1), ph (W2); ложь, добавление (W1,W2,W), дет (W1), n ​​(W2)).

Таким образом, вам больше не нужно тратить свое время на поиск pn/1, ph/1, det/1, или же n/1 для петель. Только один срез-отказ уже вызывает прекращение. Таким образом: пока это не исправлено, бессмысленно смотреть на оставшуюся программу.

Прямое исправление было бы поставить append/3 в конце. Это работает для np/1, Но это не работает для рекурсивных нетерминалов со списком фиксированной длины.

До рождения Пролога люди действительно рассматривали именно такие кодировки. Они были озадачены этим несоответствием: и грамматика, и логика предикатов являются декларативным формализмом. Но хотя многие грамматики могут быть проанализированы очень эффективно, доказательство того, что предложение описывается грамматикой, кажется, подразумевает гигантское пространство поиска. Где этот эффективный метод для использования логики здесь?

Ответом была конкретная кодировка, которая позволяла разрешению анализировать простые грамматики так же эффективно, как рукописные синтаксические анализаторы, которые, таким образом, породили Пролог. На сегодняшний день эта кодировка используется в Прологе для реализации грамматик для определенных выражений. Посмотрите ответ @WouterBeeks, как это делается.

Другие вопросы по тегам