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

Материал из SEWiki
Перейти к: навигация, поиск
(→‎Домашние задания)
 
(не показано 26 промежуточных версий 7 участников)
Строка 1: Строка 1:
−
'''Введение в языки программирования'''
+
'''Теоретические основы языков программирования'''
  
 
Лектор - Дмитрий Юрьевич [http://www.matmex.spb.ru/photoalbum/person_teachers_BulychevDY_1.html Булычев]
 
Лектор - Дмитрий Юрьевич [http://www.matmex.spb.ru/photoalbum/person_teachers_BulychevDY_1.html Булычев]
 +
 +
[https://docs.google.com/spreadsheet/ccc?key=0ApYxPEC9C_QXdC00UkVJekxYV0pYYVAxTmFXUkt6SVE Учёт посещаемости занятий]
 +
 +
[https://docs.google.com/spreadsheet/ccc?key=0ApYxPEC9C_QXdE05Q09iWlRqRzJ3d1FwTlJRSEkxbFE Учёт сдачи домашних заданий]
 +
 +
[https://docs.google.com/spreadsheet/ccc?key=0ApYxPEC9C_QXdEt4OGxJQ0VaVTRQNGFnNndmMG1hY3c Результаты контрольной работы]
 +
* Первое число - количество правильных ответов
 +
* Второе чисто - количество засчитанных (правильных и грамотно обоснованных) ответов
 +
''Результаты второй контрольной так же будут опубликованы по ссылке выше''
  
 
== Лекции ==
 
== Лекции ==
 +
 
* [http://code.google.com/p/aptu-tex/source/browse/formallang/les1/les.tex Лекция №1] 10.02.2012
 
* [http://code.google.com/p/aptu-tex/source/browse/formallang/les1/les.tex Лекция №1] 10.02.2012
 +
* 17.02.2012
 +
В семантике ошибка: правило для переменной вместо
 +
[x](s)=s(x)
 +
читать как
 +
[x](s)=[s(x)](s).
 +
* 24.02.2012
  
 
== Домашние задания ==
 
== Домашние задания ==
−
* [Задание №1] срок сдачи 17 февраля 2011
+
 
−
написать генерирующее расширения для программы возведения в степень
+
=== Задание №1 ===
 +
Cрок сдачи '''17 февраля 2011'''
 +
 
 +
Написать генерирующее расширения для программы возведения в степень.
  
 
     int exp (int x, int n) {
 
     int exp (int x, int n) {
Строка 21: Строка 40:
  
 
Это генерирующее расширение должно для своего единственного параметра n печатать остаточную программу, полученную специализацией функции exp на это значение n. Если это генерирующее расширение сохранит в себе какие-то черты exp, будет совсем хорошо.
 
Это генерирующее расширение должно для своего единственного параметра n печатать остаточную программу, полученную специализацией функции exp на это значение n. Если это генерирующее расширение сохранит в себе какие-то черты exp, будет совсем хорошо.
 +
 +
=== Задание №2 ===
 +
Cрок сдачи '''24 февраля 2011'''
 +
 +
Написать принтер, который по абстрактному синтаксическому дереву программы печатает её представление в конкретном синтаксисе (который мы обсуждали) и интерпретатор (который вычисляет значение выражения в данном состоянии).
 +
 +
Описание конкретного синтаксиса для представления программ на языке L:
 +
# Программа представляется в виде последовательности слов. Разделителем служит перевод строки.
 +
# Пусть 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
 +
# Контекст (список определений name1=expr1, name2=expr2 и т.д.) представляется как последовательность name1 |expr1| name2 |expr2| и т.д.
 +
# Программа (то есть выражение E в контексте C) представляется как последовательность |C| ";" |E|.
 +
# Все реализации д.з. №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
 +
 +
[http://narod.ru/disk/42015820001.bfed0d23b277fa721f7e86f27dc45e3d/monoMix.opt.html Программа], которая воспринимает программы в языке L в обычном синтаксисе, и печатает их представление в данной упрощенной форме. Бинарник для x86-linux, -h --- помощь.
 +
 +
=== Задание №3 ===
 +
Желаемый срок сдачи '''26 февраля 2011'''
 +
 +
# Написать порождающую грамматику для языка над алфавитом {a, b, c}, состоящего из всех слов, в которых количество букв a, b и c одинаково.
 +
# Написать порождающую грамматику для языка над алфавитом {0, 1}, состоящего из всех слов, в которых не встречается две единицы подряд.
 +
# Написать порождающую грамматику для языка над алфавитом {0, 1, *}, состоящего из всех слов вида sas, где s --- непустая строка нулей и единиц любой длины, а a --- непустая строка из звездочек любой длины.
 +
# Написать порождающую грамматику для языка над алфавитом {a, b}, состоящего из всех вида a^nb^m, где n <> m.
 +
# Написать порождающую грамматику для языка над алфавитом {a, b}, состоящего из всех слов, в которых количество букв a в два раза больше, чем количество букв b.
 +
# Правда ли, что любой рекурсивный язык контекстно-зависим (обратное, как известно, верно)?
 +
# Написать реализацию построения НКА по регулярной грамматике; написать интерпретатор этого автомата, который проверяет принадлежность заданного слова языку, и принтер, который печатает граф переходов автомата в формате .dot пакета graphviz.
 +
# Написать грамматику для порождения выражений в алфавите {x, +, *, (, )},  где x играет роль операндов, * и + --- левоассоциативные операции (то есть E+F+G означает ((E+F)+G)), операция * связывает операнды сильнее, чем + (то есть E+F*G означает E+(F*G)), причем порождаемые выражения НЕ ДОЛЖНЫ содержать ненужных скобок (а именно, например, выражение x+(x*x) не должно порождаться)
 +
----
 +
[http://bashor.github.com/GrGen/GrGen.html Генератор] Залима для проверки 1-5 пунктов.
 +
Коментарии:
 +
T -- терминальные символы. Пробелы и запятые игнорируются, т.е. abc == a b c == a b, c
 +
Все остальные символы считаются нетерминальными
 +
R -- правила преобразования вида: From : to
 +
пробелы и пустые строки игнорируются.
 +
Кроме того, можно указать свой чекер на JavaScript. Например:
 +
1) return countChar(st, 'a') == countChar(st, 'b') && countChar(st, 'a') == countChar(st, 'c');
 +
2) return st.indexOf("11") == -1;
 +
3) var matches = /^([10]+)[*]+([10]+)$/g.exec(st);
 +
return matches[1] == matches[2] && matches.length == 3;
 +
4) var matches = /^(a*)(b*)$/g.exec(st);
 +
return matches.length == 3 && matches[1].length != matches[2].length;
 +
5) return countChar(st, 'a') == countChar(st, 'b') * 2;
 +
init -- (пере)инициализация
 +
step -- выполнение "одного шага"
 +
 +
=== Задание №4 ===
 +
 +
# Проверить, что статич. семаника L, которую мы определили на занятии (новая переменная для каждой fun + попарно различные имена в контексте + имена переменных в fun отличаются от имен определений в контексте) действительно позволяет избежать неприятностей при подстановке, когда свободная переменная в подставляемом замыкается каким-то fun в том, куда подставляется.
 +
# Написать на L быстрое возведение в степень и сортировку списка.
 +
# Модифицировать defun и deint и те правила семантики, в которых они используются, чтобы из семантики для вычисления выражения получилась семантика моновариантного специализатора.
 +
# Запустить специализатор для возведения в степень при известном показателе; разобраться и проинтерпретировать результаты.
 +
# Разобраться с вопросом о замкнутости множества всех регулярных языков относительно пересечения.
 +
# Разобраться с вопросом о разрешимости проблемы эквивалентности регулярных грамматик (она же --- проблема эквивалентности конечных автоматов); если разрешима --- разработать и реализовать алгоритм проверки эквивалентности.
 +
# Написать для конечных автоматов:
 +
#* Устранение \epsilon - переходов;
 +
#* Приведение к детерминированной форме;
 +
#* "Объединитель", "дополнитель" и "замыкатель".
 +
 +
=== Задание №5 ===
 +
 +
# Реализовать преобразование рег. грамматики в рег. выражение, определяющее тот же язык.
 +
# Реализовать обратное преобразование.
 +
 +
=== Задание №6 ===
 +
 +
Реализовать приведение грамматики в НФХ и алгоритм Кока-Янгера-Касами.
 +
 +
=== Задание №7 ===
 +
 +
Реализовать интерпретатор НМА и преобразование КС-грамматики в программу для него.
 +
 +
=== Задание №8 ===
 +
 +
# Написать реализацию вычисления функций FIRST_k и FOLLOW_k.
 +
# Реализовать функцию тестирования грамматики на принадлежность к классу LL(k).
  
 
== Программа курса ==
 
== Программа курса ==
  
−
* 1. Языки программирования, синтаксис, семантика, прагматика. Когнитивные особенности человеческого мышления и их влияние на развитие языков программирования.
+
# Языки программирования, синтаксис, семантика, прагматика. Когнитивные особенности человеческого мышления и их влияние на развитие языков программирования.
−
* 2. Языки программирования в ретроспективе. Процедурное, объектно-ориентированное, логическое и функциональное программирование. Предметно-ориентированные языки. Языки вне классификации.  
+
# Языки программирования в ретроспективе. Процедурное, объектно-ориентированное, логическое и функциональное программирование. Предметно-ориентированные языки. Языки вне классификации.  
−
* 3. Абстрактный и конкретный синтаксис. Статическая и динамическая семантика. Компиляция и интерпретация. Проекции Футамуры-Ершова.
+
# Абстрактный и конкретный синтаксис. Статическая и динамическая семантика. Компиляция и интерпретация. Проекции Футамуры-Ершова.
−
* 4. Генеративный и аналитический подходы к описанию синтаксиса. Формальные грамматики, иерархия Хомского.  
+
# Генеративный и аналитический подходы к описанию синтаксиса. Формальные грамматики, иерархия Хомского.  
−
* 5. Регулярные языки и конечные автоматы. Применение регулярных выражений в народном хозяйстве (grep/sed/awk) и для лексического анализа (lex/flex). Отсутствие бесконтекстной лексики в реальных языках программирования.
+
# Регулярные языки и конечные автоматы. Применение регулярных выражений в народном хозяйстве (grep/sed/awk) и для лексического анализа (lex/flex). Отсутствие бесконтекстной лексики в реальных языках программирования.
−
* 7. Контекстно-свободные грамматики. Нормальные формы Хомского и Грейбах. Алгоритмы Эрли и Кока-Янгера-Касами. Неконтекстосвободность реальных языков программирования.
+
# Контекстно-свободные грамматики. Нормальные формы Хомского и Грейбах. Алгоритмы Эрли и Кока-Янгера-Касами. Неконтекстосвободность реальных языков программирования.
−
* 6. Нисходящий анализ. Возврат и заглядывание вперед. Класс языков LL(k). Рекурсивный спуск, магазинные автоматы, парсер-комбинаторы, PEG, "скаредный" разбор. GLL. Инструменты нисходящего анализа (Parsec, ANTLR и пр.)
+
# Нисходящий анализ. Возврат и заглядывание вперед. Класс языков LL(k). Рекурсивный спуск, магазинные автоматы, парсер-комбинаторы, PEG, "скаредный" разбор. GLL. Инструменты нисходящего анализа (Parsec, ANTLR и пр.)
−
* 7. Восходящий анализ, классы LR(k) и LALR(k). GLR. Инструменты восходящего анализа (yacc/bison).
+
# Восходящий анализ, классы LR(k) и LALR(k). GLR. Инструменты восходящего анализа (yacc/bison).
−
* 8. Двухуровневые и атрибутные грамматики, вопросы применения на практике.
+
# Двухуровневые и атрибутные грамматики, вопросы применения на практике.
−
* 9. Идентификация. Область видимости и область действия. Статическое и динамическое, раннее и позднее связывание.  
+
# Идентификация. Область видимости и область действия. Статическое и динамическое, раннее и позднее связывание.  
−
* 10. Энергичность и ленивость. Call-by-name, call-by-value, call-by-reference.
+
# Энергичность и ленивость. Call-by-name, call-by-value, call-by-reference.
−
* 11. Строгость, чистота, прозрачность по ссылкам.
+
# Строгость, чистота, прозрачность по ссылкам.
−
* 12. Языки с типами и языки без типов. Статическая и динамическая типизация.  
+
# Языки с типами и языки без типов. Статическая и динамическая типизация.  
−
* 13. Номинальная и структурная эквивалентность типов. Простейшие конструкторы.
+
# Номинальная и структурная эквивалентность типов. Простейшие конструкторы.
−
* 14. Типы с кванторами и что они означают. Универсальные и экзистенциальные типы.  
+
# Типы с кванторами и что они означают. Универсальные и экзистенциальные типы.  
−
* 15. Subtyping. Структурный и номинальный subtyping.  
+
# Subtyping. Структурный и номинальный subtyping.  
−
* 16. Динамическая семантика языков. Операционная семантика большого и малого шага.
+
# Динамическая семантика языков. Операционная семантика большого и малого шага.
−
* 17. Денотационный подход к описанию семантики.  
+
# Денотационный подход к описанию семантики.  
−
* 18. Аксиоматическая семантика. Верификация программ. Design by contract.
+
# Аксиоматическая семантика. Верификация программ. Design by contract.
−
* 19. Когерентность языков программирования и машинных архитектур. Языково-специфичные архитектуры, виртуальные машины и JIT-компиляция.
+
# Когерентность языков программирования и машинных архитектур. Языково-специфичные архитектуры, виртуальные машины и JIT-компиляция.
−
* 20*. Структура рабочей программы. Код, данные, библиотеки, поддержка времени исполнения.
+
#<nowiki>*</nowiki> Структура рабочей программы. Код, данные, библиотеки, поддержка времени исполнения.
−
* 21*. Задача генерации кода. Генерация кода путем интерпретации.
+
#<nowiki>*</nowiki> Задача генерации кода. Генерация кода путем интерпретации.
−
* 22*. Восходящее переписывание деревьев и динамическое программирование (BURS).
+
#<nowiki>*</nowiki> Восходящее переписывание деревьев и динамическое программирование (BURS).
−
* 23*. Алгоритмы распределения регистров. Распределение регистров и раскраска графов.
+
#<nowiki>*</nowiki> Алгоритмы распределения регистров. Распределение регистров и раскраска графов.
−
* 24*. Параллелизм на уровне инструкций. Планирование инструкций.
+
#<nowiki>*</nowiki> Параллелизм на уровне инструкций. Планирование инструкций.
−
* 25*. Анализ потока управления. Глубинное остовное дерево, доминирование, анализ циклической структуры программ. Сводимость. Устранение недостижимого кода, оптимальная линеаризация.
+
#<nowiki>*</nowiki> Анализ потока управления. Глубинное остовное дерево, доминирование, анализ циклической структуры программ. Сводимость. Устранение недостижимого кода, оптимальная линеаризация.
−
* 26*. Анализ потока данных. Полурешеточная модель. RD, LV, AE, UEU. Устраненние мертвого кода, экономия общих подвыражений, понижение силы операций, чистка циклов.
+
#<nowiki>*</nowiki> Анализ потока данных. Полурешеточная модель. RD, LV, AE, UEU. Устраненние мертвого кода, экономия общих подвыражений, понижение силы операций, чистка циклов.
  
 
''<nowiki>* - вопросы будут рассмотрены при наличии времени.</nowiki>''
 
''<nowiki>* - вопросы будут рассмотрены при наличии времени.</nowiki>''
  
 
== Список литературы ==
 
== Список литературы ==
−
* 1. S.Muchnik. Advanced Compiler Design & Implementation. Academic Press, Morgan Kaufmann, 1998.
+
# S.Muchnik. Advanced Compiler Design & Implementation. Academic Press, Morgan Kaufmann, 1998.
−
* 2. А.Ахо, Р.Сети, С.Ульман. Компиляторы: принципы, технологии, инструменты. Вильямс, 2003.
+
# А.Ахо, Р.Сети, С.Ульман. Компиляторы: принципы, технологии, инструменты. Вильямс, 2003.
−
* 3. А.Ахо, С.Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М., "Мир", 1978.
+
# А.Ахо, С.Ульман. Теория синтаксического анализа, перевода и компиляции. Том 1. М., "Мир", 1978.
−
* 4. F.Nielsen. Principles of Program Analysis. Springer, 2005.
+
# F.Nielsen. Principles of Program Analysis. Springer, 2005.
−
* 5. F.Nielse, H-R.Nielsen. Semantics with Applications. Wiley Professional Computing, 1992.
+
# F.Nielse, H-R.Nielsen. Semantics with Applications. Wiley Professional Computing, 1992.
−
* 6. B.Pierce. Types and Programming Languages. MIT Press, 2002.
+
# B.Pierce. Types and Programming Languages. MIT Press, 2002.
−
* 7. T.Пратт. Языки программирования: разработка и реализация. 1978.
+
# T.Пратт. Языки программирования: разработка и реализация. 1978.
−
* 8. Б.К.Мартыненко. Языки и трансляции. Из-во СПбГУ, 2008.
+
# Б.К.Мартыненко. Языки и трансляции. Из-во СПбГУ, 2008.
  
 
== Список групп для выполнения задач ==
 
== Список групп для выполнения задач ==
  
−
* 1. Мартынов Семён, Башоров Залим, Казенюк Сергей, Витвицкий Александр, Тугарёв Денис.
+
# [Haskell] Мартынов Семён, Башоров Залим, Казенюк Сергей, Витвицкий Александр, Тугарёв Денис.
−
* 2. Кринкин Михаил, Лазарев Сергей, Фофанова Мария, Бандурин Дмитрий
+
# Кринкин Михаил, Лазарев Сергей, Фофанова Мария, Бандурин Дмитрий, Ждан Анна
−
* 3. Сорокин Артём, Коровин Алексей, Опейкин Александр, Шеставин Дмитрий, Владислав Савельев
+
# [JAVA] Сорокин Артём, Коровин Алексей, Опейкин Александр, Шеставин Дмитрий, Владислав Савельев
−
* 4. Иванов Антон, Крашенинникова Ксения, Лепенькин Ярослав, Диевский Алексей, Кормишин Сергей
+
# [C++] Иванов Антон, Крашенинникова Ксения, Лепенькин Ярослав, Диевский Алексей, Кормишин Сергей
−
* 5.
+
# Певзнер Алина, Князев Сергей
−
* 6.
+
# [JAVA] Великий Алексей.
  
−
''<nowiki>* Не более 5 человек в каждой группе; старайтесь выравнивать группы по уровню.</nowiki>''
+
''<nowiki>* Не более 5 человек в каждой группе; старайтесь выравнивать группы по уровню, и не повторяться в выборе языков.</nowiki>''
  
 
== Полезные ссылки ==
 
== Полезные ссылки ==
Строка 79: Строка 230:
 
* [http://caml.inria.fr/ocaml/release.en.html Latest OCaml release]
 
* [http://caml.inria.fr/ocaml/release.en.html Latest OCaml release]
 
* [http://caml.inria.fr/pub/docs/manual-ocaml/index.html Documentation and user’s manual]
 
* [http://caml.inria.fr/pub/docs/manual-ocaml/index.html Documentation and user’s manual]
 +
 +
==== JFLAP ====
 +
JFLAP is software for experimenting with formal languages topics including nondeterministic finite automata, nondeterministic pushdown automata, multi-tape Turing machines, several types of grammars, parsing, and L-systems. In addition to constructing and testing examples for these, JFLAP allows one to experiment with construction proofs from one form to another, such as converting an NFA to a DFA to a minimal state DFA to a regular expression or regular grammar. Click here for more information on what one can do with JFLAP.
 +
* [http://www.jflap.org/ JFLAP]

Текущая версия на 21:50, 17 мая 2012

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

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

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

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

Результаты контрольной работы

  • Первое число - количество правильных ответов
  • Второе чисто - количество засчитанных (правильных и грамотно обоснованных) ответов

Результаты второй контрольной так же будут опубликованы по ссылке выше

Лекции

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

[x](s)=s(x)

читать как 

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

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

Задание №1

Cрок сдачи 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

Cрок сдачи 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

Программа, которая воспринимает программы в языке L в обычном синтаксисе, и печатает их представление в данной упрощенной форме. Бинарник для x86-linux, -h --- помощь.

Задание №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-5 пунктов. Коментарии: 

T -- терминальные символы. Пробелы и запятые игнорируются, т.е. abc == a b c == a b, c
Все остальные символы считаются нетерминальными
R -- правила преобразования вида: From : to
пробелы и пустые строки игнорируются.
Кроме того, можно указать свой чекер на JavaScript. Например:
1) return countChar(st, 'a') == countChar(st, 'b') && countChar(st, 'a') == countChar(st, 'c');
2) return st.indexOf("11") == -1;
3) var matches = /^([10]+)[*]+([10]+)$/g.exec(st);
return matches[1] == matches[2] && matches.length == 3;
4) var matches = /^(a*)(b*)$/g.exec(st);
return matches.length == 3 && matches[1].length != matches[2].length;
5) return countChar(st, 'a') == countChar(st, 'b') * 2;
init -- (пере)инициализация
step -- выполнение "одного шага"

Задание №4

  1. Проверить, что статич. семаника L, которую мы определили на занятии (новая переменная для каждой fun + попарно различные имена в контексте + имена переменных в fun отличаются от имен определений в контексте) действительно позволяет избежать неприятностей при подстановке, когда свободная переменная в подставляемом замыкается каким-то fun в том, куда подставляется.
  2. Написать на L быстрое возведение в степень и сортировку списка.
  3. Модифицировать defun и deint и те правила семантики, в которых они используются, чтобы из семантики для вычисления выражения получилась семантика моновариантного специализатора.
  4. Запустить специализатор для возведения в степень при известном показателе; разобраться и проинтерпретировать результаты.
  5. Разобраться с вопросом о замкнутости множества всех регулярных языков относительно пересечения.
  6. Разобраться с вопросом о разрешимости проблемы эквивалентности регулярных грамматик (она же --- проблема эквивалентности конечных автоматов); если разрешима --- разработать и реализовать алгоритм проверки эквивалентности.
  7. Написать для конечных автоматов:
    • Устранение \epsilon - переходов;
    • Приведение к детерминированной форме;
    • "Объединитель", "дополнитель" и "замыкатель".

Задание №5

  1. Реализовать преобразование рег. грамматики в рег. выражение, определяющее тот же язык.
  2. Реализовать обратное преобразование.

Задание №6

Реализовать приведение грамматики в НФХ и алгоритм Кока-Янгера-Касами.

Задание №7

Реализовать интерпретатор НМА и преобразование КС-грамматики в программу для него.

Задание №8

  1. Написать реализацию вычисления функций FIRST_k и FOLLOW_k.
  2. Реализовать функцию тестирования грамматики на принадлежность к классу LL(k).

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

  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 человек в каждой группе; старайтесь выравнивать группы по уровню, и не повторяться в выборе языков.

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

JFLAP

JFLAP is software for experimenting with formal languages topics including nondeterministic finite automata, nondeterministic pushdown automata, multi-tape Turing machines, several types of grammars, parsing, and L-systems. In addition to constructing and testing examples for these, JFLAP allows one to experiment with construction proofs from one form to another, such as converting an NFA to a DFA to a minimal state DFA to a regular expression or regular grammar. Click here for more information on what one can do with JFLAP.

Источник — «http://mit.spbau.ru/sewiki/index.php?title=IntroductionToProgrammingLanguages&oldid=1425»