Theory and Methods of Translation and Compilation

2020/2021

Academic Year

RUS

Instruction in Russian

3

ECTS credits

Delivered at:

Department of Applied Mathematics and Informatics (Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod))

Course type:

Compulsory course

When:

3 year, 3, 4 module

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

Аннотация

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

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

• Дать специалисту основные знания о том, как устроен компилятор
• Дать специалисту знания о разных частях компилятора и как их можно реализовать и применять

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

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

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

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

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

• Контрольная работа 1
  Преобразование РВ в НКА и в ДКА
• Контрольная работа 2
  Нисходящий СА
• Практическая работа 1 и 2
  Алгоритм преобразования РВ -> НКА -> ДКА
• Практическая работа 3
  Нисходящий СА
• Практическая работа 4
  LR(0)-анализ
• Устный ответ на вопросы из билетов
• Контрольная работа 1
  Преобразование РВ в НКА и в ДКА
• Контрольная работа 2
  Нисходящий СА
• Практическая работа 1 и 2
  Алгоритм преобразования РВ -> НКА -> ДКА
• Практическая работа 3
  Нисходящий СА
• Практическая работа 4
  LR(0)-анализ
• Устный ответ на вопросы из билетов

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

• Промежуточная аттестация (4 модуль)
  0.2 * Контрольная работа 1 + 0.2 * Контрольная работа 2 + 0.3 * Практическая работа 1 и 2 + 0.15 * Практическая работа 3 + 0.15 * Практическая работа 4

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

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

• Малявко А. А. - ФОРМАЛЬНЫЕ ЯЗЫКИ И КОМПИЛЯТОРЫ. Учебное пособие для вузов - М.:Издательство Юрайт - 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