В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 13
Текст из файла (страница 13)
⇒r un ⇒r w, и(2) S ⇒r v1 ⇒r ... ⇒r vm ⇒r w.Нетрудно заметить, что LR(1)-условие (согласно второму определениюLR(1)-грамматики) нарушается для наименьшего из чисел i, для которых un−i 6= vm−i .Пример 4.11. Рассмотрим вновь грамматику условных операторов:S → if E then S | if E then S else S | aE→bЕсли анализатор типа сдвиг-свертка находится в конфигурации, такой чтонеобработанная часть входной цепочки имеет вид else ...
$, а в магазине находится ... if E then S, то нельзя определить, является ли if E then S основой, вне зависимости от того, что лежит в магазине ниже. Это конфликт сдвиг/свертка. Взависимости от того, что следует на входе за else, правильной может быть свертка по S → if E then S или сдвиг else, а затем разбор другого S и завершениеосновы if E then S else S.
Таким образом нельзя сказать, нужно ли в этом случае делать сдвиг или свертку, так что грамматика не является LR(1).Эта грамматика может быть преобразована к LR(1)-виду следующим образом:S→M |UM → if E then M else M | aU → if E then S | if E then M else UE→bОсновная разница между LL(1)- и LR(1)-грамматиками заключаетсяв следующем. Чтобы грамматика была LR(1), необходимо распознаватьвхождение правой части правила вывода, просмотрев все, что выведеноиз этой правой части и текущий символ входной цепочки.
Это требование существенно менее строгое, чем требование для LL(1)-грамматики,когда необходимо определить применимое правило, видя только первый символ, выводимый из его правой части. Таким образом, класс LL(1)грамматик является собственным подклассом класса LR(1)-грамматик.Справедливы также следующие утверждения [2].Теорема 4.5. Каждый LR(1)-язык является детерминированным КСязыком.Теорема 4.6. Если L – детерминированный КС-язык, то существуетLR(1)-грамматика, порождающая L.4.4.
РАЗБОР СНИЗУ-ВВЕРХ ТИПА СДВИГ-СВЕРТКА4.4.579Восстановление после синтаксических ошибокОдним из простейших методов восстановления после ошибки при LR(1)анализе является следующий. При синтаксической ошибке просматриваем магазин от верхушки, пока не найдем состояние s с переходом навыделенный нетерминал A. Затем сканируются входные символы, пока не будет найден такой, который допустим после A. В этом случае наверхушку магазина помещается состояние Goto[s, A] и разбор продолжается. Для нетерминала A может иметься несколько таких вариантов.Обычно A – это нетерминал, представляющий одну из основных конструкций языка, например оператор.При более детальной проработке реакции на ошибки можно в каждой пустой клетке анализатора поставить обращение к своей подпрограмме.
Такая подпрограмма может вставлять или удалять входные символы или символы магазина, менять порядок входных символов.4.4.6Варианты LR-анализаторовЧасто построенные таблицы для LR(1)-анализатора оказываются довольно большими. Поэтому при практической реализации используются различные методы их сжатия. С другой стороны, часто оказывается, чтопри построении для языка синтаксического анализатора типа “сдвигсвертка” достаточно более простых методов. Некоторые из этих методовбазируются на основе LR(1)-анализаторов.Одним из способов такого упрощения является LR(0)-анализ – частный случая LR-анализа, когда ни при построении таблиц, ни при анализе не учитывается аванцепочка.Еще одним вариантом LR-анализа являются так называемые SLR(1)анализаторы (Simple LR(1)). Они строятся следующим образом.
ПустьC = {I0 , I1 , ... , In } – набор множеств допустимых LR(0)-ситуаций. Состояния анализатора соответствуют Ii . Функции действий и переходованализатора определяются следующим образом.1. Если [A → u.av] ∈ Ii и goto(Ii , a) = Ij , то определим Action[i, a] =shift j.2. Если [A → u.] ∈ Ii , то определим Action[i, a] = reduce A → u для всехa ∈ F OLLOW (A), A 6= S 0 .3. Если [S 0 → S.] ∈ Ii , то определим Action[i, $] = accept.4. Если goto(Ii , A) = Ij , где A ∈ N , то определим Goto[i, A] = j.5. Остальные входы для функций Action и Goto определим как error.6. Начальное состояние соответствует множеству ситуаций, содержащему ситуацию [S 0 → .S].80ГЛАВА 4.
СИНТАКСИЧЕСКИЙ АНАЛИЗРаспространенным вариантом LR(1)-анализа является также LALR(1)анализ. Он основан на объединении (слиянии) некоторых таблиц. Назовем ядром множества LR(1)-ситуаций множество их первых компонент(т.е. во множестве ситуаций не учитываются аванцепочки). Объединимвсе множества ситуаций с одинаковыми ядрами, а в качестве аванцепочек возьмем объединение аванцепочек. Функции Action и Goto строятся очевидным образом.
Если функция Action таким образом построенного анализатора не имеет конфликтов, то он называется LALR(1)анализатором (LookAhead LR(1)).Глава 5Элементы теории переводаДо сих пор мы рассматривали процесс синтаксического анализа только как процесс анализа допустимости входной цепочки. Однако, в компиляторе синтаксический анализ служит основой еще одного важногошага – построения дерева синтаксического анализа.
В примерах 4.3 и4.8 предыдущей главы в процессе синтаксического анализа в качествевыхода выдавалась последовательность примененных правил, на основе которой и может быть построено дерево. Построение дерева синтаксического анализа является простейшим частным случаем перевода –процесса преобразования некоторой входной цепочки в некоторую выходную.Определение. Пусть T – входной алфавит, а Π – выходной алфавит.Переводом (или трансляцией) с языка L1 ⊆ T ∗ на язык L2 ⊆ Π∗ называется отображение τ : L1 → L2 . Если y = τ (x), то цепочка y называется выходом для цепочки x.Мы рассмотрим несколько формализмов для определения переводов:преобразователи с магазинной памятью, схемы синтаксически управляемого перевода и атрибутные грамматики.5.1Преобразователи с магазинной памятьюРассмотрим важный класс абстрактных устройств, называемых преобразователями с магазинной памятью.
Эти преобразователи получаютсяиз автоматов с магазинной памятью, если к ним добавить выход и позволить на каждом шаге выдавать выходную цепочку.Преобразователем с магазинной памятью (МП-преобразователем)называется восьмерка P = (Q, T, Γ, Π, D, q0 , Z0 , F ), где все символы имеют тот же смысл, что и в определении МП-автомата, за исключениемтого, что Π – конечный выходной алфавит, а D – отображение множе81ГЛАВА 5. ЭЛЕМЕНТЫ ТЕОРИИ ПЕРЕВОДА82ства Q × (T ∪ {e}) × Γ в множество конечных подмножеств множестваQ × Γ∗ × Π∗ .Определим конфигурацию преобразователя P как четверку (q, x, u, y),где q ∈ Q – состояние, x ∈ T ∗ – цепочка на входной ленте, u ∈ Γ∗ – содержимое магазина, y ∈ Π∗ – цепочка на выходной ленте, выданная вплотьдо настоящего момента.Если множество D(q, a, Z) содержит элемент (r, u, z), то будем писать(q, ax, Zw, y) ` (r, x, uw, yz) для любых x ∈ T ∗ , w ∈ Γ∗ и y ∈ Π∗ .
Рефлексивнотранзитивное замыкание отношения ` будем обозначать `∗ .Цепочку y назовем выходом для x, если (q0 , x, Z0 , e) `∗ (q, e, u, y) длянекоторых q ∈ F и u ∈ Γ∗ . Переводом (или трансляцией), определяемымМП-преобразователем P (обозначается τ (P )), назовем множество{(x, y) | (q0 , x, Z0 , e) `∗ (q, e, u, y) для некоторых q ∈ F и u ∈ Γ∗ }Будем говорить, что МП-преобразователь P является детерминированным (ДМП-преобразователем), если выполняются следующие условия:1) для всех q ∈ Q, a ∈ T ∪ {e} и Z ∈ Γ множество D(q, a, Z) содержитне более одного элемента,2) если D(q, e, Z) 6= ∅, то D(q, a, Z) = ∅ для всех a ∈ T .Пример 5.1. Рассмотрим перевод τ , отображающий каждую цепочкуx ∈ {a, b}∗ $, в которой число вхождений символа a равно числу вхождений символа b, в цепочку y = (ab)n , где n – число вхождений a или b в цепочку x.
Например, τ (abbaab$) = ababab.ЭтотпереводможетбытьреализованДМП-преобразователемP = ({q0 , qf }, {a, b, $}, {Z, a, b}, {a, b}, D, q0 , Z, {qf }) c функцией переходов:D(q0 , X, Z) = {(q0 , XZ, e)}, X ∈ {a, b},D(q0 , $, Z) = {(qf , Z, e)},D(q0 , X, X) = {(q0 , XX, e)}, X ∈ {a, b},D(q0 , X, Y ) = {(q0 , e, ab)}, X ∈ {a, b}, Y ∈ {a, b}, X 6= Y .5.2Синтаксически управляемый переводДругим формализмом, используемым для определения переводов, является схема синтаксически управляемого перевода.
Фактически, такая схема представляет собой КС-грамматику, в которой к каждому правилу добавлен элемент перевода. Всякий раз, когда правило участвуетв выводе входной цепочки, с помощью элемента перевода вычисляетсячасть выходной цепочки, соответствующая части входной цепочки, порожденной этим правилом.5.2. СИНТАКСИЧЕСКИ УПРАВЛЯЕМЫЙ ПЕРЕВОД5.2.183Схемы синтаксически управляемого переводаОпределение. Cхемой синтаксически управляемого перевода (или трансляции, сокращенно: СУ-схемой) называется пятерка T r = (N, T, Π, R, S),где(1) N – конечное множество нетерминальных символов;(2) T – конечный входной алфавит;(3) Π – конечный выходной алфавит;(4) R – конечное множество правил перевода видаA → u, vгде u ∈ (N ∪T )∗ , v ∈ (N ∪Π)∗ и вхождения нетерминалов в цепочку vобразуют перестановку вхождений нетерминалов в цепочку u, такчто каждому вхождению нетерминала B в цепочку u соответствует некоторое вхождение этого же нетерминала в цепочку v; еслинетерминал B встречается более одного раза, для указания соответствия используются верхние целочисленные индексы;(5) S – начальный символ, выделенный нетерминал из N .Определим выводимую пару в схеме T r следующим образом:(1) (S, S) – выводимая пара, в которой символы S соответствуют другдругу;(2) если (xAy, x0 Ay 0 ) – выводимая пара, в цепочках которой вхождения A соответствуют друг другу, и A → u, v – правило из R, то(xuy, x0 vy 0 ) – выводимая пара.
Для обозначения такого вывода одной пары из другой будем пользоваться обозначением ⇒: (xAy, x0 Ay 0 ) ⇒(xuy, x0 vy 0 ). Рефлексивно-транзитивное замыкание отношение ⇒обозначим ⇒∗ .Переводом τ (T r), определяемым СУ-схемой T r, назовем множествопар{(x, y) | (S, S) ⇒∗ (x, y), x ∈ T ∗ , y ∈ Π∗ }Если через P обозначить множество входных правил вывода всех правил перевода, то G = (N, T, P, S) будет входной грамматикой для T r.СУ-схема T r = (N, T, Π, R, S) называется простой, если для каждогоправила A → u, v из R соответствующие друг другу вхождения нетерминалов встречаются в u и v в одном и том же порядке.Перевод, определяемый простой СУ-схемой, называется простым синтаксически управляемым переводом (простым СУ-переводом).ГЛАВА 5. ЭЛЕМЕНТЫ ТЕОРИИ ПЕРЕВОДА84Пример 5.2. Перевод арифметических выражений в ПОЛИЗ (польскую инверсную запись) можно осуществить простой СУ-схемой с правиламиE → E + T,E → T,T → T ∗ F,T → F,F → id,F → (E),ET +TTF+FidEНайдем выход схемы для входа id∗(id+id).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
