- •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.9. Резюме.
Одним из классов грамматик, обеспечивающих построение детерминированных магазинных распознавателей, является класс LL(1) грамматик. Этот класс включаетразделенныеислаборазделенныеграмматики. Чтобы определить является ли заданная грамматика LL(1) грамматикой, необходимо найти значения функцийПЕРВ иСЛЕД, а затем проверить условия принадлежности классу LL(1) грамматик. Для построения команд распознавателя нужно найти множестваВЫБОРдля каждого правила грамматики. Распознаватель выполняет команды двух видов: со сдвигом и без сдвига входной головки. При работе распознавателя в магазине происходит построение вывода входной цепочки. Такой вывод соответствуетлевому выводувходной цепоч- ки. Правила применяються при выводе цепочки в такой последовательности, как строится синтаксическое дерево при левом выводе от корня к конечным узлам, поэтому распознаватель называют нисходящим. Если при построении грамматики для заданного языка получилась не LL(1) грамматика, то ее можно попытаться преобразовать, применяя приемы устранения леворекурсив- ных правил, выделения общих частей и построения неукорачивающей грамматики. Однако, эти приемы не всегда приводят к успеху.
3.11. Восходящие распознаватели.
В основе работывосходящего распознавателялежитоперация сворачивания или свертки, которая применяется к цепочке, полученной с помощью правого вывода. Эта операция является противоположной выводу. Она заключается в том, что правая часть правила заменяется левой частью. При работе входящий распознаватель переносит символы входной цепочки в магазин и, когда в магазине оказывается правая часть какого-либо правила, осуществляет операцию свертки. Эту операцию можно определить следующим образом.
Определение. Пусть задана грамматика Г, в схеме которой имеется правило r =Aи задана цепочкаЕсли правая часть цепочки правила r является частью цепочки , то можно получить цепочку, заменяя правую часть правила грамматики левой частью. В этом случае говорят, что цепочка tполучается путем непосредственного сворачивания цепочкии используют обозначение <= Определение. Если существует множество цепочек= (nтаких, что,n-1n , то говорят, что цепочкаn сворачивается в цепочкуи используют обозначение n . |
Задача распознавания принадлежности данной цепочки языку, порождаемому грамматикой Г, может быть сформулирована следующим образом. Если из заданной цепочки с помощью операции сворачивания можно получить начальный символ грамматики, то такая цепочка может быть построена с помощью правил заданной грамматики, и, следовательно, она принадлежит языку, порождаемому этой грамматикой. Например, сворачивание цепочки, полученной с помощью правого вывода и правил следующей грамматики
Г3. 12 : (1) <I> a, (2) <I> (<I><R> , (3) <R> ,<I><R> , (4) <R> ).
можно представить так:
(a,a) 1 (<I>,a) 1 (<I>,<I>) 4
(<I>,<I><R> 3(<I><R> 2 <I>.
Каждый шаг рассмотренной процедуры связан с выделением в цепочке правой части какого-либо правила и заменой его левой частью правила. В последовательности сворачиваний правые части правил называются основойрассматриваемой цепочки. В общем случае основу можно определить так:
-
Определение. Основой цепочки называют вхождение правой части последнего правила, примененного при правом выводе рассматриваемой цепочки.
Работу магазинного автомата, выполняющего распознавание приведенной цепочки, можно представить в виде:
Магазин |
Вход |
Действие |
1. h0 |
(a,a) |
Перенос |
2. h0( |
a,a) |
Перенос |
3. h0(a |
,a) |
Свертка(1) |
4. h0(<I> |
,a) |
Перенос |
5. h0(<I>, |
a) |
Перенос |
6. h0(<I>,a |
) |
Свертка(1) |
7. h0(<I>,<I> |
) |
Перенос |
8. h0(<I>,<I>) |
|
Свертка(4) |
9. h0(<I>,<I><R> |
|
Свертка(3) |
10. h0(<I><R> |
|
Свертка(2) |
11. h0<I> |
|
Допустить |
В этом примере на каждом шаге применяется либо операция переноса, либо сворачивания, параметром которой является номер правила, а работа автомата заканчивается, когда в магазине получается начальный символ грамматики. При этом автомат вырабатывает сигнал, показывающий, что цепочка допускается автоматом.