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

Версия 22:43, 26 февраля 2012

Введение в языки программирования

Лектор - Дмитрий Юрьевич Булычев

Учёт посещаемости занятий

Учёт сдачи домашних заданий

Лекции

• Лекция №1 10.02.2012
• 17.02.2012

В семантике ошибка: правило для переменной вместо

[x](s)=s(x)

читать как

[x](s)=[s(x)](s).

• 24.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, будет совсем хорошо.

• [Задание №2] срок сдачи 24 февраля 2011

Написать принтер, который по абстрактному синтаксическому дереву программы печатает её представление в конкретном синтаксисе (который мы обсуждали) и интерпретатор (который вычисляет значение выражения в данном состоянии).

Описание конкретного синтаксиса для представления программ на языке L:

1. Программа представляется в виде последовательности слов. Разделителем служит перевод строки.
2. Пусть E --- выражение, а |E| --- представление этого выражения в данном конкретном синтаксисе. Тогда:
   • переменная v представляется в виде "x" v (то есть символ x (как терминал), и собственно имя переменной на следующей строчке).
   • функция {x -> E} представляется в виде "f" x |E|
   • применение функции F E представляется в виде "a" |E| |F|
   • условное выражение C ? T : E представляется в виде "?" |C| |T| |E|
   • бинарная операция X o Y представляется в виде "@" |X| |Y|
   • константа i представляется в виде "!" i
3. Контекст (список определений name1=expr1, name2=expr2 и т.д.) представляется как последовательность name1 |expr1| name2 |expr2| и т.д.
4. Программа (то есть выражение E в контексте C) представляется как последовательность |C| ";" |E|.
5. Все реализации д.з. №2 должны уметь читать файл, содержащий описание программы в таком синтаксисе (иначе невозможно ничего проверить).

Пример 1. Выражение

{x -> {y -> x + y}} 1 2

в данном конкретном синтаксисе выглядит так:

a
a
f
x
f
y
@
+
x
x
x
y
!
1
!
2

Пример 2. Программа

fact = {n -> n ? n * (fact n-1) : 1};
fact 4

будет представлена как

fact
f
$0
?
x
$0
@
*
x
$0
a
x
fact
@
-
x
$0
!
1
!
1
;
a
x
fact
!
4

• [Задание №3] желаемый срок сдачи 26 февраля 2011
  1. Написать порождающую грамматику для языка над алфавитом {a, b, c}, состоящего из всех слов, в которых количество букв a, b и c одинаково.
  2. Написать порождающую грамматику для языка над алфавитом {0, 1}, состоящего из всех слов, в которых не встречается две единицы подряд.
  3. Написать порождающую грамматику для языка над алфавитом {0, 1, *}, состоящего из всех слов вида sas, где s --- непустая строка нулей и единиц любой длины, а a --- непустая строка из звездочек любой длины.
  4. Написать порождающую грамматику для языка над алфавитом {a, b}, состоящего из всех вида a^nb^m, где n <> m.
  5. Написать порождающую грамматику для языка над алфавитом {a, b}, состоящего из всех слов, в которых количество букв a в два раза больше, чем количество букв b.
  6. Правда ли, что любой рекурсивный язык контекстно-зависим (обратное, как известно, верно)?
  7. Написать реализацию построения НКА по регулярной грамматике; написать интерпретатор этого автомата, который проверяет принадлежность заданного слова языку, и принтер, который печатает граф переходов автомата в формате .dot пакета graphviz.
  8. Написать грамматику для порождения выражений в алфавите {x, +, *, (, )}, где x играет роль операндов, * и + --- левоассоциативные операции (то есть E+F+G означает ((E+F)+G)), операция * связывает операнды сильнее, чем + (то есть E+F*G означает E+(F*G)), причем порождаемые выражения НЕ ДОЛЖНЫ содержать ненужных скобок (а именно, например, выражение x+(x*x) не должно порождаться)

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

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.

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

1. [Haskell] Мартынов Семён, Башоров Залим, Казенюк Сергей, Витвицкий Александр, Тугарёв Денис.
2. Кринкин Михаил, Лазарев Сергей, Фофанова Мария, Бандурин Дмитрий, Ждан Анна
3. [JAVA] Сорокин Артём, Коровин Алексей, Опейкин Александр, Шеставин Дмитрий, Владислав Савельев
4. [C++] Иванов Антон, Крашенинникова Ксения, Лепенькин Ярослав, Диевский Алексей, Кормишин Сергей
5. Певзнер Алина, Князев Сергей
6. [JAVA] Великий Алексей.

* Не более 5 человек в каждой группе; старайтесь выравнивать группы по уровню, и не повторяться в выборе языков.

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

• Latest OCaml release
• Documentation and user’s manual