В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 12
Текст из файла (страница 12)
Xm – последовательность символов грамматики, удаляемых из магазина, всегда соответствует γ – правой части правила вывода, по которому делаетсясвертка.После осуществления шага свертки генерируется выходLR(1)-анализатора, т.е. исполняются семантические действия, связанные с правилом, по которому делается свертка, например, печатаются номера правил, по которым делается свертка.Заметим, что функция Goto таблицы анализа, построенная по грамматике G, фактически представляет собой функцию переходов детерминированного конечного автомата, распознающего активныепрефиксы G.3.
Если Action[Sm , ai ] = accept, то разбор успешно завершен.4. Если Action[Sm , ai ] = error, то анализатор обнаружил ошибку, и выполняются действия по диагностике и восстановлению.Пример 4.8. Рассмотрим грамматикуG = ({E, T, F }, {id, +, ∗}, P, E) с правилами:(1)(2)(3)(4)(5)E → E +TE→TT →T ∗FT →FF → idарифметическихвыраженийГЛАВА 4. СИНТАКСИЧЕСКИЙ АНАЛИЗ72На рис. 4.9 изображены функции Action и Goto, образующие LR(1)-таблицудля этой грамматики.
Для Элемент Si функции Action означает сдвиг и помещение в магазин состояния с номером i, Rj – свертку по правилу номер j, acc – допуск, пустая клетка – ошибку. Для функции Goto символ i означает помещениев магазин состояния с номером i, пустая клетка – ошибку.На входе id + id ∗ id последовательность состояний магазина и входной лентыпоказаны на рис. 4.10.
Например, в первой строке LR-анализатор находится внулевом состоянии и “видит” первый входной символ id. Действие S6 в нулевойстроке и столбце id в поле Action (рис. 4.9) означает сдвиг и помещение символасостояния 6 на верхушку магазина. Это и изображено во второй строке: первыйсимвол id и символ состояния 6 помещаются в магазин, а id удаляется со входной ленты.Состояния012345678idS6Action+*$S4R2R4S7R4accR2R4R1R5S7R5R1R5R3R3R3E1S6GotoT F2 35S638Рис. 4.9:АктивныйпрефиксidFTEE+E + idE +FE +TE + T∗E + T ∗ idE +T ∗FE +TEМагазинВходДействие00 id 60F 30T 20E10E 1+40 E 1 + 4 id 60E 1+4F 30E 1+4T 50E 1+4T 5∗70 E 1 + 4 T 5 ∗ 7 id 60E 1+4T 5∗7F 80E 1+4T 50E1id + id ∗ id$+id ∗ id$+id ∗ id$+id ∗ id$+id ∗ id$id ∗ id$∗id$∗id$id$id$$$$сдвигF → idT →FE→TсдвигсдвигF → idT →FсдвигсдвигF → idT →T ∗FE →E +TдопускРис.
4.10:4.4. РАЗБОР СНИЗУ-ВВЕРХ ТИПА СДВИГ-СВЕРТКА73Текущим входным символом становится +, и действием в состоянии 6 навход + является свертка по F → id. Из магазина удаляются два символа (одинсимвол состояния и один символ грамматики). Затем анализируется нулевое состояние. Поскольку Goto в нулевом состоянии по символу F – это 3, F и 3 помещаются в магазин. Теперь имеем конфигурацию, соответствующую третьейстроке. Остальные шаги определяются аналогично.4.4.3Конструирование LR(1)-таблицыРассмотрим теперь алгоритм конструирования таблицы, управляющейLR(1)-анализатором.Пусть G = (N, T, P, S) – КС-грамматика.
Пополненной грамматикойдля данной грамматики G называется КС-грамматикаG0 = (N ∪ {S 0 }, T, P ∪ {S 0 → S}, S 0 ),т.е. эквивалентная грамматика, в которой введен новый начальный символ S 0 и новое правило вывода S 0 → S.Это дополнительное правило вводится для того, чтобы определить,когда анализатор должен остановить разбор и зафиксировать допуск входа.
Таким образом, допуск имеет место тогда и только тогда, когда анализатор готов осуществить свертку по правилу S 0 → S.LR(1)-ситуацией называется пара [A → α.β, a], где A → αβ – правило грамматики, a - терминал или правый концевой маркер $. Втораякомпонента ситуации называется аванцепочкой.Будем говорить, что LR(1)-ситуация [A → α.β, a] допустима для активного префикса δ, если существует вывод S ⇒∗r γAw ⇒r γαβw, гдеδ = γα и либо a – первый символ w, либо w = e и a = $.Будем говорить, что ситуация допустима, если она допустима длякакого-либо активного префикса.Пример 4.9. Рассмотрим грамматику G = ({S, B}, {a, b}, P, S) с правиламиS → BBB → aB | bСуществует правосторонний вывод S ⇒∗r aaBab ⇒r aaaBab.
Легко видеть,что ситуация [B → a.B, a] допустима для активного префикса δ = aaa, если вопределении выше положить γ = aa, A = B, w = ab, α = a, β = B. Существует также правосторонний вывод S ⇒∗r BaB ⇒r BaaB. Поэтому для активногопрефикса Baa допустима ситуация [B → a.B, $].Центральная идея метода заключается в том, что по грамматике строится детерминированный конечный автомат, распознающий активныепрефиксы. Для этого ситуации группируются во множества, которые иобразуют состояния автомата.
Ситуации можно рассматривать как состояния недетерминированного конечного автомата, распознающего активные префиксы, а их группировка на самом деле есть процесс построения детерминированного конечного автомата из недетерминированного.74ГЛАВА 4. СИНТАКСИЧЕСКИЙ АНАЛИЗАнализатор, работающий слева-направо по типу сдвиг-свертка, должен уметь распознавать основы на верхушке магазина. Состояние автомата после прочтения содержимого магазина и текущий входной символ определяют очередное действие автомата.
Функцией переходов этого конечного автомата является функция переходов LR-анализатора. Чтобы не просматривать магазин на каждом шаге анализа, на верхушке магазина всегда хранится то состояние, в котором должен оказаться этотконечный автомат после того, как он прочитал символы грамматики вмагазине от дна к верхушке.Рассмотрим ситуацию вида [A → α.Bβ, a] из множества ситуаций, допустимых для некоторого активного префикса z. Тогда существует правосторонний вывод S ⇒∗r yAax ⇒r yαBβax, где z = yα.
Предположим,что из βax выводится терминальная строка bw. Тогда для некоторогоправила вывода вида B → q имеется вывод S ⇒∗r zBbw ⇒r zqbw. Такимобразом [B → .q, b] также допустима для z и ситуация [A → αB.β, a] допустима для активного префикса zB. Здесь либо b может быть первым терминалом, выводимым из β, либо из β выводится e в выводе βax ⇒∗r bw итогда b равно a. Т.е.
b принадлежит F IRST (βax). Построение всех такихситуаций для данного множества ситуаций, т.е. его замыкание, делаетприведенная ниже функция closure.Система множеств допустимых LR(1)-ситуаций для всевозможныхактивных префиксов пополненной грамматики называется канонической системой множеств допустимых LR(1)-ситуаций. Алгоритм построения канонической системы множеств приведен ниже.Алгоритм 4.9. Конструирование канонической системы множеств допустимых LR(1)-ситуаций.Вход. КС-грамматика G = (N, T, P, S).Выход. Каноническая система C множеств допустимых LR(1)-ситуацийдля грамматики G.Метод. Заключается в выполнении для пополненной грамматики G0процедуры items, которая использует функции closure и goto.function closure(I){ /* I - множество ситуаций */do{for (каждой ситуации [A → α.Bβ, a] из I,каждого правила вывода B → γ из G0 ,каждого терминала b из F IRST (βa),такого, что [B → .γ, b] нет в I)добавить [B → .γ, b] к I;}while (к I можно добавить новую ситуацию);return I;}function goto(I,X){ /* I - множество ситуаций;4.4.
РАЗБОР СНИЗУ-ВВЕРХ ТИПА СДВИГ-СВЕРТКА75X - символ грамматики */Пусть J = {[A → αX.β, a] | [A → α.Xβ, a] ∈ I};return closure(J);}procedure items(G0 ){ /* G0 - пополненная грамматика */I0 = closure({[S 0 → .S, $]});C = {I0 };do{for (каждого множества ситуаций I из системы C,каждого символа грамматики X такого,что goto(I, X) не пусто и не принадлежит C)добавить goto(I, X) к системе C;}while (к C можно добавить новое множество ситуаций);}Если I – множество ситуаций, допустимых для некоторого активного префикса δ, то goto(I, X) – множество ситуаций, допустимых для активного префикса δX.Работа алгоритма построения системы C множеств допустимых LR(1)ситуаций начинается с того, что в C помещается начальное множествоситуаций I0 = closure({[S 0 → .S, $]}).
Затем с помощью функции goto вычисляются новые множества ситуаций и включаются в C. По-существу,goto(I, X) – переход конечного автомата из состояния I по символу X.Рассмотрим теперь, как по системе множеств LR(1)-ситуаций строится LR(1)-таблица, т.е. функции действий и переходов LR(1)-анализатора.Алгоритм 4.10. Построение LR(1)-таблицы.Вход.
Каноническая система C = {I0 , I1 , ... , In } множеств допустимых LR(1)-ситуаций для грамматики G.Выход. Функции Action и Goto, составляющие LR(1)-таблицу для грамматики G.Метод. Для каждого состояния i функции Action[i, a] и Goto[i, X] строятся по множеству ситуаций Ii :(1) Значения функции действия (Action) для состояния i определяются следующим образом:а) если [A → α.aβ, b] ∈ Ii (a – терминал) и goto(Ii , a) = Ij , то полагаем Action[i, a] = shift j;б) если [A → α., a] ∈ Ii , причем A 6= S 0 , то полагаем Action[i, a] =reduce A → α;в) если [S 0 → S., $] ∈ Ii , то полагаем Action[i, $] = accept.ГЛАВА 4.
СИНТАКСИЧЕСКИЙ АНАЛИЗ76(3) Значения функции переходов для состояния i определяются следующим образом: если goto(Ii , A) = Ij , то Goto[i, A] = j (здесь A –нетерминал).(4) Все входы в Action и Goto, не определенные шагами 2 и 3, полагаемравными error.(5) Начальное состояние анализатора строится из множества, содержащего ситуацию [S 0 → .S, $].Таблица на основе функций Action и Goto, полученных в результатеработы алгоритма 4.10, называется канонической LR(1)-таблицей. LR(1)анализатор, работающий с этой таблицей, называется каноническим LR(1)анализатором.Пример 4.10. Рассмотрим следующую грамматику, являющуюся пополненной для грамматики из примера 4.8:(0)(1)(2)(3)(4)(5)E0 → EE →E+TE→TT →T ∗FT →FF → idМножества ситуаций и переходы по goto для этой грамматики приведены нарис.
4.11. LR(1)-таблица для этой грамматики приведена на рис. 4.9.4.4.4LR(1)-грамматикиЕсли для КС-грамматики G функция Action, полученная в результатеработы алгоритма 4.10, не содержит неоднозначно определенных входов, то грамматика называется LR(1)-грамматикой.Язык L называется LR(1)-языком, если он может быть порожден некоторой LR(1)-грамматикой.Иногда используется другое определение LR(1)-грамматики.
Грамматика называется LR(1), если из условий1. S 0 ⇒∗r uAw ⇒r uvw,2. S 0 ⇒∗r zBx ⇒r uvy,3. F IRST (w) = F IRST (y)следует, что uAy = zBx (т.е. u = z, A = B и x = y).Согласно этому определению, если uvw и uvy – правовыводимые цепочки пополненной грамматики, у которых F IRST (w) = F IRST (y) иA → v – последнее правило, использованное в правом выводе цепочкиuvw, то правило A → v должно применяться и в правом разборе присвертке uvy к uAy. Так как A дает v независимо от w, то LR(1)-условиеозначает, что в F IRST (w) содержится информация, достаточная для определения того, что uv за один шаг выводится из uA. Поэтому никогда не4.4. РАЗБОР СНИЗУ-ВВЕРХ ТИПА СДВИГ-СВЕРТКА,>(o (@>(o (7@>(o 7@>7o 7)@>7o )@>)o LG@>(o (7@>(o 7@>7o 7)@>7o )@>7o 7)@>7o )@>)o LG@>)o LG@LG,>( o (@>(o (7@>(o (7@(,>(o 7@>7o 7)@>(o 7@>7o 7)@>7o 7)@7),>7o 7)@>7o 7)@>7o 7)@>)o LG@>)o LG@>)o LG@)),>7o )@>7o )@>7o )@,>7o 7)@>7o 7)@>7o 7)@LG77,>(o (7@>(o (7@>7o 7)@>7o )@>7o 7)@>7o )@>) o LG@>)o LG@>7o 7)@>7o )@>)o LG@7LG,>(o (7@>(o (7@>7o 7)@>7o 7)@>7o 7)@,>)o LG@>)o LG@>)o LG@Рис.
4.11:может возникнуть сомнений относительно того, как свернуть очередную правовыводимую цепочку пополненной грамматики.Можно доказать, что эти два определения эквивалентны.Если грамматика не является LR(1), то анализатор типа сдвиг-сверткапри анализе некоторой цепочки может достигнуть конфигурации, в ко-78ГЛАВА 4. СИНТАКСИЧЕСКИЙ АНАЛИЗторой он, зная содержимое магазина и следующий входной символ, неможет решить, делать ли сдвиг или свертку (конфликт сдвиг/свертка),или не может решить, какую из нескольких сверток применить (конфликт свертка/свертка).В частности, неоднозначная грамматика не может быть LR(1). Длядоказательства рассмотрим два различных правых вывода(1) S ⇒r u1 ⇒r ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
