Теория языков программирования и методы трасляции
Теории языков программирования и методы трансляции. Атрибутные транслирующие грамматики: методические указания к выполнению лабораторной работы №2 для студентов очной формы обучения специальности 230105 «Программное обеспечение вычислительной техники и автоматизированных систем». – Брянск: БГТУ, 2010. – 16 с.
Рекомендовано кафедрой «Информатика и программное обеспечение» БГТУ (протокол № от __.__.2010 г.)
1. Цель работы
Целью работы является получение практических навыков по составлению правил атрибутной транслирующей грамматики и проверка их правильности путем моделирования.
Продолжительность работы – 6 часов.
2. Основные понятия и термины
Транслирующие грамматики позволяют задавать соответствия между цепочками входного и выходного языков, называемые переводом. Эти соответствия отражают структурные или синтаксические свойства входных и выходных цепочек, однако при попытках их использования для описания контекстно-зависимых условий или смысла конструкций – семантики языков программирования возникают значительные трудности. Поэтому для задания семантики применяются различные приемы: W -грамматики, венский метаязык, аксиоматический и денотационный методы, а также атрибутные транслирующие грамматики.
Существует два вида записи для связанных с продукциями семантических правил — синтаксически управляемые определения и схемы трансляции. Синтаксически управляемые определения представляют собой высокоуровневые спецификации трансляции, скрывающие множество деталей реализации и освобождающие пользователя от явного указания порядка выполнения трансляции. Схемы трансляции указывают порядок, в котором выполняются семантические правила; так что эти схемы показывают определенную часть деталей реализации. Выполнение семантических правил может генерировать код, сохранять информацию в таблице символов, выводить сообщения об ошибках или выполнять какие-либо другие действия.
Синтаксически управляемое определение представляет собой обобщение контекстно-свободной грамматики, в которой каждый грамматический символ имеет связанное множество атрибутов, разделенное на два подмножества, — синтезируемые и наследуемые атрибуты этого грамматического символа. Если рассматривать узел грамматического символа в дереве разбора как запись с полями для хранения информации, то атрибут соответствует имени поля.
Атрибутные транслирующие грамматики (АТ-грамматики) отличаются от транслирующих грамматик тем, что символам грамматики приписываются атрибуты, отражающие семантическую информацию, а правилам грамматики сопоставляются правила вычисления значений атрибутов. Атрибут может представлять собой все, что угодно, — строку, число, тип, адрес памяти и т.д. Значение атрибута в узле дерева разбора определяется семантическими правилами, связанными с используемой в данном узле продукцией. Значение синтезируемого атрибута в узле вычисляется по значениям атрибутов в дочерних по отношению к данному узлах; значения наследуемых атрибутов определяются значениями атрибутов соседних (т.е. узлов, дочерних по отношению к родительскому узлу данного узла) и родительского узлов.
Семантические правила определяют зависимости между атрибутами, которые представляются графом зависимости, определяющим порядок выполнения семантических правил, что в свою очередь дает значения атрибутов в узлах дерева разбора входной строки. Семантические правила могут иметь и побочные действия, например вывод значения или изменение глобальной переменной. Дерево разбора, показывающее значения атрибутов в каждом узле, называется аннотированным, а процесс вычисления значений атрибутов в узлах дерева — аннотированием дерева разбора.
2.1 Синтезируемые атрибуты.
В синтаксически управляемом определении каждая продукция грамматики А → а имеет связанное с ней множество семантических правил вида b := f (c1, c2, …, ск), где f — функция, с1, с2, . ск — атрибуты грамматических символов продукции, а b — синтезируемый атрибут символа А или наследуемый атрибут одного из грамматических символов правой части продукции.
В любом случае атрибут b зависит от атрибутов с1 с2, . ск. Таким образом, атрибутная грамматика является синтаксически управляемым определением, в котором функции в семантических правилах не имеют побочных эффектов. Функции в семантических правилах зачастую записываются как выражения. Может быть так, что единственная цель семантического правила в синтаксически управляемом определении состоит именно в создании побочного эффекта. Такие семантические правила записываются как вызовы процедур или фрагменты программ. Их можно рассматривать как правила, определяющие значения фиктивных синтезируемых атрибутов нетерминала в левой части связанной продукции; фиктивный атрибут и знак присвоения : = при этом не указываются.
В качестве примера рассмотрим синтаксически управляемое определение программы простого калькулятора. Это определение связывает с каждым из нетерминалов Е, Т и F целочисленный синтезируемый атрибут val. Для каждой Е-, Т- и F -продукции семантическое правило вычисляет значение атрибута val нетерминала из левой части продукции по значениям атрибутов нетерминалов правой части.
Продукция Семантические правила
E→E1+ Т E.val := E1.val + T.val
Е→Т E.val := T.val
T→T1*F T.val :=T1.val * F.val
T→F T.val := F.val
F→ (E) F.val := E.val
F→ digit F.val := digit.lexval
Лексема digit имеет синтезируемый атрибут lexval, значение которого предоставляется лексическим анализатором. Правило, связанное с продукцией L → Еn для стартового нетерминала L, представляет собой процедуру вывода значения арифметического выражения, порождаемого E (это правило можно рассматривать как определяющее фиктивный атрибут для нетерминала L).
В синтаксически управляемом определении предполагается, что терминалы могут иметь только синтезируемые атрибуты, поскольку определение не дает никаких семантических правил для терминалов (обычно значения атрибутов терминалов предоставляются лексическим анализатором). Кроме того, если иное не оговорено особо, стартовый символ не имеет наследуемых атрибутов.
Синтаксически управляемое определение, использующее только синтезируемые атрибуты, называется S—атрибутным определением. S-атрибутное определение в рассматриваемом примере описывает калькулятор, считывающий арифметическое выражение из цифр, скобок, операторов + и *, за которым следует символ новой строки n, и выводит значение выражения. Например, получив выражение 3*5+4, за которым следует символ новой строки, программа выводит значение 19. На рис. 2.1 показано аннотированное дерево разбора для входной строки 3*5+4n. Выход программы, печатаемый в корне дерева, представляет собой значение E.val в первом дочернем узле корня дерева.
E.val:= 15 T.val=4
T
.val=15 F.val = 4
* digit./ewa/ = 4
T.val = 3 F.val=5
F.val=3 digit.lexval=5
digit.lexval= 3
Рис. 2.1. Аннотированное дерево разбора для 3*5+4n.
Рассмотрим узел продукции T→T*F. Значение атрибута T.val в этом узле определяется следующим образом:
Продукция Семантическое правило
Т→Т1 * F T.val := T1.val * F.val
При использовании этого семантического правила в данном узле T1.val имеет значение 3, полученное от левого наследника, a F.val — значение 5, полученное от правого наследника. Следовательно, в этом узле T.val составляет 15.
Правило, связанное с продукцией для стартового нетерминала L → Еn, выводит значение выражения, порожденного Е.
Наследуемые атрибуты представляют собой атрибуты, значения которых в узле дерева разбора определяются атрибутами родительского и/или дочерних по отношению к родительскому узлов. Наследуемые атрибуты удобны для выражения зависимости конструкций языка программирования от контекста, в котором они появляются. Например, мы можем использовать наследуемые атрибуты для отслеживания, появляется ли идентификатор слева или справа от знака присвоения, чтобы определить, потребуется ли адрес или значение данного идентификатора. Хотя всегда можно переписать синтаксически управляемое определение таким образом, чтобы использовать только синтезируемые атрибуты, зачастую более естественно воспользоваться синтаксически управляемым определением с наследуемыми атрибутами.
Рассмотрим пример, в котором наследуемый атрибут распространяет информацию о типе на различные идентификаторы в объявлении.
Пусть объявление, порождаемое нетерминалом D в синтаксически управляемом определении, приведенном ниже, состоит из ключевых слов int или real, за которыми следует список идентификаторов. Нетерминал Т имеет синтезируемый атрибут type, значение которого определяется ключевым словом объявления. Семантическое правило L.in := Т.type, связанное с продукцией D → ТL, определяет наследуемый атрибут L.in как тип объявления. Затем приведенные правила распространяют этот тип вниз по дереву разбора с использованием атрибута L.in. Правила, связанные с продукциями для L, вызывают процедуру addtype для добавления типа каждого идентификатора к его записи в таблице символов (определяемой атрибутом entry).
Продукция Семантические правила
D → TL L.in:= Т.type
T → int Т.type:= integer
T → reaI T.type := real
L → L1, id L1.in := L.in
addtype(id. entry, L.in)
L → id addtype(id.entry, L.in)
На рис. 2.2 приведено аннотированное дерево разбора для предложения real id1, id2, id3.
D
T.type = real L.in = real
L.in = real , id3
L.in = real , id2
Рис. 2.2 Дерево разбора с наследуемыми атрибутами in в каждом узле, помеченном L.