Применение грамматических правил в программе на языке 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

Эта грамматика будет использоваться ниже в данной главе для иллюстрации того, каким образом может осуществляться обработка смысла в рамках системы обозначе­ния грамматик на языке Prolog¹,

Как было показано выше, грамматика позволяет формировать фразы. С другой стороны, грамматика может использоваться для распознавания заданной фразы. Ме­ханизм распознавания позволяет определить, принадлежит ли данная фраза к неко­торому языку; это означает, что механизм распознавания устанавливает, может ли заданная фраза быть сформирована с помощью соответствующей грамматики. Про­цесс распознавания фраз, до сути, является обратным по отношению к процессу их формирования. При распознавании работа начинается с заданной строки символов, к которой применяются грамматические правила в направлении, противоположном формированию: если текущая строка содержит подстроку, равную правой части не­которого правила грамматики, то эта подстрока заменяется левой частью такого пра­вила. Процесс распознавания завершается успешно после того, как вся заданная фраза приводится к начальному нетерминальному символу грамматики. А если не удается обнаружить способ приведения заданной фразы к начальному нетерминаль­ному символу, то механизм распознавания отбрасывает эту фразу.

В таком процессе распознавания заданная фраза фактически раскладывается на синтаксические компоненты, поэтому подобный процесс часто называют также син­таксическим анализом. Обычно для реализации некоторой грамматики требуется не только составить ее правила, но и подготовить программу синтаксического анализа для этой грамматики. Как показано ниже в этой главе, такие программы синтакси­ческого анализа могут быть написаны на языке 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 - движению.