В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов, страница 10

Построим грамматику G, порождающую язык L.Пусть G = ({ [qZr] | q, r ∈ Q, Z ∈ Γ} ∪ {S}, T, P, S), где P состоит изправил следующего вида:1. Если (r, X1 ... Xk ) ∈ D(q, a, Z), k > 1, то[qZsk ] → a[rX1 s1 ][s1 X2 s2 ] ... [sk−1 Xk sk ]для любого набора s1 , s2 , ... , sk состояний из Q;2. Если (r, e) ∈ D(q, a, Z), то [qZr] → a ∈ P , a ∈ T ∪ {e};3. S → [q0 Z0 q] ∈ P для всех q ∈ Q.Нетерминалы и правила вывода грамматики определены так, что работе автомата M при обработке цепочки w соответствует левостороннийвывод w в грамматике G.Индукцией по числу шагов вывода в G или числу тактов M нетруднопоказать, что (q, w, A) `+ (p, e, e) тогда и только тогда, когда [qAp] ⇒+ w.Тогда, если w ∈ L(G), то S ⇒ [q0 Z0 q] ⇒+ w для некоторого q ∈ Q.Следовательно, (q0 , w, Z0 ) `+ (q, e, e) и поэтому w ∈ L.

Аналогично, еслиw ∈ L, то (q0 , w, Z0 ) `+ (q, e, e). Значит, S ⇒ [q0 Z0 q] ⇒+ w, и поэтомуw ∈ L(G).МП-автомат M = (Q, T, Γ, D, q0 , Z0 , F ) называется детерминированным (ДМП-автоматом), если выполнены следующие два условия:(1) Множество D(q, a, Z) содержит не более одного элемента для любых q ∈ Q, a ∈ T ∪ {e}, Z ∈ Γ;(2) Если D(q, e, Z) 6= ∅, то D(q, a, Z) = ∅ для всех a ∈ T .Язык, допускаемый ДМП-автоматом, называется детерминированным КС-языком.Так как функция переходов ДМП-автомата содержит не более одного элемента для любой тройки аргументов, мы будем пользоваться записью D(q, a, Z) = (p, u) для обозначения D(q, a, Z) = {(p, u)}.Пример 4.2.

Рассмотрим ДМП-автомат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Таблица предсказывающего анализатора для этой грамматики приведена нарис.