- •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.2. Построение инструкций ап.
Итак, для построения левого вывода LАТ - грамматики в магазине при каждом применении правила необходимо построить фрагмент магазина, соответствующий правой части правила, и установить связи атрибутов правой части правила с атрибутами заменяемой левой части правила, которые в момент замены находятся непосредственно под вершиной магазина. В результате установки связи в элементы магазина, определяющие значения наследуемых атрибутов, должны быть записаны указатели на элементы магазина, в которые нужно поместить значения этих атрибутов, а в элементы, соответствующие синтезируемым атрибутам, должны быть занесены указатели на элементы магазина, в которых будут расположены значения этих атрибутов. При этом в магазине могут образовываться цепочки указателей, ссылающихся друг на друга, которые соответствуют отложенным присваиваниям и последовательностям стрелок в графическом представлении вывода. Вывод в атрибутных грамматиках совмещается с вычислением значений атрибутов. Если грамматика задана в форме простого присваивания, то вычисление значений атрибутов осуществляется при выполнении символов действия. Полученные в результате вычисления значения атрибутов должны заноситься в отведенные этим атрибутам элементы магазина, а также во все элементы, связанные с ними цепочкой указателей. Основываясь на описанной выше схеме выполнения левого вывода в атрибутной грамматике с использованием магазина, можно сделать вывод о том, что усложнение атрибутного преобразователя по сравнению с преобразователем, построенным по транслирующей грамматике, возникает за счет необходимости выделения памяти для атрибутов в магазине и работы с указателями. Действия, связанные с построением фрагмента магазина, АТ- преобразователь может выполнять при записи правой части правила в магазин. Предписания для установки указателей и определения значений атрибутов, необходимые для построения фрагмента, могут быть определены и описаны заранее на этапе построения АТ - преобразователя. Такие предписания зависят от вида атрибута и могут быть определены исходя из того, что при выводе с использованием магазина корень синтаксического дерева вывода находится на дне магазина, а конечные вершины дерева получаются на вершине. Кроме того, необходимо учесть, что значения синтезируемых атрибутов должны передаваться по направлению от конечных вершин дерева к корню, а значения наследуемых атрибутов наоборот - от корня к конечным вершинам. Отмеченные обстоятельства позволяют сформулировать правила вычисления значений атрибутов следующим образом.
1) Если источником копирующего правила является синтезируемый атрибут или атрибут терминального символа, то в поле, соответствующее источнику, записывается указатель на поле приемника, в которое нужно поместить значение источника после его определения.
2) Если источником копирующего правила является наследуемый атрибут, то в поле, соответствующее приемнику, записывается указатель на поле источника, из которого нужно взять значение.
3) Если источником копирующего правила является константа, то ее значение заносится в поле, соответствующее приемнику.
4) Если приемниками копирующего правила являются несколько атрибутов (множественное присваивание), то они связываются цепочкой указателей.
При построении фрагментов для правил грамматики следует помнить, что атрибуты левой части заменяемого правила должны находиться в магазине всегда непосредственно под первым атрибутом правой части правила, заносимого в магазин. Построим фрагмент магазина для правила
<A>/x1 {СЛЕДУК}%y1 a %z{f}/x2/x3/x4%y2 <B> /x5 %q !! ( x2,x5 ) = x1; x3 = y1; x4 = z; q = y2;
который можно изобразить в виде следующей диаграммы:
Процедуру построения этого фрагмента можно представить в виде инструкции АТ-преобразователя. Полагая, что смысл действий достаточно точно передается словами, используемыми для их обозначения, запишем инструкцию в виде:
{1. Записать в магазин цепочку %q/x5<B>%y2/x4/x3/x2{f}%z a%y1{СЛЕДУК}2.В поле атрибута %y2 записать указатель на %q;3.В поле атрибута %z записать указатель на /x4;4.В поле атрибута %y1 записать указатель на /x3;5.В поле атрибута /x2 записать указатель на /x5;6.В поле атрибута /x5 записать указатель на /x1;}
Использование идентификаторов переменных в полученном описании противоречит принципам работы с адресуемой памятью. Чтобы избавиться от этого противоречия, воспользуемся программной реализацией магазина, расположенного в основной памяти. Обычно в этом случае расширяют возможности работы с магазином, разрешая обращения к элементам магазина, расположенным под его вершиной, и магазин называют стеком, а указатель на его вершину обозначают SP. Полагая, что указатели смежных элементов стека отличаются на единицу, в рассматриваемом случае элементы, находящиеся под вершиной, должны иметь указатели SP-1,SP-2,..., а элементы, расположенные над вершиной стека, - указатели SP+1,SP+2,... . Если в вершине стека расположен нетерминал, то указатель на него хранится в SP, а атрибуты этого нетерминала находятся в ячейках стека с указателями SP-1,SP-2,... . Заменяя нетерминал правой частью правила, состоящей из N символов, получим новое значение указателя стека SP'=SP+N-1. При этом указатели на атрибуты замененного нетерминала относительно нового значения указателя будут иметь следующие значения: SP'-N, SP'-N-1, SP'-N-2,... . В качестве иллюстрации использования адресации относительно указателя стека, найдем значение указателей для рассмотренного выше примера фрагмента стека, полагая, что стек представляет собой массив с именем STACK, а указатель SP является индексом этого массива.
Из приведенной схемы видно, что после записи 12 символов,образующих правую часть правила, указатель на первый атрибут удаленного нетерминального символа оказывается равным SP-12. Используя соглашение о представлении стека в памяти, инструкцию для построения фрагмента магазина запишем в следующем виде:
{1.Записать в стек цепочку %q/x5<B>%y2/x4/x3/x2{f}%z a%y1{СЛЕДУК}2. STACK[SP-8] =SP-11; 3. STACK[SP-3] =SP-7; 4. STACK[SP-1] =SP-6; 5. STACK[SP-5] =SP-10; 6. STACK[SP-10] =SP-12;}
Приведенное описание инструкции преобразователя можно считать aлгоритмическим, поскольку описание действий в форме фразы естественного языка, использованное для краткости, может быть заменено последовательностью операций записи в магазин, сопровождающихся изменением указателя стека. Однако использо- вание адресации относительно вершины стека обеспечивает корректное значение указателей, если только вершина стека не изменяется. Чтобы получить возможность работы с указателями независимо от положения вершины в стеке, возьмем в качестве значения указателя приращение адреса стека относительно элемента, в который заносится указатель. Используя такой способ адресации, перепишем рассматриваемую инструкцию так:
{1. Записать в стек цепочку %q/x5<B>%y2/x4/x3/x2{f}%z a%y1{СЛЕДУК}2. STACK[SP-1] =-5; 3. STACK[SP-3] =-4; 4. STACK[SP-5] =-5; 5. STACK[SP-8] =-3; 6.STACK[SP-10] =-2; }