Глава 21. Обработка лингвистической информации с помощью грамматических правил 51 3
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] , [] ) .