- •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.4. Связь асинхронного автомата с внешней средой
Использование сигналов потенциального типа, длительность которых не ограничена и время изменения не фиксировано, осложняет работу с кодами, поступающими последовательно на вход асинхронного автомата. Основная трудность заключается в том, что с помощью одного потенциального сигнала с неопределенной длительностью нельзя закодировать последовательность из одинаковых цифр. Например, пусть требуется передать на вход автомата последовательный код, состоящий и четырех единиц. Если используется двоичный потенциальный сигнал, то каждой единице будет соответствовать одно и то же значение напряжения на входе, и автомат воспримет такую последовательность как один сигнал равный единице. В общем случае такая неоднозначность при передаче последовательных двоичных кодов будет возникать для любой группы стоящих рядом одинаковых цифр.
Для того чтобы сделать возможной передачу последовательных кодов при потенциальном характере сигналов, расширяют входной алфавит автомата. Такое расширение соответствует введению одной дополнительной линии передачи x’ (рис. 7), которая используется для сихронизации или для пересылки указателя при передаче последовательности одинаковых цифр. В зависимости от того, как используется линия x’, возможны несколько способов организации передачи. Рассмотрим три основных способа, которые приведены на рис. 8. Первый способ предполагает использование линии x’ для передачи импульса определенной длительности t, который формируется для каждой позиции кода, где расположена цифра, совпадающая с предыдущей (рис. 8,а ). Этот способ соответствует преобразованию входных слов автомата, при котором между каждыми двумя одинаковыми цифрами вводится дополнительный символ-разделитель. На рис. 8,а используется даже два разделителя: один применяется в последовательности единиц, а другой - в последовательности нулей. Если обозначить r1 - разделитель единиц, а r0 - разделитель нулей, то входная последовательность 0110010 может быть записана следующим образом 01r110r0010. В рассматриваемом случае входной алфавит должен состоять из четырех букв P = {00, 01, 10, 11}, где буквы 00 и 10 соответствуют нулю, а буквы 01 и 11 - разделителю нулей и разделителю единиц. При этом входная последовательность имеет вид: 00 10 11 10 00 01 00 10 00. Следует отметить, что использование разделителей приводит к необходимости выравнивания длины входных слов, а также к увеличению времени передачи каждого слова.
При втором способе по линии x’ передается синхронизирующая последовательность импульсов с длительностью t и периодом 2t (рис. 8,б ). Такой способ предплагает использование для каждого символа, подаваемого на основной вход автомата, двух различных кодов. Например, в случае двоичных кодов, единице ставятся в соответствие коды 10 и 11, а нулю - коды 00 и 01. При этом кодирование соседних букв в каждом входном слове должно выполняться таким образом, чтобы коды таких букв имели различные значения в позиции, соответствующей синхронизирующему сигналу. Например, последовательность 0110010, для рассматриваемого случая можно представить так: 00 11 10 01 00 11 00.
Существенно, что описанный способ построения последовательного кода не приводит к изменению длины входной последовательности и увеличению времени ее передачи. Третий способ, изображенный на рис. 8,в отличается от предыдущего только тем, что в дополнительной линии x’ вместо импульсного сигнала используется сигнал потенциального типа. При этом кодирование выполняется таким же образом, как и в предыдущем случае. В заключении следует отметить, что при работе с сигналами потенциального типа на стадии абстрактного синтеза автомата приходится вводить доплнительный этап, связанный с перекодированием слов заданного оператора в соответствии с выбранным способом построения последовательного кода. Если автомат должен вырабатывать также последовательный код, то необходимо предусмотреть и соответствующее кодирование выходных слов заданного оператора.