Geum.ru

Технологии трансляции

Вид материалаПрограмма

Содержание


Содержание курса
Синтаксический анализ
Нисходящий анализ
Синтаксически управляемая трансляция
Среды времени выполнения
Подобный материал:
УЧЕБНАЯ ПРОГРАММА ПО ДИСЦИПЛИНЕ

ТЕХНОЛОГИИ ТРАНСЛЯЦИИ

Ипатов Е.Б.


Для очной формы обучения ВСЕГО 110

Всего аудиторных занятий 65

самостоятельная работа 45


Программу составил: профессор Ипатов Е.Б.


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

Для того чтобы успешно справиться с освоением содержания курса, необходимо обладать знаниями в объёме курса «Информатика и программирование» и «Теории вычислительных процессов и структур». Для того чтобы понимать содержание курса, необходимо уметь программировать на языке C# или С++; иметь начальные знания по математике (геометрии, тригонометрии, линейной алгебре, дифференциальному исчислению и математическому анализу).

В результате изучения дисциплины каждый студент должен:
    • иметь представление о:
  • Основных направлениях развития архитектур ЭВМ, в том числе и параллельных архитектурах.
  • Системе команд микропроцессоров.
  • Основных этапах сборки программы.
  • Синтаксически управляемом переводе текстов с одного языка на другой.
  • Выполнении аналитического дифференцирования с помощью обобщенного синтаксически управляемого перевода.
  • Основных технологиях, используемых при построении компиляторов.
  • Месте компилятора в программном обеспечении.
    • знать:
  • Основные фазы процесса компиляции.
  • Основные задачи лексического, синтаксического и семантического анализа.
  • Спецификации языка Lex.
  • Правила записи регулярных выражений на языке Perl и C#.
    • уметь:
  • Выполнять построение лексического анализатора на языке Lex.
  • Выполнять анализ работы автомата с магазинной памятью при построении дерева синтаксического разбора.
  • Уметь реализовывать структуру данных «стек» и «очередь» на языке Си и C#..
  • Использовать для реализации динамических структур данных, классы определённые в языке C++ и C#.
  • Проектировать хранилища данных, позволяющие хранить большие объёмы данных. Предоставлять возможность быстрого поиска и модификации в таком хранилище данных
  • Использовать стандартные реализации классических структур данных на языке C# и C++.
  • Уметь создавать простой одно-проходовый компилятор.


Основные виды занятий: лекции и практические занятия.

Основные виды текущего контроля занятий: тестирование; выполнение индивидуальных заданий.

Основной вид рубежного контроля знаний: зачет.


СОДЕРЖАНИЕ КУРСА

Тема 1. Процесс компиляции. Основные понятия. Этапы, фразы и проходы. Структура компилятора. Интегрированные среды разработки. Проектирование компилятора. Использование инструментальных средств. Место компилятора в программном обеспечении.

Тема 2. Определение языка. Синтаксис языка. Грамматики. Основные отличия регулярных и контекстно-свободных языков. Порождения. Неоднозначные грамматики. Ограничения контекстно-свободных грамматик. Задачи синтаксического анализа. Определение семантики.

Тема 3. Лексический анализ. Основные понятия. Задачи лексического анализа. Токены. Шаблоны. Лексемы. Атрибуты токенов. Лексические ошибки. Буферизация ввода. Ограничители. Распознавание токенов. Диаграммы переходов. Регулярные выражения. Регулярные определения. Нерегулярные множества.

Тема 4. Спецификации языка Lex. Построение лексического анализатора по программе на языке Lex. Поиск лексем во входном буфере на основе HKA. Использование детерминированного конечного автомата для лексического анализа. Построение DKA по регулярному выражению. Реализация прогностического оператора основные лексические затруднения. Минимизация количества состояний в лексических анализаторах. Методы сжатия таблиц.

Тема 5. Синтаксический анализ. Роль синтаксического анализатора. Обработка синтаксических ошибок. Стратегия восстановления после ошибок. Деревья разбора. Неоднозначность. Регулярные выражения и контекстно-свободные грамматики. Устранение неоднозначности. Устранение левой рекурсии. Левая факторизация. Построение не контекстно-свободных грамматик.

Тема 6. Нисходящий анализ. Анализ методом рекурсивного спуска. Предикативные анализаторы и их диаграммы переходов. Построение таблиц предикативного анализа. Функции FIRST и FOLLOW. LL(1) грамматики.

Тема 7. Восходящий синтаксический анализ. Особенности LR-анализа. Генераторы синтаксических анализаторов. Введение в YACC. Вычисление Метрик. Использование YACC. Взаимодействие Lex и YACC.

Тема 8. Синтаксически управляемая трансляция. Синтаксически управляемые определения. Наследуемые атрибуты. Графы зависимости. Построение синтаксических деревьев. Восходящее выполнение S атрибутных определений. Восходящие вычисления наследуемых атрибутов.

Тема 9. Среды времени выполнения. Вопросы исходного языка: Процедуры, области видимости объявления, стеки управления и т.д. Организация памяти. Классификация памяти времени выполнения. Размещение локальных данных в процессе компиляции. Записи активации.

Стратегия выделения памяти. Статическое распределение памяти. Стековое распределение памяти. Висячие ссылки. Распределение памяти в куче. Доступ к нелокальным именам. Блоки.

Лексическая область видимости без вложенных процедур и при наличии вложенных процедур. Дисплеи. Динамическая область видимости. Передача параметров. Передача по значению. Передача по ссылке. Передача по имени.

Тема 10. Таблицы символов. Записи таблицы символов. Информация о выделенной памяти. Использование списков для представления таблицы символов. Хеш-таблицы. Возможности языков по динамическому выделению памяти. Мусор. Висячие ссылки. Технология динамического распределения памяти.

Тема 11. Генерация промежуточного кода. Языки промежуточных представлений. Графическое представление. Трёхадресный код. Типы трехадресных инструкций. Синтаксически управляемая трансляция в трехадресный код. Реализация трехадресных инструкций.

Р-код. Байт-код. Генерация кода. Модель ЭВМ. Динамическая организация памяти. Организация магазина со статической цепочкой и дисплеем.

Тема 12. Назначение адресов. Трансляция переменных. Трансляция целых выражений. Трансляция арифметических выражений. Трансляция логических выражений. Выделение общих подвыражений.

Трансляция объектно-ориентированных свойств языков программирования. Виртуальные базовые классы. Наследование и виртуальные функции. Генерация оптимального кода методами синтаксического анализа.

Сопоставление образцов. Синтаксический анализ для Т-грамматик. Выбор дерева вывода.

Тема 13. Создание машинного кода. Выбор инструкций. Распределение регистров. Распределение регистров путем раскрашивания графа.

Тема 14. Элементы теории перевода. Преобразователи с магазинной памятью. Синтаксически управляемый перевод. Схемы синтаксически управляемого перевода. Обобщенные синтаксически управляемые переводы.

Тема 15. Атрибутные грамматики. Определение атрибутных грамматик классы атрибутных грамматик и их реализация. Язык описания атрибутных грамматик.


ЛИТЕРАТУРА

Основная:
  1. Мартыненко Б. К. Языки и трансляции. Учебное пособие. – СПб: Издательство С. Петербургского университета, 2002. 229 с.
  2. Серебряков В.А., Галочкин М.П. и др Теория и реализация языков программирования /Учебное пособие/ - М.: М3-Пресс Москва, 2003г., 345 с.


Дополнительная:
  1. Альфред Ахо Рави Сети, Джефри Ульман. Компиляторы: принципы, технологии, инструменты. Пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 768 c.
  2. Хантер Робин. Основные концепции компиляторов. Пер. с англ. – М.: Издательский дом «Вильямс», 2002. – 256 c.