Формальные языки, грамматики и автоматы / index
.htmCourse1 В.С. Фомичев " Формальные языки, грамматики и автоматы"
Содержание курса 1. Формальные языки и грамматики.
2. Контекстно-свободные грамматики и магазинные автоматы.
3. Нисходящие и восходящие распознаватели.
4. Способы описания перевода и преобразователи.
5. Атрибутные грамматики и преобразователи.
6. Автоматные грамматики и конечные автоматы.(в работе)
7. Абстрактный синтез автоматов.(в работе)
8. Переключательные функции и синтез комбинационных схем.(в работе)
9. Структурный синтез автоматов.
1. Формальные языки и грамматики 1.1. Введение
1.1.1. Трансляторы , интерпретаторы и компиляторы
1.1.2. Стадии работы компилятора
1.1.3. Построение компилятора
1.1.4. Термины
1.2. Определение формальной грамматики и языка
1.2.1. Первичные понятия
1.2.2. Примеры, иллюстрирующие первичные понятия
1.2.3. Пустой язык
1.2.4. Резюме
1.2.5. Термины
1.3. Типы формальных языков и грамматик
1.3.1. Грамматики типа 0
1.3.2. Грамматики типа 1
1.3.3. Грамматики типа 2
1.3.4. Грамматики типа 3
1.3.5. Вывод в КС-грамматиках и правила построения дерева вывода
1.3.6. Синтаксический разбор
1.3.7. Левый и правый выводы
1.3.8. Неоднозначные и эквивалентные грамматики
1.3.9. Резюме
1.3.10. Упражнения
1.3.11. Термины
1.4. Способы задания схем грамматик
1.4.1. Форма Наура-Бэкуса
1.4.2. Итерационная форма
1.4.3. Синтаксическая диаграмма
1.4.4. Резюме
1.4.5. Упражнение
1.4.6. Термины
1.5. Построение грамматик и грамматики, описывающие основные конструкции языков программирования
1.5.1. Рекомендации по построению грамматик
1.5.2. Описание списков
1.5.3. Пример построения грамматик
1.5.4. Грамматики, описывающие целые числа без знака и идентификаторы
1.5.5. Грамматики для арифметических выражений
1.5.6. Грамматика для описаний
1.5.7. Грамматика, задающая последовательность операторов присваивания
1.5.8. Грамматики, описывающие условные операторы и операторы цикла
1.5.9. Резюме
1.5.10. Упражнения
2. Контекстно-свободные грамматики и магазинные автоматы. 2.1 Приведенные грамматики.
2.2 Определение непроизводящих символов.
2.3 Определения недостижимых символов.
2.4 Определения бесполезных символов.
2.5 Исключение леворекурсивных правил.
2.6 Исключение цепных правил.
2.7 Преобразование неукорачивающих грамматик.
2.8 Магазинные автоматы.
2.9 Работа магазинного автомата.
2.10.Язык, допускаемый магазинным автоматом.
2.11 Построение магазинного автомата.
2.12 Пример построения автомата.
2.13 Резюме.
2.14 Упражнения.
2.15 Термины.
3. Нисходящие и вщсходящие распознаватели. 3.1 Нисходящие распознаватели и LL(K) - грамматики
3.2 Разделенные грамматики
3.3 Построение детерминированного нисходящего распознавателя.
3.4 Множества выбора.
3.4.1 Функции ПЕРВ, СЛЕД и ВЫБОР.
3.4.2 Построение функции ПЕРВ(µ) .
3.4.3 Построение функции СЛЕД(<B>).
3.4.4 Построение функции ВЫБОР.
3.5. Слаборазделенные грамматики
3.6. LL(1) - грамматики.
3.7. Построение магазинного автомата.
3.8. Преобразование грамматик к виду LL(1).
3.8.1. Исключение леворекурсивных правил.
3.8.2. Выделение общих частей.
3.9. Резюме.
3.10.Упражнения.
3.11.Восходящие распознаватели.
3.11.1. Расширенный магазинный автомат.
3.11.2. Пример работы расширенного автомата.
3.12. LR(k)-грамматики .
3.12.1. Построение и работа распознавателя.
3.12.2. Пример построения LR(0)-распознавателя .
3.13. SLR(1)-распознаватели и их построение .
3.14. Восходящие распознаватели для грамматик с аннулирующими правилами.
3.15. Резюме.
3.16. Упражнения.
3.17. Термины .
4. Способы описания перевода. Бесскобочные выражения. Преобразователи. 4.1. Описание перевода или трансляции .
4.1.1. Синтаксически - управляемые схемы
4.1.2. Перевод, определяемый СУ-схемой.
4.1.3. Простая СУ - схема.
4.1.4. Построение простой СУ - схемы.
4.1.5. Транслирующие грамматики
4.1.6. Входная и выходная грамматики заданной транслирующей грамматики.
4.1.7. Построение транслирующей грамматики по СУ - схеме
4.2. Бесскобочные выражения
4.2.1. Префиксная польская запись.
4.2.2. Вычисление префиксных польских записей.
4.2.3. Постфиксная польская запись.
4.2.4. Вычисление постфиксных польских записей.
4.2.5. Примеры постфиксных польских записей.
4.2.6. Примеры СУ - схем.
4.3. Магазинные Преобразователи.
4.3.1. Определение магазинного преобразователя.
4.3.2. Описание работы магазинного преобразователя.
4.3.3. Перевод, определяемый преобразователем.
4.3.4. Построение преобразователя.
4.3.5. Пример построения детерминированного преобразователя.
4.3.6. Порядок построения детерминированного магазинного преобразователя.
4.4. Резюме.
4.5. Упражнения.
4.6. Термины.
5.Атрибутные транслирующие грамматики и преобразователи 5.1. Атрибутные транслирующие грамматики.
5.1.1. Атрибутные транслирующие грамматики.
5.1.2. Определение АТ-грамматик
5.1.3. Пример АТ-грамматики
5.1.4. Демонстрация вычисления значений атрибутов с левым выводом
5.1.5. Пример использования АТ-грамматики
5.2. Cинтаксический анализ, с использованием АТ-грамматики
5.2.1. Процесс синтаксического анализа
5.2.2. Пример использования АТ-грамматики.
5.3. L - атрибутные транслирующие грамматики
5.3.1. L - атрибутные транслирующие грамматики
5.3.2. Форма простого присваивания АТ-грамматик
5.3.3. Преобразование LАТ-грамматики в LАТ-грамматику в форме простого присваивания.
5.3.4. Расширенный вывод для АТ-грамматики
5.4. Атрибутные преобразователи ( АП )
5.4.1. Представление правил LAT-грамматики в магазине
5.4.2. Построение инструкций АП
5.4.3. Описание работы АП
5.4.4. Порядок построения АП
5.4.5. Пример построения АП
5.4.6 Демонстрация работы АП
5.4.7. Построение восходящих атрибутных преобразователей
5.5. Резюме.
5.6. Упражнения.
5.7.Термины.
6. Автоматные грамматики и конечные автоматы.
( в работе ) 6.2. Ндетерминированные конечные автоматы.
6.3. Конечные преобразователи и переводы.
6.4.Преобразование некоторвх типов языков и грамматик к автоматному виду.
6.5. Построение лексического анализатора.
6.6. Резюме.
6.7. Упражнения.
6.8. Термины
7. Абстрактный синтез автоматов.
( в работе ) 7.1. Преобразование входов.
7.2. Построение распознавателя для заданного конечног языка.
7.3. Построение конечных преобразователей.
7.4. Эквивалентные автоматы и состояния.
7.5. Частичные автоматы и совместимые состояния.
7.6. Построение управляющих автоматов.
7.7. Резюме.
7.8. Упражнения.
7.9. Термины.
8. Переключательные функции и синтез комбинационных схем.
( в работе ) 8.1. Переключательные функции и их свойства
8.1.1. Алгебра переключательных функций
8.1.2. Аналитическая запись переключательных функций
8.1.3. Совершенные дизъюнктивные и конъюктивные нормальные формы
8.1.4. Графическое и геометрическое представление переключательных функций
8.2. Минимальные формы переключательных функций
8.2.1.Геометрическое представление конъюнкций
8.2.2. Различные дизъюнктивные формы переключательных функций
8.2.3. Табличный метод построения множества минималей Квайна - Мак-Класки
8.2.4. Неизбыточные покрытия и экстремали
8.2.5. Построение минимальных покрытий для функций, без экстремалей
8.2.6. Визуальные методы минимизации переключательных функций
8.3. Функциональная полнота систем переключательных функций
8.3.1. Теорема о функциональной полноте
8.3.2. Реализация функций в различных базисах
8.4. Резюме
8.5. Упражнения
8.6. Термины
9. Структурный синтез автоматов 9.1. Синхронные автоматы
9.1.1 Задача структурного синтеза.
9.1.1.1 Обобщенная структурная схема автомата. .
9.1.1.2 Структурная схема с преобразователями входных и выходных сигналов.
9.1.1.3 Структурная схема на элементах импульсного типа.
9.1.2 Основные этапы структурного синтеза.
9.1.3 Типы элементов памяти.
9.1.4 Построение функций возбуждения.
9.1.5 Примеры структурного синтеза.
9.1.5.1 Пример 1.
9.1.5.2 Пример 2.
9.1.6 Кодрование состояний с использованием соседей первого и второго рода.
9.1.7 Кодирование с числом элементов памяти, равным числу состояний .
9.1.8 Структурные схемы с дешифратором.
9.1.9 Структурная схема с удвоенным числом элементов памяти.
9.1.10 Структурные схемы, использующие типовые блоки цифровых устройств.
9.1.10.1 Структурная схема с запоминанием входного слова.
9.1.10.2 Структурная схема на основе счетчика.
9.1.10.3 Структурная схема на основе регистра со сдвигом.
9.1.11 Термины.
9.2. Асинхронные автоматы
9.2.1. Описание работы асинхронного автомата
9.2.2. Состязание элементов памяти
9.2.3. Кодирование состояний
9.2.3.1 Универсальный способ кодирования
9.2.3.2 Эвристический способ кодирования
9.2.4. Связь асинхронного автомата с внешней средой
9.2.5. Построение элементов памяти
9.2.5.1. Асинхронный триггер
9.2.5.2. Асинхронный S-триггер
9.2.5.3. Триггеры с синхронизацией
9.2.6. Триггеры с задержкой
9.2.6.1.T-триггер с задержкой
9.2.6.2. Асинхронный триггер J-K с задержкой
9.2.6.3. Триггер J-K с задержкой и синхронизацией
9.2.6.4. Триггер D-V с задержкой и синхронизацией
9.2.7. Термины