• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Theory and Methods of Translation and Compilation

2017/2018
Academic Year
RUS
Instruction in Russian
4
ECTS credits
Delivered at:
Department of Applied Mathematics and Informatics (Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod))
Course type:
Elective course
When:
2 year, 3, 4 module

Программа дисциплины

Аннотация

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

Цель освоения дисциплины

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

Планируемые результаты обучения

  • Знать что такое компилятор, как он устроен, какая часть отвечает за что
  • Составление регулярного выражения для описания шаблона токена
  • Преобразование регулярного выражения в НКА
  • Преобразование НКА в ДКА и использование ДКА для проверки реализации шаблона
  • Что такое грамматики и как их строить
  • Устранение неоднозначности, устранение левой рекурсии и левая факторизация грамматики
  • Проводить нисходящий синтаксический анализ
  • Проводить восходящий синтаксический анализ
  • Использовать LR анализ, построение LR(0)-автомата и его применение
  • Что такое трёхадресный код, трансляция выражений
Содержание учебной дисциплины

Содержание учебной дисциплины

  • Введение в компиляцию и структура компилятора
    Что такое компилятор и из каких основных частей он состоит
  • Лексический анализ
    Роль лексического анализатора, что такое токены, шаблоны, лексемы. Как распознавать токены: диаграммы переходов, конечные автоматы (НКА, ДКА). Регулярные выражения -> ДКА -> НКА
  • Генерация промежуточного кода
    Трехадресный код, типы и объявления, трансляция выражений
  • Синтаксический анализ
    Роль синтаксического анализатора, образца грамматик. Контекстно-свободные грамматики. Разработка грамматики: устранение необнозначности, устранение левой рекурсии, левая факторизация. Нисходящий СА: методом рекурсивного спуска, FIRST\FOLLOW. Восходящий СА: свертки, основы. Введение в LR анализ: пункты, LR(0)-автомат, алгоритм LR-анализа
Элементы контроля

Элементы контроля

  • неблокирующий домашнее задание
  • неблокирующий экзамен
  • неблокирующий тест
Промежуточная аттестация

Промежуточная аттестация

  • Промежуточная аттестация (4 модуль)
    0.5 * домашнее задание + 0.5 * тест
Список литературы

Список литературы

Рекомендуемая основная литература

  • Малявко А. А. - ФОРМАЛЬНЫЕ ЯЗЫКИ И КОМПИЛЯТОРЫ. Учебное пособие для вузов - М.:Издательство Юрайт - 2019 - 429с. - ISBN: 978-5-534-04288-7 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/formalnye-yazyki-i-kompilyatory-438060

Рекомендуемая дополнительная литература

  • Вирт Н. - Построение компиляторов - Издательство "ДМК Пресс" - 2010 - 192с. - ISBN: 978-5-94074-585-3 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/1262