Применение грамматических правил в программе на языке Prolog
Грамматика — это формальный механизм для определения множеств последовательностей символов. Такая последовательность символов может быть отвлеченной, не имеющей какого-либо практического значения, или, что более интересно, может представлять собой инструкцию на языке программирования, или целую программу, а также может быть фразой на естественном языке, таком как английский.
Одной из популярных систем определения грамматики является BNF (Backus-Naur Form - форма Бэкуса-Наура), которая часто используется при описании языков программирования. Начнем изложение рассматриваемой темы с анализа системы BNF. Грамматика состоит из порождающих правил. Ниже приведена простая грамматика BNF, состоящая из двух правил.
<s>::=a<s>b
Первое правило гласит: каждое вхождение символа s в строке может быть заменено последовательностью ab, а второе правило утверждает, что символ s может быть заменен последовательностью, состоящей из символа а, за которым следует з, затем Ъ, В этой грамматике символ s всегда заключен в угловые скобки " о". Такое обозначение указывает, что s - нетерминальный символ грамматики. С другой стороны, а и b — это терминальные символы. Терминальные символы ни в коем случае |не подлежат замене. В системе BNF приведенные выше два порождающих правила обычно записываются вместе в виде одного правила: <s>::=ab|a<s>b Но в данной главе для упрощения принята расширенная, более полная форма.
Грамматика может использоваться для формирования строки символов, которая называется фразой. Процесс формирования всегда начинается с некоторого начального нетерминального символа, в данном примере — с символа s. После этого символы в текущей последовательности заменяются другими строками в соответствии с правилами грамматики. Процесс формирования заканчивается, когда текущая последовательность не содержит ни одного нетерминального символа. В данном примере грамматики процесс формирования может происходить, как описано ниже. Формирование начинается со следующего символа: $
Теперь в соответствии со вторым правилом s заменяется такой последовательностью символов:
а Б b
После этого снова используется второе правило, что приводит к получению последовательности:
а & s b b
После применения первого правила окончательно формируется следующая фраза: a a a b b b
Безусловно, что эта грамматика позволяет формировать и другие фразы, например ab, aabb и т.д. В общем эта грамматика позволяет создавать строки в форме at", где г. = 1, 2, 3, ... . Множество фраз, формируемых с помощью грамматики, называется языком, определяемым этой грамматикой.
Рассматриваемый пример грамматики является простым и очень далеким от практических потребностей. Но грамматики могут использоваться для определения гораздо более интересных языков. В частности, формальные грамматики применяются для определения языков программирования и подмножеств естественных языков.
Следующая рассматриваемая грамматика все еще остается очень простой, но имеет большее практическое значение. Предположим, что манипулятору робота могут передаваться показанные ниже последовательности команд.
• up — переместиться вверх на один шаг;
• dewn — переместиться на один шаг вниз.
Ниже приведены два примера последовательностей команд, которые может воспринимать такой робот. up up up down up down
Подобная последовательность активизирует соответствующую последовательность шагов, выполняемых роботом. Мы будем называть любую последовательность шагов "движением". Таким образом, любое движение (move) состоит либо из одного шага (step), либо из любого шага, за которым следует любое движение. Такая организация функционирования робота определяется с помощью следующей грамматики:
Глава 21. Обработка лингвистической информации с помощью грамматических правил 511
<move> :: - <step> <move> :;= <step> <raove> <Step> : : = iip <step> ::= down
Эта грамматика будет использоваться ниже в данной главе для иллюстрации того, каким образом может осуществляться обработка смысла в рамках системы обозначения грамматик на языке Prolog1,
Как было показано выше, грамматика позволяет формировать фразы. С другой стороны, грамматика может использоваться для распознавания заданной фразы. Механизм распознавания позволяет определить, принадлежит ли данная фраза к некоторому языку; это означает, что механизм распознавания устанавливает, может ли заданная фраза быть сформирована с помощью соответствующей грамматики. Процесс распознавания фраз, до сути, является обратным по отношению к процессу их формирования. При распознавании работа начинается с заданной строки символов, к которой применяются грамматические правила в направлении, противоположном формированию: если текущая строка содержит подстроку, равную правой части некоторого правила грамматики, то эта подстрока заменяется левой частью такого правила. Процесс распознавания завершается успешно после того, как вся заданная фраза приводится к начальному нетерминальному символу грамматики. А если не удается обнаружить способ приведения заданной фразы к начальному нетерминальному символу, то механизм распознавания отбрасывает эту фразу.
В таком процессе распознавания заданная фраза фактически раскладывается на синтаксические компоненты, поэтому подобный процесс часто называют также синтаксическим анализом. Обычно для реализации некоторой грамматики требуется не только составить ее правила, но и подготовить программу синтаксического анализа для этой грамматики. Как показано ниже в этой главе, такие программы синтаксического анализа могут быть написаны на языке Prolog очень легко. Эта задача может быть решена с помощью языка Prolog особенно изящно благодаря использованию специальной системы обозначений правил грамматики, называемой DCG (Definite Clause Grammar - грамматика определенных предложений). Такая специальная система обозначений для грамматик поддерживается многими реализациями Prolog. Любая грамматика, оформленная с помощью системы DCG, может непосредственно использоваться в качестве программы синтаксического анализа фраз, сформированных с помощью этой грамматики. Для преобразования грамматики BNF в формат DCG достаточно лишь применить немного иные соглашения системы обозначений. В частности, приведенные выше в качестве примера грамматики BNF могут быть записаны в формате DCG следующим образом:
в ->[а] , [Ь]. s->[a] ,s, [Ь].
move --> step,
move --> step, move.
step --> tup].
step --> [down].
Обратите внимание на то, в чем состоят различия между системами обозначений BNF и DCG Символ ":: = " заменяется символом "-->", Нетерминальные символы больше не записываются в угловых скобках, а терминальные символы помещаются s квадратные скобки и тем самым преобразуются в списки Prolog. Кроме того, теперь символы отделены друг от друга запятыми, а каждое правило оканчивается точкой, как и любое предложение Prolog.
В реализациях Prolog, которые допускают возможность применения системы обозначений DCG, такие преобразованные грамматики могут непосредственно использоваться в качестве механизмов распознавания фраз. Соответствующий механизм распознавания, по сути, рассчитан на то, что фразы представлены в виде разностных списков терминальных символов, {Представление в виде разностных списков было описано в главе 8.) Поэтому каждая фраза оформлена в виде двух списков и пред-
Часть II. Применение языка Prolog в области искусственного интеллекта
ставляет собой разность между этими двумя списками. Эти два списка не являются уникальными, например, как показано ниже.
Фраза aabb может быть представлена списками [ a, a, b, b] и [ ]
или списками [ a, a, b, b, с] и [ с]
или списками [ а, а, Ь, Ъ, 1, О, 1] и [ 1, 0, 1]
С учетом того, что для представления фраз применяется такая форма, можно воспользоваться системой обозначений DCG для распознавания некоторых фраз, сформированных с помощью грамматик, рассматриваемых в качестве примера, введя следующие вопросы:
% Распознать строку aabb
[]) •
?- s( yes ?- s([a,a,b], no ?- move( yes "move( |
[]). []). |
?-no ?- X X no |
[ а, а, Ь, Ь], []). [ up, up, down], [ up, up, left], [ up, X, up] , []).
move( = up ; = down;
Теперь рассмотрим, каким образом в интерпретаторе Prolog используется заданная форма DCG для поиска ответов на такие вопросы. В ходе применения для консультаций правил грамматики интерпретатор Prolog автоматически преобразует их в обычные предложения Prolog. Таким образом, интерпретатор Prolog преобразует заданные правила грамматики в программу для распознавания фраз, сформированных с помощью этой грамматики. Применение такого преобразования иллюстрируется в следующем примере. Приведенные выше четыре правила DCG, касающиеся движений робота, преобразуются в следующие четыре предложения:
move( List, Rest) :-
step( List, Rest) , move( Listl, Rest) :-
step( Listl, -List2),
move( List2, Rest).
step( [up | Rest], Rest). step( [down | Rest], Rest).
Какая задача фактически решается с помощью такого преобразования? Рассмотрим процедуру move. Отношение move имеет два параметра — два списка:
move( List, Rest)
Это отношение принимает истинное значение, если разность между списками List и Rest представляет собой допустимое движение. В качестве примеров отношений можно указать следующие:
move( или move( ИЛИ move( |
[ up, down, up], []).
[ up, down, up, a, b, c] , [ a, b, c] )
[ up, down, up], [ down, up]).
На рис. 21.1 показано, что подразумевается под следующим предложением:
move( Listl, Rest) :-step( Listl, List2) , move( List2, Rest) .
Это предложение можно описать словами таким образом:
Разность списков Listl и Rest обозначает движение, если разность между списками Listl и List2 соответствует шагу и разность между списками List2 и Rest - движению.