zhChinese    enEnglish
  ПМ-ПУ  » Образование  » Программы курсов » Теория формальных языков и трансляций

Теория формальных языков и трансляций

Курс по выбору

Лектор: д.ф.-м.н., проф. Братчиков И.Л.

1. Введение

1.1. Естественные и искусственные языки и задача их изучения математическими средствами.
1.2. Математическая модель языка.
1.3. Формальное определение понятия "перевод".
1.4. Описание свойств естественных и искусственных языков с помощью метаязыков.
1.5. Метасинтаксические и метасемантические языки.

2. Формальные грамматики и языки

2.1. Нормальные формы Бэкуса-Наура (БНФ) как метасинтаксический язык.
2.2. Примеры задания языков с помощью БНФ.
2.3. Порождение и анализ предложений языков, заданных с помощью БНФ.
2.4. Рекурсивные БНФ. Виды рекурсий.
2.5. Определение формальной порождающей грамматики Хомского.
2.6. Выводы и языки, порождаемые грамматиками.
2.7. Проблема распознавания языков, порождаемых грамматиками.
2.8. Иерархия Хомского для формальных грамматик.
2.9. Теорема о распознавании языков, порождаемых неукорачивающими грамматиками.
2.10. Контекстно-свободные (КС-) грамматики и их свойства.
2.11. Деревья выводов.
2.12. Порождение бесконечных языков КС-грамматиками.
2.13. Неукорачивающие и укорачивающие КС-грамматики.
2.14. Соотношение языков, порождаемых этими грамматиками.
2.15. Регулярные (Р-) грамматики. Свойства правил вывода этих грамматик.
2.16. Представление Р-грамматик в виде графов с нагруженными дугами.
2.17. Интерпретация выводов на графах.
2.18. Скобочные языки и невозможность задания этих языков Р-грамматиками.
2.19. Машина Тьюринга как распознаватель языков.
2.20. Проблема остановки для машин Тьюринга.
2.21. Классы машин Тьюринга и их соответствие классам формальных грамматик.

3. Трансляторы

3.1. Задача трансляции языков программирования.
3.2. Исходные и объектные языки.
3.3. Трансляция языков высокого уровня.
3.4. Интерпретаторы и компиляторы как два класса трансляторов.
3.5. Схема типичного компилятора. Основные программные модули компилятора и их назначение.
3.6. Лексический анализ. Понятие лексемы.
3.7. Конечные автоматы как класс алгоритмов, реализующих лексический анализ.
3.8. Разработка лексических анализаторов с помощью диаграмм состояний.
3.9. Синтаксический анализ. Видонезависимый и видозависимый анализ.
3.10. Восходящие и нисходящие анализаторы.
3.11. Отношения предшествования и их вычисление по КС-грамматикам.
3.12. Анализатор предшествования как абстрактная машина.
3.13. Математическое определение и примеры работы анализатора предшествования.
3.14. Оценка трудоемкости.
3.15. Разделенные грамматики и LL(1)-анализатор.
3.16. Построение управляющей таблицы анализатора. Анализатор как абстрактная машина.
3.17. Математическое определение и примеры работы LL(1)-анализатора. Оценка трудоемкости.
3.18. Анализатор Эрли. Принцип работы.
3.19. Параметр k, определяющий "заглядывание вперед".
3.20. Понятие о положениях. Основные и присоединенные положения.
3.21. Состояния анализатора и процесс их построения.
3.22. Примеры работы анализатора. Оценка трудоемкости.
3.23. Видозависимый синтаксический анализ.
3.24. Контекстные условия языков программирования. Примеры контекстных условий в различных языках. Методы проверки контекстных условий.
3.25. Промежуточные языки, используемые трансляторами при генерации объектного кода.
3.26. Обратная польская (постфиксная) запись программ как пример промежуточного языка.
3.27. Принципы работы генераторов объектного кода. Понятие об оптимизации.
3.28. Примеры локальной и глобальной оптимизации объектного кода.
3.29. Методы обработки ошибок в формальных языках.
3.30. Понятие о локальных и глобальных анализаторах ошибок.
3.31. Обработка ошибок при трансляции и при выполнении объектного кода.
3.32. Компьютеры RISC-архитектуры и особенности разработанных для них трансляторов.

4. Заключение.

4.1. Краткий обзор содержание курса и обсуждение контрольных вопросов для экзамена.

Список рекомендуемой литературы

  1. Братчиков И.Л. Синтаксис языков программирования. М.: Наука, 1975.
  2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978.
  3. Хантер Р. Проектирование и конструирование компиляторов. М.: Финансы и статистика, 1984.
  4. Мартыненко Б.К. Синтаксически управляемая обработка данных. СПб.: Изд-во СПбГУ, 1997.