Программа курса
"Формальные языки и грамматики"

1. Алфавит A, или множество терминальных символов. Операция * над алфавитом A. Общее понятие языка L в алфавите A. Синтаксис и семантика. Возможные способы задания языка.
2. Задание языка с помощью формальных грамматик. Определение грамматики общего вида: алфавит метасимволов (нетерминалов), начальный метасимвол, правила грамматики, вывод цепочек языка.
3. Иерархия Хомского: классы формальных грамматик. Примеры языков, принадлежащих разностям классов, показывающие, что включения классов строгие. Алгоритмическая разрешимость проблемы принадлежности цепочки языку в каждом из классов (без доказательств).
4. Контекстно-зависимые языки. Теорема о совпадении классов языков, заданных контекстно-зависимыми и неукорачивающими грамматиками (без доказательства). Примеры контекстно-зависимых языков и грамматик.
5. Контекстно-свободные языки и грамматики. Левые и правые выводы. Синтаксическое дерево вывода цепочки языка. Соответствие между синтаксическими деревьями, левыми и правыми выводами.
6. Необходимое условие контекстной свободности языка: лемма о разрастании (или лемма о накачке, pumping lemma). Примеры не контекстно-свободных языков. Пример контекстно-зависимого языка, не являющегося контекстно-свободным.
7. Однозначные контекстно-свободные грамматики (КС-грамматики). Примеры однозначных и неоднозначных грамматик. Существенно неоднозначные языки.
8. Определение порождающх, достижимых и полезных метасимволов в контекстно-свободной грамматике. Преобразования контекстно-свободных грамматик, не меняющие порождаемый язык: устранение бесполезных символов (путем устранения непорождающих и затем недостижимых символов); устранение эпсилон-правил; устранение цепных правил.
9. Нормальная форма Хомского для контекстно-свободных грамматик. Теорема об эквивалентности произвольной КС грамматики некоторой грамматике в нормальной форме Хомского, примеры ее применения.
10. Леволинейные и праволинейные грамматики. Теорема о совпадении классов языков, заданных леволинейными грамматиками, праволинейными грамматиками и класса автоматных языков (а также и класса регулярных языков ввиду теоремы Клини). Построение леволинейной и праволинейной грамматики по конечному автомату и конечного автомата по леволинейной или праволинейной грамматике. Лемма о разрастании для праволинейных (леволинейных, автоматных, регулярных) языков.
11. Линейные грамматики. Лемма о разрастании для линейных языков (без доказательства). Примеры контекстно-свободных языков, не являющихся линейными, и линейных языков, не являющихся регулярными.
12. Операции на контекстно-свободными языками, не выводящие за пределы этого класса: объединение, произведение, итерация Клини. Операции, выводящие за пределы класса контекстно-свободных языков: пересечение и дополнение. Примеры КС-языков, пересечение которых не является контекстно-свободным языком. Пример КС-языка, дополнение к которому не является КС-языком.
13. Теорема о контекстной свободности пересечения контекстно-свободного и автоматного языков. Алгоритм построения контекстно-свободной грамматики для пересечения, примеры.
14. Задача разбора, т.е. восстановления вывода цепочки языка. Грамматики с маркером конца цепочки. Рекусивный, или нисходящий, разбор, восстанавливающий левые выводы цепочек языка. Класс КС-грамматик, допускающих рекурсивный разбор: LL(1)-грамматики (определение и примеры). Преобразование грамматики к виду LL(1) (избавление от левой рекурсии) в тех случаях, когда это возможно, примеры. Программная реализация LL(1)-парсера, примеры.
15. Восходящий разбор, или разбор с помощью конечного автомата со стеком. Определение LR-процесса и возможных действий (сдвиг и свертки по правилам грамматики). Соответствие между успешными LR-процессами и правыми выводами цепочек языка. Возможные неоднозначности при построении LR-процесса.
16. Разрешение неоднозначности LR-процесса путем построения множества состояний LR-разбора. Определение LR(0)-ситуации разбора. Определение LR(0)-состояния разбора как конечного множества LR(0)-ситуаций. Алгоритм построения множества состояний LR(0)-разбора. Построение таблицы действий (сдвиг и свертка по правилу) для LR(0)-разбора, примеры. Возможные конфликты типа сдвиг-свертка или свертка-свертка. Определение LR(0)-грамматики через отсутствие конфликтов в построенном множестве. Примеры LR(0) и не LR(0)-грамматик. Алгоритм работы LR(0)-парсера.
17. LR(1)-разбор. Определение LR(1)-ситуации разбора и LR(1)-состояния разбора как конечного множества LR(1)-ситуаций. Алгоритм построения множества состояний LR(1)-разбора. Построение таблицы действий (сдвиг и свертка по правилу) для LR(1)-разбора, примеры. Возможные конфликты типа сдвиг-свертка или свертка-свертка. Определение LR(1)-грамматики через отсутствие конфликтов в построенном множестве. Примеры LR(1) и не LR(1)-грамматик. Алгоритм работы LR(1)-парсера. Соответствие стека состояний LR(1) разбора и стека LR-процесса.
18. Использование семантического стека параллельно стеку состояний LR(0) или LR(1) разбора для решения задачи компиляции, т.е. перевода с одного языка на другой. Примеры.
19. Программные средства для построения компиляторов: LEX (или FLEX) и YACC (или BISON). Построение синтаксического анализатора, или парсера, с помощью системы YACC (BISON). Входной язык описания парсера. Использование сканера, реализованного с помощью LEX, как поставщика информации для парсера. Описание грамматики языка средствами YACC. Способы разрешения конфликтов с помощью приписывания приоритета лексемам и правилам. Семантический стек парсера и определение семантических действий во входном языке для YACC. Примеры построения простых компиляторов с помощью YACC.