Задачи синтаксического анализа

При работе с языками часто сталкиваются с задачей сингаксического анализа. В таких задачах сначала дается некоторое формальное определение через задание грамматики, которая выделяет определенный класс строк символов. А затем возникает вопрос о том, принадлежит ли к этому классу произвольная строка. Следующий пример иллюстрирует этот тип задач.

Грамматика. Предположим, что мы определяем предложение как строку одного из следующих видов: за символом а следует символ за символом а следует некоторое предложение за некоторым предложением следует символ за некоторым предложением следует другое предложение. Примеры предложений: Некоторые строки, не являющиеся предложениями:

Предположим, что мы захотели определить, является ли строка предложением. Тогда формулировка этой задачи в пространстве состояний выглядит Так:

Описания состояний. Один из возможных путей формулировки этой задачи состоит в том, чтобы выбрать в качестве начального состояния рассматриваемую строку Тогда множеством допустимых состояний будет множество строк, получающихся из нее путем применения тех правил переписывания (они даются ниже), которыми определяются операторы.

Операторы. Мы определяем операторы через следующие правила переписывания:

Мы видим, что эти правила просто выражают грамматику, определяющую понятие предложения.

Критерий цели. Целевое состояние описывается строкой, которая состоит из одиночного символа

Последовательность состояний, представляющая собой решение этой задачи, имеет следующий вид:

Граф, изображающий пространство состояний для этой задачи, показан на рис. 2.6.

Рис. 2.6. (см. скан) Граф для задачи синтаксического анализа.

В этой задаче оказалось так, что в силу заданной грамматики любая строка, начинающаяся с а и оканчивающаяся на является предложением. Знание такого факта, очевидно, сильно бы упростило решение вопроса о том, будет ли некоторая произвольная строка предложением. Иногда оказывается, что заданная грамматика может быть

представлена в эквивалентном, но более простом виде. Обнаружение таких упрощений позволяет строить меньшие пространства для перебора.