• 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. Термины