Лекции по конструированию компиляторов. В.А. Серебряков (1134687), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

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

1) для всех q<-Q, a<-T U {e} и Z<-Г множество Ф(q,a,Z) содержит не более одного элемента,

2) если Ф(q,e,Z)#{}, то Ф(q,a,Z)={} для всех a<-T.

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

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

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

Функция переходов определяется таблицей на рис. 4.1.

Г Q T Г* Q П

Z₀ q₀ буква z₀ q₀ буква
Z₀ q₀ ( z₀( q₀
Z₀ q₀ проч z₀ проч

( ) e q₀
+,* ) e ) +,*

+ * +* q₀
* + *+ q₀
проч +,* проч {+,*}q₀

+,* $ e $ +,*
Z₀ $ e

Рис. 4.1

Стек Состояние Вход Выход¦

Z₀ q₀ a*(b+c)$ a
Z₀ q₀ *(b+c)$
Z₀ * (b+c)$
Z₀* q₀ (b+c)$
Z₀*( q₀ b+c)$ b
Z₀*( q₀ +c)$
Z₀*( + c)$
Z₀*(+ q₀ c)$ c
Z₀*(+ q₀ )$
Z₀*(+ ) $ +
Z₀*( ) $
Z₀* q₀ $
Z₀* $ *
Z₀ $


Рис. 4.2

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

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

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

N - конечное множество нетерминальных символов;

T - конечный входной алфавит;

П - конечный выходной алфавит;

R - конечное множество правил перевода вида A->u, A₁=v₁, ... , A_m=v_m, удовлетворяющих следующим условиям:

- каждый символ, входящий в v₁, ..., v_m, либо принадлежит П, либо является B_k для B<-N и B входит в u,

- если u имеет более одного вхождения символа B, то каждый символ B_k во всех v соотнесен (верхним индексом) с конкретным вхождением 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> - СУ-схема, то т(Tr) называется синтаксически управляемым переводом (СУ-переводом).

Пример 4.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 - что выражение продифференцировано. Формальная производная - это E2. Законы дифференцирования таковы:

d(f(x)+g(x))=df(x)+dg(x) dx=1
d(f(x)*g(x))=f(x)*dg(x)+g(x)*df(x) d0=0
dsin(f(x))=cos(f(x))*df(x) d1=0
dcos(f(x))=-sin(f(x))df(x)

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

E -> E+T E1=E1+T1 F -> sin(E) F1=sin(E1)
E2=E2+T2 F2=cos(E1)*(E2)
E -> T E1=T1 F -> cos(E) F1=cos(E1)
E2=T2 F2=-sin(E1)*(E2)
T -> T*F T1=T1*F1 F -> x F1=x
T2=T1*F2+T2*F1 F2=1
T -> F T1=F1 F -> 0 F1=0
T2=F2 F2=0
F -> ( E ) F1=(E1) F -> 1 F1=1
F2=(E2) F2=0

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

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

Пример 4.2. T=<{S,A},{a},{a,b},{S->A,AbAbA;A->a,a;A->aA,aA}>. Здесь входной язык {aⁿ|n>=1}, выходной {aⁿbaⁿbaⁿ}. Выходной язык не КС.

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

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

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

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

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

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

E E1=sin(cos(x))+x
E2=cos(cos(x))
E1=sin(cos(x)) + *(-sin(x)*(1))+1
E2=cos(cos(x)) E T
*(-sin(x)*(1)) T2=1
T1=x
T1=sin(cos(x))
T2=cos(cos(x)) T F F1=x
*(-sin(x)*(1)) F2=1

F1=sin(cos(x))
F2=cos(cos(x)) F x
*(-sin(x)*(1))

sin ( E ) E1=cos(x)
E2=-sin(x)*(1)

T T1=cos(x)
T2=-sin(x)*(1)

F F1=cos(x)
F2=-sin(x)*(1)

cos ( E ) E1=x E2=1
|
T T1=x T2=1
|
F F1=x F2=1
|
x

Рис. 4.3

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

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

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

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

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

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

Иными словами, каждый элемент перевода представляет собой цепочку из нетерминалов, за которыми следует цепочка выходных символов.

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

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

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

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

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

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

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

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

С каждым правилом вывода p <- P свяжем множество F семантических правил, имеющих следующую форму:

a₀<i₀> = f^p_a0<i0>(a₁<i₁>, ... , a_j<i_j>),

где i_k <- [0,n_p] - номер символа правила p, а a_k<i_k> - атрибут символа X_ik , т.е. a_k<i_k> <- A(X_ik).

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

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

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

Характеристики

Список файлов лекций