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

Литература

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

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

В таблицу символов заносятся имена, присутствовавшие в исходном тексте — об этом обычно заботится лексический анализатор, заменяя идентификаторы, пришедшие из входного потока на некоторые стандартные (например, id₁, id₂, ...).

Думаю, что заботится все-таки о занесении в таблицу символов даже не синтаксический анализатор, 
а построитель семантического дерева Admin 21:22, 6 апреля 2009 (MSD)

Я про синтаксический анализатор вроде ни слова не сказал. Вообще, ориентировался на Ахо почти во всём, что писал. В данном случае:
Если лексическим анализатором в исходной программе обнаружен идентификатор, он записывается в таблицу символов.
Однако атрибуты идентификатора обычно не могут быть определены в процессе лексического анализа...
В процессе остальных фаз информация об идентификаторах вносится в таблицу символов и используется различными способами.
(изд 1., стр. 31)

Предлагаю обсуждать на странице обсуждения, а сюда заносить только конечный результат.
Я думаю, что вы здесь полностью в своём праве и можете исправлять то, с чем не согласны. — Ulysses 22:56, 6 апреля 2009 (MSD)

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

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

Ну, не только ключевых слов. При лексическом анализе еще много всего: другие лексемы, литеральные константы, 
комментарии, контекст препроцессора. Ключевые слова занимают сравнительно малую часть Admin 21:22, 6 апреля 2009 (MSD)

Снова источник — Ахо, хотя я был не совсем точен, сейчас подправил чуть-чуть.
Например, можно предположить, что лексические анализаторы для всех языков, по сути, одинаковы —
за исключением ключевых слов и знаков. Многие компиляторы компиляторов используют фиксированные программы
лексического анализа в генерируемых компиляторах. Эти программы пользуются только списком ключевых слов,
и всё, что требуется от пользователя, — предоставить этот список. Такой подход вполне корректен,
но может оказаться неработоспособным, если необходимо распознавание нестандартных токенов, например, 
идентификаторов, которые включают символы, отличающиеся от букв и цифр.
(изд. 1, стр. 41) — Ulysses 22:56, 6 апреля 2009 (MSD)

Синтаксический анализ основывается на теории контекстно-свободных (КС) грамматик. Общая форма КС-грамматики не позволяет разбирать язык достаточно простым (в частности, автоматически сгенерированным) парсером, потому языки программирования обычно принадлежат одному из нескольких специальных подклассов КС-языков (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  

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

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

Перевод

Ранее мы решали вопрос о принадлежности некоторой цепочки α интересующему нас языку L, задаваемому грамматикой G. Но задача компиляции шире: не только распознать входную цепочку, но и сгенерировать выходную.

Определение. Пусть Σ и Δ — два алфавита (называемые „входным“ и „выходным“ соответственно). L₁ ⊂ Σ*, L₂ ⊂ Δ*. Переводом с языка L1 на язык L2 называется отображение τ: L1 → L2.

Чтобы решить указанную задачу (т.е. конструктивно определить перевод), можно встроить в процесс проверки принадлежности некоторые действия, формирующие на выходе желаемый результат.

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

Неформальное определение. СУ-схема это грамматика, в которую с каждым синтаксическим правилом встроен элемент перевода.

Пример. Перевод алгебраического выражения в ПОЛИЗ (польская инверсная запись). Запишем правила грамматика вместе с элементами перевода.

Правило	Элемент перевода
E → E + T	E = E T +
E → T	E = T
T → T * P	T = T P *
T → P	T = P
P → (E)	P = E
P → <id>	P = <id>

Выведем цепочку a * (b + c) и одновременно переведём её в ПОЛИЗ: a b c + * (как обычно, используем левый вывод):

(E, E) ⇒ (T, T) ⇒ (T * P, T P *) ⇒ (P * P, P P *) ⇒ (a * P, a P *) ⇒ (a * (E), a E *) ⇒
       ⇒ (a * (E + T), a E T + *) ⇒* (a * (b + c), a b c + *)

Определение. Схема синтаксически управляемого перевода это пятёрка

T = (N, Σ, Δ, R, S),

где:

N — множество нетерминалов („переменных“),
Σ — входной алфавит,
Δ — выходной алфавит,
S — стартовый символ (S ∊ N),
R = {A → (α, β) | A ∊ N, α ∊ (N ∪ Σ)*, β ∊ (N ∪ Δ)*}.

Причём α и β в каждом конкретном правиле содержат одни и те же нетерминалы с точностью до перестановки.

Далее считаем, что задана некоторая СУ-схема T = (N, Σ, Δ, R, S).

Определение. Входная грамматика, соответствующая СУ-схеме T, это четвёрка

Gin = (N, Σ, R, S),

где

P = {A → α | ∃β A → (α, β) ∊ R}.

Определение. Выходная грамматика, соответствующая СУ-схеме T, это четвёрка

Go = (N, Δ, R, S),

где

P = {A → β | ∃α A → (α, β) ∊ R}.

Определение. СУ-перевод (СУ-трансляция) это множество

{(x, y) | (S, S) ⇒* (x, y), x ∊ Σ*, y ∊ Δ*},

обозначаемое обычно τ(T).

СУ-перевод можно понимать как трансформацию синтаксических деревьев (соответствующих выводу входной и выходной цепочек).

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

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

Нисходящие (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
   • Добавление переменных. Представление о таблице символов
   • Добавление присваивания
   • Добавление типов
   • Добавление управляющих конструкций