На входной ленте помещается еще не обработанная правая под-
цепочка анализируемой цепочки. К анализируемой цепочке справа
приписано k маркеров.
В верхнем магазине - цепочки-символы состояний анализатора.
Состояния подбираются так, чтобы они соответствовали возможным
вариантам дерева вывода на различных тактах анализа.
В нижнем магазине - частично свернутые левые подцепочки
входной цепочки (обработанные анализатором).
На каждом такте работы анализатора может выполняться одно из
действий: сдвиг или свертка. После выполнения определенного коли-
чества тактов анализатор допускает или отвергает анализируемую
цепочку.
Выполнение каждого такта можно разбить на 2 этапа. На 1 -
преобразование информации нижнего (и, возможно, верхнего) магази-
нов. Информация для выполнения 1 этапа - правое состояние цепоч-
ки состояний (верхний магазин) и к левых символов не обработан-
ной части входной цепочки. Если действие - сдвиг, в нижний мага-
зин записывается терминал из левого символа входной цепочки. Вер-
хний магазин остается без изменений. Если действие - свертка, то
из нижнего и верхнего магазинов исключается по одинаковому числу
символов, в нижний магазин записывается нетерминал (правая часть
гр.правила). Входная цепочка - без изменений. Информация для
свертки - правые состояние и символ из верхнего и нижнего магази-
нов соответственно (после выполнения 1 этапа). Запись в верхний
магазин "переходного состояния".
Свертка соответствует случаю использования некоторого прави-
ла вывода порождающей грамматики. Символы, исключаемые из нижне-
го магазина, соответствуют правой, а символ, записываемый в мага-
зин - левой части грамматического правила.
ОПРЕДЕЛЕНИЕ: LR(k)-анализатор, соответствующий G=(Vt,Vn,P,S)
- LR(k)=(U,X,H,T,b1,b2,S0,Z0,Sr), где:
U - конечное множество состояний анализатора;
X - конечное множество входных символов, Х=Vt U # -маркер;
H - конечное множество H=(Vt U Vn U Z0),
Х=Vt U # - маркер;
T - {Q U (p,A)}, A C Vn,
p - положительное целое,
Q - сдвиг,
пара (p,A) - cвертка, с исключением p символов из
магазинов и записью в нижний магазин
символа А
k k
b1 - (UxX ) -> T, X - цепочки длины k над алфавитом X;
b1 - частично определенная функция, задающая первые этапы
тактов анализа b2 - (UxH) -> U;
b2 - частично определенная функция, задающая вторые этапы
тактов анализа;
S0 - S0 C U - начальное состояние;
Z0 - граничный маркер;
Sr - Sr C U, заключительное состояние.
Для любой LR(k) - грамматики можно построить LR(1) - грамма-
тику, допускающую тот же язык.
ОПРЕДЕЛЕНИЕ: Автомат с магазинной памятью (сокращенно МП-ав-
томат) - это семерка
P = (Q, X, Г, b, q0, Z0, F),
где:
Q - конечное множество символов состояний, представляющих
всевозможные состояния управляющего устройства;
Х - конечный входной алфавит;
Г - конечный алфавит магазинных символов;
b - отображение множества Q * (X U {e}) * Г в множество ко-
нечных модмножеств множества Q * Г";
q0 C Q - начальное состояние управляющего устройства;
Z0 С Г - символ, находящийся в магазине в начальный момент
(начальный символ);
F C Q - множество заключительных состояний.
ОПРЕДЕЛЕНИЕ: МП-автомат P=(Q,X,Г,b,q0,Z0,F) называется де-
терминированным (сокращенно ДМП-автоматом), если для каждых q C Q
и Z C Г либо
1) b (q,a,Z) содержит не более одного элемента для каждого
а С Х и b (q,e,Z) = 0, либо
2) b (q,a,Z) = 0 для всех а С Х и b (q,e,Z) cодержит не бо-
лее одного элемента.
Утверждение. Любой LR(k) - анализатор может быть преобразо-
ван в детерминированный МП-автомат.
При доказательстве этого утверждения используют свойство
анализатора записывать по одному символу в верхний и нижний мага-
зины. Исключаться из магазина эти символы могут только одновре-
менно и только на этапе свертки, следовательно верхний магазин
может быть исключен, если каждый символ нижнего магазина снаб-
дить индексом. Индекс соответствует тому состоянию, которое запи-
сывается в нижний магазин. Каждый символ нижнего магазина должен
иметь N модификаций, где N - число состояний анализатора, соот-
ветствующих этому символу.
Для любого языка, распознаваемого LR(k)-анализатором, сущес-
твует распознающий этот язык LR(1)-анализатор (класс языков,
распознаваемых LR(k)-анализатором, совпадает с классом языков
LR(1)-анализатора. Входит в класс несущественно неоднозначных
УКС-языков.
Функции b1 и b2 обычно задаются в виде общей таблицы, сос-
тоящей из конечного числа "рядов". Каждый ряд соответствуют неко-
торому состоянию и имеет следующую структуру:
- состояние;
- наблюдаемая цепочка;
- функция действия (b1);
- символ нижнего м-на;
- функция b2 (переходное состояние). Для заключительного
состояния Sr имеется сл. строка:
- состояние Sr;
- наблюдаемая цепочка - ##### - k раз - маркеры Z0;
- функция действия (b1) - допуск;
- символ нижнего м-на;
- функция b2 (переходное состояние). Таблица наз. анализи-
рующей таблицей LR(k)-анализатора.
┌──────────┬───────────────────┬─────┬───────────────┬──────┐
│ │ k │ │ │ │
│ U │ X │ b1 │ H │ b2 │
│ Состояние│ Наблюдаемая строка│ │ Символ нижнего│ │
│ │ │ │ магазина │ │
├──────────┼───────────────────┼─────┼───────────────┼──────┤
│ │ Xi1 │(p,A)│ Zi1 │ Si1 │
│ ├───────────────────┼─────┼───────────────┼──────┤
│ │ Xi2 │ Q │ Zi2 │ Si2 │
│ ├───────────────────┼─────┼───────────────┼──────┤
│ │ ... │(p,B)│ ... │ ... │
│ ├───────────────────┼─────┼───────────────┼──────┤
│ │ Xij │ Q │ Zij │ Sij │
│ ├───────────────────┼─────┼───────────────┼──────┤
│ │ ... │ ... │ ... │ ... │
└──────────┴───────────────────┴─────┴───────────────┴──────┘
LR(k)-грамматики образут широкий класс грамматик, анализи-
руемых естественным образом снизу вверх с помощью ДМП-автомата.
Пусть ах - правовыводимая цепочка какой-то грамматики при-
чем а - либо пустая цепочка либо оканчивается нетерминалом. Тог-
да а называется открытой частью цепочки ах , х - замкнутой. Гра-
ницу между а и х назовем рубежом.
Алгоритм разбора типа "перенос-свертка" можно рассматривать
как программу расширенного ДМП-преобразователя который проводит
разбор "снизу-вверх". Для данной входной цепочки W ДМП-преобразо-
ватель смоделирует в обратном порядке ее правый вывод.
S=a(0)=>a(1)=>...=>a(m)=W
Это правый вывод цепочки W. Каждая правовыводимая цепочка
а(i) распределяется в памяти ДМП так, что ее открытая часть хра-
нится в магазине а замкнутая - на входной ленте справа от голов-
ки. Затем ДМП должен локализовать правый конец основы и сделать
свертку. Число принимаемых ДМП решений - два: решения о переносе
и о свертке (по конкретному правилу).
Грамматика будет LR(K) грамматикой, если для произвольного
правого вывода
S=a(0)=>a(1)=>...=>a(m)=Z
в каждой правовыводимой цепочки а(i), читая ее слева напра-
во, можно выделить основу и определить, каким нетерминалом надо
ее заменить, дойдя при этом не более чем до k-го символа, распо-
ложенного справа от правого конца этой основы.
ОПРЕДЕЛЕНИЕ:
Пусть G=(N,E,P,S) - КС грамматика.
Пополненной грамматикой, полученной из G, будем называть
G'=(N+S',E,P+{S'->S},S').
S' - новый начальный символ, не принадлежащий N.
S' -> S - это нулевое правило грамматики G', добавляемое для
того, чтобы свертку , в которой используется нулевое правило,
можно было интерпретировать как сигнал о том, что цепочка допус-
кается.
ОПРЕДЕЛЕНИЕ: пусть G - КС грамматика, а G' - полученная из
нее пополненная. Будем называть G LR(k) грамматикой для k >= 0,
если из условий:
1) S' -> aAw -> abw;
2) S' -> gBx -> aby;
3) FIRST(k;w) = FIRST(k;y) где k соответствует грамматике.
Из условий следует, что
aAy = gBx (т.е. a=g, A=B, x=y)
Интуитивно это определение говорит о том, что если abw и aby
-правовыводимые цепочки пополненной грамматики, у которых
FIRST(w)=FIRST(y), и A->b -последнее правило, использованное в
правом выводе цепочки abw, то правило A->b должно использоваться
также в правом разборе при свертке aby к aAy.
Так как A дает b независимо от w, то LR(k) условие говорит о
том , что в FIRST(w) содержится информация, достаточная для того,
что ab за один шаг выводится из aA. Поэтому никогда не может воз-
никнуть сомнений относительно того, как свернуть очередную право-
выводимую цепочку пополненной грамматики.
Кроме того, работая с LR(k)-грамматикой, мы всегда знаем,
допустить ли данную входную цепочку или продолжать разбор.
Если начальный символ S не встречается в правых частях пра-
вил, то в определении LR(k) грамматики вместо S' можно взять S, а