ВОЗМОЖНЫХ выборов, а затем возвращаться, если этот путь де нужного решения. Такое действие называется возвратом- В языке примера 3 число возможных шагов, на которые

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

Ограничение /:

Если дано порождающее правило

A::=h\b\...\ln,

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

first Hi) (] first ilj) = 0 для всех i¥=j.

Множество first(Ь,) есть множество всех терминальных символов, которые могут встречаться в начале предложений, полученных из . Пусть это множество вычисляется согласно следующим правилам:

1. Если первый символ аргумента терминальный, то

first(a£,) = {a}.

2. Если первый символ нетерминальный и стоит в левой части порождающего правила

Л::=а, Ittal... а„,

first (Al) = first (а,) и first (Ог) U - U first (a ).

В примере 3 можно заметить, что xfirst(A) и xfirst(B). Следовательно, в первом порождающем правиле нарушено ограничение 1. На самом деле, легко найти синтаксис для языка примера 3, удовлетворяющий ограничению 1. Нужно отложить разделение на части до тех пор, пока не будут пройдены все х. Следующие порождающие правила зквива-лентны правилам (5.5) в том смысле, что они порождают то *е множество предложений:

К сожалению, ограничение 1 недостаточно сильно, чтобы из-вить нас от дальнейших неприятностей. Рассмотрим

Пример 4:

А::=х\е. (5.6)

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

S X Ах X

XX X X -

Трудность возникает из-за того, что мы должны были следовать правилу Л ::= е вместо А\\=х. Эта ситуация назы-вается проблемой пистой сгрокм. она связана со случаем, когда нетерминальный символ может порождать пустую последовательность. Чтобы ее избежать, мы вводим

Ограничение 2:

Для любого символа AN, который порождает. пустую последовательность (И е), множество начальных символов не должно пересекаться со множеством символов, которые могут появляться в предложениях языка справа от какой-либо последовательности, порождаемой А (внешними символами А), т. е.

first(A) П follow{A)=0.

Множество follow {А) определяется так: берутся все порождающие правила Pi вида

Х::=1Аг],

затем для каждой последовательности rj,-, стоящей справа от А, определяется ее множество начальных символов Si = == first{r\i). Множество /оЯош(Л) -объединение всех таких множеств Si. Если хотя бы одна ц может порождать пустую последовательность, то множество follow (X) следует также включить в follow (А). В примере 4 ограничение 2 нарушается для символа Л, поскольку

firstiA) = followiA) = {х}.

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

А::=В\АВ

описывает множество предложений В, ВВ, ВВВ, .... Однако использование такого правила теперь запрещено ограниче-

дяем 1, так как

firsHB) П firstiAB) = flrst{B) Ф 0.

gcjiH мы заменим это правило его слегка модифицированной ерсией

ррождак>щей последовательности е. В, ВВ, ВВВ, .... то нарушим ограничение 2, поскольку

firstiA) = first{B)

g следовательно,

firstiA) n followiA)Ф0

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

А::=е\ВА,

либо расширить БНФ-нотацию с тем, чтобы она допускала явное выражение повторений. Поэтому определим {В} как множество последовательностей

е. В, ВВ, ВВВ.....

Конечно, нужно учитывать, что каждая такая конструкция может порождать пустую последовательность. (Фигурные скобки { } являются метасимволами расширенной БНФ.)

Эти рассуждения, а также пример преобразования порождающих правил (5.5) в (5.5а) могут навести на мысль, что трюки с преобразованием грамматик позволяют решить все проблемы синтаксического анализа. Но не следует забывать, что структура предложений связана с их смыслом и что смысл синтаксических конструкций обычно выражается через смысл их компонент. Рассмотрим, например, язык, состоящий из выражений, которые включают операнды а, Ь, с п знак минус, обозначающий вычитание:

5::=:Л|5-Л, А::=а\Ь\с.

Согласно этой грамматике, предложение а - b - с имеет структуру, которую с использованием скобок можно выразить Следующим образом: {{а - Ь) - с). Но если эту грамматику преобразовать в эквивалентную, но свободную от левой ре-Урсии

S ::= Л М - S,

Л::=а\Ь\с,