В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 38
Текст из файла (страница 38)
. . an можно предварительно вычислить (под длиной выражения имеется в виду длина подстроки, начинающейся с символа кода операции и заканчивающейся последним символом,входящим в выражение для этой операции). Поэтому можно проверить,сопоставимо ли некоторое правило с подцепочкой ai . . . ak входной цепочкиa1 . . . an , проходя слева-направо по ai . . . ak . В процессе прохода по цепочкепредварительно вычисленные длины префиксных выражений используютсядля того, чтобы перейти от одного терминала к следующему терминалу, пропуская подцепочки, соответствующие нетерминалам правой части правила.Рассмотрим вновь пример рис. 9.23. В префиксной записи приведенныйфрагмент программы записывается следующим образом:= + a x + @ + + b y @ + i z 5Образцы, соответствующие машинным командам, задаются правиламиграмматики (вообще говоря, неоднозначной).
Генератор кода анализируетвходное префиксное выражение и строит одновременно все возможные деревья разбора, например, с помощью алгоритма Кока–Янгера–Касами. После окончания разбора выбирается дерево с наименьшей стоимостью. Затемпо этому единственному оптимальному дереву генерируется код.9.10.5. Атрибутная схема для алгоритма сопоставления образцов.Алгоритмы 9.1 и 9.2 являются «универсальными» в том смысле, что конкретные грамматики выражений и образцов являются, по существу, параметрами этих алгоритмов. В то же время для каждой конкретной грамматикиможно написать свой алгоритм поиска образцов.
Например, в случае нашей9.10. Генерация оптимального кода методами сопоставления образцов211грамматики выражений и образцов, приведенных в табл. 9.2, алгоритм 9.2может быть представлен атрибутной грамматикой, приведенной ниже.Наследуемый атрибут Match содержит упорядоченный список (вектор) образцов для сопоставления в поддереве данной вершины. Каждый из образцовлибо имеет вид <op op–list> (op — операция в данной вершине, а op–list— список ее операндов), либо представляет собой нетерминал N . В первомслучае op–list «распределяется» по потомкам вершины для дальнейшего сопоставления. Во втором случае сопоставление считается успешным, если естьправило N → op {P ati }, где w состоит из образцов, успешно сопоставленныхпотомкам данной вершины.
В этом случае по потомкам в качестве образцовраспределяются элементы правой части правила. Эти два множества образцовмогут пересекаться. Синтезируемый атрибут Pattern — вектор логическихзначений — дает результат сопоставления по вектору-образцу Match.Таким образом, при сопоставлении образцов могут встретиться два случая.1.
Вектор образцов содержит образец <op {P ati }>, где op — операция,примененная в данной вершине. Тогда распределяем образцы P ati по потомкам и считаем сопоставление по данному образцу успешным (истинным), если успешны сопоставления элементов этого образца по всемпотомкам.2. Образцом является нетерминал N . Тогда рассматриваем все правилавида N → op {P ati }. Вновь распределяем образцы P ati по потомками считаем сопоставление успешным (истинным), если успешны сопоставления по всем потомкам.
В общем случае успешным может бытьсопоставление по нескольким образцам.Отметим, что в общем случае по потомкам одновременно распределяютсянесколько образцов для сопоставления.В приведенной ниже атрибутной схеме не рассматриваются правила выбора покрытия наименьшей стоимости (см. подраздел 9.10.3).
Выбор оптимального покрытия может быть сделан еще одним проходом по деревуаналогично тому, как это было сделано выше. Например, в правиле с ’+’имеются несколько образцов для Reg , но реального выбора одного из нихне осуществляется. Кроме того, не уточнены некоторые детали реализации,в частности, конкретный способ формирования векторов Match и Pattern.В тексте употребляется термин «добавить», что означает добавление очередного элемента к вектору образцов. Векторы образцов записаны в угловыхскобках.RULEStat ::= ’=’ Reg Reg212Глава 9. Генерация кодаSEMANTICSMatch<2>=<’+’ Reg Const>;Match<3>=<Reg>;Pattern<0>[1]=Pattern<2>[1]&Pattern<3>[1].Этому правилу соответствует один образец 2.
Поэтому в качестве образцов потомковчерез их атрибуты Match передаются, соответственно,<’+’ Reg Const> и <Reg>.RULEReg ::= ’+’ Reg RegSEMANTICSif (Match<0> содержит Reg в позиции i){Match<2>=<Reg,Reg,Reg>;Match<3>=<Const,Reg,<’@’ ’+’ Reg Const>>;}if (Match<0> содержит образец <’+’ Reg Const>в позиции j){добавить Reg к Match<2> в некоторой позиции k;добавить Const к Match<3> в некоторой позиции k;}if (Match<0> содержит образец <’+’ Reg Const>в позиции j)Pattern<0>[j]=Pattern<2>[k]&Pattern<3>[k];if (Match[0] содержит Reg в i-й позиции)Pattern<0>[i]=(Pattern<2>[1]&Pattern<3>[1])|(Pattern<2>[2]&Pattern<3>[2])|(Pattern<2>[3]&Pattern<3>[3]).Образцы, соответствующие этому правилу, следующие:(4) Reg → ’+’ Reg Const,(5) Reg → ’+’ Reg Reg ,(6) Reg → ’+’ Reg ’@’ ’+’ Reg Const.Атрибутам Match второго и третьего символов в качестве образцов при сопоставлении могут быть переданы векторы <Reg, Reg, Reg> и <Const, Reg,<’@’ ’+’ Reg Const>> соответственно.
Из анализа других правил можнозаключить, что при сопоставлении образцов предков левой части данногоправила атрибуту Match символа левой части может быть передан образец<’+’ Reg Const> (из образцов 2, 3, 6) или образец Reg.RULEReg ::= ’@’ RegSEMANTICSif (Match<0> содержит Reg в i-й позиции)Match<2>=<<’+’ Reg Const>,Reg>;if (Match<0> содержит <’@’ ’+’ Reg Const>9.10. Генерация оптимального кода методами сопоставления образцов213Рис. 9.25в j-й позиции)добавить к Match<2> <’+’ Reg Const> в k позиции;if (Match<0> содержит Reg в i-й позиции)Pattern<0>[i]=Pattern<2>[1]|Pattern<2>[2];if (Match<0> содержит <’@’ ’+’ Reg Const>в j-й позиции)Pattern<0>[j]=Pattern<2>[k].Образцы, соответствующие этому правилу, следующие:(3) Reg → ’@’ ’+’ Reg Const,(7) Reg → ’@’ Reg .Соответственно атрибуту Match второго символа в качестве образцов при сопоставлении могут быть переданы <’+’Reg Const> (образец 3) или <Reg>(образец 7).
Из анализа других правил можно заключить, что при сопоставлении образцов предков левой части данного правила атрибуту Match могутбыть переданы образцы <’@’ ’+’ Reg Const> (из образца 6) и Reg.214Глава 9. Генерация кодаRULEReg ::= ConstSEMANTICSif (Pattern<0> содержит Const в j-й позиции)Pattern<0>[j]=true;if (Pattern<0> содержит Reg в i-й позиции)Pattern<0>[i]=true.Для дерева рис. 9.23 получим значения атрибутов, приведенныена рис.
9.25. Здесь M обозначает Match, P — Pattern, C — Const, R —Reg.Г л а в а 10СИСТЕМЫ АВТОМАТИЗАЦИИПОСТРОЕНИЯ ТРАНСЛЯТОРОВСистемы автоматизации построения трансляторов (САПТ) предназначеныдля автоматизации процесса разработки трансляторов. Очевидно, что длятого, чтобы описать транслятор, необходимо иметь формализм для описания.Этот формализм затем реализуется в виде входного языка САПТ. Как правило, формализмы основаны на атрибутных грамматиках.
Ниже описаны двеСАПТ, получившие распространение: СУПЕР [4] и Yacc. В основу первойсистемы положены LL(1)-грамматики и L-атрибутные вычислители, в основувторой — LALR(1)-грамматики и S-атрибутные вычислители.10.1. Система СУПЕРПрограмма на входном языке СУПЕР («метапрограмма») состоит из следующих разделов:– заголовок;– раздел констант;– раздел типов;– алфавит;– раздел файлов;– раздел библиотеки;– атрибутная схема.Заголовок определяет имя атрибутной грамматики, первые три буквы имени задают расширение имени входного файла для реализуемого транслятора.Раздел констант содержит описание констант, раздел типов — описаниетипов.Алфавит содержит перечисление нетерминальных символов и классов лексем, а также атрибутов (и их типов), сопоставленных этим символам. Классылексем являются терминальными символами с точки зрения синтаксическогоанализа, но могут иметь атрибуты, вычисляемые в процессе лексическогоанализа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
