Теоретические основы языков программирования


Программа курса

  1. Языки программирования, синтаксис, семантика, прагматика. Когнитивные особенности человеческого мышления и их влияние на развитие языков программирования.
  2. Языки программирования в ретроспективе. Процедурное, объектно-ориентированное, логическое и функциональное программирование. Предметно-ориентированные языки. Языки вне классификации.
  3. Абстрактный и конкретный синтаксис. Статическая и динамическая семантика. Компиляция и интерпретация. Проекции Футамуры-Ершова.
  4. Генеративный и аналитический подходы к описанию синтаксиса. Формальные грамматики, иерархия Хомского.
  5. Регулярные языки и конечные автоматы. Применение регулярных выражений в народном хозяйстве (grep/sed/awk) и для лексического анализа (lex/flex). Отсутствие бесконтекстной лексики в реальных языках программирования.
  6. Контекстно-свободные грамматики. Нормальные формы Хомского и Грейбах. Алгоритмы Эрли и Кока-Янгера-Касами. Неконтекстосвободность реальных языков программирования.
  7. Нисходящий анализ. Возврат и заглядывание вперед. Класс языков LL(k). Рекурсивный спуск, магазинные автоматы, парсер-комбинаторы, PEG, "скаредный" разбор. GLL. Инструменты нисходящего анализа (Parsec, ANTLR и пр.)
  8. Восходящий анализ, классы LR(k) и LALR(k). GLR. Инструменты восходящего анализа (yacc/bison).
  9. Двухуровневые и атрибутные грамматики, вопросы применения на практике.
  10. Идентификация. Область видимости и область действия. Статическое и динамическое, раннее и позднее связывание.
  11. Энергичность и ленивость. Call-by-name, call-by-value, call-by-reference.
  12. Строгость, чистота, прозрачность по ссылкам.
  13. Языки с типами и языки без типов. Статическая и динамическая типизация.
  14. Номинальная и структурная эквивалентность типов. Простейшие конструкторы.
  15. Типы с кванторами и что они означают. Универсальные и экзистенциальные типы.
  16. Subtyping. Структурный и номинальный subtyping.
  17. Динамическая семантика языков. Операционная семантика большого и малого шага.
  18. Денотационный подход к описанию семантики.
  19. Аксиоматическая семантика. Верификация программ. Design by contract.
  20. Когерентность языков программирования и машинных архитектур. Языково-специфичные архитектуры, виртуальные машины и JIT-компиляция.
  21. * Структура рабочей программы. Код, данные, библиотеки, поддержка времени исполнения.
  22. * Задача генерации кода. Генерация кода путем интерпретации.
  23. * Восходящее переписывание деревьев и динамическое программирование (BURS).
  24. * Алгоритмы распределения регистров. Распределение регистров и раскраска графов.
  25. * Параллелизм на уровне инструкций. Планирование инструкций.
  26. * Анализ потока управления. Глубинное остовное дерево, доминирование, анализ циклической структуры программ. Сводимость. Устранение недостижимого кода, оптимальная линеаризация.
  27. * Анализ потока данных. Полурешеточная модель. RD, LV, AE, UEU. Устраненние мертвого кода, экономия общих подвыражений, понижение силы операций, чистка циклов.

* - вопросы будут рассмотрены при наличии времени.


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

  1. S.Muchnik. Advanced Compiler Design & Implementation. Academic Press, Morgan Kaufmann, 1998.
  2. А.Ахо, Р.Сети, С.Ульман. Компиляторы: принципы, технологии, инструменты. Вильямс, 2003.
  3. А.Ахо, С.Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М., "Мир", 1978.
  4. F.Nielsen. Principles of Program Analysis. Springer, 2005.
  5. F.Nielse, H-R.Nielsen. Semantics with Applications. Wiley Professional Computing, 1992.
  6. B.Pierce. Types and Programming Languages. MIT Press, 2002.
  7. T.Пратт. Языки программирования: разработка и реализация. 1978.
  8. Б.К.Мартыненко. Языки и трансляции. Из-во СПбГУ, 2008.