Обработка смысла
Формирование деревьев синтаксического анализа
Вначале проиллюстрируем понятие дерева синтаксического анализа на примере. В соответствии с определением рассматриваемой грамматики синтаксический анализ фразы
[ 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{ pluralF ncurH cats)) -> [ cats].
В процессе чтения интерпретатором Prolog эта грамматика автоматически преобразуется в стандартную программу Prolog. Первое правило грамматики, приведенное выше, преобразуется в следующее предложение:
"■rawж1 й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))))