Карпов - Основы построения трансляторов (2005) (943926), страница 15
Текст из файла (страница 15)
1.1, как было сказано ранее, состоит в том, что надо вычислять требуемые выходы для любой входной цепочки из потенциально бесконечного их множества, составляющего входной язык. Но и на вход блока генерации поступают те же цепочки языка, и каждая цепочка имеет свое собственное дерево вывода (и даже, возможно, не одно в двусмысленных грамматиках!).
Поэтому те >ке проблемы, связанные с бесконечностью количества входных цепочек„стоят и при разработке алгоритма работы блока генерации выхода. Каким же образом эти проблемы могут быть решены с использованием дерева вывода? ПРИМЕР 3.1. Рассмотрим конкретный пример — грамматику б7 арифмети- ческих выражений из главы 2: 6; ~ = б7. Š— и ~ (Е) ~ Е+Е! Š— Е ~ ЕхЕ ~ Е!Е и дерево вывода в ней цепочки 2х(3+1) на рис. 3.3, а.
Здесь под терминальным символом г грамматики будем понимать любое число. Задачей трансляции таких выражений будем считать вычисление значения выражения, полученного на входе. Искомая семантическая функция должна каждому выражению из бесконечного их множества сопоставить его значение. Естественно выполнять это сопоставление на основе структуры выражения: хотя выраженгсй бесконечна яного, но тгтов копсирукггий, котОрые мог ~пе комйингфОВигггься 6 Вьц?Йжениях~ конечное числО это су мма двух подвыражений Е+Е, их произведение ЕхЕ и т. д. (и все они задаются грамматикой!).
Свяжем с каждой нетерминальной конструкцией Е, имеющей смысл "выра>кение". семантический параметр — численное значение соответствующего выражения„которое выводится из данной конструкции (такие параметры называются семантическими атрибутами). Очевидно, что вычисление значения всего выражения, которое выводится из корня дерева, может быть выполнено последовательным вычислением значений частных подвыра>кений на основе их структуры. В частности, если выра>кение является суммой двух подвыражений, то естественно семантический атрибут (значение) этого выражения вычислять как сумму семантических атрибутов «значений) составляющих его подвыражений (рис.
3.3, о). Поэтому семантическую функцию, сопоставляющую значение каждому выражению, можно определить как последовательно вычисляемую по структуре дерева вывода„и на каждом шаге этих вычислений правила преобразований семантических атрибутов определяются типом узла дерева вывода, для которого этот шаг выполняется. Иными словами, правила преобразования семантических атрибутов определяются продукциями порождающей грамматики. а) Рис. 3.3. Примеры дерева вывода: а) дерево вывода цепочки 2~(3+1) в грамматике 87, б) аннотированное дерево вывода со значениями семантических атрибутов Итак, хотя количество возможных предложений на входе генератора — бесконечное количество, и также бесконечно число структур — деревьев вывода, которые связывает с этими предложениями блок синтаксического анализа, типов узлов (т.
е. продукций грамматики) в деревьях вывода всех возможных предложений языка конечное число. Если для каждой продукции грамматики определить, как одни семантические атрибуты выражаются через другие, то семантические вычисления значения (смысла) входного предложения языка могут быть построены на основе дерева вывода, восстановленного для этого Глава 3 Т а бл и ц а 3.1. Атрибутная грамматика арифметических выражений Атрибутная грамматика табл.
3.1 очевидна. Различные экземпляры конструкций языка (нетерминалы) в продукциях снабжены индексами, если необходимо различать их параметры в соответствующем семантическом правиле. С точки зрения синтаксиса все они, конечно. неразличимы и представляют один и тот же класс с одними и теми же свойствами (набором параметров).
Заметим, что если в левой части таблицы знаки операций — это просто символы, то в правой части — это действия в семантических вычислениях. Семантические правила атрибутной грамматики определяют значение семантического атрибута левой части продукции как функцию семантических атрибутов правой части (такие атрибуты называются синтезированными). Это представляется совершенно естественным. Действительно, пусть Хо — +Х~Х ...
Х~. — одна из продукций КС-грамматики. Это значит, что структура нетерминала (конструкции) Хо определяется как состоящая из подконструкций Х~„Х., ..., Х~ . В этом случае естественно определить и семантические характеристики целого (конструкции Хв) как функцию семантических характеристик составляющих это целое частей (т. е. Х). Поэтому семантические правила для этой продукции будут определять параметры нетерминала левой части как функцию параметров (атрибутов) нетерминалов правых частей. На дереве вывода узел вида (рис. 3.4, а) будет определять вычисление семантических атрибугов вида (рис. 3.4, ~. Итак, семантические атрибуты, связанные с корнем дерева и определяющие зиачение всего предложения. будут определяться последовательно по этому дереву снизу вверх.
В общем случае каждому нетерминальному символу порождающей грамматики в атрибутной грамматике может быть сопоставлено несколько семантических атрибутов произвольных типов. В качестве атрибутов могут быть использованы типы. строки, таблицы, адреса памяти — любые подходящие структуры данных. С каждой продукцией контекстно-свободной грамматики связываются правила вычисления атрибутов входящих в продукцию симво- Структура и значение лов (семантические правила). Семантические правила, соответствующие данной продукции, применяются для всех вхождений этой продукции в дерево вывода.
а) Рис. 3.4. а) Узел деРева вывода: б) вычисление синтезированных атрибутов на нем; в) замещающая семантическая структура Очевидно, что для задачи генерации выхода транслятора уже не важна синтаксическая структура дерева вывода — она должна быть заменена структурой функциональных зависимостей семантических атрибутов всех узлов синтак- ического дерева (рис.
3.4, в), которую можно назвать замещающей семантической структурой. Кроме того, при трансляции удобно иметь возможность выполнения в каждом узле дерева вывода действий, связанных с изменениями глобальных семантических параметров, если они необходимы. Е-например, в некоторых узлах дерева вывода может использоваться генерация (печать, вывод) выходного текста непосредственно при построении этого дерева. Г1о замещающей семантической структуре, полученной по дереву вывода или -:го части, вычисление семантических атрибутов может выполняться в любом жа добном порядке. Важно только, что значение атрибута «1> может вычисляться только после того, как будут вычислены значения всех атрибутов, от которых зависит ф.
В общем случае нет необходимости сохранять при трансляции все ;интаксическое дерево входной цепочки. прежде чем начинать выполнять ;смантические действия. Они могут выполняться сразу, как только необходимая часть синтаксического дерева построена. В некоторых случаях само . пределение семантических действий учитывает порядок построения дерева вывода в процессе синтаксического анализа (фактически того.
что семанти-«еские действия, связанные с уже построенной частью синтаксического дереза, выполнены). Глава 3 3.2.2. Синтезированные и унаследованные атрибуты Д. Кнут определил в своей работе по формализации семантики формальных языков ~К681 два типа семантических атрибутов синтаксических конструкций (нетерминалов): сиотезг~ровстоью и уиаследовалиые.
Синтезированные атрибуты нетерминала определяются через атрибуты его потомков. В дереве вывода они вычисляются снизу вверх. Унаследованные атрибуты нетерминала определяются через семантические атрибуты непосредственного его предка. В дереве вывода они вычисляются сверху вниз. Если говорить в терминах продукций, то синтезированные атрибуты — это такие атрибуты нетерминала в левой части продукции, значения которых определяются через значения атрибугов грамматических символов правой части. Унаследованные атрибуты — это те атрибуты символов правой части продукции, значения которых определяются через атрибуты других символов этой >ке продукции. Разницу между этими двумя типами атрибутов можно понять так. Значения синтезированных атрибутов некоторой конструкции языка зависят от того, из чего строится эта конструкция.
Значения унаследованных атрибутов синтаксической конструкции зависят от того, в какую другую конструкцию и каким образом входит данная конструкция. Например, тип переменной зависит не от того, какое у нее имя, а от того, в какую конструкцию описания (1п$ либо геа1) входит ее имя. Другой пример: вес цифры в дробной части числа зависит от ее положения и т.
и. В примере грамматики арифметических выражений (табл. 3.1) потребовались только синтезированные атрибуты, и в дереве вывода (см. рис, З.З, б и 3.4) они вычислялись именно снизу вверх. Рассмотрим пример, показывающий необходимость использования унаследованных атрибутов. Следующая КС-грамматика с начальным символом О: Т вЂ” мп1 Т-+геа1 1.-+Л, г Л вЂ” и порождает цепочки вида: йп$ г, г, г, г или гез1 г, г, г, т. е. это грамматика, порождающая объявления типов переменных. При трансляции этих цепочек тип каждой переменной, стоящей после служебного слова 1п$ или геа1, должен быть запомнен в таблице имен. Решает эту задачу атрибутная грамматика объявлений типов, представленная в табл.
3.2. Гпава 3 Пусть то значение, которое мы хотим приписать каждой двоичной цепочке, — это численное значение соответствующего двоичного числа. В частности, по входной цепочке 110.01 компилятор должен выдать величину 6.25 (в машинном представлении). Припишем каждому нетерминалу грамматики 6з 2 семантические атрибуты следующим образом (табл. 3.3). Таблица 3.3. Соответствие нетерминала атрибуту Примечание Нетерминал Атрибут 1 — целочисленное значение, приписываемое двоичному символу, представленному В 1 — целочисленное значение, приписываемое цепочке двоичных символов, выведенных из Л 1 — длина цепочки двоичных символов, выведенных из Ь 1> — численное значение, приписываемое двоичной це- почке символов, выведенных из 5 Построим атрибутную грамматику этого языка (табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
