Контекстно-свободные языки. Свойства и распознаватели КС-языков. Преобразование КС-грамматик. КС-грамматики в нормальной форме, страница 20

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

Свойства LR(k)-грамматик.

§  Всякая LR(k)-грамматика для любого k³0 является однозначной.

§  Существует алгоритм проверки, является ли заданная КС-грамматика LR(k)-грамматикой для строго определённого числа k.

§  Класс LR-грамматик полностью совпадает с классом детерминированных КС-языков.

Проблемы LR(k)-грамматик:

§  Не существует алгоритма, позволяющего проверить, является ли заданная КС-грамматика LR(k)-грамматикой для любого числа k.

§  Не существует алгоритма преобразования произвольной КС-грамматики к виду LR(k)-грамматики для некоторого k (либо доказывающего, что такое преобразование невозможно).

Класс LR-грамматик удобен для построения распознавателей детерминированных КС-языков, следовательно, для распознавания языков программирования.

Для формального определения LR(k)-свойства для КС-грамматик, нужно ввести ещё одно определение.

Грамматика является пополненной, если её целевой символ не встречается нигде в правых частях правил. Для приведения произвольной КС-грамматики к такому виду необходимо к множеству правил добавить S¢®S, а S¢ сделать целевым символом.

Формальное определение LR(k)-свойства.

Если для произвольной КС-грамматики G в её пополненной грамматике G¢ для двух произвольных цепочек вывода из условий:

1.  S¢ Þ* aAwÞ abw

2.  S¢ Þ* gBxÞ aby

3.  FIRST(k,w)= FIRST(k,y)

следует, что aAy = gBx, т.е. a = g, A = B, x = y, то доказано, что грамматика G обладает LR(k)-свойством (так же, как и её пополненная грамматика G¢).

Понятие пополненной грамматики введено для того, чтобы появление символа S¢ на вершине стека означало окончание работы алгоритма.

Распознаватель для LR(k)-грамматик основан на специальной управляющей таблице T. Эта таблица состоит из двух частей, называемых «действия» и «переходы».

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

Клетки управляющей таблицы в части «действия» содержат информацию о необходимых в каждой ситуации действиях, в частности:

§  «сдвиг», если требуется выполнение сдвига (переноса текущего символа из входной цепочки в стек);

§  «успех», если возможна свёртка к целевому символу грамматики S и разбор завершен;

§  целое число («свёртка»), если возможно выполнение свёртки (число обозначает номер правила грамматики, по которому должна выполняться свёртка);

§  «ошибка» – во всех других ситуациях.

Клетки управляющей таблицы T в части «переходы» служат для определения номера строки таблицы, которая будет использоваться для выполнения действия на очередном шаге. Эти клетки содержат данные:

§  целое число – номер строки таблицы T;

§  «ошибка» – во всех других ситуациях.

Для удобства работы используются два дополнительных символа начала и конца цепочки: ^_н  и ^_к. Тогда в начальном состоянии работы распознавателя символ ^_н находится на верхушке стека, а считывающая головка обозревает первый символ входной цепочки. В конечном состоянии в стеке должны находиться целевой символ и ^_к, а считывающая головка должна обозревать символ ^_к.

Алгоритм работы распознавателя:

Шаг 1    Занести в стек символ начала цепочки ^_н и начальную (нулевую) строку управляющей таблицы T (её номер), в конец цепочки поместить символ ^_к.

Шаг 2    Прочитать с вершины стека строку управляющей таблицы T (её номер). Выбрать из неё часть «действие» в соответствии с аванцепочкой.

Шаг 3    В соответствии с типом действия:

–  «сдвиг»: если это не ^_к, то прочитать и запомнить как «новый символ» очередной символ входной цепочки, сдвинув считывающую головку вправо на 1 символ; иначе остановка с ошибкой;

–  «целое число, свёртка»: выбрать соответствующее числу правило (пусть это A ® b), убрать из стека 2×½b½ символов, запомнить A как «новый символ»;

–  «ошибка»: остановка с ошибкой;

–  «успех»: свернуть к S, если текущий символ ^_к, то завершить с успехом, иначе завершить с ошибкой.

Шаг 4    Прочитать с вершины стека строку таблицы T (её номер). Выбрать часть «переход» в соответствии с «новым символом».

Шаг 5    Если «переход» содержит «ошибка», то остановка алгоритма с ошибкой. Иначе (если «переход» содержит номер) – в стек занести «новый символ» и строку таблицы (выбранный номер). Вернуться на шаг 2.

Рассмотрим пример для LR(0)-грамматики.

Пример.

Рассмотрим грамматику G({a,b}, {S}, {S®aSS|b}, S).   

Данная грамматика определяет язык, в цепочках которого количество символов ‘a’ на один меньше, чем ‘b’, первый символ всегда ‘a’, в конце всегда пара ‘bb’. Исключение – минимальная цепочка ‘b’.

Поскольку символ S входит в правую часть правил, необходимо преобразовать грамматику G в пополненную G¢. Правила P¢ перенумеруем.

G¢({a,b},{S,S¢},P¢,S¢);       P¢: (1) S¢®S; (2) S®aSS, (3) S®b.

№ строки	Стек	Действие	Переход
			S	a	b
0	^н	сдвиг	1	2	3
1	S	успех, 1
2	a	сдвиг	4	2	3
3	b	свёртка, 3
4	aS	сдвиг	5	2	3
5	aSS	свёртка, 2