Операции над регулярными языками (пересечение, дополнение, произведение, итерация и т.п.). Проблема вычисления звездной высоты регулярного выражения.
Использование программы LEX для создания лексических анализаторов (сканеров) и решения различных задач, связанных с разбиением текста на лексемы, которые можно задать набором регулярных выражений. Примеры.
Построение минимального детерминированного конечного автомата для решения задачи контекстного поиска.
Конечные автоматы с выходом (конечные преобразователи): модели Миля (Mealy) и Мура (Moore). Примеры применения автоматов с выходом в задачах преобразования текстов. Эквивалентность моделей Миля и Мура: алгоритмы построения автомата Мура по автомату Миля и, обратно, автомата Миля по автомату Мура.
Композиция двух автоматов с выходом. Построение автомата с выходом, реализующего композицию двух автоматов.
Детерминированные функции конечного веса (ограниченно-детерминированные функции), определение и свойства. Совпадение класса функций конечного веса, принимающих пустое значение на пустом слове, с классом функций, задаваемых конечными автоматами с выходом. Построение автомата Миля по детерминированной функции конечного веса.
Линейные грамматики. Лемма о разрастании для линейных языков (без доказательства). Примеры контекстно-свободных языков, не являющихся линейными, и линейных языков, не являющихся регулярными.
Операции на контекстно-свободными языками, не выводящие за пределы этого класса: объединение, произведение, итерация Клини. Операции, выводящие за пределы класса контекстно-свободных языков: пересечение и дополнение. Примеры КС-языков, пересечение которых не является контекстно-свободным языком. Пример КС-языка, дополнение к которому не является КС-языком.
Теорема о контекстной свободности пересечения контекстно-свободного и автоматного языков. Алгоритм построения контекстно-свободной грамматики для пересечения, примеры.
LR(1)-разбор. Определение LR(1)-ситуации разбора и LR(1)-состояния разбора как конечного множества LR(1)-ситуаций. Алгоритм построения множества состояний LR(1)-разбора. Построение таблицы действий (сдвиг и свертка по правилу) для LR(1)-разбора, примеры. Возможные конфликты типа сдвиг-свертка или свертка-свертка. Определение LR(1)-грамматики через отсутствие конфликтов в построенном множестве. Примеры LR(1) и не LR(1)-грамматик. Алгоритм работы LR(1)-парсера. Соответствие стека состояний LR(1) разбора и стека LR-процесса.
Использование семантического стека параллельно стеку состояний LR(0) или LR(1) разбора для решения задачи компиляции, т.е. перевода с одного языка на другой. Примеры.
Программные средства для построения компиляторов: LEX (или FLEX) и YACC (или BISON). Построение синтаксического анализатора, или парсера, с помощью системы YACC (BISON). Входной язык описания парсера. Использование сканера, реализованного с помощью LEX, как поставщика информации для парсера. Описание грамматики языка средствами YACC. Способы разрешения конфликтов с помощью приписывания приоритета лексемам и правилам. Семантический стек парсера и определение семантических действий во входном языке для YACC. Примеры построения простых компиляторов с помощью YACC.
Модельный компилятор, реализованный с помощью утилит LEX и YACC. Описание языка. Сканер языка и первый этап реализации парсера: разбор синтаксиса без генерации кода (syntax checker).
Разбор выражений: генерация дерева выражения в результате синтаксического разбора.
Таблицы символов, их структура и использование при написании компилятора.
Способы представления промежуточного кода: язык стековой машины, язык RTL. Алгоритм генерации кода для логических выражений.
Генерация ассемблерного кода по RTL. Распределение физических регистров и генерация кода для команд с ограничениями на использование регистров.
Алгоритмы оптимизации кода в случае RTL-представления промежуточного кода. Оптимизация на уровне базового блока: удаление мертвых выражений, нахождение общих подвыражений.
Глобальная оптимизация: вычисление инвариантов циклов до начала цикла, strength reduce optimization.