Обработка смысла

Формирование деревьев синтаксического анализа

Вначале проиллюстрируем понятие дерева синтаксического анализа на примере. В соответствии с определением рассматриваемой грамматики синтаксический анализ фразы

[ the, cat, scares, the, mice]

осуществляется с помощью дерева синтаксического анализа, как показано на рис. 21,2, Некоторые части этой фразы называются конструкциями; таковыми яв­ляются части, которые соответствуют нетерминальным символам в дереве синтакси­ческого анализа. В рассматриваемом примере [ tlie, mice] представляет собой кон­струкцию, соответствующую нетерминальному символу nounjphrase (именная кон­струкция), а [ scares, the, mice] — это конструкция, соответствующая нетерминальному символу verb_phrase {глагольная конструкция). Как показано на рис. 21.2, дерево синтаксического анализа фразы содержит в качестве поддеревьев деревья синтаксического анализа отдельных конструкций.

Часть II. Применение языка Prolog в области искусственного интеллекта

Sentence

Determiner

the

Noun_phrase

T.,',1

Verb phrase

/ \

Verb noun phrase

I /\

Scares determiner noun

The mice

Рис. SI.2, Дерево синтаксического анализа фразы "the cat scares the mice" (кошка пугает, мышей)

Ниже приведено определение понятия дерева синтаксического анализа. Дерево синтаксического анализа любой грамматической конструкции представляет собой дерево со следующими свойствами.

1. Все листья дерева обозначены терминальными символами грамматики.

2. Все внутренние узлы дерева обозначены нетерминальными символами; корень дерева обозначен нетерминальным символом, который соответствует рассмат­риваемой конструкции.

3. Родительс ко-дочерние отношения в дереве определяются правилами граммати­ки; например, если грамматика содержит правило

Gt;р, q, г.

то дерево может содержать узел s, дочерними узлами которого являются узлы р, q и г {рис. 21.3).

/1\

Р Ч г

Рас. 21.3. Родительский узел s и дочерние узлы p. q и г

Иногда удобно иметь дерево синтаксического анализа, явно представленное в про­грамме для выполнения над ним некоторых вычислений, например, для извлечения смысла фразы. Дерево синтаксического анализа можно легко сформировать с исполь­зованием в качестве параметров нетерминальных символов в системе обозначений DCG. Дерево синтаксического анализа может быть легко представлено с помощью терма Prolog, функтором которого является корень дерева, а параметрами — подде­ревья дерева. Например, дерево синтаксического анализа для именной конструкции "the cat" можно представить следующим образом: nounjphrase{ determiner! the) , noun( cat))

Для формирования дерева синтаксического анализа грамматика DCG может быть модифицирована путем добавления к каждому нетерминальному символу дерева его синтаксического анализа в виде параметра. Например, дерево синтаксического ана­лиза именной конструкции в рассматриваемой грамматике имеет такую форму: noim_phrase ( DetTree, NounTree)

Глава 21. Обработка лингвистической информации с помощью грамматических правил 517

где DetTree и NounTree — деревья синтаксического анализа определяющего слова (determiner) и существительного (noun). После введения этих деревьев синтаксиче­ского анализа в качестве параметров в правило грамматики, касающееся именных конструкций, будет получено следующее модифицированное правило: noun phrase[ noun phrase( DetTree, NounTree)) -> determiner( DetTree), noun; NounTree).

Это правило можно описать словами, как показано ниже.

Именная конструкция, имеющая дерево синтаксического анализа nounphra-se ( DetTree, HounTree), состоит из таких компонентов:

• определяющее слово, деревом синтаксического анализа которого является DetTree;

• существительное, деревом синтаксического анализа которого служит NounTree.

Теперь вся рассматриваемая грамматика может быть откорректирована соответст­вующим образом. Для обеспечения согласования в числе можно оставить число в ка­честве первого параметра и ввести дерево синтаксического анализа в виде второго параметра. Часть модифицированной грамматики показана ниже, sentence( Number, sentence( NP, VP!) ->

verb phrase( Number, verb phrase( Verb, NP)) --> verb ( Number, Verb) , _ noun_phrase( Numberl, NP).

noun phrase( Number, noun phrase( Det, Noun)) -->

determiner[ determiner! the)] -> [ the] . noun! singular, rsoun( cat) ) -> [ cat] . noun{ plural_F ncurH cats)) -> [ cats].

В процессе чтения интерпретатором Prolog эта грамматика автоматически преоб­разуется в стандартную программу Prolog. Первое правило грамматики, приведенное выше, преобразуется в следующее предложение:

"■rawж¹ йO VP), List, Rest) :-

verb_phrase( Number, VP, Rest6, Rest).

В соответствии с этим вопрос к системе Prolog для синтаксического анализа неко­торой фразы должен быть задан в соответствующем формате, например:

Т- sentence( Number, ParseTree, 1 the, mice, hate, the, cat], [J) ,

Mumber = plural

ParseTree = sentence; noun_pnrase( determiner[ the), noun[ mice)),

verb phrase{ verb( hate), noun phrase[ determiner! the),

пош_ ( cat))))