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

      Комментарии к записи Принципы построения распознавателей для 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)-грамматики имеет линейную зависимость сложности от длины входной цепочки, а потому является линейным распознавателем.

Статьи к прочтению:

Построение головы


Похожие статьи: