Разработка компиляторов
LR(1)-анализатор
LR(1)-анализатор использует для принятия решения один символ входной цепочки. Алгоритм построения управляющей таблицы LR(1)-анализатора подобен уже рассмотренному алгоритму для LR (0)-анализатора, но понятие ситуации в LR(1)-анализаторе более сложное: LR(1)-ситуация состоит из правила грамматики, позиции правой части (представляемой точкой) и одного символа входной строки (lookahead symbol). LR(1)-ситуация выглядит следующим образом: [A-> w1 . w2 , a] , где a - терминальный символ. Ситуация [A-> w1 .w2, a] означает, что цепочка w1 находится на вершине магазина, и префикс входной цепочки выводим из цепочки w2 x. Как и прежде, состояние автомата определяется множеством ситуаций. Для построения управляющей таблицы необходимо переопределить базовые операции closure и goto.
closure (I) { do { Iold =I; for (каждой ситуации [A-> w1.Xw2, z] из I) for (любого правила X-> u) for (любой цепочки w, принадлежащей FIRST (w2 z)) I+=[X->.u, w]; } while (I != Iold); return I; } goto (I, X) { J = {}; for (каждой ситуации [A-> w1.Xw2, z] из I) J+=[A-> w1 X.w2, z]; return closure (J); }
Естественно, операция reduce также зависит от символа входной цепочки:
R=[] foreach (I из T) foreach ([A->w., z] из I) R+={(I, z, A->w)}
Тройка (I, z, A->w) означает, что в состоянии I для символа z входной цепочки анализатор будет осуществлять свертку по правилу A->w.
