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

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

Двухуровневые грамматики W-грамматики (с их помощью описан язык ALGOL-68),

Венский метаязык (описан PL/1),

Атрибутные. Ниже рассмотрен один из перечисленных видов грамматик, а именно – атрибутные грамматики [12]. Атрибут- это свойство объекта; под атрибутом в грамматиках понимаются значение или семантический смысл (значимость) объекта. Атрибутная грамматика – это КС-грамматика, с узлами дерева вывода которой связаны атрибуты (семантические правила). КС-правилам сопоставляются правила вычисления атрибутов. Правило вычисления значений атрибутов, соответствующее данному КС-правилу, применяется для всех вхождений этого правила в дерево вывода.

Атрибуты могут быть двух видов - синтезированные и унаследованные.

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

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

Формально атрибутная грамматика – это пятёрка объектов:

, где

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

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

- начальный выделенный символ

- это правила вывода

,где

- это множество атрибутов

= где

- множество унаследованных атрибутов

- множество синтезированных атрибутов

 =

=

=

 

Унаследованные атрибуты левой части КС-правила и синтезированные атрибуты правой части получают значения, переданные от окружающих ветвлений дерева вывода. Правила вычисления значений атрибутов, связанные с каким-либо КС-правилом, определяют метод вычисления значений других атрибутов, а именно – унаследованных атрибутов правой части и синтезированных атрибутов левой части. Значения этих атрибутов передаются окружающим узлам. Или иначе можно сказать, что синтезированные атрибуты некоторого узла содержат информацию, которая синтезируется из поддерева данного узла и передаётся вверх к корню дерева вывода, а в унаследованных атрибутах хранится информация, передаваемая вниз, от корня дерева к его листьям. Унаследованные атрибуты характеризуют контекст, в котором находится его узел и его поддерево. Правила вычисления значений атрибутов записываются разными способами. Аппарат атрибутных грамматик не является законченным методом формального описания языка. Для того, чтобы им можно было воспользоваться, его необходимо дополнить методом записи правил вычисления значений атрибутов.

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

Контекстно-свободная грамматика имеет вид:

, , 0

Здесь нетерминал S используется для вывода числа в двоичной системе записи, нетерминал L – для вывода списка бит (0 и 1), нетерминал B – позволяет вывести один бит ( 0 или 1). В эту грамматику включим атрибуты (семантические правила), позволяющие в процессе анализа правильной цепочки получить значение двоичного числа в десятичной системе счисления. Для этого каждому нетерминалу припишем атрибуты следующим образом:

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

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

С учетом этих правил построим атрибутную грамматику:

;

L B ,

B 0

B 1

Здесь индексы у нетерминалов L1 и L2 использованы для того чтобы различить вхождения одноименных нетерминалов в правой и левой частях правил вывода.

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

101.01 (5.25)

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

Математически мы рассматриваем перевод как множество пар, где первый элемент принадлежит множеству объектов, которые надо перевести, а второй элемент — множеству объектов, которые яв­ляются результатами перевода. В переводах первый элемент пары — это цепочка входного языка, а второй элемент — последовательность, представляющая резуль­тат перевода входной цепочки. Когда эти пары получаются с по­мощью некоторой грамматики, перевод иногда называют синтакси­чески управляемым переводом.

В этом разделе мы используем понятие последовательности ак­тов как основу одного класса синтаксически управляемых перево­дов. Вначале мы установим, как последовательность действий можно использовать для задания пары.

П усть дана последовательность актов, состоящая из входных символов и символов действия, мы будем исполь­зовать термин входная последовательность или входная цепочка для обозначения последовательности входных сим­волов, полученной из последовательности актов путем вычеркивания всех символов действия, и термин подпос­ледовательность действий для обозначения последователь­ности символов действия, полученной из последовательности актов путем вычеркивания всех входных символов. Мы гово­рим, что входная подпоследовательность образует пару с подпоследовательностью действий.

При этом определении для последовательности актов

обсуждавшейся в прошлом разделе, входная цепочка а+b*с образует пару с подпоследовательностью действий

Для данной транслирующей грамматики множество пар можно получить, образуя пары из входной подпоследовательности каждой последовательности актов и подпоследовательности действий. Это множество пар называется переводом, определяемым данной транс­лирующей грамматикой.

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

Некоторые транслирующие грамматики обладают тем свойством, что одна и та же входная цепочка может встретиться более чем в одной последовательности актов или образовывать пары с более чем одной подпоследовательностью действий. Отметим, что нас интересуют в основном только те случаи, когда каждая вход­ная подпоследовательность является частью одной последователь­ности актов и, следовательно, имеет только один перевод.

Говоря о переводах, мы часто используем понятие входной грам­матики:

Е сли дана транслирующая грамматика, то грамматика, по­лученная путем вычеркивания всех символов действия из пра­вил этой грамматики, называется входной грамматикой для этой транслирующей грамматики. Язык, определяемый вход­ной грамматикой, называется входным языком.

В примере перевода инфиксной записи в польскую входная грам­матика — это просто грамматика, определяющая инфиксные выра­жения. Для грамматики, иллюстрировавшей определение трансли­рующей грамматики, входной грамматикой будет

Для любой транслирующей грамматики входной язык является не чем иным, как множеством входных цепочек. Таким образом, входная грамматика, описывает множество цепочек, для которых транслирующая грамматика определяет переводы.

Хотя мы определили входную грамматику, исходя из трансли­рующей грамматики, обычно ход событий при разработке компиля­тора несколько иной. Вначале обрабатываемый язык описывается входной грамматикой, а затем в правила этой грамматики вставля­ются символы действия для описания требуемого процесса обра­ботки.

Для данной транслирующей грамматики выходную грамматику, или грамматику действий, можно получить вычеркиванием вход­ных символов. Таким образом, транслирующую грамматику можно рассматривать как переводящую с одного КС-языка, входного языка, на другой КС-язык, выходной язык, или язык действий. Однако понятие грамматики действий далее никакой роли не играет.

В случае грамматики цепочечного перевода мы считаем после­довательность символов действия синонимом соответствующей вы­ходной цепочки. В примере перевода инфиксной записи в польскую мы рассматриваем последовательность действий {a}{b}{с}{*}{+} как синоним выходной последовательности abc*+ и любую из этих последовательностей символов можно назвать переводом вход­ной цепочки а+b*с. Таким образом, грамматику, транслирующую в цепочки можно интерпретировать как способ определения перевода со входного языка на выходной язык.

Перевод можно определить многими различными транслирую­щими грамматиками. Например, перевод инфиксных выражений в польскую запись, можно также описать при помощи следующей транслирующей грамматики:

<T> в правиле 2 порождает правый операнд оператора +. Значит, подходящее место для + будет не­посредственно за <Т>. Аналогичные соображения применимы к * в правиле 5. Левый вывод последовательности актов для входной последовательности (а+b)*с, согласно этой грамматике, будет та­ким:

Пример: синтезируемые атрибуты

В предыдущих разделах мы рассматривали переводы цепочек сим­волов в цепочки символов. Используемые символы принадлежали некоторым конечным множествам, и в понятие символа не включа­лось представление о том, что он должен состоять из двух частей: значения и класса. В действительности грамматики, транслирующие цепочки, способны описывать перевод только той компоненты сим­вола, которая указывает его класс. Сейчас мы расширим понятие транслирующей грамматики, чтобы включить в перевод и значение символа. Расширенное понятие называется «атрибутной граммати­кой». Здесь мы приводим конкретную атрибутную грамматику, чтобы проиллюстрировать понятие «синтезируемого атрибута».

Главная идея, лежащая в основе понятия атрибутной граммати­ки, состоит в том, что значения символов сопоставляются всем вершинам дерева вывода, как терминальным так и нетерминальным. Отношения между входными и выходными значениями выражаются по принципу «от правила к правилу»; при этом значения находятся в вершинах дерева. Чтобы проиллюстрировать, как можно было бы выразить такие отношения, рассмотрим простои пример.

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

где с — лексема, представляющая константу; ее значением явля­ется значение константы, построенное лексическим блоком. Рас­смотрим теперь проблему проектирования синтаксического бло­ка, который допускает арифметические выражения, построенные из символов данного входного множества, и выдает численные зна­чения этих выражений. Соответствие между компонентами входов и выходов, представляющих их классы, можно выразить следующей грамматикой, транслирующей в цепочки

(<S> — ее начальный символ):

Значение выходного символа ОТВЕТ должно быть числом. Требуе­мое отношение между значениями входных лексем и значением вы­ходной лексемы ОТВЕТ можно выразить словами «значение лексемы ОТВЕТ — это числовое значение входного выражения». Назначе­ние данного примера состоит в том, чтобы найти математический способ выражения отношения, описанного этой фразой.

Рассмотрим теперь конкретную входную цепочку , где значения входных лексем, выданных лексическим бло­ком, указаны индексами. Этой входной цепочке должна, конечно, соответствовать выходная цепочка . На рис. 1.а пока­зано дерево вывода, соответствующее этой входной цепочке. Мы ищем метод, посредством которого входную цепочку и дерево выво­да можно использовать для определения значений выходных сим­волов.

Самый естественный способ определения значения данного вход­ного выражения состоит в определении значения каждой его части. Так как каждое вхождение нетерминалов <E>, <T> и <Р> в дереве вывода представляет некоторое подвыражение входного выражения, естественно приписать данному вхождению нетерминала числовое значение порождаемого им подвыражения. На рис. 1.б показано дерево, изображенное на рис. 1.а, на котором каждый не­терминал <E>, <T> и <Р> помечен значением соответствующего под­выражения, а выходной символ—требуемым выходным значением.

Чтобы определить, как расставлять значения на дереве вывода, полученном по данной грамматике, вначале определим, как полу­чить значение любой нетерминальной вершины, если даны значения ее прямых потомков. С этой целью сопоставим каждому правилу грамматики для <E>, <T> и <Р> правило вычисления значения вершины, соответствующей нетерминалу левой части продукции, по данным значениям ее прямых потомков, соответствующих сим­волам правой части правил грамматики. (Для краткости там, где речь идет одновременно о правилах вычисления значений и правилах грамматики, мы будем называть первые просто правилами, а вторые — продукциями.)

Например, правило вычисления значений для продукции

состоит в том, что значения нетерминала <E> в левой части равно сумме значения нетерминала <E> в правой части и значения нетер­минала <T>. Чтобы применить это правило к левому, заключенному в скобки вхождению <E>, в дереве вывода нашего примера, заме­тим, что значение <E> в правой части равно 3, а значение <T> рав­но 9. Отсюда следует, что значение <E> в левой части равно 12, и можно приписать значение 12 соответствующей вершине дерева.

Правило для продукции состоит в том, что значение <E> равно значению <T>. Правило для продукции состоит в том, что значение <T> в левой части равно произведению значения <T> в правой части и значения <P>. Правило для состоит в том, что значение <T> равно значению <P>. Прави­ло для состоит в том, что значение <P> равно значе­нию <E>. Правило для состоит в том, что значение <P> рав­но значению с.

И наконец, продукцию мы снабдим пра­вилом, что значение символа ОТВЕТ равно значению <E>.

В рассматриваемом примере правила, сопоставляемые продук­циям, определяют как вычислять численные значения выражений. В этом смысле они отражают «значение» или «смысл» продукции. Од­нако технику сопоставления правил продукциям можно использо­вать для определения значений, которые не обязательно отражают явное значение входной цепочки. Например, с помощью правил для продукций можно с каждой вершиной дерева связать элемент не­которой таблицы.

Продолжим рассмотрение нашего примера. Для того чтобы вы­разить приведенные выше правила математически более строго, можно в каждой продукции дать разные имена разным встречаю­щимся в ней значениям, а затем сформулировать соответствующие ей правила при помощи этих имен. Например, продукцию 2 и пра­вило вычисления значения <E> можно записать так:

где символ присваивания указывает, что атрибут р получает зна­чение выражения в правой части (т. е. q+r).

Остальные продукции и соответствующие им правила можно записать так:

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

Приведенные выше продукции вместе с соответствующими пра­вилами вычисления значений являются примерами «атрибутных правил» или «атрибутных продукций» и, взятые вместе с начальным нетерминалом <S>, образуют «атрибутную грамматику». В этой терминологии значения вышеприведенных символов называются «атрибутами». Далее мы увидим, что значение на самом деле может быть вектором атрибутов.

В нашем примере значение атрибута каждого нетерминала опре­деляется символами, расположенными в дереве вывода под этим нетерминалом. Такое «восходящее» вычисление выражается в том, что правила вычисления атрибутов нетерминалов, ассоциированные с продукциями, указывают, как вычислять атрибуты в левой части продукции по данным атрибутам символов правой части. Атрибуты, значения которых получаются таким восходящим способом, т. е. снизу вверх, традиционно называются «синтезируемыми» атрибута­ми. В следующем разделе приводится пример атрибутов нетермина­лов, которые передаются и вычисляются по дереву вывода сверху вниз.

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

Пример: наследуемые атрибуты

Теперь мы приведем пример, показывающий, каким образом можно определить атрибутную информацию, так чтобы она распространя­лась вниз по дереву вывода. Рассмотрим следующую грамматику с начальным символом (описание):

Эта грамматика порождает описания, подобные тем, что встречают­ся во многих языках программирования.

Предположим, что существует лексический блок, задающий три лексемы:

V ТИП,

где лексема V обозначает переменную и ее значение является ука­зателем на соответствующий этой переменной элемент таблицы имен; ТИП — лексема со значением, определяющим, какой из типов, ВЕ­ЩЕСТВЕННЫЙ, ЦЕЛЫЙ или ЛОГИЧЕСКИЙ, должен быть по­ставлен в соответствие переменным из данного списка.

При обработке описания каждой переменной синтаксический блок вызывает процедуру УСТАНОВИТЬ-ТИП, которая помещает один из типов, ВЕЩЕСТВЕННЫЙ, ЦЕЛЫЙ или ЛОГИЧЕСКИЙ, в надлежащее поле элемента таблицы имен, соответствующего дан­ной переменной. Вызов УСТАНОВИТЬ-ТИП лучше всего осущест­вить сразу после того, как переменная поступила на вход синтакси­ческого блока. Такая синхронизация описывается следующей грам­матикой, транслирующей в цепочки, где для обозначения вызова процедуры УСТАНОВИТЬ-ТИП используется символ действия {УСТАНОВИТЬ-ТИП}:

Предположим, что процедура УСТАНОВИТЬ-ТИП имеет дна аргумента: указатель на элемент таблицы имен, соответствующий переменной, и тип переменной. Тогда вызов процедуры УСТАНО­ВИТЬ-ТИП можно записать так:

УСТАНОВИТЬ-ТИП (указатель, тип). Мы хотим ввести в вышеприведенную грамматику атрибуты и пра­вила их вычисления, чтобы в последовательностях актов входные символы были представлены вместе с их значениями, играющими роль атрибутов, а вхождения символов действия

{УСТАНОВИТЬ-ТИП} имели по два атрибута, представляющих аргументы соответ­ствующего вызова процедуры УСТАНОВИТЬ-ТИП. Тогда вхожде­ния УСТАНОВИТЬ-ТИП будут иметь такой вид:

Символ действия {УСТАНОВИТЬ-ТИП} с его атрибутами хо­рошо иллюстрирует разницу между атрибутом и значением. У этого-символа имеется два атрибута — указатель и тип, но только одно-значение, которым является пара (указатель, тип). Таким образом, понятие атрибута — это уточнение понятия значения. Так как мы переходим к особенностям модели атрибутной грамматики, теперь, мы имеем дело исключительно с атрибутами.

Возвращаясь к задаче порождения требуемой атрибутной последовательности актов, рассмотрим как вхождения

{УСТАНОВИТЬ-ТИП} получают свои атрибуты. В правиле 1 это делается просто, так как атрибуты символа действия {УСТАНОВИТЬ-ТИП} можно, получить, используя входные символы ТИП и V, входящие в это правило. В правиле 2 ТИП не доступен, и его нужно как-то пере­дать, используя атрибуты нетерминала. Для этой цели мы снабдим нетерминал (список переменных) атрибутом, который будет представлять тип. Требуемая последовательность актов будет порож­даться следующими правилами с атрибутами:

Запись означает, что t присваивается одновременно t1 и t2. На рис. 2 показано атрибутное дерево вывода последователь­ности

определяемое данной грамматикой.

Заметим, что на рис. 2, чтобы получить значения атрибутов, соответствующие вхождениям нетерминала (список переменных), используются символы, расположенные выше в дереве вывода, или символы, входящие в ту же правую часть правила. Входной символ ТИП определяет значение ВЕЩЕСТВЕННЫЙ, которое передается самому верхнему вхождению нетерминала (список переменных), а затем передается вниз по дереву другим вхождениям. Такой нис­ходящий характер вычисления значений атрибутов отражается в том, что каждое правило вычисления атрибутов нетерминалов, сопоставленное продукциям, указывает, как вычислять атрибуты нетерминала, входящего в правую часть продукции. Атрибуты, значения которых задаются таким нисходящим способом, принято называть «наследуемыми» атрибутами.

Сравнивая примеры этого и предыдущего разделов, мы видим, что информация о синтезируемых атрибутах распространяется вверх по дереву, тогда как информация о наследуемых атрибутах — вниз по дереву.

Синтезируемые атрибуты вычисляются по правилам, свя­занным с нетерминалами, входящими в левую часть продукции, тог­да как наследуемые атрибуты— по правилам, связанным с нетерми­налами, входящими в правую часть.

Одно заключительное замечание по поводу обозначений. В от­личие от символа {ОТВЕТ} символ действия {УСТЛНОВИТЬ-ТИП} не является заключенным в скобки выходным симво­лом. Поэтому мы использовали стандартное обозначение, поместив атрибуты символа действия вне скобок.

Атрибутные транслирующие грамматики

После того как были рассмотрены две атрибутные транслирующие грамматики, мы можем теперь точно определить, что понимается под «атрибутной транслирующей грамматикой». Оп­ределение атрибутных грамматик включает как синтезируемые, так и наследуемые атрибуты нетерминалов, проиллюстрированные на предыдущих примерах. В одной и той же грамматике допускаются оба типа атрибутов. Кроме того, в определении проводится различия между синтезируемыми и наследуемыми атрибутами символов дей­ствия. Все атрибуты символов действия в предыдущих примерах были наследуемыми и получали свои значения сверху по правилам, связанным с вхождением символа действия в правую часть продук­ции. При определении переводов в синтезируемых атрибутах символов действия нет серьезной необходимости, но они играют важную роль.

А трибутная транслирующая грамматика — это транслирующая грамматика, к которой добавляются следующие определения:

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

2. Все атрибуты нетерминальных символов и символов действия делятся на наследуемые и синтезируемые).

3. Правила вычисления наследуемых атрибутов определяются следующим образом:

а) каждому вхождению наследуемого атрибута в правую часть данной продукции сопоставляется правило вычисления значения этого атрибута как функции некоторых других атрибутов символов, входящих в правую или левую часть данной продукции;

б) задается начальное значение каждого наследуемого атри­бута начального символа.

4. Правила вычисления синтезируемых атрибутов определяются так:

а) каждому вхождению синтезируемого нетерминального ат­рибута в левую часть данной продукции сопоставляется правило вычисления значения этого атрибута как функции некоторых других атрибутов символов, входящих в левую или правую часть данной продукции;

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

В пункте 1 данного определения говорится о том, что входные символы, символы действия и нетерминальные символы должны быть атрибутными. Описывая грамматику, мы обычно записываем атрибуты в виде индексов. В описаниях каждое вхождение символа имеет по одному индексу для каждого своего атрибута.

Пункт 2 требует, чтобы каждый атрибут нетерминального сим­вола или символа действия был задан либо как синтезируемый, либо как наследуемый. Это нужно для того, чтобы указать, по каким правилам вычислять значение атрибута — из пункта 3 или из пунк­та 4. В обозначениях мы изображаем символы вместе с их атрибута­ми и говорим, к какому классу относится каждый атрибут. Напри­мер, можно записать

Для синтезируемых атрибутов символов действия утверждение, что атрибут является синтезируемым, должно сопровождаться прави­лом, соответствующим подпункту (б) пункта 4. Например, в опреде­ление атрибутов приведенного выше символа действия {УДВОЕ­НИЕ} можно включить правило вычисления синтезируемого атри­бута р

Подпункт (а) пункта 3 и подпункт (а) пункта 4 описывают пра­вила вычисления атрибутов, которые должны сопоставляться пра­вилам грамматики. Подпункт (а) пункта 3 относится к наследуемым атрибутам как нетерминальных символов, так и символов действия, поскольку и те, и другие могут встречаться в правой части правила. Для того чтобы определить правила, связанные с данной продук­цией, присвоим имя каждому атрибуту каждого символа продукции и включим эти имена в запись продукции. После этого имена атри­бутов используются в качестве переменных, при помощи которых описываются правила.

Например, если <X> имеет три атрибута, <Y> и <Z> — по два атрибута каждый, a b — один атрибут, то правило

может быть записано в виде

Если в левой части продукции синтезируемыми являются только ат­рибуты q и r, которые должны, следовательно, вычисляться по пра­вилам подпункта (а) пункта 4, а в правой части наследуемыми являются только атрибуты у и v, вычисляемые соответственно по правилам подпункта (а) пункта 3, то вышеуказанную продукцию можно дополнить такими правилами:

По традиции мы будем записывать правила в виде операторов при­сваивания. Левая часть каждого присваивания — это либо один ат­рибут, либо список атрибутов, заключенных в скобки. Правая часть всегда будет некоторым выражением. Эта запись означает, что значение выражения правой части нужно присвоить каждому атрибуту, входящему в левую часть. Так, второе из вышеуказанных правил присваивает произведение s*u обоим атрибутам r и v.

Атрибутные транслирующие грамматики используются для опре­деления атрибутных деревьев вывода, а затем — атрибутных после­довательностей актов и атрибутных переводов.

Д еревья определя­ются следующими процедурами построения:

1. По соответствующей неатрибутной грамматике построить де­рево вывода последовательности актов, состоящей из входных сим­волов и символов действия без атрибутов.

2. Присвоить значения атрибутам входных символов, входящих в дерево вывода.

3. Присвоить начальные значения наследуемым атрибутам на­чального символа дерева вывода.

4. Вычислить значения атрибутов символов, входящих в дерево вывода, повторяя следующее действие до тех пор, пока оно станет невозможным: найти атрибут, которого еще нет в дереве, но аргу­менты правила его вычисления уже имеются, вычислить значение этого атрибута и добавить его к дереву.

5. Если выполнение шага 4 приведет к тому, что значения всех атрибутов всех символов дерева окажутся вычисленными, то будем называть полученное дерево завершенным. В противном случае мы называем дерево незавершенным.

Для того чтобы проиллюстрировать описанные шаги, вернемся к рис. 2 и соответствующей грамматике. На рис. 2.а показано дерево вывода, построенное на шаге 1, на котором четырем вхождениям лексемы с присвоены значения атрибутов, как того требует шаг 2. Шаг 3 выполняется впустую, так как начальный символ не имеет атрибутов; таким образом, на рис. 2.а показан результат приме­нения первых трех шагов. Выполнение шага 4 изменяет дерево рис. 2.а на дерево рис. 2.б. Результирующее дерево является завершенным, так как все атрибуты входящих в него символов по­лучили значения.

Заметим, что пункты 3 и 4 определения атрибутной грамматики гарантируют, что для каждого атрибута нетерминального символа или символа действия имеется соответствующее правило вычисле­ния. Так как каждый символ дерева вывода либо входит в правую часть некоторой продукции (т. е. продукции, соединяющей этот сим­вол с его предком в дереве), либо является вершиной дерева (в та­ком случае это начальный символ); каждый наследуемый атрибут данного символа должен иметь правило согласно одному из подпунктов пункта З. Поскольку каждый нетерминальный символ де­рева вывода входит в левую часть некоторой продукции, подпункт (а) пункта 4 гарантирует наличие правила вычисления для каждого синтезируемого нетерминального атрибута. Наконец, подпункт (б) пункта 4 гарантирует наличие правила для каждого синтезируемого атрибута символа действия.

Важно осознавать, что, хотя для каждого атрибута, входящего в дерево вывода, существует правило его вычисления, нет никакой гарантии, что его значение действительно можно вычислить и таким образом получить завершенное дерево. Поскольку правило можно применять только после того, как получены все его аргументы, между атрибутами иногда может возникнуть круговая зависимость. Если атрибутная грамматика такова, что шаги 1—5 процедуры по­строения дерева всегда дают в итоге завершенное дерево, то она на­зывается вполне определенной или корректной. При проектировании компиляторов имеют дело только с вполне определенными грамматиками.

Пусть даны атрибутная транслирующая грамматика и дерево вывода, полученное с помощью этой грамматики. Последователь­ность атрибутных символов действия и атрибутных входных сим­волов, полученная по этому дереву вывода, называется атрибутной последовательностью актов.

А трибутная подпоследовательность действий данной атрибутной последовательности актов называется переводом атрибутной входной цепочки. Множество пар, состоящих из атрибутной входной цепочки и атрибутной последовательности действий, которые получаются по данной атрибутной грамматике, называется атрибутным переводом, определяемым этой граммати­кой. Если атрибутной транслирующей грамматике соответствует однозначная входная грамматика, то для каждой атрибутной вход­ной цепочки существует не более одного дерева вывода и не более одного атрибутного перевода.

Во многих применениях символы действия записываются путем заключения в скобки выходных символов. Это означает, что каждый символ действия представляет процедуру, которая выдает символ, содержащийся внутри скобок, используя при этом атрибуты символа действия в качестве атрибутов этого выходного символа. Когда подразумевается такая интерпретация, мы будем называть грамма­тику атрибутной грамматикой цепочечного перевода или атри­бутной грамматикой, транслирующей в цепочки, чтобы подчерк­нуть отличие от более общей интерпретации атрибутных символов действия как представляющих произвольные процедуры, которые используют атрибуты в качестве аргументов.

В случае атрибутной грамматики цепочечного перевода мы пред­ставляем себе последовательность атрибутных символов действия как синоним соответствующей цепочки выходных символов с атри­бутами. Таким образом, атрибутную грамматику цепочечного пере­вода можно интерпретировать как способ определения перевода атрибутного входного языка на атрибутный выходной язык.