А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 19
Текст из файла (страница 19)
Их сумма, 7, заменяет 52+, и мы получаем строку 97-3*. Теперь крайний слева оператор — знак "минус", а его операндами являются 9 и 7. Заменяя их результатом вычитания, мы получаем строку 23*. Символ умножения применяется к 2 и 3 и дает окончательный результат, равный б. Б 2.3.2 Синтезированные атрибуты Идея назначения значений программным конструкциям — например, значений и типов выражений -- может быть выражена в терминах грамматики. Мы назначаем атрибуты терминалам и нетерминалам, затем присоединяем к продукциям грамматики правила, которые описывают, каким образом происходит вычисление атрибутов в узлах дерева разбора, где рассматриваемая продукция используется для связи узла с дочерними узлами. Синтаксически управляемое определение связывается 1) с каждым грамматическим символом, множеством атрибутов; 2) с каждой продукцией, множеством семантических правил для вычисления значений атрибутов, связанных с символами продукции, 93 2З.
Синтаксически управляемая трансляция Атрибуты могут вычисляться следующим образом. Для данной входной строки х строится дерево разбора для х. Затем для вычисления атрибутов в каждом узле дерева разбора применяются семантические правила описанным далее образом.
Предположим, что узел И в дереве разбора помечен грамматическим символом Х. Обозначим как Х.а значение атрибута а символа Х в этом узле. Дерево разбора с указанием значений атрибутов в каждом узле называется аннотированным (аппо1агео) деревом разбора. Например, на рис. 2.9 показано аннотированное дерево разбора для 9-5+ 2 с атрибутом 1, связанным с нетерминалами ехрг и геге. Значение атрибута корня дерева 95-2+ представляет собой постфиксную запись для 9-5+2. Вскоре мы увидим, как вычисляются эти выражения. 1егвэ = 2 1 2 ехал 9 — )егтз = э 5 гегии = 9 Рнс. 2.9. Значения атрибутов в узлах дерева разбора Атрибут называется синтезированным, если его значение в узле дерева разбора М определяется на основании атрибутов дочерних по отношению к АГ узлов и самого узла М.
Синтезированный атрибут обладает тем требующимся свойством, что он может быть вычислен путем единственного восходящего прохода по дереву разбора. В разделе 5.1.1 мы рассмотрим другой важный тип атрибутов — наследуемые атрибуты. Говоря неформально, значения наследуемых атрибутов вычисляются на основании значений атрибутов в самом узле, родительском и сестринских узлах в дереве разбора. Пример 2.10.
Аннотированное дерево разбора на рис. 2.9 основано на синтаксически управляемых определениях для трансляции выражений, состоящих из цифр, разделенных знаками "плюс" и "минус", в постфиксную запись. Каждый нетерминал имеет строковый атрибут 1, который представляет постфиксную запись для выражения, генерируемого этим негерминалом в дереве разбора. Символ ~~ в семантическом правиле представляет собой оператор конкатенации строк. Постфиксная форма цифры — это сама цифра; например, семантическое правило продукции гепл — 9 определяет, что при ее использовании гегел в узле дерева 94 Глава 2. Простой синтаксически управляемый транслятор Рис. 2.!О. Синтаксически управляемые определения для трансляции иификсных выражений в постфиксные разбора представляет собой просто 9.
Все остальные цифры транслируются аналогично. В качестве другого примера при использовании продукции ехрг — гегги значение гегпзл становится значением ехргл Продукция ехрг — ехрг + гегиз порождает выражение, содержащее оператор "плюс".4 Левый операнд оператора сложения — ехргг, а правый — геглз. Семантическое правило данной продукции ехрг.1 = ехрггХ )! гегт.1 !! + определяет значение атрибута ех)эгл путем конкатенации постфиксных форм ехрг!.! и гегпзд левого и правого операндов, к которым затем добавляется знак "плюс".
Это правило является формализацией определения постфиксного выражения. и 2.3.3 Простые синтаксически управляемые определения Синтаксически управляемое определение в примере 2.10 имеет следующее важное свойство: строка, представляющая трансляцию нетерминала в заголовке каждой продукции, является конкатенацией трансляций нетерминалов в теле продукции в том же порядке, в котором они встречаются в продукции, с небольшими необязательными дополнительными строками.
Синтаксически управляемое определение с такими свойствами называется лроспзым. В этом и многих других правилах один и тот же нетерминал !здесь — ехрг) встречается несколько раз. Цель нижнего индекса 1 в ехрг, — помочь отличить два появления ехрг в продукции; "Г' не является частью нетерминала (см. врезку "Соглашения для различения используемых нетерминалов"). 95 2.3. Синтаксически управляемая трансляция Соглашения для различения используемых нетерминалов В правилах нам часто необходимо различать несколько использований одного и того же нетерминала в заголовке н в теле продукции (см.
пример 2.10). Причина заключается в том, что в дереве разбора различные узлы, помеченные одним и тем же нетерминалом, обычно имеют разные значения для трансляции. Мы примем следующее соглашение: нетерминалы используются в заголовке продукции без индексов, а в теле продукции — с различными индексами. Это все один и тот же нетерминал, и индекс не является частью его имени. Однако вы должны понимать разницу между примерами конкретной трансляции, в которых используется указанное соглашение, и обобщенными продукциями наподобие А — Хм Хз,...,Х„, где символы Х с индексами представляют произвольный список грамматических символов, а не экземпляров одного конкретного нетерминала с именем Х. Пример 2.11.
Рассмотрим первую продукцию и семантическое правило, пред- ставленные на рис. 2.10: ПРОдчкция СЕМАНТИЧЕСКОЕ ПРАВИЛО (2.5) ехрг — ~ ехр«1 + 1етт ехр«Л = ехртзд )! 1етт.г )) '+' Здесь трансляция ехргг представляет собой конкатенацию трансляций ехр«, и 1егт, за которыми следует символ +. Обратите внимание, что ехрг! и 1егт находятся в одном и том же порядке и в продукции, и в семантическом правиле. Перед и между их трансляциями нет никаких дополнительных символов; в данном примере имеется только один дополнительный символ за ними.
и При рассмотрении схем трансляции мы увидим, что простое синтаксически управляемое определение может быть реализовано путем печати только дополнительных строк в порядке их появления в определении. 2.3.4 Обходы дерева Обходы дерева будут использоваться для описания вычисления атрибутов и для указания выполнения фрагментов кода в схеме трансляции. Обход (1гачегза!) дерева начинается с его корня и посещает каждый узел дерева в некотором порядке. Обход в глубину (бергп-бгз1) начинается с корня н рекурсивно посещает дочерние узлы каждого узла в любом порядке, не обязательно слева направо. Такой обход называется обходом "в глубину", так как он сперва посещает все непосе- 96 Глава 2. Простой синтаксически управляемый транслятор щенные дочерние узлы, насколько это возможно, т.е.
посещает сначала все узлы, находящиеся на наибольшем удалении (" глубине" ) от корневого. Процедура ом(1 (Х) на рис. 2.11 представляет собой обход в глубину, посещающий дочерние узлы в порядке слева направо, как показано на рис. 2.12.
При таком обходе действия по вычислению трансляции в каждом узле должны включаться непосредственно перед тем, как будет покинут данный узел (т.е. после того, как будут корректно вычислены трансляции в дочерних узлах). В общем случае действия, выполняемые обходом, могут быть любыми, в том числе отсутствовать вообще. ргоседцге ля~(цобе Ж) ( (ог ( каждый дочерний узел С' узла Ж в порядке слева направо ) ( изй(С); Вычислить семантические правила в узле Х; Рис. 2.11.
Рис. 2.1 !. Обход дерева в глубину Рис. 2.!2. Пример обхода дерева в глубину Синтаксически управляемое определение не задает конкретный порядок вычисления атрибутов в дереве разбора. Пригоден любой порядок, который вычисляет атрибут а после всех атрибутов, от которых зависит а. Синтезированные атрибуты могут быть вычислены при любом восходящем (Ьопогп-цр) обходе дерева, т.е, обходе, который вычисляет атрибуты узла после вычисления атрибутов дочерних узлов. В общем случае при наличии и синтезированных, и наследуемых атрибутов вопрос порядка вычисления становится достаточно сложным; см.
раздел 5.2. 2.3. Синтаксически управляемая трансляция Обходы в прямом и обратном порядке Обходы дерева в прямом и обратном порядке — это два важных частных случая обхода в глубину, при которых мы посещаем дочерние узлы каждого узла слева направо. Зачастую дерево обходится для выполнения некоторых определенных действий в каждом узле.
Если действие выполняется, когда мы впервые попадаем в узел, то такой обход можно назвать обходом в прямом порядке (ргеогдег). Аналогично, если действие выполняется непосредственно перед тем, как узел покидается, такой обход называется обходом в обратном порядке (роз1огдег). Процедура ива (Аг) на рис. 2.11 представляет собой пример обхода в обратном порядке. Обходы в прямом и обратном порядке определяют соответствующие упорядочения узлов, основанные на том, когда выполняются действия в узлах. Прямой порядок (под)дерева с корнем Я представляет собой )У, за которым следуют прямые порядки поддеревьев всех его дочерних узлов (если таковые имеются) слева направо.
Обратный порядок (под)дерева с корнем М представляет собой обратные порядки поддеревьев всех его дочерних узлов (если таковые имеются) слева направо, за которыми следует узел Ж. 2.3.5 Схемы трансляции Синтаксически управляемое определение на рис. 2.10 строит трансляцию путем присоединения в качестве атрибутов строк к узлам дерева разбора. Теперь мы рассмотрим альтернативный подход, который не требует работы со строками; он инкрементно создает ту же самую трансляцию путем выполнения программных фрагментов. Схема синтаксически управляемой трансляции представляет собой запись для определения конкретной трансляции путем присоединения программных фрагментов к продукциям грамматики.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
