Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 11
Текст из файла (страница 11)
Трансляция может определятьсяследующим ДМП:Q={q0,+,*,),$};T={буквы,+,*,(,),$}, здесь $ - концевой маркер;Г={Z0,(,+,*};П={буквы,+,*};Функция переходов определяется таблицей на рис. 4.1.65ГQZ0Z0Z0(+,*TГ*QПq0 букваq0 (q0 проч))z0z0(z0eeq0q0прочбуква+*проч*++,*+**++,*Z0$$eq0)q0q0проч {+,*}q0e$+,*+,*Рис. 4.1СтекZ0Z0Z0Z0*Z0*(Z0*(Z0*(Z0*(+Z0*(+Z0*(+Z0*(Z0*Z0*Z0Состояниеq0q0*q0q0+q0q0))$q0q0$ВходВыход¦a*(b+c)$ a*(b+c)$(b+c)$(b+c)$b+c)$b+c)$c)$c)$c)$$+$$*Рис. 4.2Последовательность состояний автомата и магазина на строке a*(b+c)изображены в таблице рис. 4.2.4.2. Синтаксически управляемый переводСхемой синтаксически управляемого перевода (или трансляции,сокращенно: СУ-схемой) называется пятерка Tr=(N,T,П,R,S), где66N - конечное множество нетерминальных символов;T - конечный входной алфавит;П - конечный выходной алфавит;R - конечное множество правил перевода вида A->u, A1=v1, ...
, Am=vm,удовлетворяющих следующим условиям:- каждый символ, входящий в v1, ..., vm, либо принадлежит П, либоявляется Bk для B<-N и B входит в u,- если u имеет более одного вхождения символа B, то каждыйсимвол Bk во всех v соотнесен (верхним индексом) с конкретнымвхождением B;S - начальный символ, выделенный нетерминал из N.A->u называют входным правилом вывода, Ai - переводом нетерминала A,Ai=vi - элементом перевода, связанным с этим правилом перевода. Есличерез P обозначить множество входных правил вывода всех правилперевода, то G=(N,T,P,S) будет входной грамматикой для Tr. Если в СУсхеме Tr нет двух правил перевода с одинаковым входным правиломвывода, то ее называют семантически однозначной.
Выход СУ-схемыопределим снизу вверх. С каждой внутренней вершиной n дерева разбора(во входной грамматике), помеченной A, свяжем одну цепочку длякаждого Ai. Эта цепочка называется значением (или переводом) символаAi в вершине n. Каждое значение вычисляется подстановкой значенийсимволов перевода данного элемента перевода Ai=vi, определенных впрямых потомках вершины 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 | TT -> T*F | FF -> (E) | sin(E) | cos(E) | x | 0 | 1Свяжем с каждым из E, T и F два перевода, обозначенных индексом 1 и 2.Индекс 1 указывает на то, что выражение не дифференцировано, 2 - чтовыражение продифференцировано.
Формальная производная - это E2.Законы дифференцирования таковы:67d(f(x)+g(x))=df(x)+dg(x)d(f(x)*g(x))=f(x)*dg(x)+g(x)*df(x)dsin(f(x))=cos(f(x))*df(x)dcos(f(x))=-sin(f(x))df(x)dx=1d0=0d1=0Эти законы реализуются СУ-схемой:E -> E+T E1=E1+T1F -> sin(E)E2=E2+T2E -> T E1=T1F -> cos(E)E2=T2T -> T*F T1=T1*F1F -> xT2=T1*F2+T2*F1T -> FT1=F1F -> 0T2=F2F -> ( E ) F1=(E1)F -> 1F2=(E2)F1=sin(E1)F2=cos(E1)*(E2)F1=cos(E1)F2=-sin(E1)*(E2)F1=xF2=1F1=0F2=0F1=1F2=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}>. Здесьвходной язык {an|n>=1}, выходной {anbanban}. Выходной язык не КС.Для каждого магазинного преобразователя существуетэквивалентная СУ-схема [4].Теорема4.2.Обратное, вообще говоря, не верно.Семантически однозначная СУ-схема Tr=(N,T,П,R,S)называется простой, если для каждого правила A->u,v из Rсоответствующие друг другу вхождения нетерминалов встречаются в u и vв одном и том же порядке.Определение.Перевод, определяемый простой СУ-схемой, называется простымсинтаксически управляемым переводом (простым СУ-переводом).Теорема 4.3.
Пусть Tr=(N,T,П,R,S) - простая СУ-схема. Существует такойМП-преобразователь P, что t(P)=t(Tr) [5].Таким образом, класс трансляций, определяемых магазиннымипреобразователями, совпадает с классом простых СУ-переводов.68EE1=sin(cos(x))+xE2=cos(cos(x))*(-sin(x)*(1))+1E1=sin(cos(x))+E2=cos(cos(x))E*(-sin(x)*(1))TT1=sin(cos(x))T2=cos(cos(x))T*(-sin(x)*(1))F F1=xF2=1F1=sin(cos(x))F2=cos(cos(x)) F*(-sin(x)*(1))sin (T2=1T1=xxE )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, aSaS -> Sb, bSbS -> e, eВходная грамматика является LR(1) грамматикой, но не существует ДМПпреобразователя, определяющего перевод {(x$,y)|(x,y)<-t(Tr)} [5].Назовем СУ-схему Tr=<N,T,П,R,S> постфиксной, есликаждое правило из R имеет вид A->u,v, где v<-N*П*.Определение.69Иными словами, каждый элемент перевода представляет собойцепочку из нетерминалов, за которыми следует цепочка выходныхсимволов.Теорема 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: X0 -> X1 ... Xn<p>и будем предполагать, что G - редуцированная КС-грамматика, т.е. в нейнет нетерминальных символов, для которых не существует полного деревавывода , в которое входит этот нетерминал.С каждым символом X <- N U T свяжем множество A(X) атрибутовсимвола X. Некоторые из множеств A(x) могут быть пусты.
Запись a(X)означает, что a <- A(X).С каждым правилом вывода p <- P свяжем множество Fсемантических правил, имеющих следующую форму:a0<i0> = fpa0<i0>(a1<i1>, ... , aj<ij>),где ik <- [0,np] - номер символа правила p, а ak<ik> - атрибут символа Xik ,т.е. ak<ik> <- A(Xik).В таком случае будем говорить , что a0<i0> "зависит" от70a1<i1>,...,aj<ij> или что a0<i0> "вычисляется по" a1<i1>,...,aj<ij>. В частномслучае j может быть равно нулю, тогда будем говорить, что атрибут a0<i0>"получает в качестве значения константу".КС-грамматику, каждому символу которой сопоставлено множествоатрибутов, а каждому правилу вывода - множество семантических правил,будем называть атрибутной грамматикой (AG).Назовем атрибут a(X0) синтезируемым, если одному из правилвывода p: X0 ->X1 ...
Xnp сопоставлено семантическое правилоa<0>=fa<0>(...). Назовем атрибут a(Xi) наследуемым, если одному из правилвывода p:X0 -> X1 ... Xi ... Xnp сопоставлено семантическое правилоa<i>=fa<i>(...), i <- [1,np]. Множество синтезируемых атрибутов символа Xобозначим через S(X), наследуемых атрибутов - через I(X).Будем считать, что значение атрибутов терминальных символов константы, т.е. их значения определены, но для них нет семантическихправил, определеяющих их значения.В качестве примера рассмотрим атрибутную грамматику,вычисляющую значение дробного числа, представленного в десятичнойформе.Число ::= Целая_часть ‘.’ Дробная_часть=>Значение<0>=Значение<1>+Значение<3>;Порядок<3>=1.Целая_часть ::= e=>Значение<0>=0; Порядок<0>=0.Целая_часть ::= Цифра Целая_часть =>Значение<0>=Значение<1>*10**Порядок<2>+Значение<2>;Порядок<0>=Порядок<2>+1.Дробная_часть ::= e =>Значение<0>=0.Дробная_часть ::= Цифра Дробная_часть=>Значение<0>=Значение<1>*10**(-Порядок<0>)+Значение<2>;Порядок<2>=Порядок<0>+1.4.3.2.
Атрибутированное дерево разбораЕсли дана атрибутная грамматика AG и цепочка, принадлежащая языку,определяемому G, то можно построить дерево разбора этой цепочки вграмматике G. В этом дереве каждая вершина помечена символомграмматики G. Припишем теперь каждой вершине множество атрибутов,сопоставленных символу, которым помечена эта вершина. Атрибуты,71сопоставленные вхождениям символов в дерево разбора, будем называтьвхождениями атрибутов в дерево разбора, а дерево с сопоставленнымикаждой вершине атрибутами - атрибутированным деревом разбора.Между вхождениями атрибутов в дерево разбора существуютзависимости,определяемыесемантическимиправилами,соответствующими примененным синтаксическим правилам.4.3.3.
Язык описания атрибутных грамматикФормализм атрибутных грамматик оказался очень удобным средством дляописания семантики языков программирования. Вместе с тем выяснилось,что реализация вычислителей для атрибутных грамматик общего видасталкивается с большими трудностями. В связи с этим было сделаномножество попыток рассматривать те или иные классы атрибутныхграмматик, обладающих "хорошими" свойствами.
К числу таких свойствотносятся прежде всего простота алгоритма проверки атрибутнойграмматики на зацикленность и простота алгоритма вычисления атрибутовдля атрибутных грамматик данного класса.Атрибутные грамматики использовались для описания семантикиязыков программирования и было создано несколько системавтоматизации разработки трансляторов, основанных на формализмеатрибутных грамматик. Опыт их использования показал, что "чистый"атрибутный формализм может быть успешно применен для описаниясемантики языка, но его использование вызывает трудности при созданиитранслятора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
