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. Термиы 3. Контекстно-свободные грамматики и магазинные автоматы 3.1. Приведенные грамматики 3.2. Преобразование КС-грамматик 3.3. Магазинные автоматы 3.4. Нисходящие распознаватели, LL(K) и разделенные грамматики. Построение распознавателя 3.5. Функции ПЕРВ, СЛЕД и ВЫБОР 3.6. Слаборазделенные LL(1) - грамматики. Преобразование грамматик к виду LL(1) 3.7. Построение магазинного автомата 3.8. Восходящие распознаватели 3.9. LR(k)-грамматики 3.10. SLR(1)-распознаватели и их построение 3.11. Восходящие распознаватели для грамматик с аннулирующими правилами 3.12. Резюме 3.13. Упражнения 3.14. Термины 4. Способы описания перевода и преобразователи 4.1. Описание перевода или трансляции 4.2. Транслирующие грамматики 4.3. Бесскобочные выражения 4.4. Автоматные преобразователи 4.5. Построение А - преобразователей 4.6. Минимизация А – преобразователей 4.7. Магазинные преобразователи 4.8. Построение преобразователей 4.9. Резюме 4.10. Упражнения 4.11. Термины 5. Атрибутные транслирующие грамматики и преобразователи 5.1. Атрибутные транслирующие грамматики 5.1.1. Общие положения 5.1.2. Определение АТ - грамматик 5.1.3. Пример АТ - грамматики 5.1.4. Демонстрация вычисления значений атрибутов с левым выводом 5.1.5. Пример использования АТ - грамматики 5.2. Синтаксический анализ, с использованием АТ - грамматики 5.2.1. Процесс синтаксического анализа 5.2.2. Пример использования АТ - грамматики 5.3. L - атрибутные транслирующие грамматики 5.3.1. L - атрибутные транслирующие грамматики 5.3.2. Форма простого присваивания АТ - грамматик 5.3.3. Преобразование LАТ - грамматики в LАТ - грамматику в форме простого присваивания Расширенный вывод для АТ - грамматики 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.1. Интерфейс лексического анализатора 6.2. Входной язык, лексемы, токены 6.3. Таблица лексем 6.4. Распознавание лексем 6.5. Трансляция лексем 6.6. Удаление вспомогательных символов, комментариев и обработка ошибок 6.7. Объектно-ориентированные модели лексического анализатора 6.8. Программная реализация лексического анализатора 6.9. Резюме 7. Программная реализация атрибутных преобразователей 7.1. Синтаксис и семантика входного языка 7.2. Выходной язык и таблицы преобразователя 7.3. Символы действия и транслирующая грамматика 7.4. Определение атрибутов и построение АТ - грамматики 7.5. Магазин и внутреннее представление функции переходов АТ - преобразователя 7.6 Построение инструкций АТ - преобразователя 7.7. Разработка программы АТ - преобразователя 7.8. Объектно-ориентированные модели АТ - преобразователя 7.9. Реализация АТ - преобразователя 7.10. Резюме 7.11. Приложение 8. Переключательные функции и синтез комбинационных схем 8.1. Элементы общей алгебры 8.1.1. Введение в теорию решеток 8.1.1.1. Частично упорядоченные множества 8.1.1.2. Решетки 8.1.1.3. Дистрибутивные решетки 8.1.2. Булева алгебра 8.1.2.1. Основные теоремы 1 8.1.2.2. Основные теоремы 2 8.1.2.3. Основные теоремы 3 8.1.2.4. Алгебра подмножеств 8.1.2.5. Алгебра контактных схем 8.1.3. Упражнения 8.1.4. Термины 8.2. Переключательные функции и их свойства 8.2.1. Алгебра переключательных функций 8.2.2. Аналитическая запись переключательных функций 8.2.2.1. Разложение переключательных функций по одной переменной 8.2.2.2. Разложение переключательных функций по k- переменным 8.2.3. Совершенные дизъюнктивные и конъюнктивные нормальные формы 8.2.3.1. Элементарные конъюнкции и дизъюнкции 8.2.3.2. Совершенные формы 8.2.4. Графическое и геометрическое представление переключательных функций 8.2.4.1. Диаграммы Вейча 8.2.4.2. Геометрическое изображение переключательных функций 8.2.5. Упражнения 8.2.6. Термины 8.3. Минимальные формы переключательных функций 8.3.1. Общие положения 8.3.2. Коды и геометрическое представление конъюнкций 8.3.3. Табличный метод построения множества минималей Квайна - Мак-Класки 8.3.4. Построение минимальных покрытий для функций, имеющих экстремали 8.3.5. Неизбыточные покрытия и экстремали 8.3.6. Построение минимальных покрытий для функций, не имеющих экстремалей 8.3.7. Визуальный метод минимизации ПФ 8.3.8. Упражнения 8.3.9. Термины 8.4. Функциональная полнота систем переключательных функций 8.4.1. Переключательные функции одной и двух переменных 8.4.2. Замкнутые классы ПФ и теорема о функциональной полноте 8.4.2.1. Монотонные и линейные функции 8.4.2.2. Теорема о функциональной полноте 8.4.3. Реализация функций в различных базисах 8.4.3.1. Построение логических схем из элементов Шеффера 8.4.3.2. Построение логических схем из элементов Пирса 8.4.4. Упражнения 8.4.5. Термины 8.5. Резюме 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. Резюме 9.2.8. Термины