СИНТАКСИЧЕСКИЙ АНАЛИЗ (СИНТАКСИЧЕСКИЙ РАЗБОР)
[S: [S: ?][Conjunction: ?][S: ?]] [S: [NP: ?] [VP: ?] ]
Второй из этих преемников имеет семь преемников, по одному для каждого правила подстановки NP.
• В проверке цели проверяется, какие листья дерева синтаксического анализа точно соответствуют входной строке, без неизвестных и неохваченных входных данных.
Одна существенная проблема при нисходящем синтаксическом анализе возникает, когда приходится сталкиваться с так называемыми леворекурсивными правилами, т.е. правилами в форме х—>х... При поиске в глубину применение такого правила может привести к тому, что замена хна [X: х...] будет осуществляться в бесконечном цикле. А при поиске в ширину можно будет успешно найти варианты синтаксического анализа для допустимых предложений, но при наличии недопустимого предложения может возникнуть такая ситуация, что программа не сможет выйти из бесконечного пространства поиска.
Ниже приведено описание восходящего синтаксического анализа как задачи поиска.
• Начальным состоянием является список слов во входной строке, где каждое из слов рассматривается как дерево синтаксического анализа только с одним листовым узлом, например [the,wumpus, is,dead]. Вообще говоря, каждое состояние в пространстве поиска представляет собой список деревьев синтаксического анализа.
• С помощью функции определения преемника выполняется поиск в каждой позиции i списка деревьев и в каждой правой части правила грамматики. Если подпоследовательность списка деревьев, начинающаяся с i, согласуется с правой частью, то эта подпоследовательность заменяется новым деревом, категорией которого является левая часть правила, а дочерними узлами — эта подпоследовательность. Под "согласованием" подразумевается, что категория узла является такой же, как и элемент в правой части. Например, правило Article->the согласуется с подпоследовательностью, состоящей из первого узла в списке [the, wumpus, is,dead], поэтому состоянием-преемником становится [ [Article: the] , wumpus, is, dead].
• В проверке цели проверяется наличие состояния, представляющего собой единственное дерево с корнем S.
Пример восходящего синтаксического анализа приведен в табл. 22.2.
И нисходящий, и восходящий синтаксический анализ может оказаться неэффективным из-за того, что отдельные этапы синтаксического анализа различных сочетаний могут комбинироваться самыми разными способами. И в той и в другой процедуре могут возникать непроизводительные затраты времени, связанные с поиском в тех частях пространства состояний, которые не позволяют получить требуемый результат. При нисходящем синтаксическом анализе иногда создаются промежуточные узлы, которые так и не удастся связать со словами, а при восходящем синтаксическом анализе создаются частичные фрагменты синтаксического анализа слов, которые невозможно преобразовать в корневой узел S.
Но даже если бы существовала идеальная эвристическая функция, позволяющая осуществлять поиск без ненужных отступлений, эти алгоритмы все равно были бы неэффективными, поскольку для некоторых предложений количество деревьев синтаксического анализа измеряется экспоненциальной зависимостью. В следующем подразделе показано, как найти выход из этой ситуации.