Выше в этой главе уже было дано определение синтаксического анализа как процесса поиска дерева синтаксического анализа для данной конкретной входной строки. Это означает, что вызов функции синтаксического анализа Parse, такой как

должен привести к получению дерева синтаксического анализа с корнем S, листьями которого являются слова "the wumpus is dead", а внутренними узлами — нетерминальные символы грамматики. Такое дерево показано на рис. 22.1. В виде линейного текста это дерево может быть записано следующим образом:

[S: [NP: [Article: the][Noun: wumpus]] [VP: [Verb: is][Adjective: dead]]]

Синтаксический анализ может рассматриваться как процесс поиска дерева синтаксического анализа. Существуют два крайне противоположных способа задания соответствующего пространства поиска (а также множество промежуточных вариантов таких способов). Во-первых, можно начать с символа S и искать дерево, листьями которого являются соответствующие слова. Такой способ называется нисходящим синтаксическим анализом (поскольку символ S изображается в верхней части рисунка, на котором показано дерево, повернутое корнем вверх). Во-вторых, можно начать со слов и выполнять поиск дерева с корнем S. Такой метод называется восходящим синтаксическим анализом. Нисходящий синтаксический анализ может быть точно определен как задача поиска в соответствии с приведенным ниже описанием.

•    Начальное состояние представляет собой дерево синтаксического анализа, состоящее из корня S и неизвестных дочерних узлов: [S: ?]. Вообще говоря, каждое состояние в пространстве поиска также представляет собой дерево синтаксического анализа.

•    Функция определения преемника выбирает в дереве самый левый узел с неизвестными дочерними узлами. Затем в грамматике осуществляется поиск правил, которые имеют корневую метку узла, находящегося в левой части. Для каждого такого правила создается состояние-преемник, в котором символ ? заменяется списком, соответствующим правой части правила. Например, в грамматикеимеются два правила для S, поэтому дерево [S: ?] должно быть заменено следующими двумя преемниками:

[S: [S: ?][Conjunction: ?][S: ?]] [S: [NP: ?] [VP: ?] ]

Второй из этих преемников имеет семь преемников, по одному для каждого правила подстановки NP.