Конспект лекций «Методы построения компиляторов» — различия между версиями

Версия 22:29, 15 марта 2009

Литература

1. А.Ахо, Р.Сети, Д.Ульман. Компиляторы. Принципы, технологии, инструменты.М, Вильямс, 2001
2. С.З.Свердлов. Языки программирования и методы трансляции. Питер, 2007
3. Э.А.Опалева, В.П.Самойленко. Языки программирования и методы трансляции. BHV, 2005
4. Ю.Г.Карпов. Основы построения трансляторов. BHV, 2005

Лекция 1

Введение в компиляцию

Что такое компилятор. Исходный и целевой язык.

Разновидности компиляторов

• Интерпретаторы
• Форматтеры текста
• Статические анализаторы кода
• Препроцессоры
  • макросы define
  • включение файлов #include
  • условная компиляция #ifdef
  • расширения языка, которые препроцессор переводит в код на языке

Фазы компиляции

• Лексический анализ
• Синтаксический анализ
• Семантический анализ

На примере выражения 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

Лекция 2

Группировка фаз

• Front-end и back-end компиляторы.
• Проходы. Группировка фаз компилятора в проходы (например, объединение фаз лексического, синтаксического, семантического анализа и генерации кода)
• Уменьшение количества проходов (на примере предварительного описания подпрограмм). Технология обратных поправок.

Компиляция и многомодульность. Необходимость компилировать модуль в некоторый формат, содержащий правильную программу. Перемещаемые адреса. Редактор связей (линковщик).

Инструментарий для создания компиляторов

• Генераторы лексических анализаторов (сканеров)
• Генераторы синтаксических анализаторов (парсеров)
• Автоматические генераторы кода

Компиляторы компиляторов

• Lex + Yacc
• Flex + Bison
• CoCo
• Antlr
• Gold Parser Builder
• GPLex + GPPG

Контекстно свободные грамматики

Определение. Терминалы, нетерминалы, символы. Продукции. Стартовый символ.

Обозначения

a,b,c, ... - терминалы
u,v,w,x,y,z - строки (цепочки) терминалов
A,B,C, ... - нетерминалы
α,β,γ, ... - строки (цепочки) нетерминалов и терминалов
ε - пустая цепочка

Опр. формальной грамматики (порождающей грамматики Хомского)

G = (N,Σ,P,S)
N - нетерминалы
Σ - терминалы
P - правила вида α→β 

V = Σ + N - множество всех нетерминалов и терминалов V* - множество всех цепочек символов из V V+ = V* - {ε}

Классификация формальных грамматик по Хомскому (напоминание из курса ФЯиГ)

• Грамматика типа 0 (общего вида). Правила имеют вид α→β
• Грамматика типа 1 (контекстно зависимая, КЗ)

Правила имеют вид αAβ → αγβ. γ принадлежит V+, т.е. грамматика является неукорачивающей

α,β называются левым и правым контекстом

• Грамматика типа 2 (контекстно свободная, КС)

Правила имеют вид A → α. α принадлежит V*, т.е. грамматика может быть укорачивающей => КС языки не содержатся в КЗ

Наиболее близкая к БНФ

• Грамматика типа 3 (автоматная, регулярная)

Правила имеют вид A → aB, A → a, a принадлежит Σ + {ε}

Автоматные языки содержатся в КС языках

Пример. Грамматика правильных скобочных выражений.

S → (S) | SS | ε

Пример. Грамматика арифметических выражений.

E → E+E | E*E | E-E | E/E | (E) | i

Порождение (вывод)

Обозначения

=>
=>+ (1 или более)
=>* (0 или более)

Опр. Сентенциальной формой грамматики называется строка, которая может быть выведена из стартового символа.

Опр. Предложением (сентенцией) грамматики называется сентенциальная форма, состоящая из одних терминалов.

Опр. Языком 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

Примеры

1. Простейший калькулятор
   • Простейший калькулятор с приоритетом операций
   • Создание дерева разбора программы
   • Преобразование в XML
   • Добавление переменных. Представление о таблице символов
   • Добавление присваивания
   • Добавление типов
   • Добавление управляющих конструкций