- •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.7 Построение магазинного автомата.
Для грамматик, удовлетворяющих условиям LL(1) грамматик, справедливо следующее утверждение.
-
Утверждение.Для каждой LL(1) грамматики Г можно построить Детерминированный магазинный автомат М , допускающий язык, порождаемый данной грамматикой: L ( Г ) = L ( М ).
Задача построения магазинного автомата для заданной LL(1) грамматики формулируется следующим образом. Задана грамматика Г = {Vт,Va, I, R},и требуется определить об'екты, определяющие автоматМ = { P , S , s0 , F , H , h0 , f }. Учитывая, что автомат должен допускать цепочки языка, порождаемого заданной грамматикой, примемP = Vт.Чтобы упростить описание автомата, допустим, что он имеет одно состояниеs0, которое является и начальным и заключительным, то есть -S = {s0}иF = {s0}. В качестве магазинного алфавита примем следующее объединение:H = {Vт Va {h0}}. Построение функции переходов выполним с использованием множеств ВЫБОР правил заданной грамматики следующим образом: 1 ) Для каждого правила грамматики, начинающегося терминальным символом вида <A> b , построим команду автомата
f ( s0 , b , <A> ) = ( s0 , ' ) ,
где 'является зеркальным отображением цепочки. 2) Для каждого правила грамматики, начинающегося нетерминальным символом вида <A> <B> построим команду автомата
f* ( s0 , x , <A> ) = ( s0 , <B> ' )
где f* - команда автомата без сдвига входной головки, а 'является зеркальным отображением цепочки. Количество команд, которые необходимо построить для заданного правила, определяется числом элементов множества ВЫБОР. Команды магазинного автомата, работающие без сдвига входной головки, выполняют замену нетерминаала, соответствующего левой части правила, цепочкой, соответствующей правой части этого правила. В этом случае сопоставление терминального символа, получаемого при выводе, и очередного символа входной цепочки не производится, поэтому для таких команд сдвиг входной головки не нужен. 3) Для каждого аннулирующего правила грамматики вида <A> $построим команды автомата
f* ( s0 , x , <A> ) = ( s0 , $ )
для каждого элемента xиз множестваВЫБОР(<A> $). Количество таких команд определяется числом элементов множества ВЫБОР. 4) Для каждого терминального символаb, расположенного в середине или на конце правых частей правил грамматики, построим команду
f ( s0 , b , b ) = ( s0 , $ ).
5) Для перехода в заключительное состояние построим команду
f* ( s0 , , h0 ) = ( s0 , $ , $ ).
В качестве начальной конфигурации автомата условимся использовать следующее выражение с заданной входной цепочкой µ :
(s0,µ,h0<I>).
Пользуясь приведенными правилами, построим магазинный автомат для грамматики Г12, схема которой в символических обозначениях может быть записана так
Г3. 5 :R = {<A> x | (<B>),
<B> <A> <C>,<C> +<A> <C> | $}.
Вначале построим множества ВЫБОР для каждого из правил и проверим, является ли эта грамматика LL(1) грамматикой.
(1) ВЫБОР(<A> x) = ПЕРВ(x) = {x}
(2) ВЫБОР(<A> ((<B>))) = ПЕРВ((<B>)) = {(}
(3) ВЫБОР(<B> <C>) = ПЕРВ(<A><C>) = {x,(}
(4) ВЫБОР(<C> +<A><C>) = ПЕРВ(+<A><C>) = {+}
(5) ВЫБОР(<C> $) = СЛЕД(<C>) = СЛЕД(<B>) = { ) }.
Множества выбора для правил с символом <A> в левой части и для правил с символом <C> в левой части не имеют общих элементов, следовательно рассматриваемая грамматика относится к классу LL(1) грамматик. Используя функции ВЫБОР, построим соответствующие им команды искомого автомата.
( 1 ) f ( s0 , x , <A>) = ( s0, $ ) ,
( 2 ) f( s0 , ( , <A> ) = ( s0 , )<B> ) ,
( 3 ) f* ( s0 , ( , <B> ) = ( s0 , <C><A> ) , f* ( s0 , x , <B> ) = ( s0 , <C><A> ) ,
( 4 ) f ( s0 , + , <C> ) = ( s0 , <C><A> ) ,
( 5 ) f* ( s0 , ) , <C> ) = ( s0 , $ ).
Учитывая, что закрывающиеся скобки расположены на последнем месте правила (2), построим команду
f ( s0, ), ) ) = ( s0, $ ) .
Кроме того, построим команду для перехода в заключительное состояние:
f ( s0 , $ , h0) = ( s1, $ ) .
Работу построенного автомата проверим на примере входной цепочки ( x + x ). При этом получаем следующую последовательность конфигураций:
( s0, (x+x) , h0<A> ) |--- ( s0, x+x ) , h0)<B> ) |--- ( s0, x+x) , h0)<C><A> ) |--- ( s0, +x ) , h0)<C>) |--- ( s0 , x) , h0)<C><A> ) |--- ( s0, ) , h0)<C>)|--- ( s0, $ , h0 ) |--- ( s0, $ , $ ) ,
которая показывает, что входная цепочка допускается построенным автоматом.