Кафедра математических и информационных технологий Санкт-Петербургского академического университета.
Лекции по теории формальных языков.
Весенний семестр 2010/11 учебного года

Лектор Герасимов Александр Сергеевич

Примерная программа курса

Введение. Языки и операции над ними

1. Введение. Схема компилятора.
2. Языки и операции над ними.

   Распознаватели языков

3. Детерминированные конечные автоматы.
4. Недетерминированные конечные автоматы.
5. Операции над автоматными языками.
6. Регулярные языки.
7. Автоматы с магазинной памятью.

   Контекстно-свободные грамматики

8. Грамматики и порождаемые ими языки. Классы грамматик и языков.
9. Контекстно-свободные грамматики и языки.
10. Лемма о накачке.
11. Операции над контекстно-свободными языками.
12. Контекстно-свободные грамматики и автоматы с магазинной памятью.
13. Неукорачивающие контекстно-свободные грамматики.
14. Приведённые контекстно-свободные грамматики.
15. Устранение циклов, левой рекурсии и левая факторизация контекстно-свободных грамматик.

    Лексический анализ

16. Основные понятия лексического анализа. Работа лексического анализатора.

    Нисходящий синтаксический анализ

17. Разделённые грамматики.
18. LL(1)-грамматики.
19. Алгоритм анализа LL(1)-грамматик.
20. Вычисление множеств выбора правил.
21. Обработка синтаксических ошибок при LL-анализе.
22. LL(k)-грамматики.
23. Метод рекурсивного спуска.

    Синтаксический анализ на основе отношений предшествования

24. Общая схема восходящего анализа.
25. Грамматики простого предшествования.
26. Грамматики слабого предшествования.
27. Отношения операторного предшествования.

    LR-анализ

28. Общая схема LR-анализа.
29. Активные префиксы и LR(k)-пункты.
30. LR(0)- и SLR(1)-анализ.
31. LR(1)- и LALR(1)-анализ.
32. LR-анализ с неоднозначными грамматиками.
33. Обработка синтаксических ошибок при LR-анализе.
34. LR(k)-грамматики.

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

• Замятин А. П., Шур А. М. Языки, грамматики, распознаватели: Учебное пособие. Екатеринбург : Изд-во Урал. ун-та, 2007.

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

• Ахо А., Лам М., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструментарий. М.: ООО "И.Д. Вильямс", 2008.
• Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978.
• Мартыненко Б. К. Языки и трансляции: Учеб. пособие. СПб.: Издательство С.-Петербургского университета, 2004.

Слайды лекций

1. Введение. Языки и операции над ними. Детерминированные конечные автоматы.
2. Недетерминированные конечные автоматы. Операции над автоматными языками. Регулярные языки. Автоматные фрагменты языков программирования.
3. Автоматы с магазинной памятью. Грамматики.
4. Контекстно-свободные грамматики и языки: определения и примеры. Лемма о накачке.
5. Операции над контекстно-свободными языками. Контекстно-свободные языки и автоматы с магазинной памятью. Контекстно-свободные грамматики и языки программирования. Аннулирующие нетерминалы контекстно-свободной грамматики.
6. Преобразования контекстно-свободных грамматик.
7. Преобразования контекстно-свободных грамматик (окончание). Лексический анализ. Разделённые грамматики.
8. Синтаксический анализ для LL(1)-грамматик.
9. Синтаксический анализ для LL(1)-грамматик (окончание). LL(k)-грамматики. Синтаксический анализ методом рекурсивного спуска. Общая схема восходящего синтаксического анализа.
10. Грамматики простого предшествования.
11. Грамматики слабого предшествования. Отношения операторного предшествования.
12. Общая схема LR-анализа. Активные префиксы и LR(k)-пункты.
13. LR(0)-, SLR(1)-, LR(1)- и LALR(1)-анализ.
14. LR-анализ с неоднозначными грамматиками. Обработка синтаксических ошибок при LR-анализе. LR(k)-грамматики. Итоги.

Вопросы к экзамену

1. Цепочки, вхождения, языки.
2. Операции над языками.
3. Детерминированные конечные автоматы (ДКА): основные определения и примеры.
4. Приведённые ДКА. Лемма о стабильности отношения эквивалентности состояний ДКА.
5. Теорема о приведённом ДКА.
6. Алгоритм построения классов эквивалентных состояний ДКА.
7. Недетерминированные конечные автоматы (НКА): основные определения и примеры. Теорема Рабина-Скотта.
8. Алгоритм построения ДКА по НКА.
9. Недетерминированные конечные автоматы с ε-переходами (ε-НКА): основные определения. Теорема о классе языков, распознаваемых ε-НКА.
10. Алгоритм построения ДКА по ε-НКА.
11. Замкнутость класса автоматных языков относительно некоторых операций.
12. Регулярные языки. Теорема Клини.
13. Регулярные выражения. Построение конечного автомата по регулярному выражению. Регулярные фрагменты языков программирования.
14. Пример нерегулярного языка.
15. Автоматы с магазинной памятью (МПА): основные определения и примеры.
16. Сравнение распознающих возможностей ДМПА и НМПА.
17. Грамматики: основные определения и примеры.
18. Иерархия Хомского, соотношения между некоторыми классами языков.
19. КС-грамматики, КС-языки, деревья вывода: определения и примеры. Однозначность КС-грамматики.
20. Лемма о накачке.
21. Примеры применения леммы о накачке.
22. Теорема о языках в однобуквенных алфавитах и периодических множествах.
23. Замкнутость класса КС-языков относительно некоторых операций.
24. Незамкнутость класса КС-языков относительно некоторых операций. Теорема о пересечении КС-языка с регулярным языком.
25. Распознавание КС-языка НМПА.
26. Форма Бэкуса-Наура.
27. Доказательство того, что язык программирования Паскаль не является КС-языком. Контекстные условия в спецификациях языков программирования.
28. Нахождение аннулирующих нетерминалов КС-грамматики.
29. Построение эквивалентной неукорачивающей КС-грамматики.
30. Нахождение производящих нетерминалов КС-грамматики.
31. Нахождение достижимых нетерминалов КС-грамматики.
32. Построение эквивалентной приведённой КС-грамматики.
33. Устранение циклов из КС-грамматики.
34. Устранение левой рекурсии из КС-грамматики.
35. Левая факторизация КС-грамматики.
36. Лексический анализ.
37. Синтаксический анализ для разделённых грамматик.
38. Определение LL(1)-грамматики, вспомогательные определения и примеры.
39. Теорема о равносильных определениях LL(1)-грамматики.
40. Теорема о нелеворекурсивности LL(1)-грамматики.
41. Синтаксический анализ для LL(1)-грамматик.
42. Вычисление множеств выбора правил.
43. Обработка синтаксических ошибок при LL(1)-анализе.
44. LL(k)-грамматики.
45. Синтаксический анализ методом рекурсивного спуска.
46. Общая схема восходящего синтаксического анализа.
47. Отношения простого предшествования.
48. Синтаксический анализ для грамматик простого предшествования.
49. Синтаксический анализ для грамматик слабого предшествования.
50. Синтаксический анализ, основанный на отношениях операторного предшествования.
51. Общая схема и пример LR-анализа.
52. Активные префиксы, LR(k)-пункты, автомат пунктов. Лемма об активном префиксе и базисном пункте. Лемма о достижимости допустимого пункта из базисного пункта.
53. Основная теорема LR-анализа, её следствия. LR(0)-автомат.
54. Алгоритм и пример построения LR(0)-автомата.
55. LR(0)-анализ.
56. SLR(1)-анализ.
57. LR(1)-анализ.
58. LALR(1)-анализ.
59. LR-анализ с неоднозначными грамматиками.
60. Обработка синтаксических ошибок при LR-анализе.
61. LR(k)-грамматики.