Список как факты

Попробуем объяснить это на контрпримере. Уточним существительные, глаголы и т. д. с помощью простых фактов:

det(the). 
det(a). 

n(woman). 
n(man). 

v(shoots).

Теперь мы можем реализовать фразу существительного np как:

np([X,Y]) :-
    det(X),
    n(Y).

Другими словами, мы говорим: «именная группа — это предложение с двумя словами, первое из которых — det, второе — n». И это сработает: если мы запросим np([a,woman]), он будет успешным и т. д.

Но теперь нам нужно сделать кое-что более продвинутое, определить глаголную фразу. Есть две возможные глагольные фразы: одна с глаголом и именная фраза, которая изначально была определена как:

vp(X,Z):- v(X,Y),np(Y,Z).

Мы могли бы определить это как:

vp([X|Y]) :-
    v(X),
    np(Y).

И тот, у которого всего один глагол:

vp(X,Z):- v(X,Z).

Это может быть преобразовано в:

vp([X]) :-
    v(X).

Проблема угадывания

Проблема, однако, в том, что оба варианта имеют разное количество слов: есть глагольные фразы с одним словом и с тремя словами. На самом деле это не проблема, но теперь скажем — я знаю, что это неправильный английский — существует предложение, определяемое как vp, за которым следует np, так что это будет:

s(X,Z):-  vp(X,Y),  np(Y,Z).

в исходной грамматике.

Проблема в том, что если мы хотим преобразовать это в наш новый способ представления, нам нужно знать, сколько vp будет потреблять (сколько слов будет съедено vp). Мы не можем знать это заранее: поскольку на данный момент мы мало что знаем о предложении, мы не можем предположить, съест ли vp одно или три слова.

Конечно, мы можем угадать количество слов с помощью:

s([X|Y]) :-
    vp([X]),
    np(Y).
s([X,Y,Z|T]) :-
    vp([X,Y,Z]),
    np(Z).

Но я надеюсь, вы можете себе представить, что если вы определите глагольные фразы с 1, 3, 5 и 7 словами, все станет проблематично. Другой способ решить эту проблему - оставить это Прологу:

s(S) :-
    append(VP,NP,S),
    vp(VP),
    np(NP).

Теперь Prolog сначала угадает, как разделить предложение на две части, а затем попытается сопоставить каждую часть. Но проблема в том, что для предложения с n словами есть n точек останова.

Таким образом, Prolog, например, сначала разделит его как:

VP=[],NP=[shoots,the,man,the,woman]

(помните, мы поменяли местами порядок глагольной группы и именной группы). Очевидно, vp не очень обрадуется, если получит пустую строку. Так что это будет легко отвергнуто. Но далее говорится:

VP=[shoots],NP=[the,man,the,woman]

Теперь vp устраивает только shoots, но чтобы понять это, потребуются некоторые вычислительные усилия. Однако np не в восторге от этой длинной части. Итак, Пролог снова возвращается:

VP=[shoots,the],NP=[man,the,woman]

теперь vp снова будет жаловаться, что ему дали слишком много слов. Наконец, Prolog правильно разделит его:

VP=[shoots,the,woman],NP=[the,woman]

Дело в том, что он требует большого количества догадок. И для каждого из этих предположений vp и np также потребуется работа. Для действительно сложной грамматики vp и np могут еще больше разделить предложение, что приведет к огромному количеству проб и ошибок.

Истинная причина в том, что append/3 не имеет «семантического» представления о том, как разделить предложение, поэтому он пробует все возможности. Однако более интересен подход, при котором vp может предоставить информацию о том, какая доля предложения ему действительно нужна.

Кроме того, если вам нужно разбить предложение на 3 части, количество способов сделать это даже увеличивается до O(n^2) и так далее. Так что гадать не получится.

Вы также можете попытаться сгенерировать случайную глагольную фразу, а затем надеяться, что глагольная фраза совпадет:

s(S) :-
    vp(VP),
    append(VP,NP,S),
    np(NP).

Но в этом случае количество угаданных глагольных фраз резко возрастет. Конечно, вы можете давать «подсказки» и т. д., чтобы ускорить процесс, но это все равно займет некоторое время.

Решение

Что вы хотите сделать, так это указать часть предложения для каждого предиката, чтобы предикат выглядел так:

predicate(Subsentence,Remaining)

Subsentence — это список слов, начинающихся с этого предиката. Например, словосочетание с существительным может выглядеть как [the,woman,shoots,the,man]. Каждый предикат потребляет интересующие его слова: слова до определенного момента. В этом случае словосочетание-существительное интересует только ['the','woman'], потому что это словосочетание-существительное. Чтобы выполнить оставшийся синтаксический анализ, он возвращает оставшуюся часть [shoots,the,woman] в надежде, что какой-то другой предикат сможет использовать оставшуюся часть предложения.

Для нашей таблицы фактов это легко:

det([the|W],W). 
det([a|W],W). 

n([woman|W],W). 
n([man|W],W). 

v([shoots|W],W).

Таким образом, это означает, что если вы запросите набор: [the,woman,shoots,...] и спросите det/2, является ли это определителем, он ответит: "да, the является определителем, но оставшаяся часть [woman,shoots,...]" не является частью определителя, пожалуйста, сопоставьте ее. с чем-то другим.

Это сопоставление выполняется, потому что список представлен как связанный список. [the,woman,shoots,...] на самом деле представляется как [the|[woman|[shoots|...]]] (поэтому он указывает на следующий «подсписок»). Если вы соответствуете:

    [the|[woman|[shoots|...]]]
det([the|W]                   ,W)

Это объединит [woman|[shoots|...]] с W и, таким образом, приведет к:

det([the|[woman|[shoots|...]],[woman|[shoots|...]]).

Таким образом, возвращая оставшийся список, он, таким образом, израсходовал the часть.

Предикаты более высокого уровня

Теперь, если мы определим именное словосочетание:

np(X,Z):-  det(X,Y),  n(Y,Z).

И мы снова звоним с [the,woman,shoots,...], он запросит объединение X с этим списком. Сначала он вызовет det, который будет потреблять the без необходимости возврата. Далее Y равно [woman,shoots,...], теперь n/2 поглотит женщину и вернет [shoots,...]. Это также результат, который np вернет, и другой предикат должен будет его использовать.

Полезность

Скажем, вы вводите свое имя в качестве дополнительного существительного:

n([doug,smith|W],W).

(извините за использование маленьких регистров, но в противном случае Пролог видит их как переменные).

Он просто попытается сопоставить первые два слова с doug и smith, и если это удастся, попытается сопоставить оставшуюся часть предложения. Таким образом, можно составить такое предложение, как: [the,doug,smith,shoots,the,woman] (извините за это, кроме того, в английском языке некоторые именные фразы напрямую сопоставляются с существительным np(X,Y) :- n(X,Y), поэтому the можно удалить для более сложной английской грамматики).

Угадай, полностью устранены?

Угадывание полностью исключено? Нет. Все еще возможно, что есть перекрытие в потреблении. Например, вы можете добавить:

n([doug,smith|W],W).
n([doug|W],W).

В этом случае, если вы запросите [the,doug,smith,shoots,the,woman]. Сначала он будет потреблять/съедать в det, затем он будет искать существительное для потребления из [doug,smith,...]. Есть два кандидата. Пролог сначала попытается съесть только doug и сопоставить [smith,shoots,...] как целое глагольное словосочетание, но, поскольку smith не является глаголом, он отступит, пересмотрит возможность употребления только одного слова и, таким образом, решит вместо этого съесть и doug, и smith как существительное.

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

Вывод

Используя списки различий, вы можете съесть произвольное количество слов. Остаток возвращается таким образом, что другие части предложения, такие как глагольная фраза, стремятся потреблять остаток. Кроме того, список всегда полностью обоснован, поэтому никто не использует грубую силу, чтобы сначала создать все виды глагольных фраз.

Этот ответ является продолжением ответа @mat. Давайте действовать поэтапно:

1. Начнем с кода, показанного в ответе @mat:

   s   --> np, vp.
   
   np  --> det, n.
   
   vp  --> v, np.
   vp  --> v.
   
   det --> [the].
   det --> [a].
   
   n   --> [woman].
   n   --> [man].
   
   v   --> [shoots].
   

2. До сих пор мы использовали (',')/2: (A,B) означает последовательность A, за которой следует последовательность B.

   Далее мы также будем использовать ('|')/2: (A|B) означает последовательность A или последовательность B.

   Для получения информации об управляющих конструкциях в телах грамматики прочитайте это руководство. раздел.

   s   --> np, vp.
   
   np  --> det, n.
   
   vp  --> v, np | v.
   
   det --> [the] | [a].
   
   n   --> [woman] | [man].
   
   v   --> [shoots].
   

3. Мы можем сделать код более кратким, немного «встраивая»:

   s  --> np, vp.
   
   np --> ([the] | [a]), ([woman] | [man]).
   
   vp --> v,np | v.
   
   v  --> [shoots].
   

4. Как насчет еще одного встраивания --- как предложил @mat в своем комментарии...

   s  --> np, [shoots], (np | []).
   
   np --> ([the] | [a]), ([woman] | [man]).
   

5. Доведите это до максимума! (Следующее может быть записано как однострочник.)

   ?- phrase((( [the]
              | [a]), ( [woman] 
                      | [man]), [shoots], ( ( [the] 
                                            | [a]), ( [woman] 
                                                    | [man]) 
                                          | [])),
             Ws).
   

У всех разных формулировок есть свои плюсы и минусы, например, очень компактный код сложнее расширять, но он может потребоваться при нехватке места — например, при размещении кода на слайдах презентации.

Пример запроса:

?- phrase(s,Ws).
  Ws = [the, woman, shoots, the, woman]
; Ws = [the, woman, shoots, the, man]
; Ws = [the, woman, shoots, a, woman]
; Ws = [the, woman, shoots, a, man]
; Ws = [the, woman, shoots]
; Ws = [the, man, shoots, the, woman]
; Ws = [the, man, shoots, the, man]
; Ws = [the, man, shoots, a, woman]
; Ws = [the, man, shoots, a, man]
; Ws = [the, man, shoots]
; Ws = [a, woman, shoots, the, woman]
; Ws = [a, woman, shoots, the, man]
; Ws = [a, woman, shoots, a, woman]
; Ws = [a, woman, shoots, a, man]
; Ws = [a, woman, shoots]
; Ws = [a, man, shoots, the, woman]
; Ws = [a, man, shoots, the, man]
; Ws = [a, man, shoots, a, woman]
; Ws = [a, man, shoots, a, man]
; Ws = [a, man, shoots].                  % 20 solutions

Я точно знаю, что вы имеете в виду. Сначала довольно сложно думать о различиях в списках. Хорошая новость заключается в том, что обычно вам не нужно этого делать.

Существует встроенный формализм под названием «Грамматики определенных предложений» (DCG), который делает совершенно ненужным ручное кодирование различий в списках в таких случаях, как ваш.

В вашем примере я рекомендую вам просто написать это как:

s --> np, vp.

np --> det, n.

vp --> v, np.
vp --> v.

det --> [the].
det --> [a].

n --> [woman].
n --> [man].

v --> [shoots].

и примите тот факт, что в DCG [T] представляет терминал T, а , читается как «и затем». Вот как описывать списки с DCG.

Вы уже можете использовать это, чтобы запросить все решения, используя интерфейс phrase/2 для DCG:

?- phrase(s, Ls).
Ls = [the, woman, shoots, the, woman] ;
Ls = [the, woman, shoots, the, man] ;
Ls = [the, woman, shoots, a, woman] ;
etc.

Поначалу это трудно понять в процедурных терминах, поэтому я предлагаю вам не пытаться это делать. Вместо этого сосредоточьтесь на декларативном прочтении грамматики и убедитесь, что она описывает списки.

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

Списки различий работают так (объяснение непрофессионала).

Предположим, что добавление используется для соединения двух поездов X и Y.

X = {1}[2][3][4]     Y = {a}[b][c]

{ } - представляет собой отсек с двигателем или головкой.

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

Добавление происходит следующим образом: новый поезд Z теперь Y, т. е. {a}[b][c] затем двигатель снимается с головы Z и помещается в хвостовое отделение, удаленное от X, а новый поезд Z:

Z = {4}[a][b][c]

Тот же процесс повторяется

Z = {3}[4][a][b][c]
Z = {2}[3][4][a][b][c]
Z = {1}[2][[3][4][a][b][c]

наш новый длинный поезд.

Введение списков различий похоже на крючок toa на конце X, который можно легко прикрепить к Y. Последний крючок отбрасывается.

n([man|W],W).

W — это крючок, объединение W с главой списка преемников — процесс закрепления.