Конспект лекций «Методы построения компиляторов»
Содержание
Лекция 1
Введение в компиляцию
Что такое компилятор. Исходный и целевой язык.
Разновидности компиляторов
- Интерпретаторы
- Форматтеры текста
- Статические анализаторы кода
- Препроцессоры
Фазы компиляции
- Лексический анализ
- Синтаксический анализ
- Семантический анализ
На примере выражения p := i + r * 60
id1 := id2 + id3 * 60
- Обнаружение ошибок
- Генерация промежуточного кода
На примере трехадресного кода
t1 := IntToReal(60) t2 := id3 * t1; t3 := id2 + t2; id1 := t3;
- Оптимизация кода
t1 := id3 * 60.0; id1 := id2 + t1;
- Генерация кода (основное - назначение переменных регистрам)
MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1
Контекстно свободные грамматики
Определение. Терминалы, нетерминалы, символы. Продукции. Стартовый символ.
Обозначения
a,b,c, ... - терминалы u,v,w,x,y,z - строки терминалов A,B,C, ... - нетерминалы α,β,γ, ... - строки нетерминалов
Пример. Грамматика арифметических выражений.
E → E+E | E*E | (E) | -E | id
Порождение (вывод)
Обозначения
=> =>* =>+
Опр. Сентенциальной формой (цепочкой) грамматики называется строка, которая может быть выведена из стартового символа.
Опр. Предложением грамматики называется сентенциальная форма, состоящая из одних терминалов.
Опр. Языком L(G) грамматики G называется множество всех ее предложений.
Левое, правое порождение. Примеры.
Обозначения
=>(lm) =>(lm)* =>(rm)+
Дерево разбора строки грамматики. В отличие от порождения, из него исключена информация о порядке вывода.
Грамматика, которая дает более одного дерева разбора для некоторого предложения, называется неоднозначной.
Пример неоднозначной грамматики.
stmt → if expr then stmt
| if expr then stmt else stmt
| other
Леворекурсивные грамматики, их проблемы. Алгоритм устранения левой рекурсии.
Синтаксический анализ
Понятие синтаксического анализатора.
Нисходящие (top-down) и восходящие (bottom-up) синтаксические анализаторы
Нисходящий синтаксический анализ
Опр. Синтаксический анализатор, работающий методом рекурсивного спуска и не требующий откатов, называется предиктивным синтаксическим анализатором.
Нерекурсивный предиктивный анализ
Схема работы со стеком, таблицей разбора, входным буфером
Алгоритм нерекурсивного предиктивного анализа
Пример
Множества FIRST и FOLLOW
Определение.
Пример.
Алгоритм построения таблиц предиктивного анализа.
Определение LL(1) грамматики. Пояснение названия.
Утв. LL(1) грамматика не может быть лворекурсивной или неоднозначной.
Эквивалентное определение LL(1) грамматики.
Восстановление после ошибок в предиктивном анализе
Восходящий синтаксический анализ
Наиболее распространенная разновидность - ПС-анализ (перенос-свертка - shift-reduce)
Понятие основы. Примеры.
Обращенное правое порождение и обрезка основ.
Стековая реализация ПС-анализа. Основные операции:
Перенос (shift) Свертка (reduce) Допуск (accept) Ошибка (error)
Утв. Основа всегда находится на вершине стека и никогда - внутри него. Доказательство.
Понятие активного префикса.
LR-анализаторы. SLR, канонический LR и LALR анализаторы.
Общая схема и алгоритм LR-анализа. Пример.
LR-грамматики.
Неоднозначности вида shift-reduce и их разрешение.
Генераторы лексических и синтаксических анализаторов
Обзор.
Yacc, Lex Byson, Flex CoCo ANTLR Gold Parser Builder GPPG
Создание лексического анализатора (сканера) с помощью gplex
Общая структура .l файла
Особенности .l файла gplex
Возвращение типов лексем
Лексемы идентификаторов, чисел.
Ключевые слова
Позиция лексемы
Начальные состояния сканера, их изменение, использование для вырезания комментариев:
%x COMMENT
%%
"/*" { BEGIN(COMMENT);}
<COMMENT> "*/" { BEGIN(INITIAL);}
<COMMENT> <<EOF>> { Console.WriteLine("Комментарий не закрыт");}
Создание синтаксического анализатора с помощью gppg
Общая структура .y файла
Задание типов лексем
Таблица приоритетов и ассоциативности
Особенности .y файла gppg
Примеры
- Простейший калькулятор
- Простейший калькулятор с приоритетом операций
- Создание дерева разбора программы
- Преобразование в XML
- Добавление переменных. Представление о таблице символов
- Добавление присваивания
- Добавление типов
- Добавление управляющих конструкций
