В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 22
Текст из файла (страница 22)
Синтаксический анализШаг. Пусть анализатор осуществляет l = n + 1 шагов. Первые n шаговдают (I0 , w$, e) ⊢n (I0 X1 I1 . . . Xj Ij Xj+1 Ij+1 . . . Xm Im , x′ $, π ′ ).′По предположению индукции X1 . . . Xj . . . Xm x′ ⇒ πr w, затем осуществляется последний шаг. Пусть это shif t. Тогда:(I0 X1 I1 . . . Xj Ij Xj+1 Ij+1 . . . Xm Im , x′ $, π ′ ) =(I0 X1 I1 . . . Xj Ij Xj+1 Ij+1 . . . Xm Im , Xm+1 x$, π ′ ) ⊢(I0 X1 I1 . . .
Xj Ij Xj+1 Ij+1 . . . Xm Im Xm+1 , x$, π ′ ).′X1 . . . Xj . . . Xm Xm+1 x ⇒ πr w,поскольку′x′ = Xm+1 x, X1 . . . Xj . . . Xm Xm+1 x = X1 Xj . . . Xm Xm+1 x′ ⇒ πr wпо предположению индукции.Пусть это reduce. За первые n шагов достигнута конфигурация (I0 X1 I1 . . .′. . . Xj Ij Xj+1 Ij+1 . . .
Xm Im , x′ $, π ) . Затем совершается последний такт —свертка по i-му правилу. По построению Im = DF AG (X1 . . . Xj . . . Xm ) и существует LR(1)-ситуация[A → Y1 Y2 . . . Yp ., u′ ] ∈ Im , u′ ∈ F IRST (x′ ) (либо $),A → Y1 Y2 . . . Yp ∈ P , Y1 Y2 . . . Yp = Xm−p+1 . . . Xm .Тогда(I0 X1 I1 . . . Xj Ij Xj+1 Ij+1 . .
. Xm Im , Xm+1 , x$, π ′ ) == (I0 X1 I1 . . . Xm−p Im−p Y1 Im−p+1 Y2 . . . Yp Im , x′ $, π ′ ) ⊢′′′⊢ (I0 X1 I1 . . . Xm−p Im−p AIm−p+1 , x $, iπ ),′где Im−p+1 = Goto(Im−p , A).′′Кроме того, X1 X2 . . . Xm−p Ax′ ⇒ iπr w , поскольку X1 X2 . . . Xm−p Ax ⇒′⇒ ir X1 X2 . . . Xm−p Y1 Y2 . . . Y px′ = X1 X2 . . . Xm−p Xm−p+1 . . . Xm−1 Xm x′ ⇒ πr wввиду предположения индукции. В частности, при α = S , x = e получаем, чтоесли (I0 , w$, e) ⊢∗ (I0 SI , $, π), то S ⇒ πr w.4.5.6. LR(k)-грамматики. Если для КС-грамматики G функция Action,полученная в результате работы алгоритма 4.12, не содержит неоднозначноопределенных входов, то грамматика называется LR(1)-грамматикой.Язык L называется LR(1)-языком, если он может быть порожден некоторой LR(1)-грамматикой.Иногда используется другое определение LR(1)-грамматики. Грамматиканазывается LR(1), если из условий1) S ′ ⇒ ∗r uAw ⇒ r uvw;2) S ′ ⇒ ∗r zBx ⇒ r uvy ;3) F IRST (w) = F IRST (y)следует, что uAy = zBx (т. е.
u = z , A = B и x = y ).4.5. Разбор снизу-вверх типа сдвиг-свертка107В случае произвольного k > 0 определение таково.Определение 4.4. Пусть G = (N , Σ, P , S) — КС-грамматика и G′ == (N ′ , Σ, P ′ , S ′ ) — полученная из нее пополненная грамматика. ГрамматикуG будем называть LR(k)-грамматикой для k > 0, если из условий1) S ′ ⇒ ∗G′r αAω ⇒ G′r αβω ;2) S ′ ⇒ ∗G′r γBx ⇒ G′r αβy ;3) F IRSTk (ω) = F IRSTk (y)следует, что αAy = γBx (т. е. α = γ , A = B и x = y).Грамматика G называется LR-грамматикой, если она LR(k )-грамматикадля некоторого k > 0.Интуитивно это определение говорит о том, что если αβw и αβy –правовыводимые цепочки пополненной грамматики, у которых F IRSTk (w) == F IRSTk (y), и A → β – последнее правило, использованное в правом выводецепочки αβw, то правило A → β должно использоваться также в правомразборе при свертке αβy к αAy . Так как A дает β независимо от w,то LR(k )-условие говорит о том, что в F IRSTk (w) содержится информация,достаточная для определения того, что αβ за один шаг выводится из αA.Поэтому никогда не может возникнуть сомнений относительно того, как свернуть очередную правовыводимую цепочку пополненной грамматики.
Крометого, работая с LR(k )-грамматикой, мы всегда знаем, допустить ли даннуювходную цепочку или продолжать разбор.Пример 4.15. Рассмотрим грамматику G с правиламиS → Sa | a.Согласно определению, G не LR(0)-грамматика, так как из трех условий:1)S’ ⇒ 0G′r S ′ ⇒ G′r S ;2)S ′ ⇒ G′r S ⇒ G′r Sa;3)F IRST0 (e) = F IRST0 (a) = eне следует, что S ′ a = S . Применяя определение к этой ситуации, имеем α = e, β = S ,ω = e, γ = e, A = S ′ , B = S , x = e и y = a.
Проблема здесь заключается в том,что нельзя установить, является ли S основой правовыводимой цепочки Sa, не видясимвола, стоящего после S (т. е. наблюдая «нулевое» количество символов). Интуитивно представляется, что G не должна быть LR(0)-грамматикой, и она не будет ею,если пользоваться первым определением. Это определение мы и будем использоватьдалее.Пример 4.16. Пусть G - леволинейная грамматика с правилами:S → Ab | Bc;A → Aa | e;B → Ba | e.108Глава 4. Синтаксический анализЗаметим, что G не является LR(k )-грамматикой ни для какого k .Допустим, что G — LR(k )-грамматика.
Рассмотрим два правых вывода в пополненной грамматике G′ :S ′ ⇒ r S ⇒ ∗r Aak b ⇒ r ak bиS ′ ⇒ r S ⇒ ∗r Bak c ⇒ r ak c.Эти два вывода удовлетворяют условию из определения LR(k )-грамматики приα = e, β = e, ω = ak b, γ = e и y = ak c. Но так как заключение неверно, т. е. A 6= B ,то G — не LR(k )-грамматика. Более того, так как LR(k)-условие нарушается длявсех k , то G — не LR-грамматика.Если грамматика не является LR(1), то анализатор типа сдвиг–сверткапри анализе некоторой цепочки может достигнуть конфигурации, в которой он, зная содержимое магазина и следующий входной символ, не может решить, делать ли сдвиг или свертку (конфликт сдвиг–свертка), илине может решить, какую из нескольких сверток применить (конфликтсвертка–свертка).В частности, неоднозначная грамматика не может быть 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=6= vm−i .Пример 4.17. Рассмотрим еще раз грамматику условных операторов:S → if E then S | if E then S else S | a;E → 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 | U;M → if E then M else M | a;U → if E then S | if E then M else U ;E → b.Основная разница между LL(1)- и LR(1)-грамматиками заключаетсяв следующем.
Чтобы грамматика была LR(1)-грамматикой, необходимо распознавать вхождение правой части правила вывода, просмотрев всё, что выведено из этой правой части, и текущий символ входной цепочки. Это требованиесущественно менее строгое, чем требование для LL(1)-грамматики, когда4.5. Разбор снизу-вверх типа сдвиг-свертка109необходимо определить применимое правило, видя только первый символ,выводимый из его правой части. Таким образом, класс LL(1)-грамматик естьсобственный подкласс класса LR(1)-грамматик.Справедливы также следующие утверждения [2].Теорема 4.10. Каждый LR(1)-язык является детерминированным КСязыком.Теорема 4.11. Если L — детерминированный КС-язык, то существуетLR(1)-грамматика, порождающая L.Теорема 4.12. Для любой LR(k )-грамматики при k > 1 существуетэквивалентная ей LR(k − 1)-грамматика.Доказано, что проблема определения, порождает ли грамматика LR-язык,является алгоритмически неразрешимой.4.5.7.
Восстановление процесса анализа после синтаксических ошибок. Одним из простейших методов восстановления после ошибки приLR(1)-анализе является следующий. При синтаксической ошибке просматриваем магазин от верхушки, пока не найдем состояние s с переходомна выделенный нетерминал A. Затем сканируются входные символы, покане будет найден такой, который допусти́м после A.
В этом случае на верхушкумагазина помещается состояние Goto[s, A] и разбор продолжается. Для нетерминала A возможны несколько таких вариантов. Обычно A — это нетерминал,представляющий одну из основных конструкций языка, например, оператор.При более детальной проработке реакции на ошибки можно в каждойпустой клетке анализатора поставить обращение к своей подпрограмме. Такаяподпрограмма может вставлять или удалять входные символы или символымагазина, менять порядок входных символов.4.5.8.
Варианты LR-анализаторов. Построенные таблицы для LR(1)анализатора зачастую получаются довольно большими. Поэтому при практической реализации используются различные методы их сжатия. С другойстороны, часто оказывается, что при построении синтаксического анализаторатипа «сдвиг–свертка» достаточно более простых методов. Некоторые из этихметодов базируются на основе LR(1)-анализаторов.Одним из способов такого упрощения является LR(0)-анализ — частныйслучай LR-анализа, когда ни при построении таблиц, ни при анализе не учитывается аванцепочка.Еще одним вариантом LR-анализа являются так называемые SLR(1)анализаторы (Simple LR(1)). Они строятся по следующей схеме.
Пусть C == {I0 , I1 , . . . , In } — набор множеств допустимых LR(0)-ситуаций. Состоянияанализатора соответствуют Ii . Функции действий и переходов анализатораопределяются следующим образом.110Глава 4. Синтаксический анализ1. Если [A → u.av] ∈ Ii и goto(Ii , a) = Ij , то определим Action[i, a] == shift j .2. Если [A → u.] ∈ Ii , то, для всех a ∈ F OLLOW (A), A 6= S ′ , определимAction[i, a] = reduce A → u3.
Если [S ′ →S.] ∈ Ii , то определим Action[i, $] = accept.4. Если goto(Ii , A) = Ij , где A ∈ N , то определимGoto[i, A] = j .5. Остальные входы для функций Action и Goto определим как error.6. Начальное состояние соответствует множеству ситуаций, содержащемуситуацию [S ′ → .S].Распространенным вариантом LR(1)-анализа является также LALR(1)анализ. Он основан на объединении (слиянии) некоторых таблиц. Назовемядром множества LR(1)-ситуаций множество их первых компонент (т. е.во множестве ситуаций не учитываются аванцепочки).
Объединим все множества ситуаций с одинаковыми ядрами, а в качестве аванцепочек возьмемобъединение аванцепочек. Функции Action и Goto строятся очевидным образом. Если функция Action таким образом построенного анализатора неимеет конфликтов, то он называется LALR(1)-анализатором (LookAheadLR(1)).Если грамматика является LR(1), то в таблицах LALR(1)-анализаторамогут появиться конфликты типы свертка/свертка (если одно из объединяемых состояний имело ситуации [A → α, a] и [B → β , b], а другое —[A → α, b] и [B → β , a], то в LALR(1) появятся ситуации [A → α, {a, b}]и [B → β , {b, a}]).
Конфликты типа сдвиг/свертка появиться не могут, поскольку аванцепочка для сдвига во внимание не принимается.Глава 5ЭЛЕМЕНТЫ ТЕОРИИ ПЕРЕВОДАДо сих пор мы рассматривали процесс синтаксического анализа толькокак процесс анализа допустимости входной цепочки. Однако в компиляторесинтаксический анализ служит основой еще одного важного шага — построения дерева синтаксического анализа. В примерах 4.3 и 4.8 в процессесинтаксического анализа в качестве выхода выдавалась последовательностьпримененных правил, на основе которой и может быть построено дерево.Построение дерева синтаксического анализа является простейшим частнымслучаем перевода — процесса преобразования некоторой входной цепочкив некоторую выходную.Определение 5.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
