Содержание дисциплины

  1. Классификация и структура трансляторов.
  2. Алфавит. Операции над символами алфавита. Определение грамматики.
  3. Отношения и их свойства. Матрицы отношений и их построение. Отношения FIRST, LAST и их транзитивных замыканий.
  4. Основные определения курса. Сентенциальная форма и предложение. Вывод и непосредственный вывод. Фраза, простая фраза, основа. Язык.
  5. Синтаксические деревья. Неоднозначности: лексическая, синтаксическая, семантическая, грамматики, языка.
  6. Классификация грамматик по Хомскому.
  7. Операторы. Ассоциативность и приоритет.
  8. Разбор и распознаватель. Определение и виды разбора: лексический и синтаксический, нисходящий и восходящий.
  9. Лексический анализ. Сканер. Символ и лексема. Регулярные грамматики и регулярные выражения. Конечные автоматы.
  10. Синтаксический анализ. Классификация анализаторов. Предикативный анализ и разбор с возвратами. Нисходящий рекурсивный распознаватель.
  11. Семантический анализ. Атрибуты и атрибутивные грамматики. Восстановление после ошибок.
  12. Грамматики предшествования и грамматики предшествования операторов.
  13. LL(k)-грамматики. Множества FIRST и FOLLOW. Определение принадлежности грамматики LL(k) классу. Принцип работы и построение LL(k)-распознавателя.
  14. LR(k)-грамматики. Перенос и свертка. LR(k)-распознаватели. Принцип работы и построение SLR(1)-распознавателя. Разрешение конфликтов LR-анализа.
  15. Временная сложность и затраты памяти распознавателей. Распознаватели КЯК, Эрли, Ульмана, Томита, ЯНРОВ.
  16. Организация таблицы символов. Таблицы символов, имеющие блочную структуру. Таблица видов. Организация таблицы видов. Описатели.
  17. Формы записи внутреннего представления кода. Инфиксная и обратная польская запись операций. Деревья.
  18. Средства разработки трансляторов. Их классификации и основные представители.
  19. Построитель анализаторов FLEX (LEX).
  20. Построитель анализаторов BISON (YACC).
  21. Построитель анализаторов ANTLR.
  22. Грамматики TAG, PEG, TDPL. Построение компилятора.

Рекомендуемая литература

Основная литература

  1. Грис Д. Конструирование компиляторов для ЦВМ. – М.: Мир, 1975.
  2. Ахо А. и др. Компиляторы: принципы, технологии инструменты. - 2-е изд. – М.: Вильямс, 2008.

Дополнительная литература

  1. Молчанов А. Ю. Системное программное обеспечение. Лабораторный практикум. – СПб.: Питер Принт, 2005.
  2. Parr Terence. The Definitive ANTLR Reference: Building Domain-Specific Languages. – USA, North Carolina, Raleigh, 2007.

Интернет-ресурсы

  1. Формальные языки // Wikipedia.org. - URL: http://ru.wikipedia.org/wiki/Категория:Формальные языки.
  2. Средства проектирования и разработки трансляторов. - URL: http://catalog.compilertools.net/.