указывает, что словосочетание NP охватывает строку от вершины 0 до вершины 2 (первые два слова) и что если бы мы смогли найти словосочетание VP, чтобы продолжить это ребро, то получили бы словосочетание S. Ребра, подобные этому, в которых точка не достигла конца, называются неполными ребрами, и принято говорить, что для этого ребра требуется найти словосочетание VP.

Рис. 22.2. Часть диаграммы, соответствующей предложению "The agent feels a breeze" (Агент чувствует ветерок). Показаны все шесть вершин, но только три из тех ребер, которые требуются для полного синтаксического анализа

Алгоритм диаграммного синтаксического анализатора показан в листинге 22.4. Его основная идея такова, что в нем объединяются лучшие свойства нисходящего и восходящего синтаксического анализа. Процедура Predictor выполняет нисходящий анализ; она создает записи в диаграмме, которые указывают, какие символы желательно найти и в каких местах. Процедура Scanner — это процедура восходящего анализа, которая начинает работу со слов, но использует любое слово только для продления существующей записи в диаграмме. По аналогии с ней процедура

Extender формирует составляющие дерева синтаксического анализа в направлении снизу вверх, но только для продления существующей записи в диаграмме.

Листинг 22.4. Алгоритм диаграммного синтаксического анализатора, где S — начальный символ, S* — новый нетерминальный символ, a chart [ j] — список ребер, которые оканчивается в вершине j. Словосочетания, обозначенные греческими буквами, согласуются с некоторой строкой, имеющей длину от нуля и больше символов

Для запуска всего алгоритма воспользуемся таким приемом: добавим к диаграмме ребро, где S — начальный символ грамматики, a S' — новый символ, который был только что предложен. Вызов процедуры Add-Edge вынуждает процедуру Predictor ввести ребра, соответствующие правилам, применение которых может привести к получению S, т.е. . Затем осуществляется поиск первой составляющей этого правила, NP, и добавление правил, соответствующих каждому способу получения какого-то подходящего словосочетания NP. В конечном итоге процедура предсказателя Predictor добавляет в режиме нисходящего синтаксического анализа все возможные ребра, которые могут использоваться в процессе создания окончательного словосочетания S.

После завершения работы предсказателя применительно к словосочетанию 5" алгоритм входит в цикл, в котором вызывается процедура Scanner для каждого слова в предложении. Если слово, находящееся в позиции j, является членом такой категории В, которая отыскивается для некоторого ребра в позиции j, то данное ребро продлевается, а слово отмечается как экземпляр категории В. Обратите внимание на то, что каждый вызов процедуры Scanner приводит к рекурсивному вызову процедур Predictor и Extender, в результате чего происходит чередование нисходящей и восходящей обработки.

Другой компонент восходящей обработки4, процедура Extender, принимает на входе некоторое полное ребро с левой частью В и использует его для продления любого неполного правила в диаграмме, которая оканчивается там, где начинается полное ребро, если для этого неполного правила требуется категория В.