Принципы построения распознавателей для LR(k)-грамматик

 

Для того чтобы формально определить LR(k) свойство для КС-грамматик, вве­дем понятие пополненной КС-грамматики. Грамматика G’ является пополнен­ной грамматикой, построенной на основании исходной грамматики G(VT,VN,P,S), если выполняются следующие условия:

 грамматика G’ совпадает с грамматикой G, если целевой символ S не встреча­ется нигде в правых частях правил грамматики G;

 грамматика G’ строится как грамматика G’(VT,VN{S’},P{S’S},S’), если це­левой символ S встречается в правой части хотя бы одного правила из множе­ства Р в исходной грамматике G.

Фактически пополненная КС-грамматика строится таким образом, чтобы ее це­левой символ не встречался в правой части ни одного правила. Если нужно, то в исходную грамматику G для этого добавляется новый терминальный символ S’, который становится целевым символом, и новое правило S’S. Очевидно, что пополненная грамматика G’ эквивалентна исходной грамматике G, то есть L(G’) = L(G).

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

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

1) S’ * αAw  αβw,

2) S’ * γВх  αβy,

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

следует, что αAw = γВх (то есть α = γ, А = В и х = у), то доказано, что граммати­ка G обладает LR(k) свойством. Очевидно, что тогда и пополненная граммати­ка G’ также обладает LR(k) свойством.

Понятие “пополненной грамматики” введено исключительно с той целью, чтобы в процессе работы алгоритма “сдвиг-свертка” выполнение свертки к целевому символу пополненной грамматики S’ служило сигналом к завершению алгорит­ма (поскольку в пополненной грамматике символ S’ в правых частях правил ни­где не встречается). Если условие отсутствия целевого символа в правых частях правил грамматики не будет соблюдаться, то на алгоритм распознавателя по­требуется наложить дополнительные ограничения, так как появление целевого символа на вершине стека уже не будет означать завершение работы алгоритма. Поскольку построение пополненных грамматик выполняется элементарно и не накладывает никаких дополнительных ограничений на исходную КС-граммати­ку, то дальше будем считать, что все распознаватели для LR(k)-грамматик работают с пополненными грамматиками.

Распознаватель для LR(k)-грамматик функционирует на основе управляющей таблицы Т. Эта таблица состоит из двух частей, называемых “действия” и “пере­ходы”. По строкам таблицы распределены все цепочки символов на верхушке стека, которые могут приниматься во внимание в процессе работы распознавате­ля. По столбцам в части “действия” распределены все части входной цепочки символов длиной не более k (аванцепочки), которые могут следовать за считы­вающей головкой автомата в процессе выполнения разбора; а в части “перехо­ды” – все терминальные и нетерминальные символы грамматики, которые мо­гут появляться на верхушке стека автомата при выполнении действий (сдвигов или сверток).

Клетки управляющей таблицы Т в части “действия” содержат следующие дан­ные:

 “сдвиг” – если в данной ситуации требуется выполнение сдвига (переноса те­кущего символа из входной цепочки в стек);

 “успех” – если возможна свертка к целевому символу грамматики S и разбор входной цепочки завершен;

 целое число (“свертка”) – если возможно выполнение свертки (число обо­значает номер правила грамматики, по которому должна выполняться сверт­ка);

 “ошибка” – во всех других ситуациях.

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

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

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

 “ошибка” – во всех других ситуациях.

Для удобства работы распознаватель LR(k)-грамматики использует также два специальных символа ни к. Считается, что входная цепочка символов всегда на­чинается символом н и завершается символом к. Тогда в начальном состоянии работы распознавателя символ ннаходится на верхушке стека, а считывающая головка обозревает первый символ входной цепочки. В конечном состоянии в стеке должны находиться символы S (целевой символ) и н, а считывающая го­ловка автомата должна обозревать символ к.

Алгоритм функционирования распознавателя LR(k)-грамматики можно описать следующим образом:

Шаг 1. Поместить в стек символ ни начальную (нулевую) строку управляющей таблицы Т. В конец входной цепочки поместить символ к. Перейти к шагу 2.

Шаг 2. Прочитать с вершины стека строку управляющей таблицы Т. Выбрать из этой строки часть “действие” в соответствии с аванцепочкой, обозреваемой счи­тывающей головкой автомата. Перейти к шагу 3.

Шаг 3. В соответствии с типом действия выполнить выбор из четырех вариантов:

 “сдвиг” – если входная цепочка не прочитана до конца, прочитать и запом­нить как “новый символ” очередной символ из входной цепочки, сдвинуть считывающую головку на одну позицию вправо, иначе прервать выполнение алгоритма и сообщить об ошибке;

 целое число (“свертка”) – выбрать правило в соответствии с номером, уда­лить из стека цепочку символов, составляющую правую часть выбранного правила, взять символ из левой части правила и запомнить его как “новый символ”;

 “ошибка” – прервать выполнение алгоритма, сообщить об ошибке;

 “успех” – выполнить свертку к целевому символу S, прервать выполнение алгоритма, сообщить об успешном разборе входной цепочки символов, если входная цепочка прочитана до конца, иначе сообщить об ошибке.

Конец выбора. Перейти к шагу 4.

Шаг 4. Прочитать с вершины стека строку управляющей таблицы Т. Выбрать из этой строки часть “переход” в соответствии с символом, который запомнили как “новый символ” на предыдущем шаге. Перейти к шагу 5.

Шаг 5. Если часть “переход” содержит вариант “ошибка”, тогда прервать выпол­нение алгоритма и сообщить об ошибке, иначе (если там содержится номер стро­ки управляющей таблицы Т) положить в стек “новый символ” и строку табли­цы Т с выбранным номером. Вернуться к шагу 2.

Для работы алгоритма кроме управляющей таблицы Т используется также неко­торая временная переменная (“новый символ”), хранящая значение терминаль­ного или нетерминального символа, полученного в результате сдвига или сверт­ки. В программной реализации алгоритма вовсе не обязательно помещать в стек сами строки управляющей таблицы – поскольку сама таблица неизменна в про­цессе выполнения алгоритма, то достаточно запоминать соответствующие ссылки.

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