- •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. Резюме
5.4.5. Пример построения ап
Следуя приведенному порядку, построим АТ-преобразователь для грамматики Г5.4и проанализируем его работу. Вначале приведем эту грамматику к форме простого присваивания. В результате получаем грамматику:
Г5.6:
<E>%a/b i%x<R>%e/c/d !! c=x; d=b;a=e; <R>%e1/c1/d1+{СЛЕДУК}%wi%x{СЛОЖ/f1/g1/h1}<R>%e2/c2/d2 !! f1=c1; g1=x1; (h1,c2)=d1; d2=w;e1=e2; <R> %e3/c3/d3-{СЛЕДУК}%wi%x{ВЫЧИТ/f2/g2/h2}<R>%e4/c4/d4 !! f2=c3; g2=x2; (h2,c4)=d3; d4=w;e3=e4; <R>%e5/c5/d5. !! e5=d5;
1) После удаления атрибутов из грамматики Г5.6получаем грамматикуГ5.3. 2) Команды преобразователя для грамматикиГ5.3имеют вид:
(1) f*(s0,i,h0)=(s0,h0<E>,$),(2) f*(s0,i,<E>)=(s0,<R>i,$),(3) f(s0,+,<R>)=(,s0<R>{СЛОЖ}i,$),(4) f(s0,-,<R>)=(s0,<R>{ВЫЧИТ}i,$),(5) f(s0,.,<R>)=(s0,$,$),(6) f(s0,i,i)=(s0,$,$),(7) f*(,s0+,{СЛОЖ})=(s0,$,{СЛОЖ}),(8) f*(s0,-,{СЛОЖ})=(s0,$,{СЛОЖ}),(9) f*(s0,.,{СЛОЖ})=(s0,$,{СЛОЖ})(10) f*(s0,+,{ВЫЧИТ})=(s0,$,{ВЫЧИТ}),(11) f*(s0,-,{ВЫЧИТ})=(s0,$,{ВЫЧИТ}),(12) f*(s0,.,{ВЫЧИТ})=(s0,$,{ВЫЧИТ}),(13) f*(s0,,h0)=(s1,$,$).
3) Для каждой команды, выполняющей запись цепочки символов в магазин, в нашем случае это команды (1)-(5), построим инструкцию, определяющую значения указателей. Такие инструкции , построенные в соответствии с правилами вычисления значений атрибутов, имеют вид:
#1 {ЗАПИСАТЬ(h0ba<E>) b=<начальное значение>}
#2 {ЗАПИСАТЬ(dce<R>xi) STACK[SP-1]=-3 STACK[SP-5]=-2 STACK[SP-3]=-3 }
#3 {ЗАПИСАТЬ(d2c2e2<R>h1g1f1{СЛОЖ}x1iw1{СЛЕДУК}) STACK[SP-5]=-8 STACK[SP-3]=-3 STACK[SP-7]=-3 STACK[SP-10]=-4 STACK[SP-1]=-10 STACK[SP-9]=-3 }
#4 {ЗАПИСАТЬ(d4c4e4<R>h2g2f2{ВЫЧИТ}x2iw1{СЛЕДУК})STACK[SP-5]=-8STACK[SP-3]=-3STACK[SP-7]=-3STACK[SP-10]=-4STACK[SP-1]=-10STACK[SP-9]=-3 }
#5 {STACK[SP-1]=-2; {УДАЛИТЬ(3)} }
Содержание символов действия, используемых в инструкциях, можно описать следующим образом :
{СЛЕДУК} - определяет следующий свободный адрес таблицы значений и присаваивает его своему атрибуту,{СЛОЖ} - читает из магазина атрибуты, формирует атом, состоящий из знака операции сложения, адресов операндов и результата, и передает атом на выход,{ВЫЧИТ} - читает из магазина атрибуты, формирует атом, состоящий из знака операции вычитания, адресов операндов и результата, и передает атом на выход,{УДАЛИТЬ(3)} - удаляет из вершины магазина три символа.
4) Включая обозначение построенных инструкций в команды преобразователя и учитывая, что обработка символов действия была включена в правила работы АП, команды (7) - (12) можно исключить из списка команд. В результате получаем систему команд в виде:
(1) f*(s0,i,h0)=(s0,#1,$), (2) f(s0,i,<E>)=(s0,#2,$), (3) f(s0,+,<R>)=(s0,#3,$), (4) f(s0,-,<R>)=(s0,#4,$), (5) f(s0,.,<R>)=(s0,#5,$), (6) f(s0, i, i )=(s0,$,$), (7) f*(s0,,h0)=(s1,$,$).
5.4.6. Демонстрация работы ап
Работу построенного АТ-преобразователя рассмотрим на примере трансляции цепочки i%22-i%24 при начальном значении атрибута b=28, которое является указателем на первый свободный элемент ТЗ. Описание работы представим в виде последовательности тактов. 1. В исходном состоянии в стеке находится маркер дна, а на входе - заданная цепочка.
2. После выполнения команды (1) в стек заносится начальный символ грамматики с двумя атрибутами, один из которых имеет начальное значение 28.
3. Затем выполняется команда (2), которая предписывает построение фрагмента стека, определяемого инструкцией #2. В результате получаем:
4. На входе и в вершине магазина находятся терминальные символы, поэтому выполняется команда (6), которая сравнивает терминалы, читает атрибут входного терминала и проверяет значение магазинного терминала. Обнаружив, что значением магазинного терминала является указатель, команда осуществляет запись значения атрибута входного терминала в ячейку стека, определяемую указателем.
5. Знак минуса и нетерминал <R> в вершине магазина определяют выполнение команды (4). Эта команда удаляет нетерминал из вершины стека, производит построение фрагмента стека в соответствии с инструкцией #4 и сдвигает входную головку на следующую позицию.
6. Преобразователь, анализируя символ, находящийся в вершине, и обнаружив, что это операционный символ, выполняет действия, предписываемые этим символом, которые заключаются в вычислении указателя на следующий свободный элемент таблицы значений. Полученное значение указателя присваивается элементу стека с указателем SP-10, поскольку этот указатель записан в качестве значения атрибута операционного символа. В результате имеем:
7. Обнаружив в вершине стека терминал, преобразователь читает очередной символ на входе и сравнивает его с магазинным терминалом, выполняя команду (6). Убедившись, что символы совпадают, преобразователь читает атрибут входного терминала и проверяет значение атрибута магазинного терминала. Затем он заносит значение атрибута входного нетерминала в ячейку с атрибутом SP-3, удаляет атрибут из стека и сдвигает входную головку.
8. В вершине магазина находится операционный символ, который должен быть передан на выход, поэтому преобразователь читает из магазина этот символ и его атрибуты и записывает их на выходную ленту.
9. Символ в вершине магазина и входной терминал определяют возможность выполнения преобразователем команды (5). В результате выполнения инструкции, соответствующей этой команде, определяется значение синтезируемого атрибута. В ячейке стека, выделенной этому атрибуту, находится указатель, представляющий собой начало цепочки. Преобразователь заносит полученное значение атрибута во все ячейки стека, входящие в цепочку, и удаляет нетерминал R и его атрибуты из магазина.
10. После удаления нетерминала R и его атрибутов в стеке остаются атрибуты начального символа грамматики, которые могут быть использованы для построения дальнейшей трансляции конструкций, включающих арифметические выражения, например, оператора присваивания. Если же конструкции более высокого уровня не рассматриваются, то преобразователь просто удаляет все атрибуты из стека, поскольку их значения определены. После удаления атрибутов из стека в вершине магазина оказывается маркер дна. Маркер дна и пустой символ на входе определяют команду преобразователя (13) , которая переводит преобразователь в заключительное состояние s1.