IntroductionToProgrammingLanguages — различия между версиями

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

Версия 22:03, 11 февраля 2012

Лекции

  • [Лекция №1] 10.02.2012


Домашние задания

  • [Задание №1 к 17 февраля 2011]

написать генерирующее расширения для программы возведения в степень

   int exp (int x, int n) {
      int y = 1;
      while (n) {
          if (n % 2) y *= x;
          n /= 2;
          x *= x;
      }
      return y;
   }

Это генерирующее расширение должно для своего единственного параметра n печатать остаточную программу, полученную специализацией функции exp на это значение n. Если это генерирующее расширение сохранит в себе какие-то черты exp, будет совсем хорошо.

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

Вопросы после 19-го - опционально.

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

оптимальная линеаризация.

  • 26. Анализ потока данных. Полурешеточная модель. 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.

Список групп для выполнения задач

  • 1. Мартынов Семён, Башоров Залим, Казенюк Сергей, Витвицкий Александр, Тугарёв Денис.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.

Полезные ссылки

  • Latest OCaml release
  • Documentation and user’s manual