Компиляторы. Вопросы к экзамену

Вопросы к экзамену
Определение оконченного автомата. Синтез автомата.
Из чего состоит конечный автомат? Способы представления Диаграмма состояний конечного автомата. Матрицы переходов конечного автомата.
Чем отличается автомат Мили от автомата Мура?
Сформулируйте основные действия по преобразованию автомата Мили в автомат Мура. Примеры.
Сформулируйте основные действия по преобразованию автомата Мура в автомат Мили. В чем заключается целесообразность использования двух различных типов конечных автоматов?
Какие автоматы называют эквивалентными?
алгоритм минимизации конечного автомата.
Как определить, являются ли конечные автоматы эквивалентными?
Недетерминированные конечные автоматы как распознаватели.
Регулярные выражения. Правила преобразования.

Детерминированный конечный автомат
Эквивалентность недетерминированных и детерминированных конечных автоматов
Регулярные языки
Лемма накачки регулярных языков
Свойства замкнутости регулярных языков
Грамматики. Классификация Хомского.
Регулярные грамматики.
Регулярные грамматики и недетерминированные конечные автоматы восходящий и нисходящий разбор.
МП- автомат. МП- распознаватели КС- языков.
Однозначные и неоднозначные МП- автоматы.
КС- грамматики. Приведение грамматик.
Нормальная форма Хомского.
Алгоритм Кока-Янгеля-Косами.

Литература

Лабораторные работы
1 Необходимо перевести автомат из/в Милли/Мура в зависимости от того что подается как входной файл.
2 Необходимо минимизировать входной автомат.
3 Преобразовать НКА в ДКА. Только для автоматов Милли.
4 Исключить не продуктивные и не достижимые правила входной КС грамматики. Подробное описание алгоритма находится в Л-7 - Приведение грамматик.
5. Реализовать алгоритм Кока - Янгера - Касами для КС грамматики с демонстрацией его работы через построение таблицы разбора. Подробное описание алгоритма находится в Л-8 - Алгоритм Кока

РГР
РГР в 1-м семестре это часть разработки комплексного проекта «Мой первый компилятор» в рамках курсаТАиФЯ.
Цель в этом семестре разработать основы языка программирования и часть компилятора – лексический анализатор.

основные задачи РГР
Разработать требования к создаваемому языку
Определить алфавит языка, основные лексические единицы
Определить принципы работы лексического анализатора- сканера
Привести грамматику языка с учетом лексических элементов языка
Используя генератор синтаксических распознавателей проверить грамматику языка на приведенность и однозначность
Полученный модуль распознавателя проверить на тестах и описанных в п.1 примерах решаемых задач.
Оформить проделанную работу в соответствие с требованиями к РГР

Разработать требования к создаваемому языку
1. Определить назначение языка
2. Привести примеры решаемых задач
3. Определить приоритетные свойства языка

Определить алфавит языка, основные лексические единицы
Основные лексические единицы (токены)- идентификаторы, числа, знаки операций, разделители, статус пробела и т.д.
Привести примеры лексем.
Привести грамматику и регулярное выражение для токенов

Определить принципы работы лексического анализатора
Сканер должен работать в составе генератора, следовательно, она по интерфейсам согласовываться с модулем разбирающим грамматику.
Изначально определим:
Вход:
Анализируемая программа считывается из файл с расширением txt, содержит текст программы
Выход:
Выходом сканера является необходимая для генератора информация.
дополнительный выход , содержит список лексем и соответствующие токены(класс, тип).
Описать структуру программы, типы используемых данных. Описать достоинства и недостатки вашего подхода.

Используя генератор синтаксических распознавателей проверить грамматику языка на приведенность и однозначность
Разобраться в выходной информации генератора.
Определить и привести в РГР выходные данные, доказывающие правильность грамматики языка и, соответственно, сканера.

Полученный модуль распознавателя проверить на описанных выше примерах решаемых задач.
Написать «чистые» и «грязные» тесты
Проверить работу распознавателя
Результаты представить в РГР