В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 9
Текст из файла (страница 9)
Рассмотрим ДМП-автоматM = ({q0 , q1 , q2 }, {a, b, c}, {Z, a, b}, D, q0 , Z, {q2 }),у которого функция переходов определяется следующим образом:ГЛАВА 4. СИНТАКСИЧЕСКИЙ АНАЛИЗ54D(q0 , X, Y ) = (q0 , XY ), X ∈ {a, b}, Y ∈ {Z, a, b},D(q0 , c, Y ) = (q1 , Y ), Y ∈ {a, b},D(q1 , X, X) = (q1 , e), X ∈ {a, b},D(q1 , e, Z) = (q2 , e).Нетрудно показать, что этот детерминированный МП-автомат допускает языкL = {wcwR |w ∈ {a, b}+ }.К сожалению, ДМП-автоматы имеют меньшую распознавательнуюспособность, чем МП-автоматы. Доказано, в частности, что существуют КС-языки, не являющиеся детерминированными КС-языками (таковым, например, является язык из примера 4.1).Рассмотрим еще одну важную разновидность МП-автомата.Расширенным автоматом с магазинной памятью назовем семерку M =(Q, T, Γ, D, q0 , Z0 , F ), где смысл всех символов тот же, что и для обычного МП-автомата, кроме D, представляющего собой отображение конечного подмножества множества Q × (T ∪ {e}) × Γ∗ во множество конечныхподмножеств множества Q × Γ∗ .
Все остальные определения (конфигурации, такта, допустимости) для расширенного МП-автомата остаютсятакими же, как для обычного.Теорема 4.3. Пусть M = (Q, T, Γ, D, q0 , Z0 , F ) – расширенный МП-автомат.Тогда существует такой МП-автомат M 0 , что L(M 0 ) = L(M ).Расширенный МП-автомат M = (Q, T, Γ, D, q0 , Z0 , F ) называется детерминированным, если выполнены следующие условия:(1) Множество D(q, a, u) содержит не более одного элемента для любыхq ∈ Q, a ∈ T ∪ {e}, Z ∈ Γ∗ ;(2) Если D(q, a, u) 6= ∅, D(q, a, v) 6= ∅ и u 6= v, то не существует цепочкиx такой, что u = vx или v = ux;(3) Если D(q, a, u) 6= ∅, D(q, e, v) 6= ∅, то не существует цепочки x такой, что u = vx или v = ux.Теорема 4.4.
Пусть M = (Q, T, Γ, D, q0 , Z0 , F ) – расширенный ДМПавтомат. Тогда существует такой ДМП-автомат M 0 , что L(M 0 ) =L(M ).ДМП-автомат и расширенный ДМП-автомат лежат в основе рассматриваемых далее в этой главе, соответственно, LL и LR-анализаторов.4.2Преобразования КС-грамматикРассмотрим ряд преобразований, позволяющих “улучшить” видконтекстно-свободной грамматики, без изменения порождаемого ею языка.4.2. ПРЕОБРАЗОВАНИЯ КС-ГРАММАТИК55Назовем символ X ∈ (N ∪ T ) недостижимым в КС-грамматике G =(N, T, P, S), если X не появляется ни в одной выводимой цепочке этойграмматики. Иными словами, символ X является недостижимым, еслив G не существует вывода S ⇒∗ αXβ ни для каких α, β ∈ (N ∪ T )∗ .Алгоритм 4.1.
Устранение недостижимых символов.Вход. КС-грамматика G = (N, T, P, S).Выход. КС-грамматика G0 = (N 0 , T 0 , P 0 , S) без недостижимых символов, такая, что L(G0 ) = L(G).Метод. Выполнить шаги 1–4:(1) Положить V0 = {S} и i = 1.(2) Положить Vi = {X | в P есть A → αXβ и A ∈ Vi−1 } ∪ Vi−1 .(3) Если Vi 6= Vi−1 , положить i = i + 1 и перейти к шагу 2.
В противномслучае перейти к шагу 4.(4) Положить N 0 = Vi ∩ N , T 0 = Vi ∩ T . Включить в P 0 все правила изP , содержащие только символы из Vi .Назовем символ X ∈ (N ∪ T ) бесполезным в КС-грамматике G =(N, T, P, S), если в ней не существует вывода вида S ⇒∗ xXy ⇒∗ xwy,где w, x, y принадлежат T ∗ . Очевидно, что каждый недостижимый символ является бесполезным.Алгоритм 4.2. Устранение бесполезных символов.Вход. КС-грамматика G = (N, T, P, S).Выход. КС-грамматика G0 = (N 0 , T 0 , P 0 , S) без бесполезных символов, такая, что L(G0 ) = L(G).Метод. Выполнить шаги 1–5:(1) Положить N0 = ∅ и i = 1.(2) Положить Ni = {A|A → α ∈ P и α ∈ (Ni−1 ∪ T )∗ } ∪ Ni−1 .(3) Если Ni 6= Ni−1 , положить i = i+1 и перейти к шагу 2.
В противномслучае положить Ne = Ni и перейти к шагу 4.(4) Положить G1 = ((N ∩ Ne ) ∪ {S}, T, P1 , S), где P1 состоит из правилмножества P , содержащих только символы из Ne ∪ T .(5) Применив к G1 алгоритм 4.1, получить G0 = (N 0 , T 0 , P 0 , S).КС-грамматика без бесполезных символов называется приведенной.Легко видеть, что для любой КС-грамматики существует эквивалентнаяприведенная. В дальнейшем будем предполагать, что все рассматривамые грамматики – приведенные.ГЛАВА 4.
СИНТАКСИЧЕСКИЙ АНАЛИЗ564.3Предсказывающий разбор сверху-вниз4.3.1Алгоритм разбора сверху-внизПусть дана КС-грамматика G = (N, T, P, S). Рассмотрим предсказывающий разбор (или разбор сверху-вниз) для грамматики G.Основная задача предсказывающего разбора – определение правилавывода, которое нужно применить к нетерминалу. Процесс предсказывающего разбора с точки зрения построения дерева разбора проиллюстрирован на рис.
4.1.6D 66; ; ; ; <<D =D E Рис. 4.1:Фрагменты недостроенного дерева соответствуют сентенциальным формам. Вначале дерево состоит только из одной вершины, соответствующей аксиоме S. В этот момент по первому символу входной цепочкипредсказывающий анализатор должен определить правило S → X1 X2 ..., которое должно быть применено к S. Затем необходимо определитьправило, которое должно быть применено к X1 , и т.д., до тех пор, покав процессе такого построения сентенциальной формы, соответствующейлевому выводу, не будет применено правило Y → a ... . Этот процесс затем применяется для следующего самого левого нетерминального символа сентенциальной формы.На рис.
4.2 приведена структура предсказывающего анализатора, который определяет очередное правило с помощью таблицы. Такую таблицу можно построить непосредственно по грамматике.Таблично-управляемый предсказывающий анализатор имеет входную ленту, управляющее устройство (программу), таблицу анализа, магазин (стек) и выходную ленту.Входная лента содержит анализируемую строку, заканчивающуюсясимволом $ – маркером конца строки. Выходная лента содержит после-4.3.
ПРЕДСКАЗЫВАЮЩИЙ РАЗБОР СВЕРХУ-ВНИЗFZ]Zabg;<=<oh^DE57Ijh]jZffZij_^kdZau\Zxs_]hZgZebaZlhjZ<uoh^LZ[ebpZZgZebaZlhjZРис. 4.2:довательность примененных правил вывода.Таблица анализа – это двумерный массив M [A, a], где A – нетерминал, и a – терминал или символ $. Значением M [A, a] может быть некоторое правило грамматики или элемент “ошибка”.Магазин может содержать последовательность символов грамматики с $ на дне. В начальный момент магазин содержит только начальныйсимвол грамматики на верхушке и $ на дне.Анализатор работает следующим образом.
Вначале анализатор находится в конфигурации, в которой магазин содержит S$, на входной ленте w$ (w – анализируемая цепочка), выходная лента пуста. На каждомтакте анализатор рассматривает X – символ на верхушке магазина и a– текущий входной символ. Эти два символа определяют действия анализатора. Имеются следующие возможности.1. Если X = a = $, анализатор останавливается, сообщает об успешном окончании разбора и выдает содержимое выходной ленты.2.
Если X = a 6= $, анализатор удаляет X из магазина и продвигаетуказатель входа на следующий входной символ.3. Если X – терминал, и X 6= a, то анализатор останавливается и сообщает о том, что входная цепочка не принадлежит языку.4. Если X – нетерминал, анализатор заглядывает в таблицу M [X, a].Возможны два случая:а) Значением M [X, a] является правило для X. В этом случае анализатор заменяет X на верхушке магазина на правую часть данногоправила, а само правило помещает на выходную ленту. Указательвхода не передвигается.б) Значением M [X, a] является “ошибка”.
В этом случае анализаторостанавливается и сообщает о том, что входная цепочка не принадлежит языку.Работа анализатора может быть задана следующей программой:ГЛАВА 4. СИНТАКСИЧЕСКИЙ АНАЛИЗ58do{X=верхний символ магазина;if (X - терминал || X=="$")if (X==InSym){удалить X из магазина;InSym=очередной символ;}else error();else /*X - нетерминал*/if (M[X,InSym]=="X->Y1Y2...Yk"){удалить X из магазина;поместить Yk,Yk-1,...Y1 в магазин(Y1 на верхушку);вывести правило X->Y1Y2...Yk;}else error(); /*вход таблицы M пуст*/}while (X!=$) /*магазин пуст*/Пример 4.3. Рассмотрим грамматику арифметическихG = ({E, E 0 , T, T 0 , F }, {id, +, ∗, (, )}, P, E) с правилами:E → T E0E 0 → +T E 0E0 → eT → FT0выраженийT 0 → ∗F T 0T0 → eF → (E)F → idТаблица предсказывающего анализатора для этой грамматики приведена нарис. 4.3.
Пустые клетки таблицы соответствуют элементу “ошибка”.НетерминалEE0TT0FidE → T E0Входной символ*(E → T E0+E 0 → +T E 0T → FT$E0 → e E0 → e0T → FTT0 → e)0T 0 → ∗F T 0F → idT0 → e T0 → eF → (E)Рис. 4.3:При разборе входной цепочки id + id ∗ id$ анализатор совершает последовательность шагов, изображенную на рис. 4.4. Заметим, что анализатор осуществляет в точности левый вывод.
Если за уже просмотренными входными символами поместить символы грамматики в магазине, то можно получить в точности левые сентенциальные формы вывода. Дерево разбора для этой цепочкиприведено на рис. 4.5.4.3. ПРЕДСКАЗЫВАЮЩИЙ РАЗБОР СВЕРХУ-ВНИЗМагазинE$T E 0$F T 0E 0 $id T 0 E 0 $T 0E 0 $E0$+T E 0 $T E 0$F T 0E 0 $id T 0 E 0 $T 0E 0 $∗F 0 T 0 E 0 $F T 0E 0 $id T 0 E 0 $T 0E 0 $E0$$Входid + id ∗ id$id + id ∗ id$id + id ∗ id$id + id ∗ id$+id ∗ id$+id ∗ id$+id ∗ id$id ∗ id$id ∗ id$id ∗ id$∗id$∗id$id$id$$$$59ВыходE → T E0T → FT0F → idT0 → eE 0 → +T ET → FT0F → idT 0 → ∗F T 0F → idT0 → eE0 → eРис. 4.4:(7)7LGH(7)LG(7H)7LGHРис.
4.5:4.3.2Функции F IRST и F OLLOWПри построении таблицы предсказывающего анализатора нам потребуются две функции – F IRST и F OLLOW .Пусть G = (N, T, P, S) – КС-грамматика. Для α – произвольной цепочки, состоящей из символов грамматики, определим F IRST (α) какмножество терминалов, с которых начинаются строки, выводимые из α.Если α ⇒∗ e, то e также принадлежит F IRST (α).60ГЛАВА 4. СИНТАКСИЧЕСКИЙ АНАЛИЗОпределим F OLLOW (A) для нетерминала A как множество терминалов a, которые могут появиться непосредственно справа от A в некоторой сентенциальной форме грамматики, т.е. множество терминаловa таких, что существует вывод вида S ⇒∗ αAaβ для некоторых α, β ∈(N ∪ T )∗ . Заметим, что между A и a в процессе вывода могут находитьсянетерминальные символы, из которых выводится e. Если A может бытьсамым правым символом некоторой сентенциальной формы, то $ такжепринадлежит F OLLOW (A).Рассмотрим алгоритмы вычисления функции F IRST .Алгоритм 4.3.
Вычисление F IRST для символов грамматики.Вход. КС-грамматика G = (N, T, P, S).Выход. Множество F IRST (X) для каждого символа X ∈ (N ∪ T ).Метод. Выполнить шаги 1–3:(1) Если X – терминал, то положить F IRST (X) = {X};если X – нетерминал, положить F IRST (X) = ∅.(2) Если в P имеется правило X → e, то добавить e к F IRST (X).(3) Пока ни к какому множеству F IRST (X) нельзя уже будет добавить новые элементы, выполнять:если X – нетерминал и имеется правило вывода X → Y1 Y2 ... Yk ,то включить a в F IRST (X), если a ∈ F IRST (Yi ) для некоторого i,1 6 i 6 k, и e принадлежит всем F IRST (Y1 ), ...
, F IRST (Yi−1 ), тоесть Y1 ... Yi−1 ⇒∗ e. Если e принадлежит F IRST (Yj ) для всех j =1, 2, ... , k, то добавить e к F IRST (X).Алгоритм 4.4. Вычисление F IRST для цепочки.Вход. КС-грамматика G = (N, T, P, S).Выход. Множество F IRST (X1 X2 ... Xn ), Xi ∈ (N ∪ T ).Метод. Выполнить шаги 1–3:(1) При помощи предыдущего алгоритма вычислить F IRST (X) длякаждого X ∈ (N ∪ T ).(2) Положить F IRST (X1X2 ... Xn ) = ∅.(3) Добавить к F IRST (X1X2 ... Xn ) все не e-элементы из F IRST (X1 ).Добавить к нему также все не e-элементы из F IRST (X2 ), если e ∈F IRST (X1 ), не e-элементы из F IRST (X3 ), если e принадлежит какF IRST (X1 ), так и F IRST (X2 ), и т.д.
Наконец, добавить цепочку eк F IRST (X1 X2 ... Xn ), если e ∈ F IRST (Xi ) для всех i.Рассмотрим алгоритм вычисления функции F OLLOW .4.3. ПРЕДСКАЗЫВАЮЩИЙ РАЗБОР СВЕРХУ-ВНИЗ61Алгоритм 4.5. Вычисление F OLLOW для нетерминалов грамматики.Вход. КС-грамматика G = (N, T, P, S).Выход. Множество F OLLOW (X) для каждого символа X ∈ N .Метод.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
