В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 23
Текст из файла (страница 23)
Эти преобразователи получаются из автоматов с магазинной памятью, если к ним добавить выход и позволить на каждомшаге выдавать выходную цепочку.Преобразователем с магазинной памятью (МП-преобразователем) называется восьмерка P = (Q, T , Γ, Π, D, q0 , Z0 , F ), где все символы имеюттот же смысл, что и в определении МП-автомата, за исключением того, что Π — конечный выходной алфавит, а D — отображение множества Q × (T ∪ {e}) × Γ во множество конечных подмножеств множестваQ × Γ ∗ × Π∗ .Определим конфигурацию преобразователя P как четверку (q , x, u, y),где q ∈ Q — состояние, x ∈ T ∗ — цепочка на входной ленте, u ∈ Γ∗ —112Глава 5. Элементы теории переводасодержимое магазина, y ∈ Π∗ — цепочка на выходной ленте, выданная вплотьдо настоящего момента.Если множество D(q , a, Z) содержит элемент (r, u, z), то будем писать(q , ax, Zw, y) ⊢ (r, x, uw, yz) для любых x ∈ T ∗ , w ∈ Γ∗ и y ∈ Π∗ .
Рефлексивно-транзитивное замыкание отношения ⊢ будем обозначать ⊢∗ .Цепочку 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.1.
Схемы синтаксически управляемого перевода.Определение 5.2.Cхемой синтаксически управляемого перевода (или трансляции, сокращенно: СУ-схемой) называется пятеркаT r = (N , T , Π, R, S), где:5.2. Синтаксически управляемый перевод1131) 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 , x′ Ay ′ ) — выводимая пара, в цепочках которой вхождения Aсоответствуют друг другу, и A → u, v — правило из R, то (xuy , x′ vy ′ )— выводимая пара.
Для обозначения такого вывода одной пары издругой будем пользоваться обозначением ⇒: (xAy , x′ Ay ′ ) ⇒ (xuy , x′ vy ′ ).Рефлексивно-транзитивное замыкание отношение ⇒ обозначим ⇒ ∗ .Переводом τ (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.2.
Перевод арифметических выражений в ПОЛИЗ (польскую инверсную запись) можно осуществить простой СУ-схемой с правиламиE → E + T,E → T,T → T ∗ F,T → F,F → id,F → (E),ET +;T;T F ∗;F;id;E.114Глава 5. Элементы теории переводаНайдем выход схемы для входа 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, aSa;S → Sb, bSb;S → e, e.Входная грамматика является LR(1)-грамматикой, но не существует ДМП-преобразователя, определяющего перевод {(x, y)|(x, y) ∈ τ (T r)}.Назовем СУ-схему 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. Синтаксически управляемый перевод1155.2.2. Обобщенные схемы синтаксически управляемого перевода.Расширим определение СУ-схемы, с тем чтобы выполнять более широкийкласс переводов. Во-первых, позволим иметь в каждой вершине дерева разбора несколько переводов.
Как и в обычной СУ-схеме, каждый перевод зависитот прямых потомков соответствующей вершины дерева. Во-вторых, позволим элементам перевода быть произвольными цепочками выходных символови символов, представляющих переводы в потомках. Таким образом, символыперевода могут повторяться или вообще отсутствовать.Определение 5.3.
Обобщенной схемой синтаксически управляемого перевода (или трансляции, сокращенно: OСУ-схемой) называется шестеркаT r = (N ,T ,Π,Γ,R,S), где все символы имеют тот же смысл, что и дляСУ-схемы, за исключением того, что1) Γ — конечное множество символов перевода вида Ai , где A ∈ N и i —целое число;2) R — конечное множество правил перевода видаA → u , A1 = v1 , . . . , A m = vm ,удовлетворяющих следующим условиям:а) Aj ∈ Γ для 1 6 j 6 m,б) каждый символ, входящий в v1 , . . ., vm , либо принадлежит Π, либоявляется Bk ∈ Γ, где B входит в u,в) если u имеет более одного вхождения символа B , то каждый символBk во всех v соотнесен (верхним индексом) с конкретным вхождением B .Правило A → u называют входным правилом вывода, Ai — переводомнетерминала A, Ai = vi — элементом перевода, связанным с этим правиломперевода.
Если в ОСУ-схеме нет двух правил перевода с одинаковым входнымправилом вывода, то ее называют семантически однозначной.Выход ОСУ-схемы определим снизу вверх. С каждой внутренней вершиной 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 , а также операции ∗ и +.Такие выражения порождает грамматика116Глава 5. Элементы теории переводаE → E + T | T;T → T ∗ F | F;F → (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 = 1;d0 = 0;d1 = 0.Эти законы можно реализовать следующей ОСУ-схемой:E → E + T , E 1 = E1 + T 1 ;E2 = E 2 + T 2 ;Рис. 5.15.3. Атрибутные грамматики117E → T , E1 = T 1 ;E2 = T 2 ;T → T ∗ F , T1 = T1 ∗ F1 ;T2 = T1 ∗ F2 + T2 ∗ F1 ;T → F , T 1 = F1 ;T 2 = F2 ;F → (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 → x, F1 = x;F2 = 1;F → 0, F1 = 0;F2 = 0;F → 1, F1 = 1;F2 = 0;Дерево вывода для sin (cos (x)) + x приведено на рис.
5.1.5.3. Атрибутные грамматикиСреди всех формальных методов описания языков программирования атрибутные грамматики (введенные Кнутом [7]), по-видимому, наиболее известны и распространены. Причиной этого является то, что формализм атрибутных грамматик основывается на дереве разбора программы в КС-грамматике,что сближает его с хорошо разработанной теорией и практикой построениятрансляторов.5.3.1. Определение атрибутных грамматик. Атрибутной грамматикой называется четверка AG = (G, AS , AI , R), где:1) G = (N , T , P , S) — приведенная КС-грамматика;2) AS — конечное множество синтезируемых атрибутов;3) AI — конечное множество наследуемых атрибутов, AS ∩ AI = ∅;4) R — конечное множество семантических правил.Атрибутная грамматика AG сопоставляет каждому символу X из N ∪ Tмножество AS (X) синтезируемых атрибутов и множество AI (X) наследуемых атрибутов.
Множество всех синтезируемых атрибутов всех символов изN ∪ T обозначается AS , наследуемых — AI . Атрибуты разных символовявляются различными атрибутами. Будем обозначать атрибут a символа Xкак a(X). Значения атрибутов могут быть произвольных типов, например,представлять собой числа, строки, адреса памяти и т. п.118Глава 5. Элементы теории переводаПусть правило p из P имеет вид X0 → X1 X2 . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
