Теория компиляции

Аннотация. Курс посвящен введению в теорию компиляции и основы современных формальных языков.

1. Алфавит A, или множество терминальных символов. Операция * над алфавитом A. Общее понятие языка L в алфавите A. Синтаксис и семантика. Возможные способы задания языка.
2. Задание языка с помощью формальных грамматик. Определение грамматики общего вида: алфавит метасимволов (нетерминалов), начальный метасимвол, правила грамматики, вывод цепочек языка.
3. Иерархия Хомского: классы формальных грамматик. Примеры языков, принадлежащих разностям классов, показывающие, что включения классов строгие. Алгоритмическая разрешимость проблемы принадлежности цепочки языку в каждом из классов (без доказательств).
4. Контекстно-зависимые языки. Теорема о совпадении классов языков, заданных контекстно-зависимыми и неукорачивающими грамматиками (без доказательства). Примеры контекстно-зависимых языков и грамматик.
5. Контекстно-свободные языки и грамматики. Левые и правые выводы. Синтаксическое дерево вывода цепочки языка. Соответствие между синтаксическими деревьями, левыми и правыми выводами.
6. Необходимое условие контекстной свободности языка: лемма о разрастании (или лемма о накачке, pumping lemma). Примеры не контекстно-свободных языков. Пример контекстно-зависимого языка, не являющегося контекстно-свободным.
7. Однозначные контекстно-свободные грамматики (КС-грамматики). Примеры однозначных и неоднозначных грамматик. Существенно неоднозначные языки.
8. Определение порождающх, достижимых и полезных метасимволов в контекстно-свободной грамматике. Преобразования контекстно-свободных грамматик, не меняющие порождаемый язык: устранение бесполезных символов (путем устранения непорождающих и затем недостижимых символов); устранение эпсилон-правил; устранение цепных правил.
9. Нормальная форма Хомского для контекстно-свободных грамматик. Теорема об эквивалентности произвольной КС грамматики некоторой грамматике в нормальной форме Хомского, примеры ее применения.
10. Понятие конечного автомата: состояния автомата, входной алфавит, переходы, начальное и конечные состояния. Диаграмма состояний конечного автомата (диаграмма Мура). Автоматы с полным и неполным набором переходов (источники). Детерминированные и недетерминированные конечные автоматы.
11. Реализация устройств и программирование при помощи конечных автоматов. Наиболее общая модель: действия, совершаемые в момент входа в состояние и при переходе из состояния в состояние. Общая структура программы, использующей автоматный подход, примеры.
12. Язык, задаваемый конечным автоматом (детерминированным или недетерминированным). Модель порождения и модель распознавания цепочек языка, с помощью детерминированных и недетерминированных автоматов. Примеры автоматных языков.
13. Лемма о разрастании (лемма о накачке, pumping lemma) для автоматных языков. Примеры ее применения для доказательства того, что конкретный язык не является автоматным.
14. Теорема о совпадении классов языков, задаваемых детерминированными и недетерминированными конечными автоматами. Алгоритм построения детерминированного конечного автомата, эквивалентного заданному недетерминированному, примеры его применения. Примеры недетерминированных КА, для которых минимальное число состояний эквивалентного детерминированного КА экспоненциально зависит от числа состояний НКА.
15. Минимальный детерминированный конечный автомат, задающий автоматный язык. Изоморфизм всех минимальных детерминированных конечных автоматов для данного автоматного языка. Критерий минимальности ДКА. Построение минимального ДКА по данному автоматному языку (определение состояний этого автомата как классов эквивалентных слов языка). Алгоритм минимизации детерминированного конечного автомата.
16. Регулярные языки и выражения, примеры. Теорема Клини о совпадении классов автоматных и регулярных языков.
17. Леволинейные и праволинейные грамматики. Теорема о совпадении классов языков, заданных леволинейными грамматиками, праволинейными грамматиками и класса автоматных языков (а также и класса регулярных языков ввиду теоремы Клини). Построение леволинейной и праволинейной грамматики по конечному автомату и конечного автомата по леволинейной или праволинейной грамматике. Лемма о разрастании для праволинейных (леволинейных, автоматных, регулярных) языков.

1. Операции над регулярными языками (пересечение, дополнение, произведение, итерация и т.п.). Проблема вычисления звездной высоты регулярного выражения.
2. Использование программы LEX для создания лексических анализаторов (сканеров) и решения различных задач, связанных с разбиением текста на лексемы, которые можно задать набором регулярных выражений. Примеры.
3. Построение минимального детерминированного конечного автомата для решения задачи контекстного поиска.
4. Конечные автоматы с выходом (конечные преобразователи): модели Миля (Mealy) и Мура (Moore). Примеры применения автоматов с выходом в задачах преобразования текстов. Эквивалентность моделей Миля и Мура: алгоритмы построения автомата Мура по автомату Миля и, обратно, автомата Миля по автомату Мура.
5. Композиция двух автоматов с выходом. Построение автомата с выходом, реализующего композицию двух автоматов.
6. Детерминированные функции конечного веса (ограниченно-детерминированные функции), определение и свойства. Совпадение класса функций конечного веса, принимающих пустое значение на пустом слове, с классом функций, задаваемых конечными автоматами с выходом. Построение автомата Миля по детерминированной функции конечного веса.
7. Линейные грамматики. Лемма о разрастании для линейных языков (без доказательства). Примеры контекстно-свободных языков, не являющихся линейными, и линейных языков, не являющихся регулярными.
8. Операции на контекстно-свободными языками, не выводящие за пределы этого класса: объединение, произведение, итерация Клини. Операции, выводящие за пределы класса контекстно-свободных языков: пересечение и дополнение. Примеры КС-языков, пересечение которых не является контекстно-свободным языком. Пример КС-языка, дополнение к которому не является КС-языком.
9. Теорема о контекстной свободности пересечения контекстно-свободного и автоматного языков. Алгоритм построения контекстно-свободной грамматики для пересечения, примеры.
10. LR(1)-разбор. Определение LR(1)-ситуации разбора и LR(1)-состояния разбора как конечного множества LR(1)-ситуаций. Алгоритм построения множества состояний LR(1)-разбора. Построение таблицы действий (сдвиг и свертка по правилу) для LR(1)-разбора, примеры. Возможные конфликты типа сдвиг-свертка или свертка-свертка. Определение LR(1)-грамматики через отсутствие конфликтов в построенном множестве. Примеры LR(1) и не LR(1)-грамматик. Алгоритм работы LR(1)-парсера. Соответствие стека состояний LR(1) разбора и стека LR-процесса.
11. Использование семантического стека параллельно стеку состояний LR(0) или LR(1) разбора для решения задачи компиляции, т.е. перевода с одного языка на другой. Примеры.
12. Программные средства для построения компиляторов: LEX (или FLEX) и YACC (или BISON). Построение синтаксического анализатора, или парсера, с помощью системы YACC (BISON). Входной язык описания парсера. Использование сканера, реализованного с помощью LEX, как поставщика информации для парсера. Описание грамматики языка средствами YACC. Способы разрешения конфликтов с помощью приписывания приоритета лексемам и правилам. Семантический стек парсера и определение семантических действий во входном языке для YACC. Примеры построения простых компиляторов с помощью YACC.
13. Модельный компилятор, реализованный с помощью утилит LEX и YACC. Описание языка. Сканер языка и первый этап реализации парсера: разбор синтаксиса без генерации кода (syntax checker).
14. Разбор выражений: генерация дерева выражения в результате синтаксического разбора.
15. Таблицы символов, их структура и использование при написании компилятора.
16. Способы представления промежуточного кода: язык стековой машины, язык RTL. Алгоритм генерации кода для логических выражений.
17. Генерация ассемблерного кода по RTL. Распределение физических регистров и генерация кода для команд с ограничениями на использование регистров.
18. Алгоритмы оптимизации кода в случае RTL-представления промежуточного кода. Оптимизация на уровне базового блока: удаление мертвых выражений, нахождение общих подвыражений.
19. Глобальная оптимизация: вычисление инвариантов циклов до начала цикла, strength reduce optimization.

• Возможные способы задания языка программирования.
• Формальные грамматики.
• Иерархия Хомского.
• Контекстно-зависимые и контекстно-свободные языки.
• Понятие конечного автомата.
• Программирование при помощи конечных автоматов.
• Построение минимального ДКА по данному автоматному языку.
• Регулярные языки и выражения.
• Построение леволинейной и праволинейной грамматики по конечному автомату и конечного автомата по леволинейной или праволинейной грамматике.
• Операции над регулярными языками.
• Использование программы LEX для создания лексических анализаторов.
• Конечные преобразователи.
• Построение автомата с выходом, реализующего композицию двух автоматов.
• Операции над контекстно-свободными языками.
• Алгоритм работы LR(1)-парсера.
• Программные средства для построения компиляторов.
• Генерация дерева выражения в результате синтаксического разбора.
• Таблицы символов, их структура и использование при написании компилятора.
• Алгоритм генерации кода для логических выражений.
• Генерация ассемблерного кода по RTL.

• Пентус А.Е., Пентус М.Р. Математическая теория формальных языков. — Интернет-университет информационных технологий www.intuit.ru. — Москва, «Бином», 2006. — 247 стр.
• Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты. — Москва, Вильямс, 2001. — 768 стр.
• Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1: Синтаксический анализ. — Москва, Мир, 1978. — 612 стр.