Глава 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 Множественноечисло

В процессе считывания интерпретатором Prolog¹ правил 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] , [] ) .