Грамматика языка
На следующем этапе необходимо обеспечить объединение слов в словосочетания. Мы будем использовать пять нетерминальных символов для определения словосочетаний различных типов: предложение (Sentence— S), именное словосочетание (Noun Phrase — NP), глагольное словосочетание (Verb Phrase — VP), предложное словосочетание (Prepositional Phrase — PP) и относительное предложение1 (Relative Clause — RelClause). Грамматика языка Ј0 приведена в листинге 22.3, где для каждого правила подстановки показан пример. Грамматика ?0 вырабатывает допустимые английские предложения, например, такие, как показаны ниже.
John is in the pit
The wumpus that stinks is in [2,2] Mary is in Boston and John stinks
К сожалению, эта грамматика не только производит приемлемые предложения, но и допускает перепроизводство, т.е. производит предложения, которые не являются грамотными, такие как "Me go Boston" и "I smell pit gold wumpus nothing east". Кроме того, эта грамматика допускает недопроизводство — она отвергает многие правильные английские предложения, такие как "I think the wumpus is smelly". (Еще одним недостатком этой грамматики является то, что она не обеспечивает запись первого слова предложения с прописной буквы или добавление точки в конце. Это связано с тем, что данная грамматика предназначена в основном для устной, а не письменной речи.)
Выше в этой главе уже было дано определение синтаксического анализа как процесса поиска дерева синтаксического анализа для данной конкретной входной строки. Это означает, что вызов функции синтаксического анализа Parse, такой как
Parse("the wumpus is dead". So, S)
должен привести к получению дерева синтаксического анализа с корнем S, листьями которого являются слова "the wumpus is dead", а внутренними узлами — нетерминальные символы грамматики ?0. Такое дерево показано на рис. 22.1. В виде линейного текста это дерево может быть записано следующим образом:
[S: [NP: [Article: the] [Noun: wumpus]] [VP: [Verb: is][Adjective: dead]]]
CF3 Синтаксический анализ может рассматриваться как процесс поиска дерева синтаксического анализа. Существуют два крайне противоположных способа задания соответствующего пространства поиска (а также множество промежуточных вариантов таких способов). Во-первых, можно начать с символа S и искать дерево, листьями которого являются соответствующие слова. Такой способ называется нисходящим синтаксическим анализом (поскольку символ S изображается в верхней части рисунка, на котором показано дерево, повернутое корнем вверх). Во-вторых, можно начать со слов и выполнять поиск дерева с корнем S. Такой метод называется восходящим синтаксическим анализом2. Нисходящий синтаксический анализ может быть точно определен как задача поиска в соответствии с приведенным ниже описанием.
• Начальное состояние представляет собой дерево синтаксического анализа, состоящее из корня S и неизвестных дочерних узлов: [S: ?]. Вообще говоря, каждое состояние в пространстве поиска также представляет собой дерево синтаксического анализа.
• Функция определения преемника выбирает в дереве самый левый узел с неизвестными дочерними узлами. Затем в грамматике осуществляется поиск правил, которые имеют корневую метку узла, находящегося в левой части. Для каждого такого правила создается состояние-преемник, в котором символ ? заменяется списком, соответствующим правой части правила. Например, в грамматике ?0 имеются два правила для S, поэтому дерево [S: ?] должно быть заменено следующими двумя преемниками: