(Е - начальный символ). Ясно, что строка

(jr + y)XJC

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

TxF FxF

=HE+T)XF MT + T}XF

=(F+T) XF =ix + y)XF

Или же это можно было бы вывести так:

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

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

2, 3, 4, 5, 1, 2, 4, 6, 4, 7, 6.

Правосторонний разбор предложения является обратной последовательностью порождающих правил, используемых для генерирования предложения посредством правостороннего вывода; например, в вышеприведенном случае правосторонний разбор запишется в виде

6, 4, 2, 7, 4, 1, 5, 4, 6, 3.2.

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

Можем также описать вывод и в терминах построения дерева, известного как синтаксическое дерево (или дерево разбора). В случае со строкой

синтаксическое дерево будет таким, как показано на рис. 2.1. Проблему разбора можно свести к

1) нахождению левостороннего разбора;

2) нахождению правостороннего разбора;

3) построению синтаксического дерева. В большинстве случаев левосторонний и

синтаксическое дерево являются уникальными. Однако рассмотрим грамматику порождающими правилами:

правосторонний разборы

Предложение х + х + х имеет два синтаксических дерева (рис. 2.2) и два левосторонних (и правосторонних) разбора:

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

S-5-

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

можно воспользоваться для того, чтобы показать, что грамматика является однозначной (но не для того, чтобы показать, что она является неоднозначной).

Де Ремер [17] сравнил задачу разбора с игрой в домино. В этой игре для каждого порождающего правила грамматики выделяется пластинка, верхняя и нижняя части которой соответствуют левым и правым сторонам правила. Для грамматики, рассмотренной в начале данной главы, пластинки окажутся такими, как показано на рис. 2.3. Игру

начинаем на большой доске. Начальный символ, заключенный в полукруг с плоским основанием, находится в верхней части доски, а символы в предложении, заключенные в полукруг с плоским верхом, располагаются в ряд в нижней части доски. Например, для разбора предложения

начальная позиция представлена на рис. 2.4. Цель игры заключается в том, чтобы с помощью пластинок соединить предложение и начальный символ. Здесь необходимо подчеркнуть следующие положения:

1. Существует столько копий каждой пластинки, сколько требуется.

2. Пластинки гибкие, и их можно по потребности вытягивать.

3. Нельзя играть перевернутыми пластинками.

4. Закругленные сверху и снизу пластинки, обозначающие один и тот же символ, соединяются по плоским граням.

Решение вышеописанного примера приведено на рис. 2.5.