Программирование на языке пролог
Шрифт:
Приведенное утверждение для предиката группа_существи-тельногоговорит о том, как задачу выделения группы существительного свести к задаче выделения определителя и следующего за ним существительного. Это аналогично сведению задачи разбора предложения к выделению группы существительного, за которой следует группа глагола. Все это очень абстрактно. Ничто из сказанного не говорит нам о том, как много слов входят в состав определителя, группы существительного или предложения. Эта информация должна извлекаться, исходя из нашей версии правил, которые фактически вводят английские слова. Мы вновь можем представить их в виде утверждений языка Пролог, но на этот раз мы должны добавить дополнительный
определитель([the|Х],Х).
Это правило (грамматики) выражает тот факт, что определитель стоит в начале последовательности, начинающейся со слова the. Более того, определитель занимает лишь первое слово этой последовательности и оставляет все следующие за ним.
В действительности, для того чтобы показать, как в этой группе слов «используются» слова из последовательности и какая часть последовательности остается необработанной, к каждому предикату, распознающему группу слов некоторого вида, можно добавить дополнительный аргумент. В частности, для единообразия было бы разумно сделать то же самое и с предикатом предложение. Как теперь выглядит исходная цель, с которой мы обращаемся к программе? Необходимо решить, какие два аргумента задавать в вопросе для предиката предложение. Эти аргументы обозначают последовательность, с которой начинается обработка, и последовательность, оставшуюся после ее завершения. Очевидно, что первый из аргументов – тот же самый, что мы задавали ранее в предикате предложение. Кроме того, так как мы хотим выделить предложение, которое включает в себя всю последовательность целиком, то нам надо, чтобы после того, как предложение выделено, ничего не осталось, т. е. чтобы осталась лишь пустая последовательность. Поэтому мы должны обратиться к программе следующим образом:
?- предложение(the,man,eats,the,аррlе],[]).
Посмотрим теперь, как выглядит грамматика в целом после того, как мы переписали ее с учетом обсуждавшихся выше изменений:
предложение(S0,S):- группа_существительного(S0,S1), группа_глагола(S1,S).
группа_существительного(S0,S):- определитель(S0,S1), существительное(S1,S).
группа_глагола(S0,S):- глагол(S0,S).
группа_глагола(S0,S):- глагол(S0,S1), группа_существительного(S1,S).
определитель([the|S],S).
существительное([man|S],S).
существительное([аррle|S],S).
глагол([eats|S],S).
глагол([sings|S],S).
Таким образом, теперь мы получили эффективную версию программы для распознавания предложений, допустимых грамматикой. Однако, к сожалению, последняя запись программы выглядит несколько беспорядочной по сравнению с предыдущей версией. Все дополнительные аргументы засоряют ее и их необходимость не очевидна. Теперь мы рассмотрим, как преодолеть эту проблему.
9.3. Запись грамматических правил в Прологе
Специальная форма записи грамматических правил в языке Пролог была разработана, чтобы помочь программисту в написании синтаксических анализаторов, использующих описанные только что методы. Такая форма записи облегчает чтение программы, так как скрывается вся информация, не представляющая интереса. В силу того, что эта форма записи является более краткой, чем обычная для Пролога, вероятность сделать глупую опечатку также меньше, если для написания синтаксических анализаторов используются грамматические правила.
Хотя форма записи грамматических правил, о которой здесь идет речь, вводится сама по себе, важно помнить, что это лишь сокращенная
Рассматриваемая форма записи основывается на форме записи, использованной в начале этой главы для контекстно-свободных грамматик. Действительно, если бы грамматика, представленная в разд. 9.1 (она воспроизведена ниже), была введена в Пролог-систему, то она (грамматика) была бы оттранслирована в точности в те же самые утверждения, которые составляют последнюю версию программы синтаксического анализатора, приведенной в конце предыдущего раздела.
предложение--› группа_существительного, группа_глагола.
группа_существительного--› определитель, существительное.
группа_глагола--› глагол.
группа_глагола -› глагол, группа_существительного, определитель--› [the].
существительное--› [man].
существительное--› [apple].
глагол--› [eats].
глагол--› [sings].
На самом деле грамматические правила представляют структуры языка Пролог с главным функтором '--›' который объявлен как инфиксный оператор. Все, что должна сделать Пролог-система,- это проверить, имеет ли вводимый терм (при использовании предиката consultи ему подобных) указанный функтор и, если это так, оттранслировать его в соответствующее утверждение.
Как происходит эта трансляция? Прежде всего, каждый атом, обозначающий класс словосочетания, должен быть оттранслирован в предикат с двумя аргументами – для входной последовательности и последовательности, остающейся после обработки, как в нашей программе. Затем, всякий раз, когда в правиле встречаются идущие одно за другим имена словосочетаний, соответствующие предикаты должны быть расположены так, чтобы аргументы показывали, что последовательность, которая остается после обработки одного словосочетания, образует входную последовательность для следующего словосочетания. И наконец, всякий раз, когда в правиле указывается, что словосочетание может быть реализовано как последовательность более мелких словосочетаний, аргументы должны говорить о том, что число слов, входящих в словосочетание, равно суммарному числу слов, входящих в более мелкие словосочетания, упоминаемые в правой части правила. Эти критерии гарантируют, например, что правило:
предложение-› группа_существительного, группа_глагола.
транслируется в утверждение:
предложение (S0, S):- группа_существительного(S0,S1), группа_глагола(S1,S).
или
Между началом S0 и S имеется предложение, если между началом S0 и S1 имеется группа существительного, и если между началом S1 и S имеется группа глагола.