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

5.3. LR-ТАБЛИЦЫ РАЗБОРА

В разд. 5.1 мы познакомились в целом с работой анализатора по принципу "снизу вверх". Не обсуждался лишь вопрос о том, как решить, выполнять ли конкретное приведение, когда правая часть правила появляется в вершине стека. В этой головоломке не достает таблицы разбора, которая позволяет в каждом случае принимать правильное решение. В этом разделе мы опишем форму таблицы (весьма отличающ;уюся от LL-таблицы) и объясним ее использование, а в следующем - покажем, как эта таблица образуется из грамматики. Правила грамматики таковы:

(1) Sreal IDLlST (3) IDLISTID

(2) IDLISTIDL1ST, ID (4) 1DABCD

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

1. Элементы сдвига. Эти элементы имеют вид S7 и означают: поместить в стек символов символ, соответствующий столбцу; поместить в стек состояний 7 и перейти к состоянию 7; если входной символ - терминал, принять его.

2. Элементы приведения. Они имеют вид R4 и означают: выполнить приведение с помощью правила (4), т.е. допустив, что n есть

Таблица 5.1

число символов в правой части правила (4); удалить n элементов из стека символов и n элементов из стека состояний, и перейти к состоянию, указанному в верхней части

стека состояний. Нетерминал в левой части правила (4) нужно считать следующим входным символом.

3. Элементы ошибок. Эти элементы являются пробелами, в таблице и соответствуют синтаксическим ошибкам.

4. Элемент(ы) остановки. Ими завершается разбор.

Рассмотрим теперь, как с помощью вышеописанной таблицы разбора будет разбираться строка:

real А, В, С 1

Покажем содержимое стека символов и стека состояний на каждом этапе. Начнем с состояния 1, которое отображается в стеке:

Стек Стек

символов состояний

real А, В, C1

входной символ - real - из элемента таблицы (1, real), сдвиг в состояние 2: real А, ФВ, C1

входной символ - А, сдвиг в состояние 3: real Аф, В, C1

Входной символ - приведение посредством правила (4):

входной символ - приведение посредством правила (3):

real Аф, B, С 1

входной символ - 1DL1ST, сдвиг в состояние 5: real Аф, B, С1

входной символ - ",", сдвиг в состояние 6: real A, B, С1

входной символ - В, сдвиг в состояние 3: real A, B, С1

входной символ - ",", приведение посредством правила (4): real A, B, С1

входной символ - 1D, сдвиг в состояние 7: real A, B, С1

входной символ - ",", приведение посредством правила (2):