Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 9
Текст из файла (страница 9)
На шаге свертки текущий входной символ неменяется. Для LR-анализаторов Xm-r+1 ... Xm - последовательностьсимволов грамматики, удаляемых из магазина, всегда соответствует w правой части правила вывода, по которому делается свертка.После осуществления шага свертки генерируется выход LRанализатора, т.е.
исполняются семантические действия, связанные справилом, по которому делается свертка, например печатаются номераправил, по которым делается свертка.3. Если action[Sm,ai]=accept, то разбор завершен.4. Если action[Sm,ai]=error, анализатор обнаружил ошибку, товыполняются действия по диагностике и восстановлению.Ниже приведен алгоритм LR-анализа. Все LR-анализаторы ведутсебя одинаково.
Разница между ними заключается в различномсодержании таблиц действий и переходов.Алгоритм 3.7. Алгоритм LR-анализа.54while (true){Пусть S - состояние на верхушке магазина;if (action[S,InSym]==“shift S'“){поместить InSym и затем S' на верхушкумагазина;прочитать в InSym следующий входной символ;}else if (action[S,InSym]==“reduce N->w”){удалить из магазина 2*|w| символов;пусть теперь на верхушке магазина состояние S';поместить на верхушку магазина N, азатем состояние goto[S',N];вывести правило N->w;}else if (action[S,InSym]==“accept”){result(“success”);break;}else {result(error());break;}}Вначале в магазине помещено начальное состояние S0, а в буфере w$,InSym содержит первый символ w$; Анализатор выполняет приведеннуюпрограмму до тех пор, пока будет достигнуто либо состояние accept, либосостояние error.Пример 3.6.
На рис. 3.16 изображены функции action и goto LR-таблиц дляграмматики арифметических выражений с бинарными операциями + и *примера 3.5. Здесь Si означает сдвиг и помещение в магазин состояния i, Rj- свертку по правилу номер j, acc - допуск, пустая клетка - ошибку.На входе id+id*id последовательность состояний магазина и входапоказаны на рис. 3.17. Например, в первой строке LR-анализаторнаходится в нулевом состоянии и читает первый входной символ id.Действие S6 в нулевой строке и столбце id в поле action рис.
3.17 означаетсдвиг и помещение S6 на верхушку магазина. Это и изображено во второйстроке: первый символ id и символ состояния S6 помещаются в магазин иid удаляется из входной строки.55Состоянияid012345678S6S6S6action+goto*$S4R2R4S7R4accR2R4R1R5S7R5R1R5R3R3R3ETF123538Рис. 3.16Активный Магазинпрефиксid-> idFTEE+сдвигE+ididE+FT -> FE+TсдвигE+T*E+T*ididE+T*FT*FE+T-> E+TEВход00 id 60000FTEEДействиеid + id * id $сдвиг+ id * id $F3211 + 4+ id * id $+ id * id $+ id * id $id * id0 E 1 + 4 id 6* id $T -> FE -> Tсдвиг$F ->0 E 1 + 4 F 3* id $0 E 1 + 4 T 5id $0 E 1 + 4 T 5 * 70 E 1 + 4 T 5 * 7 id 60 E 1 + 4 T 5 * 7 F 8id $ сдвиг$ F ->$ T ->0 E 1 + 4 T 5$E0 E 1допускРис.
3.17Текущим входным символом становится +, и действием в состоянии6 на вход + является свертка по F->id. Из магазина удаляются два символа(один символ состояния и один символ грамматики). Теперь анализируетсянулевое состояние Поскольку goto в нулевом состоянии по символу F - это3, F и 3 помещаются в магазин. Теперь имеем конфигурацию,соответствующую третьей строке. Остальные шаги определяютсяаналогично.563.3.3. LR-грамматикиГрамматики, для которых можно построить таблицу LR-разбора,называются LR-грамматиками.
Есть КС-грамматики, не являющиеся LRграмматиками,однакопрактическидляописанияязыковпрограммирования достаточно класса LR.Чтобы грамматика была LR, анализатор, работающий слева-направопо типу сдвиг-свертка, должен уметь распознавать основы на верхушкемагазина. Выделение основы осуществляется конечным автоматом,читающим содержимое магазина от дна к верхушке. Состояние автоматапосле прочтения содержимого магазина и текущий входной символопределяют очередное действие автомата. Функцией переходов этогоконечного автомата является таблица переходов LR-анализатора. Чтобы непросматривать магазин на каждом шаге анализа, на верхушке магазинавсегда хранится то состояние, в котором должен оказаться этот конечныйавтомат после того, как он прочитал символы грамматики в магазине отдна к верхушке.Для принятия решения о сдвиге или свертке анализаторпросматривает очередные k входных символов.
Практический интереспредставляют случаи k=0 и k=1. Например, в таблице действий рис. 3.16используется один символ. Грамматика, которая может бытьпроанализирована LR анализатором, заглядывая на k входных символов накаждом шаге, называется LR(k)-грамматикой.Можно дать другое определение LR(k)-грамматики. Пополненнойграмматикой для данной грамматики G называется КС-грамматика, вкоторой введена новая аксиома S' и правило вывода S'->S. Этодополнительное правило вводится для того, чтобы определить, когдаанализатор должен остановить разбор и зафиксировать допуск входа.Таким образом допуск имеет место тогда и только тогда, когда анализаторосуществляет свертку по правилу S'->S. Пополненная грамматиканазывается LR(k) для k>=0, если из условий(1) S' =>* uAw => uvw,(2) S' =>* zBx => uvy,(3) FIRST(w)=FIRST(y)следует, что uAy=zBx (т.е.
u=z, A=B и x=y).Согласно этому определению, если uvw и uvy - правовыводимыецепочки пополненной грамматики, у которых FIRST(w)=FIRST(y) и A->v последнее правило, использованное в правом выводе цепочки uvw, топравило A->v должно применяться и в правом разборе при свертке uvy кuAy. Так как A дает v независимо от w, то LR(k) условие означает, что в57FIRST(w) содержится информация, достаточная для определения того, чтоuv за один шаг выводится из uA. Поэтому никогда не может возникнутьсомнений относительно того, как свернуть очередную правовыводимуюцепочку пополненной грамматики. Кроме того, для LR(k) грамматикиизвестно, когда допускается входная цепочка.Основная разница между LL- и LR-грамматиками заключается вследующем. Чтобы грамматика была LR(k), необходимо распознаватьвхождение правой части правила вывода, просмотрев все, что выведено изэтой правой части и заглянув на k входных символов вперед.
Этотребование существенно менее строгое, чем требование для LL(k)грамматики, когда необходимо определить применимое правило, видятолько первые k символов, выводимых из его правой части. Класс LLграмматик является собственным подклассом LR. Рассмотрим теперьконструирование таблиц LR-анализатора.LR(1) ситуацией называется пара [A->u.v,a], где A->uv - правилограмматики, а a - терминал или правый концевой маркер $.
"1" указываетна длину второй компоненты ситуации, которая называется аванцепочкойситуации. Аванцепочка не играет роли в ситуациях вида [A->u.v,a], где vне равно e, но ситуация вида [A->u.,a] ведет к свертке по правилу A->uтолько если следующим входным символом является a. Таким образомсвертка по правилу A->u требуется только для тех входных символов a,для которых [A->u.,a] является LR(1) ситуацией в состоянии на верхушкемагазина.Будем говорить, что LR(1)-ситуация [A->u.v,a] допустима дляактивного префикса z, если существует вывод S=>*yAw=>yuvw, где z=yuи либо a - первый символ w, либо w равно e и a равно $ (рис.
3.18).Будем говорить, что ситуация допустима, если она допустима для какоголибо активного префикса.Пример 3.7. Рассмотрим грамматикуS -> BBB -> aB | bСуществует правосторонний вывод S=>*aaBab=>aaaBab. Ситуация [B>a.B,a] допустима для активного префикса z=aaa, если в определениивыше положить y=aa, A=B, w=ab, u=a, v=B. Существует такжеправосторонний вывод S*=>BaB=>BaaB. Из этого вывода видно, что дляактивного префикса Baa допустима ситуация [B->a.B,$].58SAyuМагазинvza...wНепрочитанная частьвходной цепочкиРис. 3.18Центральная идея LR-метода заключается в том, что пограмматике строится детерминированный конечный автомат,распознающий активные префиксы.
Для этого ситуации группируютсяво множества, которые и образуют состояния автомата. Ситуацииможно рассматривать как состояния недетерминированного конечногоавтомата, распознающие активные префиксы, а их группирование насамом деле есть процесс построения детерминированного конечногоавтомата из недетерминированного.Для конструирования набора множеств допустимых LR(1)-ситуацийбудут применяться пополненная грамматика G' и процедуры-функцииclosure и goto.Рассмотрим ситуацию вида [A->u.Bv,a] из множества ситуаций,допустимых для некоторого активного префикса z.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
