2004 г.

Глава 5. Элементы теории перевода

5.1. Преобразователи с магазинной памятью

Преобразователем с магазинной памятью (стековой памятью) (МП-преобразователем) называется восьмерка: P=(Q,Т,Г,П,Ф,q₀,Z₀,F) где

Q - множество состояний,
T- конечный входной алфавит,
Г- конечный алфавит магазинных символов,
П- конечный выходной алфавит,
Ф- отображение множества Q x (T {e})x Г в множество конечных подмножеств множества Q x Г* х П* ,
q₀Q- начальное состояние,
Z₀Г - начальный символ стека,
FQ - множество заключительных состояний.

Определим конфигурацию преобразователя P как четверку (q,z,u,y), где

qQ- состояние,
xT*- цепочка на входной ленте,
uГ* - содержимое стека,
yП* - цепочка на выходной ленте, выданная вплоть до настоящего момента.

Если Ф(q,a,Z) содержит (r,u,z) , то будем писать (q,ax,Zw,y)|-(r,x,uw,yz) для любых xA*, wГ* и yП* y<-П*. Рефлексивное и транзитивное замыкание отношения |- будем обозначать |-* .

Цепочку y назовем выходом для x , если (q₀,x,Z₀,e)|-*(q,e,u,y) для некоторых qF и uГ* . Переводом (или преобразованием), определяемым МП-преобразователем P (обозначается t(P) ), назовем множество {(x,y)|(q₀,x,Z₀,e)|-*(q,e,u,y) для некоторых qF и uГ* . Будем говорить, что МП-преобразователь P=(Q,Т,Г,П,Ф,q₀,Z₀,F) детерминированный (ДМП-преобразователь), если выполняются следующие условия:

1. для всех qQ, aT{e} и ZT множество Ф(q,a,Z) содержит не более одного элемента,
2. если Ф(q,a,Z){}, то Ф(q,a,Z) = {} для всех aT.

Пример 5.1. Перевод арифметического выражения в ПОЛИЗ.

ПОЛИЗ - Польская инверсная запись или, постфиксная запись арифметических выражений. Трансляция может определяться следующим ДМП:

• Q={q₀,+,*),$};
• T ={буквы,+,*(,),$}, здесь $ - концевой маркер;
• Г={Z₀,(,+,*};
• П={буквы,+,*};

Последовательность состояний автомата и стека на строке a*(b+c) изображены в таблице рис.5.2.

5.2. Синтаксически управляемый перевод

Схемой синтаксически управляемого перевода (или трансляции, сокращенно: СУ-схемой) называется пятерка Tr=(N,T,П,R,S), где

N - конечное множество нетерминальных символов;
T- конечный входной алфавит;
П- конечный выходной алфавит;
R- конечное множество правил перевода вида A -> u, A₁ ->v₁, A₂ -> v₂,...,A_m -> v_m удовлетворяющих следующим условиям:

• каждый символ, входящий в v₁,v₂,...,v_m , либо принадлежит П, либо является B_k для (BN) & (B v) (здесь k - номер вхождения B в v),
• если u имеет более одного вхождения символа B, то каждый символ B_k во всех соотнесен (верхним индексом) с конкретным вхождением B ;

S - начальный символ, выделенный нетерминал из N.

A -> u называют входным правилом вывода, A_i - переводом нетерминала A и A_i=v_i - элементом перевода, связанным с этим правилом перевода. Если через P обозначить множество входных правил вывода всех правил перевода, то G=(N,T,P,S) будет входной грамматикой для Tr. Если в СУ-схеме Tr нет двух правил перевода с одинаковым входным правилом вывода, то ее называют семантически однозначной. Выход СУ-схемы определим снизу вверх. С каждой внутренней вершиной n дерева разбора (во входной грамматике), помеченной A, свяжем одну цепочку для каждого A_i. Эта цепочка называется значением (или переводом) символа A_i в вершине n. Каждое значение вычисляется подстановкой значений символов перевода данного элемента перевода A_i=v_i, определенных в прямых потомках вершины n.

Переводом t(Tr), определяемым СУ-схемой Tr, назовем множество {(x,y)|x имеет дерево разбора во входной грамматике для Tr и y - значение выделенного символа перевода S в корне этого дерева }. Если Tr=(N,T,П,R,S) - СУ-схема, то t(Tr) называется синтаксически управляемым переводом (СУ-переводом).

Пример 5.2. Рассмотрим формальное дифференцирование выражений, включающих константы 0 и 1, переменную и функции x, sin, cos, + и *. Такие выражения порождает грамматика

E -> E +T|T
T -> T *F|F
F -> (E)|sin(E)|cos(E)|x|0|1

Свяжем с каждым из E, T и F два перевода, обозначенных индексом 1 и 2. Индекс 1 указывает на то, что выражение не дифференцировано, 2 - что выражение продифференцировано. Формальная производная - это E₂. Законы дифференцирования таковы:

Эти законы реализуются СУ-схемой:

Дерево вывода для (sin(cos(x))+x приведено на рис.5.3.

Теорема 5.1. Если число вхождений каждого нетерминала в слове v не превосходит 1, то t(Tr) является КС-языком. Обратное не всегда верно.

Пример 5.2. T = ({S,A},{a},{a,b},{S -> A,AbAbA,A -> a,a,A -> aA,aA}) . Здесь входной язык {an|n1}, выходной {anbanban}. Выходной язык не КС.

Теорема 5.2. Для каждого магазинного преобразователя существует эквивалентная СУ- схема.

Обратное, вообще говоря, не верно.

Определение. Семантически однозначная СУ-схема Tr=(N,T,П,R,S) называется простой, если для каждого правила A -> u,v из R соответствующие друг другу вхождения нетерминалов встречаются в u и v в одном и том же порядке.

Перевод, определяемый простой СУ-схемой, называется простым синтаксически управляемым переводом (простым СУ-переводом).

Теорема 5.3. Пусть Tr=(N,T,П,R,S) - простая СУ-схема. Существует такой МП-преобразователь P, что t(P)=t(Tr) .

Таким образом, класс трансляций, определяемых магазинными преобразователями, совпадает с классом простых СУ-переводов.

Теорема 5.4. Пусть Tr=(N,T,П,R,S) - семантически однозначная простая СУ-схема, входной грамматикой которой служит LL(k)- грамматика. Тогда перевод {(x$,y)|(x,y) t(Tr)} можно осуществить детерминированным МП-преобразователем.

Существуют семантически однозначные простые СУ-схемы, имеющие в качестве входных грамматик LL(k) грамматики и не реализуемые ни на каком ДМП-преобразователе.

Рис. 5.3

Пример 5.3. Рассмотрим простую СУ-схему T с правилами

S -> Sa,aSa
S -> Sb,bSb
S -> e,e

Входная грамматика является LR(1) грамматикой, но не существует ДМП-преобразователя, определяющего перевод {(x$,y)|(x,y) t(Tr)}.

Определение. Назовем СУ-схему Tr=(N,T,П,R,S) постфиксной, если каждое правило из R имеет вид A ->u,v, где v N*П*. Иными словами, каждый элемент перевода представляет собой цепочку из нетерминалов, за которыми следует цепочка выходных символов.

Теорема 5.5. Пусть Tr=(N,T,П,R,S) - семантически однозначная простая постфиксная СУ-схема, входной грамматикой которой служит LR(k) -грамматика. Тогда перевод {(x$,y)|(x,y) t(Tr)} можно осуществить детерминированным МП-преобразователем.

5.3. Атрибутные грамматики

Среди всех формальных методов описания языков программирования атрибутные грамматики получили, по-видимому, наибольшую известность и распространение. Причиной этого является то, что формализм атрибутных грамматик основывается на дереве разбора программы в КС-грамматике, что сближает его с хорошо разработанной теорией и практикой построения трансляторов.

5.3.1. Определение атрибутных грамматик

Пусть G- КС-грамматика: G = (T,N,P,Z), где T,N,P,Z, - соответственно, множество терминальных символов, нетерминальных символов, множество правил вывода и аксиома грамматики. Правила вывода КС-грамматики будем записывать в виде

p:X₀ ->X₁...X_n

и будем предполагать, что G- редуцированная КС-грамматика, т.е. в ней нет нетерминальных символов, для которых не существует полного дерева вывода , в которое входит этот нетерминал.

С каждым символом X N T свяжем множество A(X) атрибутов символа X. Некоторые из множеств A(x) могут быть пусты. Запись a(X) означает, что aA(X).

С каждым правилом вывода p P свяжем множество F семантических правил, имеющих следующую форму:
a₀=fpa₀(a₁,a₂,...,a_j) где ik [0,пр] - номер символа правила p, а ak - атрибут символа X_ik, т.е. a_kA(X_ik).

В таком случае будем говорить, что a_o "зависит" от a₁,...,a_j или что a₀ "вычисляется по" a₁,...,a_j. В частном случае j может быть равно нулю, тогда будем говорить, что атрибут a₀ "получает в качестве значения константу".

КС-грамматику, каждому символу которой сопоставлено множество атрибутов, а каждому правилу вывода - множество семантических правил, будем называть атрибутной грамматикой(AG).

Назовем атрибут a(X₀) синтезируемым, если одному из правил вывода p:X₀ ->X₁...X_np сопоставлено семантическое правило a^{< 0 >} = fa^{< 0 >}(...). Назовем атрибут a(X_i) наследуемым, если одному из правил вывода p: X₀ -> X₁...X_i...X_пр сопоставлено семантическое правило a=fa(...), i[1,пр] . Множество синтезируемых атрибутов символа X обозначим через S(X), наследуемых атрибутов- через I(X) .

Будем считать, что значение атрибутов терминальных символов- константы, т.е. их значения определены, но для них нет семантических правил, определеяющих их значения.

5.3.2. Атрибутированное дерево разбора

Если дана атрибутная грамматика AG и цепочка, принадлежащая языку, определяемому G, то можно построить дерево разбора этой цепочки в грамматике G. В этом дереве каждая вершина помечена символом грамматики G. Припишем теперь каждой вершине множество атрибутов, сопоставленных символу, которым помечена эта вершина. Атрибуты, сопоставленные вхождениям символов в дерево разбора, будем называть вхождениями атрибутов в дерево разбора, а дерево с сопоставленными каждой вершине атрибутами - атрибутированным деревом разбора.

Между вхождениями атрибутов в дерево разбора существуют зависимости, определяемые семантически-ми правилами, соответствующими примененным синтаксическим правилам.

5.3.3. Язык описания атрибутных грамматик

Формализм атрибутных грамматик оказался очень удобным средством для описания семантики языков программирования. Вместе с тем выяснилось, что реализация вычислителей для атрибутных грамматик общего вида сталкивается с большими трудностями. В связи с этим было сделано множество попыток рассматривать те или иные классы атрибутных грамматик, обладающих "хорошими" свойствами. К числу таких свойств относят-ся прежде всего простота алгоритма проверки атрибутной грамматики на зацикленность и простота алгоритма вычисления атрибутов для атрибутных грамматик данного класса. Атрибутные грамматики использовались для описания семантики языков программирования и было создано несколько систем автоматизации разработки трансляторов, основанных на формализме атрибутных грамматик. Опыт их использования показал, что "чис-тый" атрибутный формализм может быть успешно применен для описания семантики языка, но его использо-вание вызывает трудности при создании транслятора. Эти трудности связаны как с самим формализмом, так и с некоторыми технологическими проблемами. К трудностям первого рода можно отнести несоответствие чисто функциональной природы атрибутного вычислителя и связанной с ней неупорядоченностью процесса вычисле-ния атрибутов (что в значительной степени является преимуществом этого формализма) и упорядоченностью элементов программы. Это несоответствие ведет к тому, что приходится идти на искусственные приемы для их сочетания. Технологические трудности связаны с эффективностью трансляторов, генерированных с помощью атрибутных систем. Как правило, качество таких трансляторов довольно низко из-за больших расходов памяти, неэффективности искусственных приемов, о которых было сказано выше. Учитывая это, мы будем вести даль-нейшее изложение на языке, сочетающем особенности атрибутного формализма и обычного языка, в котором предполагается возможность управления порядком исполнения операторов. Этот порядок привязывается к об-ходу атрибутированного дерева разбора сверху вниз слева направо. Все атрибуты должны быть вычислены за один такой обход. Атрибутные грамматики, обладающие таким свойством, называются L-атрибутными. При записи синтаксиса мы будем использовать расширенную БНФ. Элемент правой части синтаксического правила, заключенный в скобки [], может отсутствовать. Элемент правой части синтаксического правила, заключенный в скобки (), означает возможность повторения один или более раз. Элемент правой части синтаксического правила, заключенный в скобки [()], означает возможность повторения ноль или более раз. В скобках [] или [()] может указываться разделитель конструкций. Ниже дан синтаксис языка описания атрибутных грамматик.

Описание атрибутной грамматики состоит из раздела описания атрибутов и раздела правил. Раздел описания атрибутов определяет состав атрибутов для каждого символа грамматики и тип каждого атрибута. Правила состоят из синтаксической и семантической части. В синтаксической части исполь-зуется расширенная БНФ. Семантическая часть правила состоит из локальных объявлений и семантиче-ских действий. В качестве семантических действий допускаются как атрибутные присваивания, так и составные операторы.

Метка в семантической части правила привязывает выполнение оператора к обходу дерева разбора сверху-вниз слева направо. Конструкция " i : оператор" означает, что оператор должен быть выполнен сразу после обхода i-й компоненты правой части. Конструкция "i E : оператор" означает, что оператор должен быть выполнен, только если порождение i -й компоненты правой части пусто. Конструкция "i A : оператор" означает, что оператор должен быть выполнен после разбора каждого повторения i-й компоненты правой части (имеется в виду конструкция повторения). Каждое правило может иметь локальные определения (типов и переменных). В формулах используются как атрибуты символов данного правила (локальные атрибуты) и в этом случае соответствующие символы указываются номерами в правиле (0 для символа левой части, 1 для символа правой части и т.д.), так и атрибуты символов предков левой части правила (глобальные атрибуты). В этом случае соответствующий символ указывается именем нетерминала. Таким образом, на дереве образуются области видимости атрибутов: атрибут символа имеет область видимости, состоящую из правила, в которое символ входит в правую часть, плюс все поддерево, корнем которого является символ, за исключением поддеревьев - потомков того же символа в этом поддереве (рис. 5.4).

Рис. 5.4

Значение терминального символа доступно через атрибут VAL соответствующего типа.

Назад Вперед