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

Вопросы к экзамену
Вопросы к экзамену 2015
Задачи по темам
Задачи к экзамену

Лабораторные работы
1. Построение лексического анализатора
2. Построение преобразователей
3. Примеры программ на языке Haskell

Курсовая и лабороторные работы. Уч.пособие (задания для ЛР и КР)
Темы курсовых работ (дополнительно) (см. также разделы "Программные системы" и "Языки программирования")
Обзор литературы
Языки программирования. Проекты для реализации трансляторов, интерпретаторов.
Конспекты лекций (по аналогичным курсам в других ВУЗах)
Книги, статьи, методические материалы и др.
Ресурсы интернета
Лабораторная работа по системе COCO/R (часть 2)
COCO/R для C++ (часть 2)

Программные системы, инструментарий

• Генераторы лексических анализаторов Yacc & Lex
  Здесь даны примеры построения различных компиляторов, парсеров etc.
• Cистема "COCO/R" разработана в университете г.Линца (Австрия). Один из соавторов Х.Мессенбек - создатель языков программирования Object Oberon и Oberon-2 (совместно с Н.Виртом). См. его статьи в разделе "Языки программирования....". Система проста в использовании и позволяет генерировать компиляторы для языков C#, Delphi, Pascal, C++, Java, Modula-2, Ada и др.
  Загрузить: coco.rar(810K) - COCO/R длс C#
  Загрузить: coco_d.rar(2.8M) - COCO/R длс Delphi
  Или непосредственно с сайта авторов: www.ssw.uni-linz.ac.at/Research/Projects/Coco/
  Описание системы в книге Мозговой М.В. Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход.- СПб.,Наука и техника, 2006.-320.
• Система "Конечные автоматы и грамматики" (студенты каф.806)
• Cистема "КАШТАН". Проблемно-ориентированная программная среда для изучения и исследования средств описания и синтеза распознающих компонентов языкового процессора.
  Загрузить: kashtan.rar(536K)
  Описание системы в книге Компаниец Р.И.,Маньков Е.В., Филатов Н.Е. Системное программирование. Основы построения трансляторов./Учебное пособие для высших и средних учебных заведений.- СПб.,КОРОНА принт, 2000.-256с.
• Проект Parser Generator (студенты ЛЭТИ)
• Описание генератора сканеров и генератора парсеров (рус) LEX и YACC (англ.). Vern Paxson
• Генератор сканеров Flex, версия 2.5 (англ.). Vern Paxson
  загрузка с http://www.gnu.org/software/flex/flex.html
• Генератор синтаксических анализаторов, совместимый с YACC для Bison версии 1.35. Чарльз Доннелли, Ричард Столлмен
• Bison 2.0 (англ.)
  загрузка с http://www.gnu.org/software/bison/bison.html
• ANTLR - генератор эффективных анализаторов на основе LL(k)-грамматик
  загрузка с http://www.antlr.org

• Язык SIMPLE
  М.Черкашин. Компилятор пишется так... Журнал "Монитор" № 4 1992 год
• Язык Tiny-C
  Использование учебного компилятора в курсе "Формальные языки и основы компиляции"
• Интерпретатор языка МИНИЛАН (программа на Паскале)
• Подмножество языка Паскаль
• Язык программирования NIP
• Язык программирования Тьюрингол
• M-Язык (описание и компилятор на С см. в Лекции ВМиК. Элементы теории трансляции )

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

Среди них (всего в списке 365 языков!):
• Язык программирования Whitespace В алфавите только 3 символа: пробел, табуляция и перенос строки
• Язык программирования Brainf*ck.
  Полный по Тьюрингу язык программирования с восемью инструкциями. Работающий компилятор в 171 байт длиной!
• FALSE. Цель - создать мощный (и "замудренный") язык с как можно более компактным компилятором (первоначально 1024 байта на Ассемблере 68000)
• AAAAAAAAAAAAAA!!!! Алфавит языка состоит из одной буквы А, пробела, запятой и восклицательного знака!
• Полный по Тьюрингу язык программирования COW.
  Вот программа, вычисляющая последовательность чисел Фибоначчи:
  MoO moO MoO mOo MOO OOM MMM moO moO MMM mOo mOo moO MMM mOo MMM moO moO MOO MOo mOo MoO moO moo mOo mOo moo
• 
  Как правило, эзотерические языки очень просты и хорошо подходят для упражнений по теории компиляции.
  Но есть и языки типа Malbolge (по названию восьмого круга ада из "Божественной комедии" Данте - Злые Щели).
  Первая программа - пишущая HEllO WORld - была найдена генетическим алгоритмом
  А вот так выглядит CAT-программа (копирует стандартный ввод в стандартный вывод):

  (aBA@?>=<;:9876543210/.-,JH)('&%$#"!~}|{zy\J6utsrq
  ponmlkjihgJ%dcba`_^]\[ZYXWVUTSRQPONMLKJIHGF('C%$$^
  K~<;4987654321a/.-,\*)
  j
  !~%|{zya}|{zyxwvutsrqSonmlO
  jLhg`edcba`_^]\[ZYXWV8TSRQ4
  ONM/KJIBGFE>CBA@?>=<;{9876w
  43210/.-m+*)('&%$#"!~}|{zy\
  wvunslqponmlkjihgfedcEa`_^A
  \>ZYXWPUTSRQPONMLKJIH*FEDC&
  A@?>=<;:9876543210/.-m+*)(i
  &%$#"!~}|{zyxwvutsrqpRnmlkN
  ihgfedcba`_^]\[ZYXWVU7SRQP3
  NMLKJIHGFEDCBA@?>=<;:z8765v
  3210/.-,+*)('&%$#"!~}_{zyx[
  vutsrqjonmlejihgfedcba`_^]@
  [ZYXWVUTSRo
  
  
  

• Борисенко В.В. Лекции по программированию (мех-мат МГУ, 2002-2003)
  • Лекция 10. Формальные грамматики
  • Лекция 11. Конечные автоматы и регулярные языки
  • Лекция 12. LR-разбор
• Формальные грамматки и языки (ВМиК МГУ)
  • Элементы теории формальных языков и грамматик. Задачи.
  • Элементы теории трансляции. Задачи.
  • Модельный SQL-интерпретатор
• В.А.Серебряков. Лекции по конструированию компиляторов. Москва, 1993
• В.А.Серебряков, М.П.Галочкин Основы конструирования компиляторов
• Д.В.Варсанофьев, А.Г.Дымченко "Основы компиляции" осень,1991. Материалы к лекциям
  1. Языки и грамматики. Простейший компилятор.
  2. Иерархия Хомского. Регулярные языки.
  3. Lex и другие.
  4. КС-языки и грамматики.
  5. Разбор снизу-вверх. Сдвиг-свертка.Простое и операторное предшествование.
  6. LR(k)-грамматики.SLR(1), LALR(1) - грамматики.
  7. YACC
  8. Атрибутные грамматики. Семантические подпрограммы.
  9. Таблицы символов.
  10. Проверка типов.
  11. Организация памяти во время выполнения программы.
• Г.Н.Твердохлебов. КОНСПЕКТ ЛЕКЦИЙ ПО ДИСЦИПЛИНЕ "СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ" Тема: "Трансляторы" Восточноукраинский государственный университет, 1995 г.

• Ахо А., Ульман Дж. Теория синтаксического анализа, вывода и компиляции. М.:Мир,1978, т.1 и 2.
  том 1 (5М)
  том 2 (4М)
• Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии, инструмента.: Пер.с англ.- М.:Издательский дом "Вильямс", 2001. Сокращенный перевод глав 1,2,3
• С.П. Крицкий. Трансляция языков программирования: синтаксис, семантика, перевод. (Ростовский ГУ)
• методические материалы по курсу "Основы построения трансляторов" ф-т Автоматики и вычислительной техники (АВТФ) Новосибирского государственного технического университета (НГТУ). Примеры на C++
• Е.И.Чигарина,М.А.Шамашов.Основы теории формальных грамматик. уч.пособие.САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ им.академика С.П. КОРОЛЕВА, 2001г. tfg_lecture.rar (415K)

• Европейский центр программирования http://www.europrog.ru
• Н.Вирт. Конструирование компилятора. http://www.oberon2005.ru/book/ccnwe.pdf
• Оберон-технологии в России http://www.oberoncore.ru
• Информатика-21. МЕЖДУНАРОДНЫЙ ОБЩЕСТВЕННЫЙ НАУЧНО-ОБРАЗОВАТЕЛЬНЫЙ ПРОЕКТ http://www.inr.ac.ru/~info21/
• Коллекция избранных книг по классике компьютерных наук (ACM Favorite Computer Science Books). http://pd.acm.org/books/classics/camp.cfm
• Компиляторы. Принципы, методы и средства http://www.kit.kulichki.ru
• Генераторы лексических и синтаксических анализаторов и многое др.(см.там же)
• SoftCraft: Основы разработки трасляторов http://www.softcraft.ru/translat/lect/content.shtml (рус.)
• YACC.1 - компилятор компиляторов (рус.)
• Марченко А.Л. C++. Бархатный путь. Избранные главы (рус.)
• Е.А. Роганов Основы информатики и программироваия. Уч.пособие (рус.)
• Контекстно-свободные грамматики (рус.)
• В.С.Фомичев. Формальные языки, грамматики и автоматы (рус.)
• Б.К.Мартыненко. Языки и транслицмм (рус.)