Конспект лекций «Методы построения компиляторов»

Материал из Вики ИТ мехмата ЮФУ
Версия от 01:11, 6 апреля 2009; Ulysses (обсуждение | вклад) (→‎Фазы компиляции)

Перейти к: навигация, поиск

Литература

  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
Фазы компиляции.png

Почти на каждой стадии могут выполняться дополнительные оптимизации, а также происходит анализ и обработка ошибок.

В таблицу символов заносятся имена, присутствовавшие в исходном тексте — об этом обычно заботится лексический анализатор, заменяя идентификаторы, пришедшие из входного потока на некоторые стандартные (например, id1, id2, ...). Далее, на протяжении всего процесса компиляции для каждой записи таблицы могут добавляться определённые атрибуты — дополнительная информация о соответствующем идентификаторе (например, тип, отведённая память, область видимости).

Математическим обеспечением фаз лексического и синтаксического анализа является теория формальных языков. Обычно лексические анализаторы генерируются с помощью регулярных выражений. Этот процесс легко автоматизировать и унифицировать: фактически, для каждого нового языка достаточно указать набор ключевых слов, чтобы сгенерировать сканнер. Синтаксический анализ основывается на теории контекстно-свободных (КС) грамматик. Общая форма КС-грамматики не позволяет разбирать язык достаточно простым (в частности, автоматически сгенерированным) парсером, потому языки программирования обычно принадлежат одному из нескольких специальных подклассов КС-языков (LL, LR, LALR), которые проще разбирать и некоторые из которых будут подробно изучены в курсе.

Упомянутые достижения теории формальных языков насчитывают уже несколько десятков лет, и в этой области не ожидается каких-либо новых разработок, тем более что имеющиеся теоретические результаты хорошо решают практические задачи. По другому обстоит дело с изучением других двух разделов компиляции: семантическим анализом и оптимизацией. Работы по формальному описанию семантики языков программирования интенсивно появлялись в 70–80-х годах. Однако ни одна из построенных теорий не вошла в широкое употребление при построении компиляторов, и сегодня дело обстоит таким образом, что семантика вначале описывается на естественном языке, а затем реализуется в компиляторе большим набором вручную закодированных условных операторов.

Напротив, в последние годы растёт актуальность теории оптимизирующих преобразований — это объясняется появлением всё более высокоуровневых языков и разнообразных аппаратных платформ. Оптимизация также требует привлечения развитого математического аппарата (в частности, для решения вопроса о корректности преобразований). Многие из достижений активно внедряются в промышленные компиляторы. Всё больше это касается преобразований, связанных с распараллеливанием.

Лекция 2

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

  • Front-end и back-end компиляторы.

Перечисленные выше фазы обычно группируются в два модуля — front-end и back-end, в зависимости от того, к какой стороне процесса компиляции они ближе, к исходному языку или к машинному коду для целевой платформы, соответственно. Возможность отдельно разрабатывать front-end и back-end повышает эффективность труда разработчиков компиляторов — насколько, зависит от эффективности используемого внутреннего представления, связывающего эти два модуля. В последнее время всё чаще выделяют middle-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 | ε

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

Обозначения 

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

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

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

Опр. Языком L(G) грамматики G называется множество всех ее предложений.

Обозначения 

=>(lm)
=>(lm)*
=>(rm)+

Левый, правый вывод (порождение).

Пример 

E → E + T
  | T
T → T * P
  | P
P → i
  | ( E )

Левый и правый вывод для предложения i + i * i

Дерево вывода (синтаксическое дерево, дерево разбора) строки предложения. В отличие от порождения, из него исключена информация о порядке вывода.

Крона дерева разбора - цепочка меток листьев слева направо

Грамматика, которая дает более одного дерева разбора для некоторого предложения, называется неоднозначной.

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

E → E+E | E*E | i

Два дерева разбора для цепочки i + i * i

Преобразование в эквивалентную однозначную грамматику: 

E → E + T
  | T
T → T * P
  | P
P → i

Пример неоднозначной грамматики. Грамматика условного оператора 

S → if b then S
  | if b then S else S
  | a

Два дерева разбора для цепочки if b then if b then a

Преобразование в эквивалентную однозначную грамматику: 

S → if b then S
  | if b then S2 else S
  | a  
S2 → if b then S2 else S2
  | a

Утверждение. Проблема неоднозначности произвольной КС-грамматики алгоритмически не разрешима

Леворекурсивные грамматики, их проблемы. Алгоритм устранения левой рекурсии.

Перевод

Схема синтаксически управляемого (СУ) перевода

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

Понятие синтаксического анализатора.

Нисходящие (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
    • Добавление переменных. Представление о таблице символов
    • Добавление присваивания
    • Добавление типов
    • Добавление управляющих конструкций
Источник — «http://it.mmcs.sfedu.ru/_wiki/index.php?title=Конспект_лекций_«Методы_построения_компиляторов»&oldid=1512»