Пролог английской грамматики без ограничений

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

Вот мои правила: (вп -> глагольная фраза, нп -> именная фраза, ап -> прилагательная фраза, пп -> подготовительная фраза)

    verb(S) :- member(S, [put,  pickup, stack, unstack]).
    det(S) :- member(S, [the]).
    adj(S) :- member(S, [big, small, green, red, yellow, blue]).
    noun(S) :- member(S, [block, table]).
    prep(S) :- member(S, [on, from]).

    vp([V|R]) :- verb(V), pp(PP), np(NP), append(NP, PP, R).
    np([D, N]) :- det(D), noun(N).
    np([D|R]) :- det(D), ap(AP), noun(N), append(AP, [N], R).
    ap([A]) :- adj(A).
    ap([A|R]) :- adj(A), ap(R).
    pp([P|R]) :- prep(P), np(R).

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

Например, следующий запрос никогда не даст S = [положить, красный, блок, на, зеленый, блок], потому что он сначала расширит прилагательную фразу слева «красный» до бесконечных возможностей, прежде чем пытаться выполнить правильно.

?- vp(S)
S = [put, the, red, green, block, on, the, block] ;

infinite-loop prolog left-recursion dcg failure-slice
person Khodeir    schedule 27.03.2013    source источник
comment
Я думаю, вы имеете в виду контекстно-свободную грамматику.   -  person Daniel Lyons    schedule 28.03.2013

Ответы (3)


arrow_upward
5
arrow_downward

Короткий ответ: используйте грамматику определенных предложений (dcg ) для представления вашей грамматики. См. этот ответ для типичной кодировки.

Но теперь к вашей реальной проблеме в вашей программе. Вы не только не получите желаемого ответа; ситуация еще хуже: даже в гораздо более простом фрагменте вашей программы у вас будут те же проблемы. Вот наименьший фрагмент вашей программы, который до сих пор не завершается:

verb(S) :- member(S, [put,  pickup, stack, unstack]).
det(S) :- member(S, [the]).
adj(S) :- member(S, [big, small, green, red, yellow, blue]).
noun(S) :- false, member(S, [block, table]).
prep(S) :- member(S, [on, from]).

vp([V|R]) :- verb(V), pp(PP), false, np(NP), append(NP, PP, R).
np([D, N]) :- false, det(D), noun(N).
np([D|R]) :- det(D), ap(AP), false, noun(N), append(AP, [N], R).
ap([A]) :- false, adj(A).
ap([A|R]) :- adj(A), ap(R), false.
pp([P|R]) :- prep(P), np(R), false.

?- vp([put, the, red, green, block, on, the, block]).

Вставив цели false мы получили небольшой фрагмент вашей программы, который до сих пор не завершается. Фактическим источником является ap/1, который является рекурсивным, но не ограничен фактическим вводом. Дополнительные примеры см. в разделе failure-slice. .

Нет простого способа исправить вашу программу. Самый простой выход — использовать грамматики.

person false    schedule 27.03.2013
comment
@DanielLyons: В этом и заключается идея срезов отказа: вы должны изменить что-то в видимой части. Зачеркнутая часть значения не имеет. - person false; 28.03.2013
comment
@DanieLyons: Вы путаете завершение со случайным нахождением ответа. Да, иногда вы получаете ответы. Но вы не можете легко предсказать, когда. Также добавление vp(_). в качестве факта сверху сделает это... - person false; 28.03.2013
comment
@DanielLyons: весь фрагмент отказа является причиной того, что программа не завершается. И, пожалуйста, помните, что и Prolog, и DCG были разработаны именно для решения этой проблемы. - person false; 28.03.2013
comment
Вернувшись, я теперь вижу, что неправильно понял вопрос ОП. Прошу прощения за флейм. - person Daniel Lyons; 28.03.2013
comment
@DanielLyons: Все в порядке! Вы удалили свои собственные комментарии? (Я не помечал их, нашел их в порядке). Но в любом случае: я думаю, вы могли бы извлечь большую выгоду из понятия «срез неудачи». - person false; 28.03.2013
comment
Я сделал, они ненужный беспорядок. Я хотел бы узнать больше о срезах неудач (то, что вы так увлечены ими, на самом деле является довольно сильным стимулом). Я все собираюсь сесть за книгу О'Киф и покопаться в них и в ссылках, которые у вас есть. - person Daniel Lyons; 28.03.2013
comment
stackoverflow.com/questions/10139640/ также содержит ссылку. Я не уверен, что вы имеете в виду под ненужным беспорядком. С помощью фрагмента отказа вы можете сузить размер вашей программы до источника незавершения. - person false; 28.03.2013
comment
Я имел в виду, что мои комментарии были беспорядком. - person Daniel Lyons; 28.03.2013

arrow_upward
1
arrow_downward

Похоже, вы злоупотребляете генеративной силой Пролога, помещая добавление в последнюю позицию. Попробовал поменять на более разумное место:

...
vp([V|R]) :- verb(V), append(NP, PP, R), pp(PP), np(NP).
np([D, N]) :- det(D), noun(N).
np([D|R]) :- det(D), append(AP, [N], R), ap(AP), noun(N).
...

и теперь ваш парсер видимо работает.

?- vp([put, the, red, green, block, on, the, block]).
true .

но предлагаю, как уже сделал false (+1), переключиться на DCG для разбора.

person CapelliC    schedule 28.03.2013

arrow_upward
0
arrow_downward

Фундаментальная проблема заключается в том, что Prolog предназначен для выполнения DFS по правилам, поэтому, когда дело доходит до проблем генерации в бесконечном пространстве поиска (как в вашем случае), части пространства могут остаться нетронутыми. Независимое от платформы исправление состоит в том, чтобы дополнить грамматику ограничением глубины и уменьшить глубину при каждом рекурсивном вызове. Как только глубина достигает 0, терпит неудачу. Постепенно увеличивая глубину повторяющимися запросами (например, vp(S, 1). vp(S, 2).), вы гарантируете, что в конечном итоге будут затронуты все части пространства состояний.

Это в основном просто итеративное углубление. Если вы пользуетесь SWI-PL, вы также можете использовать call_with_depth_limit/3 предикат, чтобы сделать то же самое без изменения грамматики.

person Kyle Dewey    schedule 23.06.2014
comment
Этот вопрос был о грамматиках, где список ввода может использоваться для значительного ограничения пространства поиска - часто вплоть до минимального линейного случая. Итеративное углубление в целом хорошо, но его наивное применение приводит к недопустимым накладным расходам. - person false; 23.06.2014