предложение(Х,предложение(NP,VP))--› группа_существительного(X,NP), группа_глагола(X,VP).
Это правило указывает, что, если можно найти последовательность, составляющую группу существительного с деревом разбора NP,за которой следует последовательность, составляющая группу глагола, с деревом разбора VPто можно найти последовательность, составляющую полное предложение, и деревом разбора для этого предложения является предложениe(NP,VP).Или, в более процедурной формулировке: для того, чтобы выполнить разбор предложения необходимо найти группу существительного, за которой следует группа глагола, и затем объединить деревья разбора этих двух составляющих, используя функтор предложениедля построения дерева разбора предложения. Отметим, что аргументы X– это аргументы, использовавшиеся ранее для согласования формы числа, и решение поставить аргументы для построения дерева разбора после, а не перед ними является совершенно произвольным. Если вам трудно понять это расширение возможностей грамматических правил, то полезно напомнить, что последнее правило представляет собою всего лишь краткую запись следующего утверждения на языке Пролог:
предложение(Х,предложение(NР,VP),S0,S):-группа_существительного(Х,NР,S0,S1),
группа_глагола(Х,VР,S1,S).
где S0, S1и S– части входной последовательности слов. Аргументы, предназначенные для построения дерева разбора, можно ввести в правила грамматики обычным образом. Здесь приведен получившийся после этого фрагмент грамматики (аргумент, используемый для согласования формы числа, для ясности опущен):
предложение(предложение(NР,VP))--›группа _существительного (NP), группа _ глагола (VP).
группа_глагола(группа_глагола(V))--› глагол(V).
существительное(существительное(man)) – › [man].
глагол(глагол(eats))--› [eats].
Механизм трансляции, необходимый для перевода грамматических правил с дополнительными аргументами в утверждения Пролога, представляет простое расширение описанного ранее механизма. Ранее, для каждого класса словосочетаний создавался новый предикат с двумя аргументами, представляющими входную последовательность и последовательность, оставшуюся после обработки. Теперь надо создать предикат, имеющий на два аргумента больше, чем имеет соответствующее ему грамматическое правило. По соглашению, эти два дополнительных аргумента записываются в конце списка аргументов предиката (хотя в других Пролог-системах может использоваться иное соглашение). Таким образом, грамматическое правило
предложение(Х)--› группа_существительного(Х),группа_глагола(Х).
транслируется в утверждение
предложение(Х,S0,S):- группа_существительного(Х,S0,S1),группа_глагола(Х,S1,S).
При вызове целевых утверждений, содержащих грамматические правила, с самого верхнего уровня интерпретатора (т. е. из вопросов, задаваемых программистом.- Ред.)или из обычных правил Пролога, необходимо явным образом указать дополнительные аргументы, добавив их в конец списка аргументов. Таким образом, правильное целевое утверждение, содержащее обращение к функтору предложение,должно быть таким:
?- предложение(Х,[a,clergyman,eats,a, cake],[]).
?- предложение(Х, [every, bird, sings,and,pigs,can,fly],L).
Упражнение 9.2.Напишите новый вариант предиката phrase,допускающий использование грамматических правил с дополнительными аргументами. Этот предикат должен допускать целевые утверждения вида:
?- phrase(предложение(Х),[the, man,sings]).
9.5. Введение дополнительных условий
Рассматривавшиеся до сих пор грамматические правила, входящие в программу синтаксического анализатора, содержали информацию лишь о том, какая часть входной последовательности обрабатывается каждым из правил. Каждый элемент описания правил должен содержать указание о том, как обрабатывать два дополнительных аргумента, добавленных транслятором грамматических правил. Так что каждое целевое утверждение в результирующем утверждении Пролога обрабатывало определенную часть входной последовательности. Иногда может возникнуть желание определить целевые утверждения иного типа, не связанные непосредственно с обработкой входной последовательности, и рассматриваемый формализм грамматических правил позволяет сделать это. В языке принято следующее соглашение: каждое целевое утверждение, заключенное в фигурные скобки {}, при трансляции не меняется.
Рассмотрим несколько примеров ситуаций, в которых было бы полезно использовать эту возможность. Мы покажем, как можно улучшить «словарь» синтаксического анализатора, т. е. его «знания» о словах обрабатываемого языка.
Прежде всего рассмотрим накладные расходы, связанные с введением нового слова в программу, в которой используются оба множества дополнительных аргументов (для согласования формы числа и для построения дерева разбора). Если нужно добавить новое слово, например banana, то для этого необходимо добавить хотя бы правило
существительное(едч, существительное(banana))--› [banana].
которое сводится к следующему факту на Прологе:
существительное(едч, существительное(banana),[banana|S],S).
Это слишком большой объем информации для определения каждого существительного, особенно когда мы знаем, что каждое существительное представляется лишь одним элементом входного списка и порождает небольшое дерево с функтором существительное.Значительно более экономичный способ представления основывается на разделении информации. Информация, общая для всех существительных, помещается в одном месте, а информация о конкретных словах в другом месте. Это можно сделать, если одновременно использовать возможности грамматических правил и обычного Пролога. Общая информация о том, каким образом существительные входят в другие словосочетания, представляется с помощью грамматического правила, а информация о том, какие слова являются существительными, представляется с помощью обычных утверждений Пролога. Этот подход можно применить к последнему примеру следующим образом:
существительное(S,существительное(N)) --› [N], {является_существительным(N,S)}.
где обычный предикат является_существительнымуказывает, какие слова являются существительными и в какой форме - единственного или множественного числа – они употребляются.
является_существительным(banana,едч).
является_существительным(bananas,мнч).
является_существительным(man,едч).
. . .
Давайте подробно разберем, что означает это грамматическое правило. Оно указывает, что словосочетание класса существительноеможет состоять из единственного слова N(переменная, определенная в списке), удовлетворяющего некоторому ограничению. Это ограничение заключается в том, что Nдолжно входить в число слов, представленных предикатом является_существительным,с указанием конкретной формы числа S. В этом случае, форма числа словосочетания также S, а порождаемое дерево разбора состоит из двух вершин: вершины существительноеи расположенной под ней вершины N. Почему целевое утверждение является_существительным (N,S)должно быть заключено в фигурные скобки? Потому, что оно выражает отношение, не имеющее ничего общего с обработкой входной последовательности. Если убрать фигурные скобки, то результат трансляции будет выглядеть примерно так:
является_существительным(N,S,S1,S2)
и это целевое утверждение никогда не было бы сопоставлено с утверждениями для является_существительным. Заключив целевое утверждение в фигурные скобки, мы тем самым предотвращаем какие-либо его изменения при трансляции. Так что правило будет правильно оттранслировано в следующее утверждение
существительное(S,существительное(N),[N|Посл],Посл):- является_существительным(N,S).
Несмотря на внесенное изменение, используемый способ обработки отдельных слов по-прежнему остается недостаточно изящным. Неудобство этого способа состоит в том, что для каждого вновь вводимого слова надо записывать два утверждения является_существительным– одно для формы единственного числа, а другое для формы множественного числа. Но в этом нет необходимости, поскольку для большинства существительных формы единственного и множественного числа связаны простым правилом:
Если X– существительное в форме единственного числа, то слово, получаемое в результате прибавления 's' к концу слова X, является формой множественного числа этого существительного.
Это правило можно использовать для пересмотра определения для существительное. В результате будет получено новое множество условий, которым должно удовлетворять слово N, для того, чтобы быть существительным. Так как эти условия связаны с внутренней структурой слова и не имеют никакого отношения к обработке входной последовательности, то они будут записаны с использованием фигурных скобок. Слова английского языка представляются как атомы Пролога и поэтому обсуждение вопроса разбиения слов на буквы сводится к рассмотрению литер, составляющих соответствующие атомы. Следовательно, в новом определении необходимо будет использовать предикат name. Улучшенный вариант правила выглядит следующим образом:
существительное(мнч,существительное(КореньN))--›
[N], {(name(М,Мнимя), присоединить(Едимя,"s",Мнимя), name(КореньN,Едимя), является_существительным(КореньN,едч))}.
Конечно, представленное здесь общее правило о форме множественного числа существительных справедливо не во всех случаях (например, множественное число для «fly» не совпадает с «flys»), И по-прежнему необходимо исчерпывающим образом описывать все исключения. Обратите внимание на использование двойных кавычек для представления списка, содержащего литеру 's'.Теперь необходимо определять утверждения для предиката является_существительнымлишь для существительных в единственном числе, если форма множественного числа для них образуется по указанному выше правилу. Заметьте, что в соответствии с приведенным определением в дерево разбора вставляется существительное в форме единственного, а не множественного числа. Это может оказаться полезным при последующей обработке дерева разбора. Обратите также внимание на то, как использованы фигурные скобки. В различных реализациях Пролога некоторые детали синтаксиса могут немного отличаться, но наиболее безопасно заключать содержимое фигурных скобок в дополнительные круглые скобки, если оно состоит более чем из одного целевого утверждения, и оставлять пропуск между фигурной скобкой и точкой, завершающей правило.
Большинство трансляторов синтаксических правил, помимо целевых утверждений, заключенных в фигурные скобки, оставляют неизменными и некоторые другие целевые утверждения. Так, обычно нет необходимости заключать в фигурные скобки '!' или дизъюнкции (;) целевых утверждений.
9.6. Заключение
В этом разделе мы подведем итог тем сведениям, которые мы получили о синтаксисе грамматических правил. Затем будут указаны некоторые из возможных расширений и показаны некоторые интересные способы использования грамматических правил. Лучший способ описать синтаксис грамматических правил – сделать это с помощью самих же грамматических правил. Таким образом, здесь приводится некоторое неформальное описание синтаксиса. Отметим, что оно не является абсолютно строгим, так как в нем не учитывается влияние приоритета операторов на синтаксис.
грамматическое правило--› заголовок, ['--›'], тело.
заголовок--› нетерминальный_символ.
заголовок--› нетерминальный_символ, [','], терминальный_символ
тело--› тело, [','], тело.
тело--› тело, [';'], тело.
тело--› элемент_тела.
элемент_тела--› ['!'].
элемент_тела--› ['{'], целевые_утверждения_пролога, ['}'].
элемент_тела--› нетерминальный_символ.
элемент_тела--› терминальный_символ.
Ряд элементов описания неопределен. Здесь приведены их определения на естественном языке.
нетерминальный_символ обозначает класс словосочетаний, которые могут входить во входную последовательность. Он имеет вид структуры языка Пролог, функтор которой обозначает категорию словосочетаний, а аргументы дают дополнительную информацию (форму числа, значение и так далее).
терминальный_символ указывает ряд слов, которые могут быть частью входной последовательности. Он имеет вид списка языка Пролог и может быть либо пустым списком [], либо списком некоторой фиксированной длины. Элементы этого списка должны быть сопоставимы со словами последовательности в соответствии с заданным порядком.
целевые_утверждения_пролога- это любые целевые утверждения языка Пролог. Они могут быть использованы для записи дополнительных условий и действий, ограничивая возможные пути анализа и указывая, как сложные результаты строятся из простых.
При трансляции на Пролог, целевые_утверждения_прологаостаются неизменными, а нетерминальный_символполучает два дополнительных аргумента, которые вставляются после явно указанных аргументов. Дополнительные аргументы соответствуют последовательности, в которой выделяется словосочетание, и последовательности, которая остается после выделения словосочетания. Терминальные символы появляются среди дополнительных аргументов нетерминальных символов. При вызове предиката, определенного грамматическими правилами, с верхнего уровня интерпретатора или из обычного правила Пролога необходимо явно указать два дополнительных аргумента.
Во втором правиле для предиката заголовокописывается класс грамматических правил, с которыми нам еще не приходилось сталкиваться. До сих пор определения терминальных и нетерминальных символов содержали информацию лишь о том, как они обрабатывают входную последовательность. Иногда может возникнуть желание определить правила таким образом, чтобы они вставляли элементы во входную последовательность (для обработки другими правилами). Например, предложение в повелительном наклонении можно было бы анализировать следующим образом. В исходное предложение
Eat your supper.
вставляется дополнительное слово:
You eat your supper.
Получившееся предложение имеет правильную структуру, согласующуюся с нашими представлениями о структуре предложений. Это можно сделать, используя грамматическое правило вида:
предложение--› императив, группа_существительного, группа_глагола.
императив,[you]--› [].
императив--› [].
Из приведенных здесь правил лишь одно заслуживает внимания. Это первое правило для императив, которое транслируется в утверждение
императив(L,[уоu|L]).
То есть, последовательность, возвращаемая после обработки, длиннее исходной последовательности. В общем случае, левая часть грамматического правила может включать нетерминальный символ, за которым, через запятую, следует список слов. Смысл такого правила состоит в том, что в процессе разбора предложения слова, указанные в списке, вставляются во входную последовательность после того, как завершится обработка целевыми утверждениями в правой части правила.
Упражнение 9.3.Приведенное определение для грамматических правил, даже если бы оно было полным, не сможет выполнить функции синтаксического анализатора, если на вход ему подавать последовательность знаков. Почему?
В заключение рассмотрим пример грамматических правил, используемых для непосредственного извлечения «смысла» предложений, минуя этап построения дерева разбора. Этот пример взят из статьи Pereira, Warren, Artificial Intelligence, v. 13. Представленные далее правила транслируют предложения из ограниченного подмножества предложений английского языка в некоторое представление на языке исчисления предикатов, отражающее смысл этих предложений. Описание исчисления предикатов и используемой формы записи даны в гл. 10. В качестве примера работы программы мы приведем предложение «every man loves a woman» и соответствующую структуру, отражающую его смысл: [14]
all(X,(man(X)’exists(Y,(woman(Y)& loves(X,Y)))))
Здесь представлены грамматические правила программы:
?- op(100,xfy,&)
?- op(150,xfy,’)
предложение(Р)--› группа_существительного(Х,Р1,Р),группа_глагола(Х,Р1).
группа_существительного(Х,Р1,Р)--›определитель(Х,Р2,Р1,Р),существительное(Х,Р3), отн_утверждение(Х,Р3,Р2).
группа_существительного(Х,Р,Р)--› наст_существительное(Х).
группа_глагола(Х,Р)--› перех_глагол(Х,Y,Р1),группа_существительного(Y,Р1,Р).
группа_глагола(Х,Р)--› неперех_глагол(Х,Р).
отн_утверждение(Х,Р1,(Р1&Р2))--› [that], группа_глагола(Х,Р2).
отн_утверждение(_,Р,Р)--› [].
определитель(Х,Р1,Р2,аll(Х,(Р1>Р2)))--› [every].
определитель(Х,Р1,Р2,ехists(Х,(Р1&Р2)))--› [а].
существительное(Х,man(Х))--› [man].
существительное(Х, woman (X))--› [woman].
наст_существительное(john)--› [john].
пepex_глагол(X,Y,loves(X,Y))--› [loves].
неперех_глагол(Х,lives(Х)))--› [lives].
В этой программе аргументы используются для построения структур, представляющих смысл словосочетаний. Смысл каждого словосочетания определяет последний аргумент соответствующего правила. Однако смысл словосочетания может зависеть от некоторых других факторов, представленных другими аргументами. Например, глагол lives(живет) порождает высказывание вида lives(X),где X– это объект, обозначающий человека, который живет. Смысл слова livesне позволяет заранее определить, чем будет являться X. Чтобы быть полезным, понятие подобное livesдолжно быть применимо к некоторому конкретному классу объектов. Что представляет этот объект, будет определено из контекста, в котором используется глагол lives.Таким образом, имеем следующее определение: для любого X, применение глагола livesк Xимеет смысл lives(X).Слово, подобное every(каждый), является значительно более сложным. В этом случае понятие, соответствующее слову, должно применяться к некоторой переменной и к двум высказываниям, содержащим эту переменную. Результат можно сформулировать так: если подстановка некоторого объекта вместо переменной в первом утверждении делает что-то истинным, то подстановка того же объекта вместо переменной во втором утверждении также сделает что-то истинным.
Упражнение 9.4.Разберитесь в приведенной программе. Попробуйте проследить выполнение программы при обращении к ней с вопросами типа
?- предложение(Х, [every, man, loves, a, woman],[]).
Во что транслируются программой предложения «Every man that lives loves a woman» и «Every man that loves a woman lives». Предложение «Every man loves a woman» является в действительности двусмысленным - может существовать либо единственная женщина, которая нравится каждому мужчине, либо несколько женщин, каждая из которых нравится мужчине. Может ли программа породить альтернативные решения, описывающие смысл каждой из двух указанных интерпретаций предложения? Если нет, то почему? Какое простое предположение о построении структуры, отражающей смысл предложения, было сделано при написании программы?
ГЛАВА 10. ПРОЛОГ И МАТЕМАТИЧЕСКАЯ ЛОГИКА
Язык программирования Пролог был разработан коллективом во главе с Колмерауэром приблизительно в 1970 году. Это была первая попытка в разработке языка, который позволял бы программисту описывать свои задачи средствами математической логики, а не с помощью традиционных для программирования конструкций, указывающих чтои когдадолжна делать вычислительная машина. Эта идея нашла отражение в названии языка программирования «Пролог» (английское название «Prolog» является сокращением для Programming in Logic.- Перев.).
В этой книге основное внимание было уделено вопросам, связанным с использованием Пролога в качестве инструментального средства для решения практических задач. При этом ничего не говорилось о путях достижения конечной цели – создании системы логического программирования, шагом к которой является Пролог. В этой главе мы намереваемся отчасти исправить это несоответствие, рассмотрев вкратце связь Пролога с математической логикой и вопрос о том, в какой степени программирование на Прологе соответствует идее логического программирования.
10.1. Краткое введение в исчисление предикатов
Если мы намерены обсуждать связь Пролога с математической логикой, то прежде всего необходимо установить, что мы понимаем под логикой. Первоначально логика развивалась как некоторый способ представления определенного класса высказываний, так чтобы можно было, используя формальную процедуру, проверить, справедливы они или нет. Таким образом, логика может быть использована для выражения высказываний, отношений между высказываниями и правил выводаодних высказываний из других. Логическое исчисление специального вида, о котором будет идти речь в этой главе, называется исчисление предикатов.Здесь мы лишь затронем некоторые вопросы исчисления предикатов. Хорошим введением в математическую логику является книга Hodges W. Logic,Penguin Books, 1977. Более подробное обсуждение предмета дано в книге Mendelson E. Intro ductiontoMathematicalLogic,VanNostrandReinhold. [15]Вы так же можете обратиться к любой книге по математической логике. Другая книга, представляющая интерес, написана Chin L. С, Lee R. С.-Т. Symbolic Logic and Mechanical Theorem Proving,Academic Press, 1973. [16]
Для того чтобы делать высказывания о мире, необходимо уметь описывать объекты этого мира. В исчислении предикатов объекты представляются с помощью термов.Существуют термы трех типов:
• Константа.Это символ, обозначающий индивидуальный объект или понятие. Константы можно рассматривать как атомы языка Пролог и далее будет использоваться соответствующая форма записи. Так, грек, агатаи мирявляются константами.
• Переменная.Это символ, используемый в разное время для обозначения разных индивидуальных объектов. Переменные вводятся лишь одновременно с кванторами, о которых будет сказано далее. Термы, являющиеся переменными, можно рассматривать как переменные языка Пролог и далее для их обозначения будет использоваться синтаксис, принятый в Прологе. Таким образом, X, Человеки Грекявляются переменными.
• Составной терм.Составной терм состоит из функционального символаи упорядоченного множества термов, являющихся его аргументами.Идея состоит в том, что составной терм обозначает тот или иной индивидуальный объект, зависящий от других индивидуальных объектов, представленных его аргументами. Функциональный символ описывает характер зависимости. Например, можно было бы иметь функциональный символ, обозначающий «расстояние» и имеющий два аргумента. В этом случае составной терм обозначает расстояние между объектами, представленными его аргументами. Составной терм можно рассматривать как структуру языка Пролог, имеющую в качестве функтора функциональный символ. Составные термы будут записываться по правилам синтаксиса Пролога так, что, например, жена(генри)может обозначать жену Генри, расстояние(точка1, X)может обозначать расстояние между некоторой заданной точкой и каким-то другим объектом, который будет указан, а классы(мэри, на_следующий_ день_после(Х))может обозначать классы, в которых преподавала Мэри на следующий после X(необходимо указать день).
Таким образом, способы, используемые для представления объектов в исчислении предикатов, в точности соответствуют способам, имеющимся для этого в Прологе.
Для того чтобы делать высказывания об объектах, необходимо иметь возможность описывать отношения между объектами. Это делается с помощью предикатов. Атомарное высказывание(атомарная формула) состоит из предикатного символа и соответствующего ему упорядоченного множества термов, являющихся его аргументами. Это полностью аналогично целевому утверждению Пролога. Так, например, человек(мэри), владеет(Х,осел(Х))и нравится (Мужчина, вино)являются атомарными высказываниями (атомарными формулами). В языке Пролог структура может быть использована как в качестве целевого утверждения, так и в качестве аргумента для другой структуры. В исчислении предикатов дело обстоит иначе. Там имеется строгое разделение между функциональными символами, используемыми в качестве функторов для построения аргументов, и предикатными символами, используемыми в качестве функторов для построения высказываний (формул).
Используя атомарные высказывания, можно различными способами создавать составные высказывания. Именно здесь начинают появляться понятия не имеющие непосредственных аналогов в языке Пролог. Существует несколько способов построения более сложных высказываний из более простых. Прежде всего, можно использовать логические связки.Таким способом можно выразить понятия 'не', 'и', 'или', 'влечет' и 'является эквивалентным'. Далее приведено краткое описание этих связок и вкладываемых в них значений. Здесь ? и ? используются для обозначения произвольных высказываний (формул). В следующей таблице приводятся традиционная форма записи высказываний, используемая в исчислении предикатов, и форма записи, используемая в этой главе.