Методы разработки компиляторов. Атрибутные грамматики

1.

Методы разработки
компиляторов.
Атрибутные грамматики
Лекции по курсу
Методы разработки компиляторов
семестр 7, ФИИТ
Михалкович С.С.

2.

Атрибутные грамматики
Курс «Методы разработки компиляторов»
2

3.

Определения
Определение. Атрибутная грамматика – расширение КС-грамматики,
при котором каждому символу (терминалу, нетерминалу) ставится в
соответствие конечное множество атрибутов (семантических
параметров) некоторого типа.
Для каждого правила грамматики определяется одно или несколько
семантических правил – функциональных зависимостей одних
семантических атрибутов от других.
Дерево разбора, включающее значения атрибутов в каждом узле,
называется аннотированным или украшенным, а процесс
вычисления атрибутов по дереву – аннотированием дерева разбора.
Курс «Методы разработки компиляторов»
3

4.

Пример
Курс «Методы разработки компиляторов»
4

5.

Интерпретатор по атрибутной
грамматике
Курс «Методы разработки компиляторов»
5

6.

Синтезированные атрибуты
Курс «Методы разработки компиляторов»
6

7.

Унаследованные атрибуты
Курс «Методы разработки компиляторов»
7

8.

Пример 2
Курс «Методы разработки компиляторов»
8

9.

Пример 2 – AST-дерево и дерево
разбора
AST-дерево и дерево вывода
Курс «Методы разработки компиляторов»
9

10.

Пример 2 – интерпретатор
После построения AST-дерева добавим к каждому узлу метод eval()
для вычисления результата поддерева
Затем вызовем eval() для корня дерева
Данный подход лучше первого интерпретатора тем, что
• Вначале строится дерево и проверяются все ошибки (компилятор
в дерево)
• Можно запускать программу с различными исходными данными
без перекомпиляции (это быстрее)
Курс «Методы разработки компиляторов»
10

11.

Пример 3. Заполнение таблицы
символов по описанию переменных
Курс «Методы разработки компиляторов»
11

12.

Пример 3. Заполнение таблицы
символов по описанию переменных
Курс «Методы разработки компиляторов»
12

13.

Пример 3 – дерево разбора
Курс «Методы разработки компиляторов»
13

14.

Вопросы
В каком порядке вычислять атрибуты?
Всегда ли существует порядок, в котором можно вычислить все
атрибуты?
Можно ли предложить один алгоритм для всех деревьев
разбора?
Курс «Методы разработки компиляторов»
14

15.

Определения, утверждения
Курс «Методы разработки компиляторов»
15

16.

Пример 4. Грамматика для представления
рациональных двоичных чисел
Курс «Методы разработки компиляторов»
16

17.

Пример 4. Грамматика 2 для представления
рациональных двоичных чисел
Курс «Методы разработки компиляторов»
17

18.

Пример 4. Грамматика 2 для представления
рациональных двоичных чисел
Курс «Методы разработки компиляторов»
18

19.

Пример 4. Дерево разбора и граф
зависимостей для 101.01
Выводы - ?
Курс «Методы разработки компиляторов»
19

20.

Пример 5. Символьное дифференцирование
Курс «Методы разработки компиляторов»
20

21.

Пример 5. Символьное дифференцирование
(2)
Курс «Методы разработки компиляторов»
21

22.

S-атрибутные и L-атрибутные грамматики
Курс «Методы разработки компиляторов»
22

23.

Порядок вычислений в L-атрибутной
грамматике
Курс «Методы разработки компиляторов»
23

24.

Практический пример 34 + 23
Курс «Методы разработки компиляторов»
24

25.

Калькулятор для нелеворекурсивной
грамматики
Курс «Методы разработки компиляторов»
25

26.

Курс «Методы разработки компиляторов»
26

27.

Калькулятор для нелеворекурсивной
грамматики (3)
Граф зависимости атрибутов
Курс «Методы разработки компиляторов»
27

28.

Построитель AST-дерева для
нелеворекурсивной грамматики 3 + 4 + 5
Курс «Методы разработки компиляторов»
28

29.

Граф зависимостей для a - 4 + c
Курс «Методы разработки компиляторов»
29

30.

В каком порядке вычислять атрибуты
Курс «Методы разработки компиляторов»
30

31.

Q&A
Курс «Методы разработки компиляторов»
31