Skip to content

Latest commit

 

History

History
80 lines (70 loc) · 6.22 KB

plan.md

File metadata and controls

80 lines (70 loc) · 6.22 KB
Raw

<-- метка " сейчас мы находимся здесь "

Семестр 1 (Осень)

Введение.

  • 2 подхода к конструктивному описанию языка
  • Приложения
  • Примеры за пределами синтаксического анализа исходного кода:
  1. примитивный язык запросов к БД
  2. формальный верификатор ПО для работы с каналом связи
  3. статический анализ работы приложения с памятью

Конечные автоматы; Регулярные языки; Регулярные грамматики.

Лексический анализ: теория и практика.

  • регулярные выражения: языковые формулы, выход за пределы регулярных языков.
  • почему регулярных языков недостаточно?
  • примеры построения лексеров. flex. Обгон утилиты wc по производительности.

Магазинные автоматы; Рекурсивные автоматы. Свойства замкнутости КС языков. Композиция, прямое произведение и пересечение.

  • примеры для языка Дика с несколькими типами скобок.

КС-грамматики. Синтаксический анализ.

  • Нормальная Форма Хомского, Ослабленная Нормальная Форма Хомского.
  • Алгоритм приведения к НФХ.
  • CYK-алгоритм синтаксического анализа для строк.
  • Расширенная форма Бекуса-Наура.
  • Генерация МП-автомата по грамматике. И наоборот.

Иерархия Хомского.

  • 4 типа языков по Хомскому.
  • "Промежуточные типы грамматик". Мягко-контекстно-зависимые языки. Грамматики с контекстами.

КС-достижимость

  • Обобщение CYK на графы.
  • Алгоритм Хеллингса.
  • КС-достижимость через операции линейной алгебры (перенесено на весну).

LL-разбор и рекурсивный спуск.

  • Рекурсивный спуск.
  • LL(k) - анализ. Множества FIRST и FOLLOW.
  • Теория и практика. Практика построения LL-анализаторов.
  • Boost::Spirit QI. Примеры. (Забыл рассказать. Не критично, рассмотрим).
  • Устранение левой рекурсии.
  • Обобщенный LL.

LR-разбор.

  • SLR/LALR - реализации.
  • Практика построения LR-анализаторов. ANTLR. Bison. Исправление сдвиг-свёртка и свёртка-свёртка конфликтов.

Элементы синтаксически управляемой трансляции.

  • Атрибутные грамматики. Наследуемые и синтезируемые атрибуты.
  • Семантические действия.

Внутреннее устройство современного компилятора.

  • Последовательность преобразования программ при компиляции.
  • Связь дерева синтаксического разбора и абстрактного синтаксического дерева.
  • Семантический анализ.
  • Оптимизационные проходы.
  • Теория и современность.
  • Clang как фронтенд: как это устроено на самом деле... <-- 1-е прочтение курса состоялось.

Семестр 2 (Весна)

Компиляторные технологии.

  • Абстрактное синтаксическое дерево. Повторение.
  • Обходы по дереву. AST Consumers. Паттерн ООП "посетитель", выполнение операций на вершинах AST. Примеры.
  • Статический анализ программ на абстрактном синтаксическом дереве.
  • Использование libclang + python clang для работы с астрактным синтаксическим деревом Clang.
  • Реализация простейшего статического анализатора С/C++ кода на python при помощи libclang.
  • Трансляция AST в промежуточное представление.

О некоторых грамматиках большей выразительности, чем КС-грамматики

  • Иерархия Хомского. Повторение.
  • О некоторых грамматиках промежуточного типа: мягко-контекстно-зависимые грамматики (Mildly context-sensitive grammars).
  • Грамматики с контекстами.
  • Рассмотрение приложений: пример реализации анализатора подмножества языка Си с семантическим анализом, реализуемым непосредственно грамматическим разбором.
  • Другие грамматики типа MCS: грамматики надстройки деревьев, параллельные грамматики.

Алгоритмы КС-достижимости в терминах линейной алгебры

  • Матричный подход
  • Тензорный подход

О некоторых обобщённых алгоритмах КС-разбора

  • О GLR-алгоритме
  • О GLL-алгоритме на примере инструмента Iguana parser

О некоторых приложениях КС-достижимости