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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
(→‎Фазы компиляции)
(→‎Фазы компиляции)
Строка 35: Строка 35:
 
   MOVF R1, id1
 
   MOVF R1, id1
  
−
Количество проходов компилятора и его связь с фазами компиляции
+
Группировка фаз
 +
* Front-end и back-end компиляторы.
 +
* Проходы
 +
* Уменьшение количества проходов (на примере предварительного описания подпрограмм)
 +
 
 +
Инструментарий для создания компиляторов
 +
 
 +
* Генераторы лексических анализаторов (сканеров)
 +
* Генераторы синтаксических анализаторов (парсеров)
 +
* Автоматические генераторы кода
 +
 
 +
Компиляторы компиляторов
 +
* Lex + Yacc
 +
* Flex + Bison
 +
* CoCo
 +
* Antlr
 +
* Gold Parser Builder
 +
* GPLex + GPPG
 +
 
  
 
-----
 
-----

Версия 22:34, 14 февраля 2009

Лекция 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

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

  • 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, ... - нетерминалы
α,β,γ, ... - строки нетерминалов

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

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

Примеры

  1. Простейший калькулятор
    • Простейший калькулятор с приоритетом операций
    • Создание дерева разбора программы
    • Преобразование в XML
    • Добавление переменных. Представление о таблице символов
    • Добавление присваивания
    • Добавление типов
    • Добавление управляющих конструкций
Источник — «http://it.mmcs.sfedu.ru/_wiki/index.php?title=Конспект_лекций_«Методы_построения_компиляторов»&oldid=973»