В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1134643), страница 14
Текст из файла (страница 14)
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 ... ⇒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 ∈ Π∗ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
