В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1134643), страница 15
Текст из файла (страница 15)
Рефлексивнотранзитивное замыкание отношения ` будем обозначать `∗ .Цепочку 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).
Нетрудно видеть, что существуетпоследовательность шагов вывода(E, E) ⇒ (T, T ) ⇒ (T ∗ F, T F ∗) ⇒ (F ∗ F, F F ∗) ⇒ (id ∗ F, id F ∗) ⇒ (id ∗(E), id E∗) ⇒ (id ∗ (E + T ), id E T + ∗) ⇒ (id ∗ (T + T ), id T T + ∗) ⇒ (id ∗ (F +T ), id F T + ∗) ⇒ (id ∗ (id + T ), id id T + ∗) ⇒ (id ∗ (id + F ), id id F + ∗ ) ⇒ (id ∗(id + id), id id id + ∗),переводящая эту цепочку в цепочку id id id + ∗.Рассмотрим связь между переводами, определяемыми СУ-схемами иосуществляемыми МП-преобразователями [2].Теорема 5.1.
Пусть P – МП-преобразователь. Существует такая простая СУ-схема T r, что τ (T r) = τ (P ).Теорема 5.2. Пусть T r – простая СУ-схема. Существует такой МПпреобразователь P, что τ (P ) = τ (T r).Таким образом, класс переводов, определяемых магазинными преобразователями, совпадает с классом простых СУ-переводов.Рассмотрим теперь связь между СУ-переводами и детерминированными МП-преобразователями, выполняющими нисходящий или восходящий разбор [2].Теорема 5.3. Пусть T r = (N, T, Π, R, S) – простая СУ-схема, входнойграмматикой которой служит LL(1)-грамматика.
Тогда перевод{x$, y)|(x, y) ∈ τ (T r)} можно осуществить детерминированным МПпреобразователем.Существуют простые СУ-схемы, имеющие в качестве входных грамматик LR(1)-грамматики и не реализуемые ни на каком ДМП-преобразователе.Пример 5.3. Рассмотрим простую СУ-схему с правиламиS → Sa,S → Sb,S → e,aSabSbeВходная грамматика является LR(1)-грамматикой, но не существует ДМПпреобразователя, определяющего перевод {(x$, y)|(x, y) ∈ τ (T r)}.5.2. СИНТАКСИЧЕСКИ УПРАВЛЯЕМЫЙ ПЕРЕВОД85Назовем СУ-схему T r = (N, T, Π, R, S) постфиксной, если каждоеправило из R имеет вид A → u, v, где v ∈ N ∗ Π∗ .
Иными словами, каждый элемент перевода представляет собой цепочку из нетерминалов, закоторыми следует цепочка выходных символов.Теорема 5.4. Пусть T r – простая постфиксная СУ-схема, входная грамматика для которой является LR(1). Тогда перевод{(x$, y)|(x, y) ∈ τ (T r)}можно осуществить детерминированным МП-преобразователем.5.2.2Обобщенные схемы синтаксически управляемого переводаРасширим определение СУ-схемы, с тем чтобы выполнять более широкий класс переводов.
Во-первых, позволим иметь в каждой вершине дерева разбора несколько переводов. Как и в обычной СУ-схеме, каждыйперевод зависит от прямых потомков соответствующей вершины дерева. Во-вторых, позволим элементам перевода быть произвольными цепочками выходных символов и символов, представляющих переводы впотомках. Таким образом, символы перевода могут повторяться или вообще отсутствовать.Определение. Обобщенной схемой синтаксически управляемого перевода (или трансляции, сокращенно: OСУ-схемой) называется шестерка T r = (N, T, Π, Γ, R, S), где все символы имеют тот же смысл, что идля СУ-схемы, за исключением того, что(1) Γ – конечное множество символов перевода вида Ai , где A ∈ N и i –целое число;(2) R – конечное множество правил перевода видаA → u, A1 = v1 , ...
, Am = vm ,удовлетворяющих следующим условиям:(а) Aj ∈ Γ для 1 6 j 6 m,(б) каждый символ, входящий в v1 , . . . , vm , либо принадлежит Π,либо является Bk ∈ Γ, где B входит в u,(в) если u имеет более одного вхождения символа B, то каждыйсимвол Bk во всех v соотнесен (верхним индексом) с конкретным вхождением B.A → u называют входным правилом вывода, Ai – переводом нетерминала A, Ai = vi – элементом перевода, связанным с этим правилом перевода. Если в ОСУ-схеме нет двух правил перевода с одинаковым входным правилом вывода, то ее называют семантически однозначной.86ГЛАВА 5. ЭЛЕМЕНТЫ ТЕОРИИ ПЕРЕВОДАВыход ОСУ-схемы определим снизу вверх. С каждой внутренней вершиной n дерева разбора (во входной грамматике), помеченной A, свяжем одну цепочку для каждого Ai .
Эта цепочка называется значением(или переводом) символа Ai в вершине n. Каждое значение вычисляетсяподстановкой значений символов перевода данного элемента переводаAi = vi , определенных в прямых потомках вершины n.Переводом τ (T r), определяемым ОСУ-схемой T r, назовем множество{(x, y) | x имеет дерево разбора во входной грамматике для T r и y – значение выделенного символа перевода Sk в корне этого дерева}.Пример 5.4. Рассмотрим формальное дифференцирование выражений, включающих константы 0 и 1, переменную x, функции sin и cos , а также операции ∗и +.
Такие выражения порождает грамматикаE →E+T |TT →T ∗F |FF → (E) | sin (E) | cos (E) | x | 0 | 1Свяжем с каждым из E, T и F два перевода, обозначенных индексом 1 и 2. Индекс 1 указывает на то, что выражение не дифференцировано, 2 – что выражение продифференцировано.
Формальная производная – это E2 . Законы дифференцирования таковы:d(f (x) + g(x)) = df (x) + dg(x)d(f (x) ∗ g(x)) = f (x) ∗ dg(x) + g(x) ∗ df (x)d sin (f (x)) = cos (f (x)) ∗ df (x)d cos (f (x)) = − sin (f (x))df (x)dx = 1d0 = 0d1 = 0Эти законы можно реализовать следующей ОСУ-схемой:5.3. АТРИБУТНЫЕ ГРАММАТИКИE → E +TE1 = E1 + T1E2 = E2 + T2E→TE1 = T1E2 = T2T →T ∗FT1 = T1 ∗ F1T2 = T1 ∗ F2 + T2 ∗ F1T →FT1 = F1T2 = F2F → (E)F1 = (E1 )F2 = (E2 )F → sin (E)F1 = sin (E1 )F2 = cos (E1 ) ∗ (E2 )F → cos (E)F1 = cos (E1 )F2 = − sin (E1 ) ∗ (E2 )F →xF1 = xF2 = 1F →0F1 = 0F2 = 0F →1F1 = 1F2 = 087Дерево вывода для sin (cos (x)) + x приведено на рис. 5.1.5.3Атрибутные грамматикиСреди всех формальных методов описания языков программированияатрибутные грамматики (введенные Кнутом [6]) получили, по-видимому,наибольшую известность и распространение.
Причиной этого являетсято, что формализм атрибутных грамматик основывается на дереве разбора программы в КС-грамматике, что сближает его с хорошо разработанной теорией и практикой построения трансляторов.5.3.1Определение атрибутных грамматикАтрибутной грамматикой называется четверка AG = (G, AS , AI , R),где(1) G = (N, T, P, S) – приведенная КС-грамматика;ГЛАВА 5. ЭЛЕМЕНТЫ ТЕОРИИ ПЕРЕВОДА88( VLQFRV[[( FRVFRV[VLQ[(( VLQFRV[( FRVFRV[VLQ[ (77 [7 7 VLQFRV[7 FRVFRV[VLQ[ 7)) VLQFRV[) FRVFRV[VLQ[ )) [) [VLQFRV (( FRV[( VLQ[77 FRV[7 VLQ[)) FRV[) VLQ[(77 [7 )) [) [Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
