iiioh(Lisll. Ri • 1):• ittp(Listl, Listl),
пюм[ I.isti. Rut).
Step
v.Ji.lu...... *—:--------------------
I
R«t
LiiU
Listl
Рис. 21.1. Отношения между последовательностями символов
Такое описание позволяет также понять, почему используется представление в виде разностных списков: пара (Listl, Rest) представляет собой конкатенацию списков, оформленных в виде пар (Listl, List2) и (List2, Resc). Как показано в главе 8, конкатенация списков, представленных таким образом, осуществляется намного эффективнее по сравнению с конкатенацией обычных списков с помощью предиката cone.
Теперь мы можем приступить к подготовке более общего описания процесса трансляции, в котором устанавливается связь между системой обозначений DCG и стандартным языком Prolog. Каждое правило DCG транслируется в предложение Prolog в соответствии с описанной ниже основной схемой. Вначале предположим, что правило DCG выгладит следующим образом:
п --> nl, п2 г •. •i пи.
Если все компоненты nl, п2,..., пп этого правила представляют собой нетерминальные символы, то оно транслируется в следующее предложение:
n[ Listl, Rest):-nl (Listl, List2}, n2 (List2, List3},
nn(Listri, Rest).
Если же какой-либо из компонентов nl, n2 .................. nn является терминальным сим
волом (задан в правиле DCG в квадратных скобках), то он обрабатывается иначе. Он
не появляется в виде одной из целей в предложении, а непосредственно вставляется
в соответствующий список. В качестве примера рассмотрим следующее правило DCG:
n->nl, [ t2], пЗ, [ t4].
где nl и пЗ — нетерминальные символы, a t2 и t4 — терминальные. Это правило транслируется в такое предложение:
ni Listl, Rest):-
г.1 (Listl, [t2 | List3]), n3 (List3, [t4 | Rest] I.
Более интересные примеры грамматик можно найти в языках программирования и в естественных языках. И те и другие могут быть изящно реализованы с помощью DCG Ниже приведен пример грамматики для простого подмножества английского языка.
sentence -> noun_phrase, verb_phrase. verb_phrase --> verb, nounjbrase. norai_phrase -> determiner, noun.
Часть II. Применение языка Prolog в области искусственного интеллекта
determiner - -> f a]. determiner- --> [ the]. noun -> [ cat], noun --> [ mouse. verb --> [ scares], verb --> [ hates].
Ниже приведены примеры фраз, формируемых с помощью этой грамматики.
the, cat, scares, a, mouse] I Кошка пугает мышь
the, mouse, hates, the, cat] % Мышь ненавидит кошку
the, mouse, scares, the, mouse] % Мышь пугает мышь
Теперь введем в эту грамматику существительные и глаголы во множественном числе, чтобы иметь возможность формировать фразы наподобие [ the, mice, hate, the, cats] (Мыши ненавидят кошек) следующим образом;
| noun | -> |
| noun | -> |
| verb | --> |
| verb | —> |
mice].
scare]. hate].
Грамматика, дополненная таким образом, позволяет сформировать желаемую фразу. Но, к сожалению, она, кроме того, формирует также некоторые нежелательные, неправильные английские фразы, например, такие: [ the, mouse, hate, the cat] % Мышь ненавидит кошку
Проблема заключается в том, что в грамматику входит следующее правило: sentence --> noun_phrase, verb_phrase.
Оно указывает, что для формирования фразы можно соединить любую именную конструкцию с любой глагольной конструкцией. Но в английском языке и многих других языках именная и глагольная конструкции во фразе не являются независимыми — они должны быть согласованы в числе. Обе эти конструкции должны быть одновременно заданы либо в единственном, либо во множественном числе. Такая особенность языка называется контекстной зависимостью (context dependency). Возможность применения той или иной конструкции зависит от контекста, в котором она встретилась. Контекстные зависимости не могут быть учтены непосредственно в грамматиках BNF, но могут быть легко обработаны с помощью грамматик DCG с использованием расширения, предусмотренного в системе DCG, в отличие от BNF, а именно параметров, которые разрешается дополнительно указывать в нетерминальных символах грамматики. Например, в качестве параметра именной и глагольной конструкции можно указать число (Number) следующим образом: noun_phrase (Number) verb phrase{ dumber)
После добавления этого параметра появляется возможность легко откорректировать грамматику, рассматриваемую в качестве примера, чтобы обеспечить согласование в числе между именной и глагольной конструкцией, как показано ниже. sentence < Number) --> noun phrase(Number), verb phrase(Number). verb phrase(Number) --> verb(Number), noun phrase(Numberl). nou:n phrase (Number) - > determiner! Number), noun { Number). noun _ singular) --> [ mouse). % Единственное число noun(plural) --> [ mice]. I Множественное число
В процессе считывания интерпретатором Prolog1 правил DCG и преобразования в предложения Prolog параметры нетерминальных символов добавляются к обычным параметрам двух списков на основании того соглашения, что эти два списка вводятся в последнюю очередь. Таким образом, правило
sentence(Number) --> noun_phrase(Number), verb_phrase(Numbet), преобразуется в такое предложение: sentence(Number, Listl, Rest): -
ncun_phrase(Number, Listl, Llst2),
verb_phrase(Humber, List2, Rest).
Глава 21, Обработка лингвистической информации с помощью грамматических правил 515
Теперь необходимо откорректировать соответствующим образом вопросы к системе Prolog, чтобы включить в них дополнительные параметры, как показано ниже.
?- sentence(plural, [ the, mice, hate, the, cats), []}. yes
?- sentence! plural, [ the, mice, hates, the, cats], [)). no
?- sentence! plural, [ the, mouse, hates, the, cat], []). no
?- sentence! Kumber, [ the, mouse, hates, the, cat], []). Number - singular
?- sentence! singular, [ the, What, hates, the, cat], []}. What = cat; What - mouse; no
Упражнения
23.1. Преобразуйте в стандартное предложение Prolog следующее правило DCG: s - > [а], s, [Ь].
21.1. Напишите процедуру Prolog translate! DCGrule, PrologClause)
которая преобразует заданное правило DCG в соответствующее предложение Prolog.
21.3. Одно из правил DCG в грамматике, описывающей движения робота, выглядит
таким образом:
move --> step, move.
Если это правило будет заменено правилом
move — > move, step.
то язык, определяемый грамматикой, модифицированной соответствующим образом, остается тем же самым. Но соответствующая процедура распознавания на языке Prolog становится иной. Проанализируйте, в чем состоит различие. Каково преимущество первоначальной грамматики? Каким образом эти две грамматики обрабатывают следующий вопрос:?- move [ [up, lef t], []).
