Тема 1.
Классификация языков и грамматик по Хомскому.
Цепочки символов; определение языка;
определение грамматики; компоненты грамматики; представление грамматики в форме
Бэкуса-Наура; 4 типа грамматик по Хомскому.
Тема 2.
Построение дерева вывода. Сентенциальная форма грамматики; Понятие вывода;
цепочки вывода; 2 способа построения дерева вывода.
Тема 3.
Регулярные языки и грамматики. Теория построения конечных автоматов на базе регулярных
грамматик; Автоматные грамматики.
Тема 4.
Распознаватели КС языков. Общие положения, Теория
построения расширенных МП автоматов на базе КС грамматик; Конфигурация
распознавателя КС языков.
Тема 5.
Преобразование КС грамматик. Приведение грамматики к приведенному виду:
Алгоритмы удаления бесплодных символов, недостижимых символов, λ
правил и цепных правил.
Тема 6.
Нисходящий распознаватель с подбором альтернатив для КС языков с возвратом.
Алгоритм нисходящего распознавателя с описанием начальной и конечной
конфигураций; ограничения на грамматики; пример работы алгоритма.
Тема 7.
Восходящий распознаватель для КС языков с возвратом на основе алгоритма
«сдвиг-свертка». Алгоритм восходящего распознавателя с описанием начальной и
конечной конфигураций; ограничения на грамматики; пример работы алгоритма.
Тема 8.
Нисходящий распознаватель без возвратов. Метод рекурсивного спуска. LL(1) грамматика. Общие сведения о построении
распознавателей без возвратов; ограничения, накладываемые на грамматики которые
использует метод рекурсивного спуска; определение LL(1)
грамматик; построение множеств FIRST и FOLLOW; алгоритм разбора.
Тема 9.
Табличные распознаватели для КС языков. Отличие табличных распознавателей от
нисходящих и восходящих; Преимущества и недостатки табличных распознавателей;
Алгоритма Кока-Янгера-Касами.
Тема 10.
Грамматики предшествования. Описание грамматик простого и операторного
предшествования; Алгоритмы разбора для грамматик простого и операторного
предшествования.
Тема 11.
Основные принципы построения трансляторов. Определение компилятора,
транслятора; Сходства и различия; Общая схема работы; описание синтаксического
разбора;
Тема 12.
Принципы построения лексических анализаторов. Методы организации таблиц лексем
и идентификаторов: простой, метод бинарных деревьев, хэш-функций; Построение
дерева разбора синтаксических конструкций.
Тема 13.
Семантический анализ. Определение, Назначение. Пример работы. Место в общей
схеме работы интерпретатора; Обратная польская запись; Схемы СУ перевода.
Тема 14.
Этапы создания интерпретатора.; пример построения простейшего интерпретатора.
Выделение лексем, выделение идентификаторов, выделение и интерпретирование
конструкций языка
Информацию о самом курсе можно посмотреть здесь: Теория языков программирования
