В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 29
Текст из файла (страница 29)
В первом случае op–list “распределяется” по потомкам вершины для дальнейшего сопоставления. Во втором случае сопоставлениесчитается успешным, если есть правило N → op {P ati }, где w состоит из образцов, успешно сопоставленных потомкам данной вершины. Вэтом случае по потомкам в качестве образцов распределяются элементыправой части правила. Эти два множества образцов могут пересекаться. Синтезируемый атрибут Pattern – вектор логических значений, даетрезультат сопоставления по вектору-образцу Match.Таким образом, при сопоставлении образцов могут встретиться дваслучая:1.
Вектор образцов содержит образец <op {P ati }>, где op – операция,примененная в данной вершине. Тогда распределяем образцы P atiпо потомкам и сопоставление по данному образцу считаем успешным (истинным), если успешны сопоставления элементов этого образца по всем потомкам.2. Образцом является нетерминал N . Тогда рассматриваем все правила вида N → op {P ati }. Вновь распределяем образцы P ati по потомкам и сопоставление считаем успешным (истинным), если успешны сопоставления по всем потомкам. В общем случае успешнымможет быть сопоставление по нескольким образцам.Отметим, что в общем случае в потомки одновременно передаетсянесколько образцов для сопоставления.В приведенной ниже атрибутной схеме не рассматриваются правилавыбора покрытия наименьшей стоимости (см.
предыдущий раздел). Выбор оптимального покрытия может быть сделан еще одним проходом подереву, аналогично тому, как это было сделано выше. Например, в правиле с ’+’ имеется несколько образцов для Reg, но реального выбора одного из них не осуществляется. Кроме того, не уточнены некоторые деталиреализации. В частности, конкретный способ формирования векторовMatch и Pattern.
В тексте употребляется термин “добавить”, что означает9.9. ГЕНЕРАЦИЯ ОПТИМАЛЬНОГО КОДА МЕТОДАМИ СИНТАКСИЧЕСКОГО АНАЛИЗА181добавление к вектору образцов очередного элемента. Векторы образцовзаписаны в угловых скобках.RULEStat ::= ’=’ Reg RegSEMANTICSMatch<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 ::= ’@’ RegГЛАВА 9. ГЕНЕРАЦИЯ КОДА1826WDW0 5HJ!3 W!0 5HJ&RQVW!!3 W!5HJ0 &RQVW!3 W!5HJ5HJ&RQVW&RQVW0 5HJ5HJ5HJ5HJ!3 WWWW!0 5HJ5HJ5HJ!3 WWW!0 5HJ!3 W!0 5HJ5HJ5HJ!3 WWW!#0 5HJ&RQVW!5HJ!3 IW!5HJ5HJ5HJ&RQVW5HJ5HJ5HJ&RQVW&RQVW0 &RQVW5HJ #5HJ&RQVW!!3 WWI!5HJ#0 &RQVW5HJ #5HJ&RQVW!!3 WWI!0 5HJ5HJ5HJ5HJ5HJ!3 WWWWW!5HJ5HJ0 &RQVW5HJ #5HJ&RQVW!&RQVW!3 IWWI!0 5HJ&RQVW!5HJ 5HJ&RQVW!!3 WWW!5HJ5HJ&RQVW&RQVW0 &RQVW5HJ #5HJ&RQVW!&RQVW&RQVW!3 WWIWW!Рис.
9.19:SEMANTICSif (Match<0> содержит Reg в i-й позиции)Match<2>=<<’+’ Reg Const>,Reg>;if (Match<0> содержит <’@’ ’+’ Reg Const> в 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).
Из анализа других правил можно заключить, что при со-9.9. ГЕНЕРАЦИЯ ОПТИМАЛЬНОГО КОДА МЕТОДАМИ СИНТАКСИЧЕСКОГО АНАЛИЗА183поставлении образцов предков левой части данного правила атрибутуMatch могут быть переданы образцы <’@’ ’+’ Reg Const> (из образца 6) и Reg.RULEReg ::= ConstSEMANTICSif (Pattern<0> содержит Const в j-й позиции)Pattern<0>[j]=true;if (Pattern<0> содержит Reg в i-й позиции)Pattern<0>[i]=true.Для дерева рис. 9.15 получим значения атрибутов, приведенные нарис. 9.19. Здесь M обозначает Match, P – Pattern, C – Const, R – Reg.184ГЛАВА 9.
ГЕНЕРАЦИЯ КОДАГлава 10Системы автоматизациипостроения трансляторовСистемы автоматизации построения трансляторов (САПТ) предназначены для автоматизации процесса разработки трансляторов. Очевидно,что для того, чтобы описать транслятор, необходимо иметь формализмдля описания. Этот формализм затем реализуется в виде входного языка САПТ. Как правило, формализмы основаны на атрибутных грамматиках. Ниже описаны две САПТ, получившие распространение: СУПЕР [3]и Yacc. В основу первой системы положены LL(1)-грамматики и L-атрибутныевычислители, в основу второй – LALR(1)-грамматики и S-атрибутныевычислители.10.1Система СУПЕРПрограмма на входном языке СУПЕР (“метапрограмма”) состоит из следующих разделов:- Заголовок;- Раздел констант;- Раздел типов;- Алфавит;- Раздел файлов;- Раздел библиотеки;- Атрибутная схема.Заголовок определяет имя атрибутной грамматики, первые три буквы имени задают расширение имени входного файла для реализуемоготранслятора.Раздел констант содержит описание констант, раздел типов – описание типов.Алфавит содержит перечисление нетерминальных символов и классов лексем, а также атрибутов (и их типов), сопоставленных этим симво185186ГЛАВА 10.
СИСТЕМЫ АВТОМАТИЗАЦИИ ПОСТРОЕНИЯ ТРАНСЛЯТОРОВлам. Классы лексем являются терминальными символами с точки зрения синтаксического анализа, но могут иметь атрибуты, вычисляемыев процессе лексического анализа. Определение класса лексем состоит взадании имени класса, имен атрибутов для этого класса и типов этихатрибутов.В разделе определения нетерминальных символов содержится перечисление этих символов с указанием приписанных им атрибутов и ихтипов.
Аксиома грамматики указывается первым символом в списке нетерминалов.Раздел библиотеки содержит заголовки процедур и функций, используемых в формулах атрибутной грамматики.Раздел файлов содержит описание файловых переменных, используемых в формулах атрибутной грамматики.
Файловые переменные можно рассматривать как атрибуты аксиомы.Атрибутная схема состоит из списка синтаксических правил и сопоставленных им семантических правил. Для описания синтаксиса языкаиспользуется расширенная форма Бэкуса-Наура. Терминальные символы в правой части заключаются в кавычки, классы лексем и нетерминалы задаются их именами. Для задания в правой части необязательныхсимволов используются скобки [ ], для задания повторяющихся конструкций используются скобки ( ).
В этом случае может быть указанразделитель символов (после /). Например,A ::= B [ C ] ( D ) ( E / ’,’ )Первым правилом в атрибутной схеме должно быть правило для аксиомы.Каждому синтаксическому правилу могут быть сопоставлены семантические действия. Каждое такое действие – это оператор, который может использовать атрибуты как символов данного правила (локальныеатрибуты), так и символов, могущих быть предками (динамически) символа левой части данного правила в дереве разбора (глобальные атрибуты). Для ссылки на локальные атрибуты символы данного правила (кактерминальные, так и нетерминальные) нумеруются от 0 (для символалевой части). При ссылке на глобальные атрибуты надо иметь в виду,что атрибуты имеют области видимости на дереве разбора.
Областью видимости атрибута вершины, помеченной N, является все поддерево N, заисключением его поддеревьев, также помеченных N.Исполнение операторов семантической части правила привязывается к обходу дерева разбора сверху вниз слева направо. Для этого каждыйоператор может быть помечен меткой, состоящей из номера ветви правила, к выполнению которой должен быть привязан оператор, и, возможно, одного из суффиксов A, B, E, M.Суффикс A задает выполнение оператора перед каждым вхождением синтаксической конструкции, заключенной в скобки повторений ( ).Суффикс B задает выполнение оператора после каждого вхождения синтаксической конструкции, заключенной в скобки повторений ( ).
Суф-10.2. СИСТЕМА YACC187фикс M задает выполнение оператора между вхождениями синтаксической конструкции, заключенной в скобки повторений ( ). Суффикс E задает выполнение оператора в том случае, когда конструкция, заключенная в скобки [ ], отсутствует.Пример использование меток атрибутных формул:D ::= ’d’ =>$0.y:=$0.x+1.A ::= B (C) [D] =>$2.x:=1;2M: $2.x:=$2.x+1;$3.x:=$2.x;3E: $3.y:=$3.x;3: writeln($3.y).Процедура writeln напечатает число вхождений символа C в C-список,если D опущено.
В противном случае напечатанное число будет на единицу больше.10.2Система YaccВ основу системы Yacc положен синтаксический анализатор типа LALR(1),генерируемый по входной (мета) программе. Эта программа состоит изтрех частей:%{Си-текст%}%token Список имен лексем%%Список правил трансляции%%Служебные Си-подпрограммыСи-текст (который вместе с окружающими скобками %{ и %} можетотсутствовать) обычно содержит Си-объявления (включая #include и #define),используемые в тексте ниже. Этот Си-текст может содержать и объявления (или предобъявления) функций.Список имен лексем содержит имена, которые преобразуются Yaccпрепроцессором в объявления констант (#define).
Как правило, эти имена используются как имена классов лексем и служат для определенияинтерфейса с лексическим анализатором.Каждое правило трансляции имеет видЛевая_часть : альтернатива_1 {семантические_действия_1}| альтернатива_2 {семантические_действия_2}188ГЛАВА 10. СИСТЕМЫ АВТОМАТИЗАЦИИ ПОСТРОЕНИЯ ТРАНСЛЯТОРОВ|...| альтернатива_n {семантические_действия_n};Каждое семантическое действие – это последовательность операторов Си. При этом каждому нетерминалу может быть сопоставлен одинсинтезируемый атрибут. На атрибут нетерминала левой части ссылкаосуществляется посредством значка $$, на атрибуты символов правойчасти – посредством значков $1, $2 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
