Восходящие LLK – распознаватели

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

Int i/j, j/i, …;

1. I -> TS;
2. T -> int | char
3. S -> AR
4. R -> ,AR
5. R -> $
6. A -> i
7. A -> j

К примеру, у нас есть строка:

Int i, j; ->(2.1) T i, j; ->(6) TA, j ; ->(7) TA,A; ->(5) TA,AR; ->(4) TAR; ->(3) TS; ->(1) I

Это суть операции свертки.

Для правильной работы магазинного автомата, вводится понятие грамматических вхождений. Грамматическое вхождение задается для символов, правой части грамматики, в виде индексов, обозначающих номер правила и номера позиции символа в правиле. Условимся грамматическим вхождением, входящее в правило один раз, не индексировать.

Для построение распознавания необходимо построить две таблицы: таблицы переходов и управляющие таблицы. Для их построения понадобится две функции: ВПЕРВ и ВПОСЛЕ.

ВПЕРВ(Y)
ВПОСЛЕ(Z)

Функция ВПЕРВ(Y) равна самому значению Y и грамматическим вхождениям., которое стоят на первом месте цепочки выводимые из Y, без применения онулирующих правил.

Пример:

1. I -> TS;
2. T -> int | char
3. S -> A3R3
4. R -> ,A4R4
5. R -> $
6. A -> i
7. A -> j

ВПРЕВ(T) = {T, int , char}
ВПРЕВ(S) = {S, A3 , i, j}
ВПРЕВ(;) = {;}

Функция ВПОСЛЕ(Z)  определяет множество грамматических вхождений, которые могут встречаться ВПОСЛЕ(Z)  выводимого в начальной грамматике, если в правилах грамматике ВПОСЛЕ(Z) идет Y, то ВПОСЛЕ(Z) будет идти ВПЕРЕВ(Y), другими словами:

ВПОСЛЕ(Z) = ВПЕРЕВ(Y).

Пример:

ВПОСЛЕ(T) = ВПЕРЕВ(S) = {S, A3, i, j}.
ВПОСЛЕ(S) = {;}.
ВПОСЛЕ(;) = {$}.

При построения восходящего распознавателя различают два алгоритма LR(0) или LR(1).

Если грамматика содержит онулирующие правила, то для нее может подойти только LR(1) алгоритм.