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

Автор книги: У. Клоксин

Соавторы: К. Меллиш
сообщить о нарушении

Текущая страница: 19 (всего у книги 26 страниц)

8.5. Фиксация ошибок

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

• Ваша Пролог-система позволяет использовать редактор, а затем вернуться в Пролог с той же базой данных, что и прежде. Может быть, существует возможность сделать это прямо, с помощью соответствующего встроенного предиката. Возможен и другой вариант, когда Пролог позволяет вам сохранить текущее состояние базы данных в специальном файле, а позднее снова восстановить его. Тогда вы сохраняете ваше текущее состояние, выходите из Пролога, изменяете программу, запускаете Пролог снова и восстанавливаете предыдущее состояние базы данных. Вернувшись туда же, где вы были раньше, но с изменениями в одном или нескольких программных файлах, вам необходимо лишь выполнить предикат reconsultдля этих файлов, чтобы заменить старые определения измененных программ новыми.

• Если ваша Пролог-система не позволяет вернуться к прежнему состоянию после использования редактора и изменения ваших программных файлов, то вам придется запустить Пролог и применить предикат consultко всем вашим программным файлам, находящимся на внешней памяти.

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

?– [filel,file2,file3].

?– [file4,file5,fileб].

то в результате будут считаны в память все файлы file1, file2, file3, file4, file5, file6.

Иногда изменения в программе кажутся столь незначительными, что их можно ввести с терминала с помощью предикатов consult(user)или reconsult(user). Однако не следует пользоваться этим способом слишком часто. По невнимательности можно легко забыть какие-либо мелкие изменения, которые вносились таким способом, и при выполнении программы вновь столкнуться с теми же ошибками, которые встречались при прошлом запуске программы. Кроме того, поскольку в конечном итоге вы намерены внести исправления в ваши программные файлы, то нерационально повторять их прямой ввод с терминала. Итак, не поддавайтесь искушению вводить утверждения прямо с терминала в надежде поскорее заставить программу работать.

Ниже приводится небольшой пример того, как можно использовать предикаты consultи reconsult, чтобы внести изменения в программу с терминала. Этот сеанс работы начинается, когда в базе данных программиста нет ни одного утверждения.

?– присоединить([а,b,с,d],[е],Х).

нет

?– consult (user).

присоединить([А|В],С,[А|D]):– присоединить(А,С,D).

присоединить([],Х,Х).

обр([],[]).

обр([А|В],С):– o6p(B,D), присоединить(D,[А],С).

/* ввод литеры – признак конца файла */

да

?– обр([a,b,c,d,e],X).

нет

?– присоединить([а,b,с,d,е], [f],Х).

нет

?– присоединить([],[а,b,-],Х).

X = [а,b,с]

да

?– reconsult(user)

присоединить([А|В],С,[А|D]):– присоединить(В,С,D).

/* ввод литеры – признак конца файла */

да

?– oбp([a,b,c,d],X).

нет

?– consult (user).

присоединить([],Х,Х).

/* ввод литеры – признак конца файла */

да

?– oбp([a,b,c,d,e],X). X = [e,d,c,b,a].

да

В приведенном сеансе работы наш беспечный программист начинает с ввода через терминал утверждений для предикатов присоединитьи обр.Конечно, он мог бы сначала ввести их в файл, а затем предложить Прологу применить к этому файлу предикат consult.Впрочем, для такого маленького примера этого, может быть, и не стоило делать. К несчастью, в первом утверждении для присоединитьдопущена ошибка – в цели задано А, хотя на этом месте должно быть В. Эта ошибка обнаруживается, когда система не может ответить на вопросы, содержащие присоединитьи обр.Каким-то образом программист догадывается, что егоопределение присоединитьневерно (в реальном сеансе для этого, вероятно, потребовалось бы использовать средства отладки). Так или иначе, он решает заменить имеющееся определение новым, используя для этого предикат reconsult.К сожалению, в своем новом определении он забывает задать граничное условие (случай []). Поэтому программа по-прежнему не работает. К этому моменту исходное определение для присоединить,состоящее из двух утверждений, заменено новым определением из одного утверждения, которое оказалось неполным. Наш программист замечает, что он допустил ошибку и что ситуацию можно исправить, просто добавив к уже имеющемуся определению одно утверждение. Это делается также с помощью предиката consult.На этот раз программа заработала.

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

ГЛАВА 9. ИСПОЛЬЗОВАНИЕ ГРАММАТИЧЕСКИХ ПРАВИЛ В ПРОЛОГЕ

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

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

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

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

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

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

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

группа_глагола–› глагол.

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

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

существительное–› [man].

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

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

Рис. 9.1.

Эта грамматика состоит из множества правил, каждое из которых записано в отдельной строке. Каждое правило определяет форму словосочетания определенного вида. Первое правило показывает, что предложение состоит из словосочетания, называемого группа_существительного,за которым следует словосочетание, называемое группа_глагола.Эти два словосочетания есть не что иное, как подлежащееи сказуемоепредложения (см. рис. 9.1).

Чтобы представлять, что значит правило в контекстно-свободной грамматике, их следует читать следующим образом: X–›Yкак « X может иметь вид Y», а ' X, Y' как « X, за которым следует Y». Так первое правило может быть прочитано:

предложение может иметь вид: группа_существительного, за которой следует группа_ глагола.

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

группа_существительного может иметь вид: определитель, за которым следует существительное.

Неформально, группа существительного – это группа слов, служащая для обозначения некоторого объекта (или объектов). Такая группа содержит слово – существительное, которое определяет главный класс, которому принадлежит этот объект. Так « the man» (человек) обозначает человека, « the program» (программа) обозначает программу и так далее. Кроме того, в соответствии с приведенной грамматикой, существительному должна предшествовать группа слов, названная «определитель» (см. рис. 9.2). Аналогично, внутренняя структура словосочетания группа_глаголаописывается соответствующими правилами. Заметим, что для этого словосочетания существуют два правила. Это вызвано тем, что оно может принимать два вида. Словосочетание группа_глаголаможет содержать словосочетание группа_существительного,как в предложении «the man eats the apple»(человек ест яблоко), или группа_существительногоможет отсутствовать, как в предложении «the man sings»(человек поет).

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

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

можно читать так:

определитель может иметь вид: словоthe.

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

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

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

Рис. 9.2.

И так далее. В результате этой процедуры, если она завершится успешно, мы выделим все словосочетания и их части, входящие в заданное предложение, в соответствии с тем, как они определены грамматикой, и получим структуру, подобную приведенной на рис. 9.3. Эта диаграмма, показывающая структуру разбиения предложения на словосочетания, называется деревом (синтаксического) разборапредложения.

Мы увидели, как, имея грамматику языка, можно построить деревья разбора для предложений этого языка, чтобы показать их структуру. Задача построения дерева разбора предложения по заданной грамматике называется задачей синтаксического разбора (анализа).Программа для ЭВМ, которая строит деревья разбора для предложений языка, называется синтаксическим анализатором.

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

предложение

Рис. 9.3.

9.2. Описание синтаксического анализа на языке Пролог

Основная структура данных, о которой идет речь при обсуждении задачи синтаксического анализа, представляет последовательность слов. Предполагается, что можно выделить подпоследовательности этой структуры, представляющие различные словосочетания, допустимые грамматикой, и, основываясь на этом, показать, что последовательность в целом допустима в качестве словосочетания типа предложение. Так как стандартным способом представления последовательности является список, то входные данные для синтаксического анализатора будут представлены как список языка Пролог. А какое же представление имеют сами слова? Для решаемой здесь задачи знание внутренней структуры слов представляется несущественным, так как все, что необходимо делать,– это сравнивать слова друг с другом. Поэтому естественно представлять слова как атомы языка Пролог,

Давайте разработаем программу, позволяющую определять, является ли заданная последовательность слов предложением в соответствии с приведенной выше грамматикой. Для того чтобы сделать это, программа будет должна выявить внутреннюю структуру заданных ей предложений. Далее будет показано, как разрабатывать программу, которая запоминает эту структуру и делает ее доступной для обозрения, но здесь этот вопрос не будет рассматриваться, чтобы не усложнять программу. Так как программа проверяет, является ли некоторая последовательность слов предложением, то давайте определим предикат предложение. Этот предикат использует лишь один аргумент и соответствует следующему утверждению:

предложение(Х) означает, что X является последовательностью слов, образующей грамматически правильное предложение.

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

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

Ответом на этот вопрос будет «да», если «the man eats the apple» является предложением, и «нет» в противном случае.

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

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

группа_существительного(Х) означает, что последовательность X является группой существительного. Аналогично, группа_глагола(Х) значит, что последовательность X является группой глагола.

Используя эти предикаты, мы можем дать определение предиката предложение. Последовательность X является предложением, если ее можно разбить на две подпоследовательности Yи Z, где Y– это группа_существительного, Z– группа_глагола. Так как мы представляем последовательности как списки, то у нас уже есть предикат присоединить, выполняющий разбиение списка на два других. Таким образом, можно записать:

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

Аналогично

группа_существительного(Х):– присоединить(Y,Z,Х), определитель(Y), существительное(Z).

группа_глагола(Х):– присоединить(Y,Z,Х), глагол(Y), группа_существительного(Z).

группа_глагола(Х):– глагол(Х).

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

определитель([the]).

существительное([аррlе]).

существительное([man]).

глагол([eats]).

глагол([sings]).

Теперь наша программа завершена. Действительно, эта программа успешно идентифицирует последовательности слов, являющиеся предложениями для приведенной грамматики. Однако, прежде чем считать задачу решенной, следует посмотреть, что в действительности произойдет, когда мы зададим вопрос о некоторой последовательности слов. Рассмотрим утверждение для предиката предложение:

предложение(Х):– присоединить(Y,Z,Х), группа_существительного(Y), группа_глагола(Z).

и следующий вопрос:

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

Переменная Xв правиле конкретизируется значением [the, man, eats, the, apple], а переменные Yи Zне будут конкретизированы, так что данная цель будет порождать возможные пары значений для Yи Zтакие, что результат присоединения списка Zк списку Yравен X. С помощью механизма возврата будут порождены все возможные пары, по одной при каждом возврате. Цель группа_ существительногобудет выполняться лишь при условии, что Yдействительно приемлем как группа_существительного. Иначе она не выполняется и присоединить будет вынужден найти другое значение для Y. Так что последовательность выполнения первой части предиката предложениебудет следующей:

1. Целью является предложение(thе, man, eats, the, apple]).

2. Разбиение исходного списка на два списка Yи Z. Возможны следующие варианты разбиения;

Y = [], Z = [the,man,eats,the,apple] Y = [the], Z = [man,eats,the,apple]

Y= [the,man], Z = [eats,the,apple]

Y= [the,man,eats], Z = [the,apple]

Y= [the,man,eats,the], Z = [apple]

Y= [the, man, eats, the, apple], Z = []

3. Выбор варианта значений для Yи Zиз приведенного выше списка вариантов и проверка принадлежности Yклассу группа_существительного.То есть, попытка согласования подцели группа_существительного(Y).

4. Если группа_существительноговыполняется для Y, то перейти к группа_глагола.Иначе возвратиться к шагу 3 и попробовать другой вариант.

Очевидно, что при таком подходе выполняется совершенно ненужный поиск. Цель присоединить(Y,Z,X)порождает множество решений, большая часть которых бесполезна и не может быть идентифицирована как группа существительного. Должен существовать более прямой путь получения решения. Как следует из нашей грамматики, группа_существительногодолжна содержать в точности два слова. Этим можно было бы воспользоваться, чтобы не прибегать к поиску среди возможных вариантов разбиения исходной последовательности слов. Опасность заключается в том, что это не всегда так, если мы изменяем грамматику. Даже небольшое изменение в правиле для определитель могло бы повлиять на возможную длину группы существительного, а значит и на способ идентификации группы существительного. При разработке программы было бы хорошо сохранять некоторую модульность. Если мы хотим изменить одно утверждение, то это не должно вызывать изменение программы в целом.

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

Это обсуждение приводит нас к новому определению предиката группа_существительного,который теперь имеет уже два аргумента:

группа_существительного(Х, Y) истинно, если начальная часть последовательности X является группой существительного, а остальная часть последовательности есть Y.

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

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

?– группа_существительного([thе,аррlе,sings], [sings]).

должны иметь ответ «да». Теперь, чтобы отразить это изменение, мы должны пересмотреть определение предиката группа_существительного.Для этого надо решить, как последовательность, выбранная в качестве группы существительного, разбивается на последовательность, представляющую определитель, за которой следует последовательность, являющаяся существительным. Мы можем вновь предоставить решение задачи о том, какую часть последовательности следует выбрать, непосредственно тем утверждениям, которые обрабатывают соответствующие группы слов, положив:

группа_существительного(Х,Y):– определитель(Х,Z), существительное(Z, Y).

Таким образом, в начале последовательности Xимеется группа, существительного,если мы можем выделить определитель в начале X, обозначив оставшуюся часть Z, а затем можем выделить существительное в начале Z. Часть последовательности, остающаяся после выделения группы существительного, совпадает с последовательностью, следующей за существительным. На диаграмме это выглядит так:

[the, man, eats, the, apple]

|–X–|

       |–Z–|

                |–Y–|

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

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

определитель([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).

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