- •1. Формальные языки и грамматики
- •1.1. Введение
- •1.1.1. Трансляторы , интерпретаторы и компиляторы
- •1.1.2. Стадии работы компилятора
- •1.1.3. Построение компилятора
- •1.2.2. Примеры, иллюстрирующие первичные понятия
- •1.2.3. Пустой язык
- •1.2.4. Резюме
- •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.4. Способы задания схем грамматик
- •1.4.1. Форма Наура-Бэкуса
- •1.4.2. Итерационная форма
- •1.4.3. Синтаксические диаграммы
- •1.4.4. Резюме
- •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. Резюме
- •2. Контекстно-свободные грамматики и автоматы.
- •2.1 Приведенные грамматики.
- •2.2 Определение непроизводящих символов.
- •2.3 Определения недостижимых символов.
- •2.5 Исключение леворекурсивных правил.
- •2.6 Исключение цепных правил.
- •2.7 Преобразование неукорачивающих грамматик.
- •2.8 Магазинные автоматы.
- •2.9 Работа магазинного автомата.
- •2.10. Язык, допускаемый магазинным автоматом.
- •2.11 Построение магазинного автомата.
- •2.12 Пример построения автомата.
- •2.13 Резюме.
- •3. Нисходящие распознаватели.
- •3.1 Распознаватели и ll(k) - грамматики
- •3.3 Построение детерминированного нисходящего распознавателя.
- •3.4 Множество выбора.
- •3.4.1 Функции перв, след и множество выбор.
- •3.4.4 Построение множества выбор.
- •3.5 Слаборазделенные грамматики
- •3.6 Ll(1) - грамматики.
- •3.7 Построение магазинного автомата.
- •3.8 Преобразование грамматик к виду ll(1).
- •3.8.1 Исключение леворекурсивных правил.
- •3.8.2 Выделение общих частей.
- •3.9. Резюме.
- •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. Резюме.
- •4.3. Магазинные Преобразователи.
- •4.3.1. Определение магазинного преобразователя.
- •4.3.2. Описание работы магазинного преобразователя.
- •4.3.3. Перевод определяемый преобразователем.
- •4.3.4. Построение преобразователя.
- •4.3.5. Пример построения преобразователя.
- •4.3.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.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. Построение восходящих атрибутных преобразователей
- •9.1 Структурный синтез синхронных автоматов .
- •9.1.1.1 Обобщенная структурная схема автомата.
- •9.1.1.3 Структурная схема на элементах импульсного типа.
- •9.1.2 Основные этапы структурного синтеза.
- •9.1.3 Типы элементов памяти.
- •9.1.4 Построение функций возбуждения.
- •9.1.5 Примеры структурного синтеза.
- •9.1.5.1 Пример 1
- •9.1.6 Кодрование состояний с использованием соседей первого и второго рода.
- •9.1.7 Кодирование с числом элементов памяти, равным числу состояний .
- •9.1.8 Структурные схемы с дешифратором.
- •9.1.10 Структурные схемы, использующие типовые блоки цифровых устройств.
- •9.1.10.1 Структурная схема с запоминанием входного слова.
- •9.1.10.2 Структурная схема на основе счетчика.
- •9.1.10.3 Структурная схема на основе регистра со сдвигом.
- •9. Асинхронные автоматы
- •9.2 Общие положения.
- •9.2.1. Описание работы асинхронного автомата
- •9.2.2. Состязание элементов памяти
- •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.2 Асинхронный триггер j-k с задержкой
- •9.2.6.3. Триггер j-k с задержкой и синхронизацией
- •9.2.6.4. Триггер d-V с задержкой и синхронизацией
- •9.2.7. Резюме
9.2.5. Построение элементов памяти
Настоящий параграф посвящен построению элементов памяти - триггеров на элементах потенциального типа. Такие триггеры выпускаются промышленностью в виде интегральных микросхем и широко применяются для постоения узлов и блоков ЦВМ. На практике используется большое число триггеров различного вида. В основном они отличаются логикой работы, наличием синхронизации и задержки при установлении входных сигналов. Логика работы триггера определяется его реакцией на входные сигналы. При этом различают следующие типы триггеров. D-триггер, который называют также триггером-задержкой. Он имеет один вход и сохраняет значение входного сигнала до момента подачи следующего сигнала на его вход. Т-триггер, который называют триггером со счетным входом. Он имеет один вход и изменяет свое состояние на противоположное при каждом воздействии входного сигнала. R-S-триггеримеет два входа. Вход S служит для установки триггера в состояние 1, а вход R - для установки в состояние 0. При этом одновременная подача сигналов на оба входа триггера запрещена (RS = 0). R-триггеримеет два входа R и S. Отличается от триггера R-S тем, что пи одновременной подаче сигналов на оба входа R = S = 1 он переходит в сост ояние 0. S-триггеримеет два входа R и S. Отличается от триггера R-S тем, что при одновременном действии сигналов на обоих входах R = S = 1 он переходит в состояние 1. Е-триггер также имеет два входа R и S. Отличается от триггера R-S тем, что под действием входных сигналов R = S = 1 он не изменяет своего состояния. J-K-триггеримеет два входа. Вход J служит для установки триггера в состояние 1, а вход К - для установки в состояние 0. Отличается от Е-триггера тем, что при одновременном действии сигналов на его входах J = K = 1, он изменяет состояние на противоположное. R-S-T-триггеробладает тремя входами. Его называют также счетным триггером с разделительной установкой. Он сочетает в себе свойства R-S-триггера и Т-триггера. При работе триггера должны выполняться следующие условия: RS = RT = ST = 0. D-V-триггерпредставляет собой D-триггер с дополнительным управляющим входом V. Если сигнал V = 1, то такой триггер работает как триггер типа D. Если же V = 0, то триггер не изменяет своего состояния под действием сигнала на основном входе. T-V-триггер представляет собой Т-триггер с дополнительным управляющим входом V. Если сигнал V = 1, то такой триггер работает как триггер типа Т. Если же V = 0, то состояние триггера не изменяется.
9.2.5.1. Асинхронный триггер
На входе обычного триггера, построенного из элементов потенциального типа, подаются потенциальные сигналы, поэтому его назвают асинхронным триггером. Такие триггеры строят как обыкновенные асинхронные автоматы, используя в качестве элемента памяти асинхронный триггер типа R-S. В отличие от всех остальных триггеров построение R-S-триггера производится по характеристическому уравнению. Это уравнение имеет вид: qt+1= (qRVS)t. Построим по приведенному уравнению триггер вначале на элементах ИЛИ-НЕ, а затем на элементах И-НЕ. Для этого опустим верхние индексы и преобразуем хто уравнение так, чтобы оно не содержало операции конъюнкции:
Полученное выражение определяет схему с обратной связью, которая приведена на рис. 9,а. Пользуясь равенством
получаем схему триггера типа R-S на элементах И-НЕ, изображенную на рис. 9,б. Кружки на входах условного обозначения триггера показывают, что изменение состояния триггера должно происходить при действии сигнала, соответствующего
нулю. Для того чтобы лучше представить работу триггера, проанализируем схему на рис. 9,а. Обозначим выход первой логической схемы буквой w и вычислим выходные сигналы логических элементов для различных значений входных сигналов.
Действуя описанным способом, нетрудно построить и проверить работу R-S-триггеров с дополнительными входами установки в нуль и единицу. Например, работа триггера с дополнительным входом R1 описывается характеристическим уравнением:
Схема триггера, построенная по этому уравнению на элементах И-НЕ, приведена рис. 10.