- •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. Резюме
3.15. Резюме.
Каждую цепочку, построенную с помощью правого вывода, можно преобразовать в начальный символ грамматики, последовательно заменяя правые части правил, выделенные в цепочки, левыми частями. Такая операция замены, являющаяся обратной по отношению к операции вывода, называется сворачиванием или сверткой. Восходящий распознаватель работает, последовательно выполняя операции переноса и свертки. Вначале он переносит символы входной цепочки в магазин до тех пор, пока в магазине не образуется правая часть какого-либо правила, а затем он выполняет операцию сворачивания.Формальной моделью восходящего распознавателя является расширенный автомат, допускающий, в отличие от простого автомата, при переходе чтение цепочки, находящейся в вершине магазина. Детерминированные восходящие распознаватели могут быть построены для LR(k) грамматик, которые являются подклассом контекстно-свободных грамматик. Процедура построения LR(k)-распознавателя оказывается весьма сложной и трудоемкой, поэтому в настоящем пособии рассматриваются грамматики LR(0) и SLR(1), которые включаются в подкласс LR(1) грамматик. Подкласс грамматик SLR(1) грамматик является достаточно широким. Кроме грамматик LR(0) он включает грамматики LL(1) и грамматики слабого предшествования. Диаграмма включения подклассов LR(1) грамматики приведена на рис.3.1. Принадлежность к подклассу LR(0) или SLR(1) грамматик устанавливается путем проверки возможности построения соответствующего распознавателя. Процедура построения восходящих распознавателей состоит из двух частей: построение таблицы переходов и построение таблицы действий. Первая часть этой процедуры оказывается одинаковой для преобразователей LR(0) и SLR(1). Отличия в процедуре построения проявляются во второй части.
LR(1) | | ------------------SLR(1)---------------- | | | | | | LR(0) со слабым LL(1) предшествованием
Рис. 3.1
4.3. Магазинные Преобразователи.
Магазинные автоматы, рассмотренные в предыдущем разделе, позволяют определить для цепочки, заданной на входе, ее принадлежность к языку, допускаемому автоматом. Настоящий раздел посвящен другому типу моделей устройств, называемому магазинными преобразователями. Подобные устройства позваляют строить по заданной входной цепочки соответствующую ей выходную цепочку. Множество таких пар цепочек называют переводом или трансляцией, допускаемым магазинным преобразователем. Для того чтобы построить преобразователь необходимо заранее знать какой перевод он должен выполнять. Кроме того, преобразователь можно построить не для любого перевода, а только для такого, который может быть описан с помощью простой СУ-схемы. Для построения детерминированного преобразователя необходимо еще, чтобы входная грамматика заданной СУ-схемы пораждала детерминированный язык.