Теория компиляции

Лектор: Борисенко Владимир Витальевич

Дистанционное обучение

Предлагается для дистанционных лекций и семинаров использовать Zoom.
Время встречи (Meeting), весенний семестр 2022 г.:
среда в 16:45, продолжительность 1 час 30 минут.
Первая лекция 2 марта 2022.

Ссылка на Zoom-конференцию:
https://us02web.zoom.us/j/2842740990?pwd=bkhtRlNxL3E3SnZCTU1oSFNHcHJNQT09

Meeting ID: 284 274 0990
пароль 1

Осенний семестр 2021-22 учебного года

Записи лекций (текст на "виртуальной доске"), осенний семестр 2021

Формат предсталения конечного автомата в виде XML-файла, пример: "automaton.xml". Имена состояний и входные сигналы могут содержать произвольные строки. Переход по пустой последовательности обозначается как вход "eps":

    <transition>
        <input>eps</input>
        <destination>state_name</destination>
    </transition>

Видео лекции 29 Sep 2021

Видео лекции 06 Oct 2021

Видео лекции 13 Oct 2021

Видео лекции 27 Oct 2021

Весенний семестр 2022 г.

Записи лекций (текст на "виртуальной доске"), весенний семестр 2022

• Видео лекции 16 марта 2022:
  Повторение материала предыдущего семестра. Формальные языки и грамматики. Классы грамматик: контекстно зависимые, контекстно свободные, праволинейные (автоматные, регулярные языки). Правые и левые выводы, синтаксические деревья для контекстно-свободных языков. LR-процесс. Соотвествие между правыми выводами и успешными LR-процессами. Построение множества состояний LR(0)-разбора.
• Видео лекции 23 марта 2022:
  Задача разбора, восходящий разбор, LR-процесс. Построение множества состояний LR(0)-разбора и таблицы LR-парсера. Алгоритм работы LR-парсера. Семантический стек парсера. Конфликты сдвиг-свертка и свертка-свертка. Пример грамматики, не являющейся LR(0)-грамматикой.
• Видео лекции 30 марта 2022:
  Разрешение конфликтов LR(0)-разбора путем учета первого символа аванцепочки. Построение множества состояний LR(1)-разбора. Детерминированные языки. Пример однозначного языка, не допускающего LR(1)-разбор.

Материалы прошлых лет

Осенний семестр 2020-21 учебного года

Записи лекций, осенний семестр 2020-21

Примеры задач для экзамена.

Видео лекции 8 апреля 2020: Парсер логических выражений.

Видео лекции 29 апреля 2020: Учебный компилятор "Delta".

• Программа курса.
• flex & bison для MS Windows.
• Описание Lex и Yacc.
• Примеры сканеров, реализованных при помощи LEX:
  • выделение имен и целых констант из входного потока;
  • удаление комментариев из C и C++ программ;
  • выделение имен, целых и вещественных констант из входного потока;
  • раскрашивание лексем в C/C++ программе;
  • сканер для калькулятора формул, реализованного с помощью YACC.
• LL(1)-разбор (рекурсивный разбор):
  • LL(1)-парсер для перевода формулы из прямой польской записи в обычную;
  • LL(1)-парсер для языка арифметических формул, сканер реализован без использован flex;
  • LL(1)-парсер для языка арифметических формул, сканер реализован с помощью flex. Архив всех файлов проекта: ;
  • Qt-проект "Рисование графика функции", разбор выражения, определяющего функцию, реализован с помощью рекурсивного парсера с использованием flex: .
    
• LR(1)-разбор (восходящий разбор с помощью конечного автомата со стеком)
  • Калькулятор арифметических формул, реализованный с помощью системы Lex и YACC:
    • архив со всеми исходными файлами "YaccCalc.zip";
    • исходный текст сканера (файл "scan.l");
    • исходный текст парсера (файл "calc.y").
  • Парсер описаний переменных языка C, реализованный с помощью Lex и YACC:
    • архив со всеми исходными файлами "CTypes.zip";
    • исходный текст сканера (файл "scan.l");
    • исходный текст парсера (файл "ctypes.y").
  • Парсер логических выражений:
    • архив со всеми исходными файлами "LParser.zip";
    исходный текст сканера (файл "lscan.l");
    • исходный текст парсера;
    дерево логических выражений (файл "ltree.c").
  • Учебный компилятор "Delta", реализованный с помощью Lex и YACC.
    • Список задач по проекту "Учебный компилятор Delta".
  • Примеры программ для лабораторных работ.