Часть II. Формальное описание языков программирования ( Формальная спецификация формальных языков ) Атрибутные грамматики (2). Генерация кода. - презентация

1 Часть II. Формальное описание языков программирования ( Формальная спецификация формальных языков ) Атрибутные грамматики (2). Генерация кода

2 Дано: дерево разбора (проверка типов проведена) Оттранслировать в ассемблерный код Правила вычислений из атрибутной грамматики генерируют ассемблерный код

3 Простой императивный язык 1 ::= skip | := | 2 ; 3 | if then 2 else 3 | while do 2 1 ::= | | | | 2 * 3 1 ::= true | false | 1 = 2 | 1 2 | ¬ 2 | 2 3 | 2 3

4 Язык ассемблера (1) Процесор с одним регистром сумматором LOAD x: скопировать значение ячейки памяти (переменной x) в сумматор LOAD const: записать в сумматор значение целой константы STO x: записать значение из сумматора ячейку памяти

5 Язык ассемблера (2) ADD x: сложить значение переменной x с содержимым сумматора. Результат остается на сумматоре. BR L: переход на метку L (goto) BZ L: если сумматор равен 0, то перейти на метку L L: NOP: метка L, ассоциированная с «нуль» инструкцией NOP

6 Стратегия генерации кода (1) Синтезируемый атрибут code –Содержит последовательность инструкций Пример: 1 ::= code := < 2.code, "STO T1", 3.code, "ADD T1 > T1 – временная переменная Вычисляет сумму и сохраняет ее на сумматоре T1 – временная переменная Вычисляет сумму и сохраняет ее на сумматоре">

7 Стратегия генерации кода (2) 1 ::= if then 2 else 3 1.code :=

8 Проблемы Problems T1 нельзя использовать в 3.code –Нужно генерировать временные имена Имена меток L1 и L2 нельзя использовать в 2.code, 3.code и где-либо еще –Нужно генерировать имена меток Хранить счетчик временных имен в наследуемом атрибуте temp –Хранить глобальный счетчик имен меток как наследуемый атрибут labin и наследуемый labout

9 Генерация кода операторов (1) ::=.code :=.code.labin := 0 1 ::= 2 ; 3 1.code := append( 2.code, 3.code) 2.labin := 1.labin 3.labin := 2.labout 1.labout := 3.labout

10 Генерация кода операторов (2) ::= skip.code :=.labout :=.labin |.code :=.code.labout :=.labin

11 Генерация кода операторов (3) 1 ::= if then 2 else 3 2.labin := 1.labin labin := 2.labout 1.labout := 3.labout 1.code := append(.code, ( "BZ" label( 1.labin) ), 2.code, ( "BR" label( 1.labin + 1) ), ( label( 1.labin) "NOP ), 3.code, ( label( 1.labin+1) "NOP ) )

12 Генерация кода операторов (4) 1 ::= while do 2 2.labin := 1.labin labout := 2.labout 1.code := append( ( label( 1.labin) "NOP ),.code, ( "BZ" label( 1.labin + 1) ), 2.code, ( "BR" label( 1.labin) ), ( label( 1.labin+1) "NOP ) )

13 Генерация кода операторов (5) ::= :=.temp := 1.code := append(.code, ("STO".name)) Требуется доступ к переменным в стеке или в хипе.

14 Генерация кода выражений 1 ::= 1.code :=.value) > | 1.code :=.name) > | temp := 1.temp 3.temp := 1.temp code := append( 2.code, ( "STO" temp( 1.temp) ), 3.code, ( "ADD" temp( 1.temp) ) )

15 Пример генерации кода (1) Исходная программа if x = 42 then if a = b then y := 1 else y := 2 else y := 3

16 Пример генерации кода (2) Результат генерации для внешнего if # код для (x=42) BZ L1 # код для внутреннего if BR L2 L1: NOP # code for y := 3 L2: NOP

17 Внутренний оператор if # code for x = 42 BZ L1 # code for a = b BZ L3 # code for y := 1 BR L4 L3: NOP # code for y := 2 L4: NOP BR L2 L1: NOP # code for y := 3 L2: NOP

18 Код для присваивания # code for x = 42 BZ L1 # code for a = b BZ L3 LOAD 1 STO y BR L4 L3: NOP LOAD 2 STO y L4: NOP BR L2 L1: NOP LOAD 3 STO y L2: NOP

19 Резюме по атрибутным грамматикам (1) Атрибутные шрамматики хороши для спецификации контекстно-свободных языков Техника построена на комбинации вычислений синтезируемых и наследуемых атрибутов Последовательность вычислений атрибутов может определяться автоматически Имеется возможность для отсеивания некорректных деревьев разбора (семантически некорректных программ)

20 Резюме по атрибутным грамматикам (2) Глобальные структуры данных (окружение ) передается через атрибуты Глобальные счетчики (например, метки) реализуются как пары атрибутов Абстрактные типы данных (например, множества) используются до тех пор, пока не начинается собственно программирование Правила могут использовать вспомогательные функции Реальные применения: для проверки типов (type checking) и генерации кода (code generation)

21 Литература 1. Formal specification of programming languages, F.Pagan 2. Formal syntax and semantics of programming languages, Kurtz and Slonnegar.