Конспект лекций «Методы построения компиляторов» — различия между версиями
Ulysses (обсуждение | вклад) (→Фазы компиляции) |
Ulysses (обсуждение | вклад) (→Перевод: СУ-перевод) |
||
| Строка 213: | Строка 213: | ||
==Перевод== | ==Перевод== | ||
| + | Ранее мы решали вопрос о принадлежности некоторой цепочки α интересующему нас языку L, задаваемому грамматикой G. Но задача компиляции шире: не только распознать входную цепочку, но и сгенерировать выходную. | ||
| − | ===Схема синтаксически управляемого (СУ) перевода=== | + | '''Определение.''' Пусть Σ и Δ — два алфавита (называемые „входным“ и „выходным“ соответственно). L<sub>1</sub> ⊂ Σ*, L<sub>2</sub> ⊂ Δ*. ''Переводом'' с языка 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> | ||
| + | |} | ||
| + | Выведем цепочку <tt>a * (b + c)</tt> и одновременно переведём её в ПОЛИЗ: <tt>a b c + *</tt> (как обычно, используем ''левый вывод''): | ||
| + | (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,'' это четвёрка | ||
| + | G<sub>in</sub> = (N, Σ, R, S), | ||
| + | где | ||
| + | P = {A → α | ∃β A → (α, β) ∊ R}. | ||
| + | |||
| + | '''Определение.''' ''Выходная грамматика, соответствующая СУ-схеме T,'' это четвёрка | ||
| + | G<sub>o</sub> = (N, Δ, R, S), | ||
| + | где | ||
| + | P = {A → β | ∃α A → (α, β) ∊ R}. | ||
| + | |||
| + | '''Определение.''' ''СУ-перевод'' (''СУ-трансляция'') это множество | ||
| + | {(x, y) | (S, S) ⇒* (x, y), x ∊ Σ*, y ∊ Δ*}, | ||
| + | обозначаемое обычно τ(T). | ||
| + | |||
| + | СУ-перевод можно понимать как ''трансформацию синтаксических деревьев'' (соответствующих выводу входной и выходной цепочек). | ||
==Синтаксический анализ== | ==Синтаксический анализ== | ||
Версия 23:25, 6 апреля 2009
Содержание
Литература
- А.Ахо, Р.Сети, Д.Ульман. Компиляторы. Принципы, технологии, инструменты.М, Вильямс, 2001
- С.З.Свердлов. Языки программирования и методы трансляции. Питер, 2007
- Э.А.Опалева, В.П.Самойленко. Языки программирования и методы трансляции. BHV, 2005
- Ю.Г.Карпов. Основы построения трансляторов. 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 |
|
Почти на каждой стадии могут выполняться дополнительные оптимизации, а также происходит анализ и обработка ошибок.
В таблицу символов заносятся имена, присутствовавшие в исходном тексте — об этом обычно заботится лексический анализатор, заменяя идентификаторы, пришедшие из входного потока на некоторые стандартные (например, id1, id2, ...).
Думаю, что заботится все-таки о занесении в таблицу символов даже не синтаксический анализатор, а построитель семантического дерева 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. Но задача компиляции шире: не только распознать входную цепочку, но и сгенерировать выходную.
Определение. Пусть Σ и Δ — два алфавита (называемые „входным“ и „выходным“ соответственно). L1 ⊂ Σ*, L2 ⊂ Δ*. Переводом с языка 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
Примеры
- Простейший калькулятор
- Простейший калькулятор с приоритетом операций
- Создание дерева разбора программы
- Преобразование в XML
- Добавление переменных. Представление о таблице символов
- Добавление присваивания
- Добавление типов
- Добавление управляющих конструкций
