1 ТЕОРИЯ ФОРМАЛЬНЫХ ЯЗЫКОВ И ТРАНСЛЯЦИЙ Лекции для студентов 3 курса отделения информатики Мартыненко Борис Константинович д.ф.-м.н., проф. кафедры информатики

2 Введение ОГЛАВЛЕНИЕ Часть I: ЯЗЫКИ, ГРАММАТИКИ, АВТОМАТЫ Глава 1. Языки и их представлениеГлава 1 Глава 2. ГрамматикиГлава 2

3 Глава 3. Конечные автоматы иГлава 3 регулярные грамматики Глава 4. Контекстно-свободныеГлава 4 грамматики Глава 5. Магазинные автоматыГлава 5 ОГЛАВЛЕНИЕ

4 Глава 6. Машины ТьюрингаГлава 6 Глава 7. Машины Тьюринга: проблемаГлава 7 остановки, языки типа 0 Глава 8. Линейно ограниченныеГлава 8 автоматы и контекстно- зависимые языки Глава 9. Операции над языками ОГЛАВЛЕНИЕ

5 Глава 1. Трансляции, их представление иГлава 1 реализация Глава 2. LL(k)-Грамматики и трансляцииГлава 2 Глава 3. LR(k)-Грамматики и трансляцииГлава 3 Часть II: ТРАНСЛЯЦИИ И СИНТАКСИЧЕСКИЕ МЕТОДЫ ИХ РЕАЛИЗАЦИИ

6 ПриложениеПриложение: Неразрешимые и разрешимые проблемы, касающиеся формальных языков Указатель литературы Программа курса Список задач ТЕОРИЯ ФОРМАЛЬНЫХ ЯЗЫКОВ И ТРАНСЛЯЦИЙ

7 Литература Учебное пособие Мартыненко Б. К. Языки и трансляции. С.Пб.: изд. СПбГУ, с.

8 Литература 1.Greibach S. A. A note on undecidable properties of formal languages // Math. Systems Theory Vol. 2, 1. P.1–6. 2. Hopcroft J. E., Ullman J. D. Formal languages and their relation to automata. Reading, MA: Addison-Wesley Pub. Co., Inc., p.

9 Литература 3. Rozenberg G., Salomaa A. Handbook of Formal Languages. Berlin, Heidelberg: Springer-Verlag, Vol.1: 873 p., Vol. 2: 528 p., Vol. 3: 625 p. 4. Salomaa A. Formal languages. N.Y.: Academic Press, p.

10 Литература 5.Агафонов В. Н. Синтаксический анализ языков программирования: Учеб. пособие. Новосибирск: Изд-во НГУ, с. 6. Ахо А., Ульман Дж. Теория синтаксиче- ского анализа, перевода и компиляции. М.: Мир, Т. 1: Синтаксический анализ. 612 с.; Т. 2: Компиляция. 487 с.

11 Литература 7. Братчиков И. Л. Синтаксис языков про- граммирования. М.: Наука, с. 8. Гинзбург С. Математическая теория контекстно-свободных языков. М.: Мир, с. 9. Гладкий А. В. Формальные грамматики и языки. М.: Наука, с.

12 Литература 10. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, с. 11. Гросс М., Лантен А. Теория формаль- ных грамматик. М.: Мир, с. 12. Кнут Д. Искусство программирования для ЭВМ. Т.1. М.: Мир, с.

13 Литература 13. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. М.: Мир, с. 14. Рейуорд-Смит В. Дж. Теория формаль- ных языков: Вводный курс. М.: Радио и связь, с. 15. Саломаа А. Жемчужины теории фор- мальных языков. М.: Мир, с.

14 Литература 16. Семантика языков программирования: Сб. статей под ред. А.Н.Маслова и Э.Д.Стоцкого М.: Мир, с. 17. Фитиалов С.Я. Формальные граммати- ки. Л..: Изд-во Ленингр. ун-та, с. 18. Фостер Дж. Автоматический синтакси- ческий анализ. М.: Мир, с.

15 Литература 19. Хантер Р. Проектирование и конструи- рование компиляторов. М.: Финансы и статистика, с. 20. Языки и автоматы: Сб. статей под ред. В.М.Курочкина. М.: Мир, с.