Программирование на языке пролог

существительное--› [apple].

глагол--› [eats].

глагол--› [sings].

На самом деле грамматические правила представляют структуры языка Пролог с главным функтором '--›' который объявлен как инфиксный оператор. Все, что должна сделать Пролог-система,- это проверить, имеет ли вводимый терм (при использовании предиката consultи ему подобных) указанный функтор и, если это так, оттранслировать его в соответствующее утверждение.

Как происходит эта трансляция? Прежде всего, каждый атом, обозначающий класс словосочетания, должен быть оттранслирован в предикат с двумя аргументами – для входной последовательности и последовательности, остающейся после обработки, как в нашей программе. Затем, всякий раз, когда в правиле встречаются идущие одно за другим имена словосочетаний, соответствующие предикаты должны быть расположены так, чтобы аргументы показывали, что последовательность, которая остается после обработки одного словосочетания, образует входную последовательность для следующего словосочетания. И наконец, всякий раз, когда в правиле указывается, что словосочетание может быть реализовано как последовательность более мелких словосочетаний, аргументы должны говорить о том, что число слов, входящих в словосочетание, равно суммарному числу слов, входящих в более мелкие словосочетания, упоминаемые в правой части правила. Эти критерии гарантируют, например, что правило:

предложение-› группа_существительного, группа_глагола.

транслируется в утверждение:

предложение (S0, S):- группа_существительного(S0,S1), группа_глагола(S1,S).

или

Между началомS0иSимеется предложение, если между началомS0иS1имеется группа существительного, и если между началомS1иSимеется группа глагола.

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

определитель--› [the].

транслируется в утверждение:

определитель(the|S],S).

Если программа синтаксического анализатора представлена в виде совокупности грамматических правил, то каким образом надо задать целевые утверждения, чтобы можно было обработать их программой? Так как известно, как грамматические правила транслируются в утверждения обычного Пролога, то можно выразить целевые утверждения обычным образом, добавив при этом дополнительные аргументы. Первый добавляемый аргумент представляет обрабатываемый список слов, а второй аргумент соответствует списку слов, оставшемуся после обработки, который как правило является пустым списком []. Таким образом, целевое утверждение можно задать так:

?- предложение([thе, man, eats,the,apple],[]).

?- группа_существительного([the,man,sings],X).

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

phrase (P,L)истинно, если списокLявляется допустимым словосочетанием типаР.

Таким образом, можно было бы заменить первое из приведенных выше целевых утверждений следующим:

?- phrase(прeдложeниe, [the,man,eats,the,apple]).

Заметим, что определение предиката phraseпредполагает, что обрабатывается весь список целиком, а список, оставшийся после обработки должен быть пустым. Поэтому второе целевое утверждение нельзя изменить, используя предикат phrase.Если в реализации Пролога нет встроенного предиката phrase,то его можно легко определить следующим образом:

phrase(P,L):- Goal =.. [P,L,[]], call(Goal).

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

Упражнение 9.1.Может быть вы захотите определить на Прологепроцедуру translateтаким образом, что translate(X,Y)истинно, если X– грамматическое правило (подобное тем, с какими мы сталкивались в этом разделе), a Y– терм, представляющий соответствующее утверждение Пролога. Это упражнение довольно трудное. Процедуры подобные translateимеются в Пролог-системе либо как встроенные, либо в виде библиотечных программ. Но если вы действительно напишите процедуру translate,то это поможет вам понять, что представляет собой процесс трансляции.

9.4. Присоединение дополнительных аргументов

До сих пор рассматривался лишь довольно ограниченный класс грамматических правил. В этом разделе мы введем одно полезное расширение, позволяющее использовать в грамматических правилах дополнительные аргументы. Это «расширение» не выходит за рамки стандартных средств, предоставляемых в Прологе для записи грамматических правил.