На рис. 22.3 и в табл. 22.3 показаны диаграмма и трассировка процесса синтаксического анализа с помощью этого алгоритма предложения "I feel it" (которое является положительным ответом на вопрос "Do you feel a breeze?" — "Вы чувствуете ветерок?"). В этой диаграмме зарегистрированы тринадцать ребер (обозначенных метками от а до m), включая пять полных ребер (показанных над вершинами диаграммы) и восемь неполных ребер (показанных под вершинами). Обратите внимание на то, как действуют в цикле процедуры предсказания Predictor, сканирования Scanner и продления Extender. Например, в процедуре предсказания используется тот факт, что для ребра а должен быть выполнен поиск словосочетания S, чтобы можно было разрешить сделать предсказание о том, что должно появиться словосочетание NP (ребро b), а затем словосочетание Pronoun (ребро с). После этого процедура сканирования распознает, что в нужном месте находится словосочетание Pronoun (ребро d), а процедура продления объединяет неполное ребро b с полным ребром d. для получения нового ребра, е.

Рис. 22.3. Диаграмма синтаксического анализа предложения "". Запись m: S означает, что ребро m имеет словосочетание S в левой части правила, а запись f :VP/Verb означает, что ребро f имеет словосочетание VP в левой части, но для него требуется также выполнить поиск словосочетания Verb. В этой диаграмме имеется пять полных ребер, показанных над вершинами, и восемь неполных ребер, показанных под вершинами

Таблица 22.3. Трассировка процесса синтаксического анализа предложения. Для каждого ребра от а до л показано, какая процедура используется для вывода этого ребра из других ребер, уже имеющихся в диаграмме. Некоторые ребра были исключены в целях сокращения объема таблицы

Этот алгоритм диаграммного синтаксического анализатора позволяет предотвратить формирование большого класса ребер, которые пришлось бы исследовать при использовании простой восходящей процедуры. Рассмотрим предложение: "The ride the horse gave was wild" (Скачка, на которую пустилась эта лошадь, была дикой). Процедура восходящего синтаксического анализа отметила бы словосочетание "ride the horse" (скакать на лошади) как VP, а затем отбросила бы все дерево синтаксического анализа, обнаружив, что такой вариант анализа не складывается в общее словосочетание S. Но в языкене разрешается, чтобы словосочетание VP следовало за словом "the", поэтому данный алгоритм диаграммного синтаксического анализатора никогда не предсказал бы наличие в этой точке словосочетания VP и поэтому избежал бы напрасного расходования времени на формирование здесь составляющей VP. Алгоритмы, которые действуют слева направо и предотвращают формирование таких невозможных составляющих, называются синтаксическими анализаторами по левому углу, поскольку они формируют дерево синтаксического анализа, начинающееся с начального символа грамматики и продолжающееся вниз к самому левому слову предложения (к левому углу). Ребро добавляется к диаграмме, только если оно может послужить для продления этого дерева синтаксического анализа (соответствующий пример приведен на рис. 22.4).

Рис. 22.4. Алгоритм синтаксического анализа по левому углу позволяет предотвратить предсказание словосочетания VP, начинающегося со слова "ride", но предсказывает словосочетание VP, начинающееся со слова "was", поскольку в данной грамматике допускается наличие словосочетания VP, которое следует за NP. Треугольник, показанный над словами "the horse gave" (на которую пустилась эта лошадь), означает, что для этих слов был сделан синтаксический анализ, который показал, что они представляют собой относительное предложение RelClause, но дополнительные промежуточные составляющие этого синтаксического анализа не показаны