IntroductionToProgrammingLanguages — различия между версиями
Материал из SEWiki
KorovinAA (обсуждение | вклад) (→Список групп для выполнения задач) |
Dimatwl (обсуждение | вклад) (→Список групп для выполнения задач) |
||
Строка 68: | Строка 68: | ||
* 1. Мартынов Семён, Башоров Залим, Казенюк Сергей, Витвицкий Александр, Тугарёв Денис. | * 1. Мартынов Семён, Башоров Залим, Казенюк Сергей, Витвицкий Александр, Тугарёв Денис. | ||
* 2. Кринкин Михаил, Лазарев Сергей, Фофанова Мария | * 2. Кринкин Михаил, Лазарев Сергей, Фофанова Мария | ||
− | * 3. Сорокин Артём, Коровин Алексей, Опейкин Александр | + | * 3. Сорокин Артём, Коровин Алексей, Опейкин Александр, Шеставин Дмитрий |
* 4. Иванов Антон, Крашенинникова Ксения, Лепенькин Ярослав, Диевский Алексей | * 4. Иванов Антон, Крашенинникова Ксения, Лепенькин Ярослав, Диевский Алексей | ||
* 5. | * 5. |
Версия 20:24, 14 февраля 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, будет совсем хорошо.
Программа курса
- 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.
* Не более 5 человек в каждой группе; старайтесь выравнивать группы по уровню.