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

Определение формальной грамматики и языка, заданного ей. Примеры. Алфавиты терминалов и нетерминалов (метасимволов). Правила грамматики и выводы. Пример грамматики для ограниченного подмножества естественного языка.
Иерархия Хомского. Грамматики без ограничений. Контекстно зависимые грамматики. Пример контекстно зависимого языка L = {a^n b^n c^n, n ∈ Z}.
Контекстно свободные языки и грамматики. Левые и правые выводы для КС-грамматик и синтаксические деревья. Лемма о разрастании для контекстно свободных языков. Пример контекстно зависимого языка, который не вляется контексно свободным.
Однозначные грамматики. Примеры неоднозначных и однозначных грамматик для одних и тех же языков. Существенно неоднозначные языки, примеры (без доказательства).
Конечное автоматы и автоматные языки. Детерминированные и недетерминированные конечные автоматы. Лемма о разрастании для автоматных языков. Алгоритм построения детерминированного конечного автомата, эквивалентного данному недетерминированному конечному автомату в смысле порождаемого им языка.
Праволинейные и леволинейные грамматики. Совпадение классов автоматных языков, леволинейных языков и праволинейных языков.
Регулярные языки и выражения. Теорема Клини о совпадении классов регулярных и автоматных языков.
Минимальные детерминированные конечные автоматы. Изоморфизм всех минимальных детерминированных конечных автоматов, порождающих данный автоматный (или регулярный) язык. Алгоритм построения минимального детерминированного конечного автомата.
Преобразование контекстно своодных грамматик. Удаление недостижимых и бесполезных символов, избавление от эпсилон-правил. Грамматики в нормальной форме Хомского (квадратичные грамматики).
Операции над контекстно свободными языками, не выводящие за пределы класса КС-языков и выводящие за пределы этого класса. Пример двух контекстно свободных языков, пересечение которых не является КС-языком. Пример КС-языка, дополнение к которому не является КС-языком.
Алгоритмические проблемы теории формальных языков. Положительное решение большинства алгоритмических проблем в классе автоматных (или регулярных) языков.
Алгоритмически разрешимые и неразрешимые проблемы в классе контекстно свободных языков. Разрешимость проблемы принадлежности цепочки языку. Неразрешимость проблемы равенства двух контекстно свободных языков, заданных КС-грамматиками. Неразрешимость проблемы однозначности контекстно свободной грамматики.
Задача разбора как задача, противоположная задаче вывода. Основные классы алгоритмов разбора для контекстно свободных языков. Нисходящий, или рекурсивный, или LR(1)-разбор. Пример парсера для языка арифметических формул, реализованного с помощью рекурсии.
Восходящий разбор, или разбор с помощью конечного автомата со стеком (также называемого автоматом с магазинной памятью). Понятие LR-процесса, взаимно однозначное соответствие между правыми выводами в грамматике и LR-процессами. LR(0)-разбор и алгоритм построения множества LR(0)-состяний разбора. Конфликты типа сдвиг-свертка и свертка-свертка. Примеры LR(0)-языков (т.е. языков, допускающих LR(0)-разбор) и языков, не допускающих его.
LR(1)-состояния разбора. Алгоритм построения множества LR(1)-состояний разбора. Таблицы LR(1)-разбора и алгоритм работы LR(1)-парсера. Семантический стек и его использование для решения задач, связанных с разбором. Пример компилятора арифметических формул, реализованного с помощью LR(1)-парсера.