дает возможность сократить эту цифру процентов на 90. Так что LL-метод в отношении размера таблицы разбора не представляется лучшим, чем LR-метод.

Коэн и Рот [14] сравнили максимальное, минимальное и среднее время разбора предложений с помощью LL- и LR-анализаторов. Они приводят показатели относительной эффективности этих методов при их использовании на машине DEC PDP-10. Результаты показывают, что LL-метод «быстрее» процентов на 50.

Оба метода разбора позволяют включить в синтаксис действия для выполнения некотортх аспектов процесса компиляции. В следующей главе мы увидим, как это осуществляется в LL-анализаторах. Для LR-анализаторов такие действия обычно связаны с приведениями, и часто в грамматику там, где требуется не окончание правила, а другие действия, вводятся фиктивные правила. Это не влияет на признак принадлежности грамматики к LR(1) до тех пор, пока грамматика обладает LL(1)-свойством.

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

Упражнения

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

а) LR(0);

б) SLR(l), но не LR(0);

в) LR(1), но не SLR(l).

5.2. Определите, какие из следующих грамматик являются LR(1 (-грамматиками и обоснуйте свой вывод:

а) Е-Е+Е Е-i

б) Z-0S0

- 1S1

в) S -0S0

- 0S1

Там, где грамматика не обладает признаком LR(I), приведите эквивалентную LR(1)-грамматику, если такая существует.

5.3. Постройте таблицу разбора для грамматики, имеющей следующие правила (S - начальный символ):

S -E T-F

Е-Е+Т F- (E)

Е-Т F- x

T-T х F F- y

Является ли эта грамматика SLR(1)-грамматикой?

5.4. Докажите, что следующая грамматика не обладает признаком LR(I) (PROGRAM - начальный символ):

PROGRAM begin DECLIST semi STATELIST end DECLIST d semi DECLIST d

STATELIST- s semi STATELIST s

Преобразуйте эту грамматику в эквивалентную SLR(I)-грамматику и постройте соответствующую таблицу разбора.

5.5. Постройте таблицу разбора для грамматики (S - начальный символ):

a t F F-, ITEM F

ITEM-a t t

5.6. Докажите, что следующая грамматика не обладает признаком LR(I) (S- начальный символ):

S-1S0 S -0S1 S-1 0

S -0 1 -

5.7. Обладает ли а) грамматика из упражнения 5.6 и б) язык, генерируемый этой грамматикой, LR(k)-свойством для любого k?

5.8. Покажите, что следующая грамматика является не LR(I)-грамматикой, а LR(2)-грамматикой:

S -V: = Е S -L S L-1: V-1

Предложите, что можно сделать на стадии лексического анализа в отношении непринадлежности ее к LR(1)?

5.9. Какие преимущества могло бы иметь построение SLR(1)-таблицы разбора на основании LR(0)-гpамматики?

5.10. Требуется ли для метода LR-разбора использование двух стеков (стека символов и стека состояний) или эти два стека можно объединить в один? Обоснуйте свой ответ.

5.11. Докажите, что все регулярные языки обладают LR(I)-свойством.

Г л а в а 6. ВЛЮЧЕНИЕ ДЕЙСТВИЙ В СИНТАКСИС

Анализ и синтез в компиляции, хотя их часто удобно рассматривать как отдельные процессы, во многих случаях происходят параллельно. Это совершенно очевидно для однопроходного компилятора, но и в многопроходнтх компиляторах генерирование объектного или какого-либо промежуточного кода большей частью осуществляется одновременно с синтаксическим анализом. Последнее не должно вызывать удивления: ведь как только синтаксический анализатор распознает, например, присваивание, он, естественно, выдаст код для присваивания в данной точке. В настоящей главе мы покажем, что в грамматике могут содержаться вызовы действий не только для генерирования кода, но и для выполнения других задач компиляции, таких, как построение таблиц символов и обращение к ним и т. п.

6.1. ПОЛУЧЕНИЕ ЧЕТВЕРОК

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

S -EXP EXP-TERM

ЕХР+TERM TERM-FACT

TERM x FACT FACT--FACT

(EXP) ID-abcde где S - начальный символ.

Примеры выражений: (a+b)*c a*b+c a*b+c*d*e

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

Грамматика для четверок имеет следующие правила: QUAD -OPERAND ОР1 OPERAND=INT ОР2 OPERAND=INT OPERAND-INT ID

INT -DIGIT DIGIT INT

DIGIT-0123456789 ID-abcde