Разработка компиляторов
Разработка компиляторов
ВведениеОбзор платформы .NET
Общая схема архитектуры .NET
Достоинства платформы .NET
Недостатки платформы .NET
Основные черты MSIL
Пример кода на MSIL
Базовая модель .NET
Иерархия классов (отрывок)
Понятие сборки
Манифест: описание сборки
Уникальность сборки
Безопасность в .NET
Общая система типов .NET
Примитивные типы
Примитивные типы в .NET
Типы-значения
Ссылочные типы
Упаковка и распаковка
Как работает распаковка
Пример упаковки и распаковки
Упаковка и распаковка в С++
Литература к лекции
Разработка компиляторов
Причины возникновения языка C#Простота C#
Управляющие конструкции C#
Типы данных
Классы
Модификаторы
Конструкторы и деструкторы
Методы и их параметры
Свойства класса и доступ к ним
Индексаторы
События
Перегрузка операторов
Явные и неявные преобразования
Список параметров
Препроцессор C#
Атрибуты
Пользовательские атрибуты
Опасный код в С#
Еще о C#
C-бемоль
Литература к лекции
Разработка компиляторов
Основные задачи компиляторовИнтерпретатор
Компилятор
Объектная программа
Трансляция в ассемблер
T-диаграммы
Методики создания компилятора
Метод раскрутки
Кросс-транслятор
Виртуальная машина
Компиляция "на лету"
Фазы компиляции
Лексический анализ
Синтаксический анализ
Видозависимый анализ
Оптимизация кода
Генерация кода
Внешний и внутренний интерфейсы
Просмотры
Техника "заплат"
Литература к лекции
Разработка компиляторов
Задача определения языкаОпределение грамматики
Некоторые свойства грамматик
Иерархия Хомского
Распознаватели для различных классов грамматик
Конечные автоматы
Детерминированные конечные автоматы
Недетерминированные и конечные автоматы
Эквивалентность конечных автоматов
Минимизация конечного автомата
Пример минимизации конечного автомата
Эквивалентность праволинейных грамматик и конечных автоматов
Свойства контекстно-свободных грамматик
О преобразовании грамматик
Магазинные автоматы
Пример магазинного автомата
Детерминированные МП-автоматы
Форма Бэкуса-Наура
Расширенная форма Бэкуса-Наура
Грамматика ван Вейнгаардена
Графическое представление
Литература к лекции
Разработка компиляторов
Лексический анализЛексический анализ различных языков программирования
Атрибуты лексем
Таблица представлений
Хэш-функции
Использование грамматик для лексического анализа
Регулярные выражения
Построение лексического анализатора по регулярному выражению
Lex
Структура Lex-программы
Способы записи регулярных выражений в Lex-программе
Пример Lex-программы
Другие возможности Lex'а
Заглядывание вперед при лексическом анализе
Использование регулярных выражений .NET
Пример использования механизма регулярных выражений .NET
Литература к лекции
Разработка компиляторов
О методах определения языковКлассы синтаксических анализаторов
Метод рекурсивного спуска
Вычисление значения формулы
Формула, содержащая операции типа умножения
Формула, содержащая операции типа сложения
Методы, которые следует разработать самостоятельно
Условия использования метода рекурсивного спуска
Алгоритм построения множества FIRST
LL(k)-грамматика
Пример
Леворекурсивные грамматики
Алгоритм устранения леворекурсивности
Рекурсивный спуск с возвратами
Литература к лекции
Разработка компиляторов
Восходящие анализаторыLR(k)-анализатор
Управляющая программа анализатора
Управляющая таблица LR(0)-анализатора
Состояния 0 и 1
Состояния 2 и 3
Базовые операции
Алгоритм построения конечного автомата
Автомат для грамматики
Управляющая таблица
LR(1)-анализатор
Управляющая таблица LR(1)-анализатора
LALR(1)-анализатор
Таблица LALR-анализатора для грамматики G1
Пример LR(1)-грамматики
Неоднозначные грамматики. Конфликты "перенос-свертка"
Пример конфликта перенос-свертка
Разрешение конфликта перенос-свертка
Неоднозначные грамматики. Конфликт перенос-перенос
Неоднозначные грамматики. Приоритет операций
Неоднозначные грамматики. Ассоциативность
Литература к лекции
Разработка компиляторов
Генератор анализаторов YACCСекция описаний
Секция правил грамматики
Семантики
Семантики (продолжение)
Секция описаний процедур
Пример
Пример (продолжение)
Обработка ошибок
Информация, необходимая для выдачи сообщения об ошибке
Локальные стратегии продолжения анализа
Error-правила
Пример использования error-правил
Литература к лекции
Разработка компиляторов
ИдентификацияСтруктура таблиц
Обработка определяющего вхождения идентификатора
Пример
Конструирование типов
Представление типов
Контроль типов
Эквивалентность типов
Преобразование типов
Роль промежуточных языков в компиляторе
Идея массового применения промежуточного языка
Атрибутное дерево разбора
Польская запись
Триады и тетрады
Разработка компиляторов
Управление памятью с точки зрения разработчика компилятораОсновные фазы работы с памятью
Проблемы управления памятью
Проблемы управления памятью (окончание)
Висячие ссылки и мусор
Статическая и динамическая память
Влияние управления памятью на языки программирования
Неявное управление памятью
Фазы управления памятью
Статическое управление памятью
Пример статического распределения памяти
Стековое управление памятью
Пример стекового управления памятью памяти
Управление кучей
Отслеживание свободной памяти с помощью подсчета ссылок
Некоторые свойства сборки мусора
Поколения объектов
Алгоритм выделения памяти в .NET
Пример на сборку мусора
Интерфейс компилятора со сборщиком мусора
Литература к лекции
Разработка компиляторов
ОптимизацияВиды оптимизации
Зависимость между оптимизациями
Стадии оптимизации
Покадровая оптимизация
Обозначения
Представление программы
Пример
Поток управления
Def-Use Chains
Удаление пустого оператора
Удаление мертвого кода
Чистка циклов вверх
Чистка циклов вниз
Объединение циклов
Раскрутка циклов
Понижение силы операций
Упрощение выражений
Экономия общих подвыражений
Зависимость качества оптимизации от размера участка экономии
Литература к лекции
Разработка компиляторов
Анализ потока управленияГраф потока управления
Обязательное предшествование
Пример
Глубинное остовное дерево
Построение глубинного остовного дерева
Простейшие свойства
Фрагменты
Альт
Выделение максимального альта
Построение отношения обязательного предшествования
Луч
Выделение лучей
Сильно связный подграф
Иерархия вложенных зон
Линейные компоненты
Выделение линейных компонент в сводимом графе
Литература к лекции
Разработка компиляторов
Анализ потоков данныхПример
Достижимые определения
Живые переменные
Стадии анализа
Разметки и потоковые функции
Итеративный алгоритм
Полурешетки
Неподвижные точки монотонной функции
Пример
Произведение полурешеток
Формализация задачи анализа потоков данных
Прямая и обратная задачи
Решение задачи анализа потоков данных (1)
Свойства итеративного подхода
Алгоритм с рабочим списком
Пример: достижимые определения (1)
Пример: живые переменные (1)
Заключение
Литература к лекции
Разработка компиляторов
Основные черты MSILО хранении переменных в MSIL
Работа с указателями в MSIL
Команды загрузки в MSIL
Команды выгрузки в MSIL
Арифметические команды MSIL
Переходы и вызовы в MSIL
Прочие команды MSIL
Трансляция в MSIL: исходный текст на C-бемоль
Трансляция в MSIL: пример
Механизм рефлексии в .NET
Пример на рефлексию
Генерация MSIL с использованием Reflection.Emit
О последовательности генерации MSIL
Генерация кода виртуальной машины
Создание сборки и класса
Генерация кода: исключения, метки
Генерация кода: условный оператор
Генерация кода: заключение
Литература к лекции
Разработка компиляторов
Выбор инструкцийДеревянные языки
Согласование размещений
Пример использования BURS
Организация входного файла lburg
Пример входного файла lburg
Ограничения BURS
Литература
Подстановка деревьев
Регулярные деревянные грамматики
Выводимость образцов
Вывод в деревянной грамматике
Язык, определяемый грамматикой
Эквивалентность грамматик
Нормализация грамматик
Пример нормализации грамматики
Представление выводов
Построение выводов
Построение выводов (продолжение)
Построение выводов (окончание)
Пример
Системы восходящего переписывания деревьев
Грамматики восходящего переписывания
Представление вывода в BURS
Динамическое программирование
Динамическое программирование (продолжение)
Динамическое программирование (окончание)
Свертка
Свертка (продолжение)
Свертка (окончание)
Конструкции языка С-бемоль
Грамматика языка С
