This is an old revision of the document!
Table of Contents
Описание курса
Цели и задачи
Цель курса: Формирование системных знаний о теории формальных языков и автоматов с акцентом на практическое применение в разработке компиляторов и языковых процессоров.
Компетенции:
Знать: - Иерархию Хомского и классы формальных грамматик - Принципы работы детерминированных и недетерминированных автоматов - Методы синтаксического анализа (LL, LR, рекурсивный спуск) - Архитектуру компиляторов и трансляторов
Уметь: - Проектировать грамматики для предметно-ориентированных языков - Реализовывать лексические и синтаксические анализаторы - Генерировать промежуточное представление кода - Использовать ANTLR4 и LLVM для построения трансляторов
Владеть: - Навыками работы с современными инструментами языковой разработки - Методами оптимизации и генерации кода - Техниками отладки языковых процессоров
Структура курса
| Раздел | Лекции | Лабы | Практ. | Сам. раб. |
|---|---|---|---|---|
| Раздел 1: Регулярные языки и конечные автоматы | 7 | 4 | 3 | 7 |
| Раздел 2: КС-грамматики и МП-автоматы | 7 | 4 | 3 | 7 |
| Раздел 3: Синтаксический анализ | 7 | 4 | 3 | 7 |
| Раздел 4: Практика трансляции | 7 | 4 | 3 | 7 |
| Итого | 28 | 16 | 12 | 28 |
Содержание разделов
Раздел 1: Регулярные языки и конечные автоматы
Теория: - Формальные языки и грамматики - Конечные автоматы (ДКА/НКА) - Регулярные выражения - Минимизация и преобразование автоматов
Практика: - Реализация сканеров на ANTLR4 - Генерация лексических анализаторов - Оптимизация регулярных выражений
Раздел 2: КС-грамматики и МП-автоматы
Теория: - Контекстно-свободные грамматики - Автоматы с магазинной памятью - Нормальные формы (Хомского, Грейбах) - Свойства КС-языков
Практика: - Проектирование грамматик для DSL - Построение нисходящих парсеров - Обработка синтаксических ошибок
Раздел 3: Синтаксический анализ
Теория: - LL(1) и LR(1) анализ - Рекурсивный спуск - Табличные методы разбора - Абстрактные синтаксические деревья
Практика: - Реализация парсеров на ANTLR4 - Построение и обход AST - Семантический анализ
Раздел 4: Практика трансляции
Теория: - Архитектура компиляторов - Промежуточные представления - Генерация кода - Оптимизации
Практика: - Интеграция с LLVM - Генерация native-кода - Создание предметно-ориентированных языков
Инструментарий
Основные инструменты
ANTLR4 - Генерация лексеров и парсеров - Поддержка множества целевых языков - Интеграция с системами сборки
LLVM - Промежуточное представление LLVM IR - Кросс-платформенная генерация кода - Оптимизации на уровне IR
DeepSeek (контролируемое использование) - Анализ и рефакторинг кода - Генерация шаблонов реализаций - Помощь в отладке сложных конструкций
Оценочные материалы
Формы контроля
* Лабораторные работы: 40% * Практические задания: 20% * Экзамен: 40%
Вопросы для подготовки
1. Иерархия Хомского: классы и их характеристики 2. ДКА и НКА: эквивалентность и преобразования 3. Регулярные выражения и их применение в лексическом анализе 4. КС-грамматики: свойства и нормальные формы 5. Синтаксический анализ: LL(1) vs LR(1) 6. Построение AST и семантический анализ 7. Генерация кода с использованием LLVM 8. Оптимизации на разных этапах компиляции
Литература
Основная
1. Теренс Парр - “The Definitive ANTLR 4 Reference” 2. Крис Латтнер - “LLVM Essentials” 3. Альфред Ахо и др. - “Компиляторы: принципы, технологии и инструменты”
Дополнительная
1. Официальная документация ANTLR4 2. LLVM Tutorial и Language Reference 3. Статьи по построению DSL и языковых процессоров