В.А.Серебряков Лекции по конструированию компиляторов Москва 1993 Предисловие Предлагаемая вниманию читателя книга основана на курсе лекций, прочитанных автором на факультете вычислительной математики и кибернетики Московского государственного университета в 1991- 1993 гг. Автор надеется, что издание книги восполнит существенный пробел в литературе на руссом языке по разработке компиляторов. Содержание книги представляет собой "классические" разделы предмета: лексический и синтаксический анализ, организация памяти, генерация кода. Сделана попытка на протяжении всего изложения провести единую "атрибутную" точку зрения на процесс разработки компилятора. В книге не затрагиваются чрезвычайно важные вопросы глобальной оптимизации и разработки компиляторов для машин с параллельной архитектурой. Автор надеется восполнить эти пробелы в будущем. Книга будет полезной как студентам и аспирантам программистских специальностей, так и профессионалам в этих областях. Оглавление Глава 1. Введение 6 1.1. Место компилятора в программном обеспечении 6 1.2. Структура компилятора 7 Глава 2. Лексический анализ 11 2.1. Регулярные множества и регулярные выражения 13 2.2. Конечные автоматы 14 2.3. Построение детерминированного конечного автомата по регулярному выражению 17 2.4. Построение детерминированного конечного автомата с минимальным числом состояний 20 2.5. Программирование лексических анализаторов 22 2.6. Конструктор лексических анализаторов LEX 27 Глава 3. Синтаксический анализ 31 3.1. Основные понятия и определения 31 3.2. Таблично-управляемый предсказывающий разбор 33 3.2.1. Алгоритм разбора сверху-вниз 33 3.2.2. Множества FIRST и FOLLOW 37 3.2.3. Конструирование таблиц предсказывающего анализатора 39 3.2.4. LL(1)-грамматики 40 3.2.5. Удаление левой рекурсии 41 3.2.6. Левая факторизация 43 3.2.7. Рекурсивный спуск 44 3.2.8. Диаграммы переходов для рекурсивного спуска 46 3.2.9. Восстановление после синтаксических ошибок 48 3.3. Разбор снизу-вверх типа сдвиг-свертка 49 3.3.1. Основа 49 3.3.2. LR(k)-анализаторы 51 3.3.3. LR грамматики 56 3.3.4. Конфликты разбора типа сдвиг-свертка 62 3.3.5. Восстановление после синтаксических ошибок 63 Глава 4. Промежуточные представления программы 64 4.1. Представление в виде ориентированного графа 64 4.2. Трехадресный код 64 4.3. Линеаризованные представления 69 4.4. Организация информации в генераторе кода 72 4.5. Уровень промежуточного представления 73 Глава 5. Элементы теории перевода 74 5.1. Преобразователи с магазинной памятью 74 5.2. Синтаксически управляемый перевод 76 5.3. Атрибутные грамматики 79 5.3.1. Определение атрибутных грамматик 79 5.3.2. Атрибутированное дерево разбора 80 5.3.3. Язык описания атрибутных грамматик 81 Глава 6. Контекстные условия языков программирования 85 6.1. Описание областей видимости и блочной структуры 85 6.2. Структура среды Модулы-2 86 6.3. Занесение в среду и поиск объектов 90 Глава 7. Организация таблиц символов компилятора 98 7.1. Таблицы идентификаторов и таблицы символов 98 7.2. Таблицы идентификаторов 99 7.3. Таблицы символов и таблицы расстановки 102 7.4. Функции расстановки 103 7.5. Таблицы на деревьях 104 7.6. Реализация блочной структуры 108 7.7. Сравнение различных методов реализации таблиц 109 Глава 8. Генерация кода 110 8.1. Модель машины 110 8.2. Динамическая организация памяти 113 8.3. Назначение адресов 122 8.4. Трансляция переменных 124 8.5. Трансляция целых выражений 130 8.6. Распределение регистров при вычислении арифметических выражений 132 8.7. Трансляция логических выражений 143 8.8. Выделение общих подвыражений 151 8.9. Генерация оптимального кода методами синтаксического анализа 155 8.9.1. Сопоставление образцов 155 8.9.2. Синтаксический анализ для Т-грамматик 158 8.9.3. Выбор дерева вывода наименьшей стоимости 165 Глава 9. Системы автоматизации построения трансляторов 169 9.1. Система Супер 169 9.2. Система Yacc 172 Литература 175 Глава 1. Введение 1.1. Место компилятора в программном обеспечении Компиляторы составляют существенную часть программного обеспечения ЭВМ. Это связано с тем, что языки высокого уровня стали основным средством разработки программ. Только очень незначительная часть программного обеспечения, требующая особой эффективности, программируется с помощью ассемблеров. В настоящее время распространено довольно много языков программирования. Наряду с традиционными языками, такими, как Фортран, широкое распространение получили так называемые "универсальные языки" (Паскаль, Си, Модула-2, Ада и другие), а также некоторые специализированные (например, язык обработки списочных структур Лисп). Кроме того, большое распространение получили языки, связанные с узкими предметными областями, такие, как входные языки пакетов прикладных программ. Для некоторых языков имеется довольно много реализаций. Например, реализаций Паскаля, Модулы-2 или Си для ЭВМ типа IBM/PC на рынке десятки. С другой стороны, постоянно растущая потребность в новых компиляторах связана с бурным развитием архитектур ЭВМ. Это развитие идет по различным направлениям. Совершенствуются старые архитектуры как в концептуальном отношении, так и по отдельным, конкретным линиям. Это можно проиллюстрировать на примере микропроцессора Intel-80X86. Последовательные версии этого микропроцессора 8086, 80186, 80286, 80386, 80486, 80586 отличаются не только техническими характеристиками, но и, что более важно, новыми возможностями и, значит, изменением (расширением) системы команд. Естественно, это требует новых компиляторов (или модификации старых). То же можно сказать о микропроцессорах Motorola 68010, 68020, 68030, 68040. В рамках традиционных последовательных машин возникает большое число различных направлений архитектур. Примерами могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как Intel, Motorola, Sun, DEC, начинают переходить на выпуск машин с RISC-архитектурами. Естественно, для каждой новой системы команд требуется полный набор новых компиляторов с распространенных языков. Наконец, бурно развиваются различные параллельные архитектуры. Среди них отметим векторные, многопроцессорные, с широким командным словом (вариантом которых являются суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ с параллельной архитектурой, начиная от супер-ЭВМ (Cray, CDC и другие), через рабочие станции (например, IBM/RS-6000) и кончая персональными (например, на основе микропроцессора I- 860). Естественно, для каждой из машин создаются новые компиляторы для многих языков программирования. Здесь необходимо также отметить, что новые архитектуры требуют разработки совершенно новых подходов к созданию компиляторов, так что наряду с собственно разработкой компиляторов ведется и большая научная работа по созданию новых методов трансляции. 1.2. Структура компилятора Обобщенная структура компилятора и основные фазы компиляции показаны на рис. 1.1. На фазе лексического анализа (ЛА) входная программа, представляющая собой поток символов, разбивается на лексемы - слова в соответствии с определениями языка. Основным формализмом, лежащим в основе реализации лексических анализаторов, являются конечные автоматы и регулярные выражения. Лексический анализатор может работать в двух основных режимах: либо как подпрограмма, вызываемая синтаксическим анализатором за очередной лексемой, либо как полный проход, результатом которого является файл лексем. В процессе выделения лексем ЛА может как самостоятельно строить таблицы имен и констант, так и выдавать значения для каждой лексемы при очередном обращении к нему. В этом случае таблица имен строится в последующих фазах (например, в процессе синтаксического анализа). +-------------+ +-------------+ +-----------------+ | Лексический |-->| Диагностика | |+---------------+| Вход | анализ | +-------------+ || Поток лексем +|| ---->|-------------|------------------>|| таблицы имен ||-+ | Конечные | || и констант || | | автоматы | |+---------------+| | +-------------+ +-----------------+ | +-----------------------------------------------+ v +-------------------+ +-------------+ +------------------+ | Синтаксический |->| Диагностика | |+----------------+| | анализ | +-------------+ || Дерево разбора || |-------------------+----------------> || + таблицы ||+ | Контекстно-сво- | || имен и констант||| | бодные грамматики | |+----------------+|| +-------------------+ +------------------+| +------------------------------------------------+ v +-------------+ +-----------++----------------------+ | Контекстный |-->|Диагностика||+--------------------+| | анализ | +-----------+|| Атрибутированное || |-------------|--------------->|| дерево или дерево ||-+ | Атрибутные | || + таблица символов || | | грамматики | |+--------------------+| | +-------------+ +----------------------+ | +--------------------------------------------+ v +----------------+ +--------------------------+ | Генерация | |+------------------------+| | промежуточного | || Промежуточная форма || | представления | || (префиксная, пост- || |----------------|--->|| фиксная, тройки и др.)||---+ | СУ-трансляция | |+------------------------+| | +----------------+ +--------------------------+ | +--------------------------------------------+ | +-------------------------------------+ v v | +-------------+ +-------------------------+ | | Оптимизация | |+-----------------------+| | |-------------|-->|| Промежуточная форма || | | Потоковый | || (ориентированный граф)||--> | | анализ | |+-----------------------+| | +-------------+ +-------------------------+ | +----------------------------------------+ | v +-----------------------+ +-------------+ | Генерация кода | |+-----------+| |-----------------------+---->|| || | Таблицы решений, | || Объектный || | динамическое | || модуль || | программирование и др.| |+-----------+| +-----------------------+ +-------------+ Рис. 1.1 На этапе ЛА обнаруживаются некоторые (простейшие) ошибки (недопустимые символы, неправильная запись чисел, идентификаторов и др.). Основная задача синтаксического анализа - разбор структуры программы. Как правило, под структурой понимается дерево, соответствующее разбору в контекстно-свободной грамматике языка. В настоящее время чаще всего используется либо LL(1)- анализ (и его вариант - рекурсивный спуск), либо LR(1)-анализ и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный спуск чаще используется при ручном программировании синтаксического анализатора, LR(1) - при использовании систем автоматизации построения синтаксических анализаторов. Результатом синтаксического анализа является синтаксическое дерево со ссылками на таблицу имен. В процессе синтаксического анализа также обнаруживаются ошибки, связанные со структурой программы. На этапе контекстного анализа выявляются зависимости между частями программы, которые не могут быть описаны контекстно- свободным синтаксисом. Это в основном связи "описание- использование", в частности анализ типов объектов, анализ областей видимости, соответствие параметров, метки и другие. В процессе контекстного анализа строится таблица символов, которую можно рассматривать как таблицу имен, пополненную информацией об описаниях (свойствах) объектов. Основным формализмом, использующимся при контекстном анализе, являются атрибутные грамматики. Результатом работы фазы контекстного анализа является атрибутированное дерево программы. Информация об объектах может быть как рассредоточена в самом дереве, так и сосредоточена в отдельных таблицах символов. В процессе контекстного анализа также могут быть обнаружены ошибки, связанные с неправильным использованием объектов. Затем программа может быть переведена во внутреннее представление. Это делается для целей оптимизации и/или удобства генерации кода. Еще одной целью преобразования программы во внутреннее представление является желание иметь переносимый компилятор. Тогда только последняя фаза (генерация кода) является машинно-зависимой. В качестве внутреннего представления может использоваться префиксная или постфиксная запись, ориентированный граф, тройки, четверки и другие. Фаз оптимизации может быть несколько. Оптимизации обычно делят на машинно-зависимые и машинно-независимые, локальные и глобальные. Часть машинно-зависимой оптимизации выполняется на фазе генерации кода. Глобальная оптимизация пытается принять во внимание структуру всей программы, локальная - только небольших ее фрагментов. Глобальная оптимизация основывается на глобальном потоковом анализе, который выполняется на графе программы и представляет по существу преобразование этого графа. При этом могут учитываться такие свойства программы, как межпроцедурный анализ, межмодульный анализ, анализ областей жизни переменных и т.д. Наконец, генерация кода - последняя фаза трансляции. Результатом ее является либо ассемблерный модуль, либо объектный (или загрузочный) модуль. В процессе генерации кода могут выполняться некоторые локальные оптимизации, такие как распределение регистров, выбор длинных или коротких переходов, учет стоимости команд при выборе конкретной последовательности команд. Для генерации кода разработаны различные методы, такие как таблицы решений, сопоставление образцов, включающее динамическое программирование, различные синтаксические методы. Конечно, те или иные фазы транслятора могут либо отсутствовать совсем, либо объединяться. В простейшем случае однопроходного транслятора нет явной фазы генерации промежуточного представления и оптимизации, остальные фазы объединены в одну, причем нет и явно построенного синтаксического дерева. Глава 2. Лексический анализ Основная задача лексического анализа - разбить входной текст, состоящий из последовательности одиночных символов, на последовательность слов, или лексем, т.е. выделить эти слова из непрерывной последовательности символов. Все символы входной последовательности с этой точки зрения разделяются на символы, принадлежащие каким-либо лексемам, и символы, разделяющие лексемы (разделители). В некоторых случаях между лексемами может и не быть разделителей. С другой стороны, в некоторых языках лексемы могут содержать незначащие символы (пробел в Фортране). В Си разделительное значение символов- разделителей может блокироваться ('\' в конце строки внутри "..."). Обычно все лексемы делятся на классы. Примерами таких классов являются числа (целые, восьмеричные, шестнадцатиричные, действительные и т.д.), идентификаторы, строки. Отдельно выделяются ключевые слова и символы пунктуации (иногда их называют символы-ограничители). Как правило, ключевые слова - это некоторое конечное подмножество идентификаторов. В некоторых языках (например, ПЛ/1) смысл лексемы может зависеть от ее контекста и невозможно провести лексический анализ в отрыве от синтаксического. С точки зрения дальнейших фаз анализа лексический анализатор выдает информацию двух сортов: для синтаксического анализатора, работающего вслед за лексическим, существенна информация о последовательности классов лексем, ограничителей и ключевых слов, а для контексного анализа, работающего вслед за синтаксическим, важна информация о конкретных значениях отдельных лексем (идентификаторов, чисел и т.д.). Поэтому общая схема работы лексического анализатора такова. Сначала выделяем отдельную лексему (возможно, используя символы- разделители). Если выделенная лексема - ограничитель, то он (точнее, некоторый его признак) выдается как результат лексического анализа. Ключевые слова распознаются либо явным выделением непосредственно из текста, либо сначала выделяется идентификатор, а затем делается проверка на принадлежность его множеству ключевых слов. Если да, то выдается признак соответствующего ключевого слова, если нет - выдается признак идентификатора, а сам идентификатор сохраняется отдельно. Если выделенная лексема принадлежит какому-либо из других классов лексем (число, строка и т.д.), то выдается признак класса лексемы, а значение лексемы сохраняется. Лексический анализатор может работать или как самостоятельная фаза трансляции, или как подпрограмма, работающая по принципу "дай лексему". В первом случае (рис. 2.1) выходом лексического анализатора является файл лексем, во втором (рис. 2.2) лексема выдается при каждом обращении к лексическому анализатору (при этом, как правило, тип лексемы возвращается как значение функции "лексический анализатор", а значение передается через глобальную переменную). С точки зрения формирования значений лексем, принадлежащих классам лексем, лексический анализатор может либо просто выдавать значение каждой лексемы и в этом случае построение таблиц переносится на более поздние фазы, либо он может самостоятельно строить таблицы объектов (идентификаторов, строк, чисел и т.д.). В этом случае в качестве значения лексемы выдается указатель на вход в соответствующую таблицу. +------------------+ | Синт. анализатор |<-----+ +------------------+ | ^| | +---------------------+ || +----------+ | Тип, Значение | ... | Тип || | Значение | +---------------------+ лексемы || +----------+ | |v ^ | +---------+ +------------------+ | +--->| Таблица | | Лекс. анализатор |------+ +---------+ +------------------+ Файл лексем "Дай лексему" Рис. 2.1 Рис. 2.2 Работа лексического анализатора описывается формализмом конечных автоматов. Однако непосредственное описание конечного автомата неудобно практически. Поэтому для описания лексических анализаторов, как правило, используют либо формализм регулярных выражений, либо формализм контекстно свободных грамматик, а именно подкласса автоматных, или регулярных, грамматик. Все три формализма (конечных автоматов, регулярных выражений и автоматных грамматик) имеют одинаковую выразительную мощность. По описанию лексического анализатора в виде регулярного выражения или автоматной грамматики строится конечный автомат, распознающий соответствующий язык. 2.1. Регулярные множества и регулярные выражения Пусть T - конечный алфавит. Регулярное множество в алфавите T определяется рекурсивно следующим образом (знаком '<-' будем обозначать принадлежность множеству, знаком '<=' включение): (1) {} (пустое множество) - регулярное множество в алфавите T; (2) {a} - регулярное множество в алфавите T для каждого a<- T; (3){е} - регулярное множество в алфавите T (e - пустая цепочка); (4) если P и Q - регулярные множества в алфавите T, то таковы же и множества (а) P U Q (объединение), (б) PQ (конкатенация, т.е. множество pq, p<-P, q<-Q), (в) P* (итерация: P*={e} U P U PP U...; (5) ничто другое не является регулярным множеством в алфавите T. Итак, множество в алфавите T регулярно тогда и только тогда, когда оно либо {}, либо {e}, либо {a} для некоторого a<-T, либо его можно получить из этих множеств применением конечного числа операций объединения, конкатенации и итерации. Приведенное выше определение регулярного множества одновременно определяет и форму его записи, которую будем называть регулярным выражением. Для сокращенного обозначения выражения PP* будем пользоваться записью P+ и там, где это необходимо, будем использовать скобки. В этой записи наивысшим приоритетом обладает операция *, затем конкатенация и, наконец, операция U, для записи которой иногда будем использовать значок '|'. Так, 0|10* означает (0|(1(0*))). Кроме того, мы будем использовать запись вида d1 = r1 d2 = r2 ....... dn = rn где di - различные имена, а каждое ri - регулярное выражение над символами T U {d1,d2,...,di-1}, т.е. символами основного алфавита и ранее определенными символами. Таким образом, для любого ri можно построить регулярное выражение над Т, повторно заменяя имена регулярных выражений на обозначаемые ими регулярные выражения. Пример 2.1. Несколько примеров регулярных выражений и обозначаемых ими множеств Идентификатор - это регулярное выражение Идентификатор = Буква (Буква|Цифра)* Буква = {a,b,...,z} Цифра = {0,1,...,9} Число в десятичной записи - это регулярное выражение Целое = Цифра+ Дробная_часть = . Целое | е Спепень = ( Е ( + | - | е ) Целое ) | е Число = Целое Дробная_часть Степень Ясно, что для каждого регулярного множества можно найти по крайней мере одно регулярное выражение, обозначающее это множество. И обратно: для каждого регулярного выражения можно построить регулярное множество, обозначаемое этим выражением. Для каждого регулярного множества существует бесконечно много обозначающих его регулярных выражений. Будем говорить, что два регулярных выражения равны, если они обозначают одно и то же множество. 2.2. Конечные автоматы Недетерминированный конечный автомат (НКА) - это пятерка M=(Q,T,D,Q0,F), где (1) Q - конечное множество состояний; (2) T - конечное множество допустимых входных символов; (3) D - функция переходов, отображающая множество QxT во множество подмножеств множества Q и определяющая поведение управляющего устройства; (4) Q0<=Q - множество начальных состояний управляющего устройства; (5) F<=Q - множество заключительных состояний. Детерминированный конечный автомат (ДКА) - это пятерка M=(Q,T,D,q0,F), где (1) Q - конечное множество состояний; (2) T - конечное множество допустимых входных символов; (3) D - функция переходов, отображающая множества QxT в множество Q и определяющая поведение управляющего устройства; (4) q0<-Q - начальное состояние управляющего устройства; (5) F<=Q - множество заключительных состояний. Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт определяется текущим состоянием управляющего устройства и входным символом, обозреваемым в данный момент входной головкой. Сам шаг состоит из изменения состояния и сдвига входной головки на одну ячейку вправо (рис. 2.3). +-----------+ | Состояние | +-----------+ | v +---------------------------------------+ | | a | .............. | +---------------------------------------+ Прочитанная Текущий Непрочитанная часть входной входной часть входной входной цепочки символ цепочки Рис. 2.3 Текущее состояние управляющего устройства, символ под головкой и цепочка символов вправо от головки называются конфигурацией автомата. Конфигурация (q0,w) называется начальной, а пара (q,e), где q<-F, называется заключительной (или допускающей). | v +---+ | 1 | +---+ | Цифра +------ v | \---+Не (цифра,Е,"." +-----+ | Цифра | 2 |--------------->|| 3 || | /---\ +-----+ +------ |. \ E v --------------------+ +---+ | | 4 | | +---+ | | Цифра | +------- v | | \--- Не цифра,Е +-----+ | | Цифра | 5 |------------>|| 6 || | | /--- +-----+ | +------- |E | v | +---+ | | 7 |<--------------------+ +---\ +,- | \ Цифра v \ +---+ | | 8 | | +---+ | Цифра | / +------- v / | \---/ Не цифра +------+ | Цифра | 9 |--------->|| 10 || | /--- +------+ +------- Рис. 2.4 Такт автомата M представляется бинарным отношением |-, определенным на конфигурациях: отношение имеет место, если есть переход из конфигурации (q1,w1) в конфигурацию (q2,w2). Отношения |-+ и |-* - это, соответственно, транзитивное и рефлексивно-транзитивное замыкание отношения |-. Говорят, что автомат M допускает цепочку w, если (q0,w)|-*(q,e) для некоторого q<-F. Языком, допускаемым (распознаваемым, определяемым) автоматом M, (обозначается L(M)), называется множество входных цепочек, допускаемых автоматом M. Т.е. L(M)={w | w<-T* и (q0,w)|-*(q,e) для некоторого q<-F} Конечный автомат может быть изображен графически в виде графа, в котором каждому состоянию соответствует вершина, а дуга, помеченная символом a, соединяет две вершины p и q, если функция переходов содержит (q,a)->p. На диаграмме выделяются конечные состояния (в примерах выше двойным контуром). Пример 2.2. Диаграмма для чисел языка Паскаль приведена на рис. 2.4. 2.3. Построение детерминированного конечного автомата по регулярному выражению. Приведем теперь алгоритм построения детерминированного конечного автомата по регулярному выражению [1]. К регулярному выражению (сокращенно РВ) r добавим маркер конца: (r)#. После построения ДКА для расширенного РВ легко построить ДКА для исходного РВ: все состояния ДКА из которых есть переход в конечное с чтением символа "#", можно считать конечными, а символ "#" и соответствующие переходы удалить. Представим РВ в виде дерева, листья которого - терминальные символы, а внутренние вершины - операции "." (конкатенации), "U" (объединение), "*" (итерация). Каждому листу дерева (кроме e-листьев) припишем уникальный номер и ссылаться на него будем, с одной стороны, как на позицию в дереве и, с другой стороны, как на позицию символа, соответствующего листу. Теперь, обходя дерево T сверху-вниз слева-направо, вычислим четыре функции: nullable, firstpos, lastpos и followpos. Функции nullable, firstpos и lastpos определены на узлах дерева, а followpos - на множестве позиций. Значением всех функций, кроме nullable, является множество позиций. Функция followpos вычисляется через три остальные функции. Функция firstpos(n) для каждого узла n синтаксического дерева регулярного выражения дает множество позиций, которые соответствуют первым символам в подцепочках, генерируемых подвыражением с вершиной в n. Аналогично, lastpos(n) дает множество позиций, которым соответствуют последние символы в подцепочках, генерируемых подвыражениями с вершиной n. Для узлов n, поддеревья которых (т.е. дерево, у которого узел n является корнем) могут породить пустое слово, определим nullable(n)=true, а для остальных узлов false. узел n nullable(n) firstpos(n) lastpos(n) --------------------------------------------------------- лист е | true | 0 | 0 --------+-------------+------------------+-------------- лист i | false | {i} | {i} --------+-------------+------------------+-------------- U | nullable(a) | firstpos(a) | lastpos(a) / \ | or | U | U a b | nullable(b) | firstpos(b) | lastpos(b) --------+-------------+------------------+-------------- . | nullable(a) | if nullable(a) |if nullable(b) / \ | and | then firstpos(a) |then lastpos(a) | | U firstpos(b) | U lastpos(b) a b | nullable(b) | else firstpos(a) |else lastpos(b) --------+-------------+------------------+-------------- * | | | | | true | firstpos(a) | lastpos(a) a | | | -------------------------------------------------------- Рис. 2.5 Таблица для вычисления функций nullable и firstpos приведена на рис. 2.5. Вычисление функции lastpos строится аналогично. {1,2,3}.{6} / \ {1,2,3}.{5} {6}#{6} / \ позиция | followpos {1,2,3}.{4} {5}b{5} --------+------------- / \ 1 | {1,2,3} {1,2,3}.{3} {4}b{4} 2 | {1,2,3} / \ 3 | {4} {1,2}*{1,2} {3}a{3} 4 | {5} | 5 | {6} {1,2}U{1,2} 6 | - / \ ---------------------- {1}a{1} {2}b{2} Рис. 2.6 Рис. 2.7 Пример 2.3. Функции firstpos и lastpos для выражения (a+b)abb# приведены на рис. 2.6. Слева от каждой вершины значение firstpos, справа - lastpos. Заметим, что эти функции могут быть вычислены за один обход дерева. Если i - позиция, то followpos(i) есть множество позиций j таких, что существует некоторая строка ...cd..., входящая в язык, описываемый РВ, такая, что i - соответствует этому вхождению c, а j - вхождению d. Функция followpos может быть вычислена также за один обход дерева по следующим двум правилам 1. Пусть n - внутренний узел с операцией "." (конкатенация), a,b - его потомки. Тогда для каждой позиции i, входящей в lastpos(a), добавляем к множеству значений followpos(i) множество firstpos(b). 2. Пусть n - внутренний узел с операцией "*" (итерация), a - его потомок. Тогда для каждой позиции i, входящей в lastpos(a), добавляем к множеству значений followpos(i) множество firstpos(а). Для примера 2.3 значения функции followpos приведены на рис. 2.7. Функция followpos позволит теперь сразу построить детерминированный конечный автомат с помощью следующего алгоритма. Алгоритм 2.1. Прямое построение ДКА по регулярному выражению. Будем строить множество состояний автомата Dstates и помечать их. Состояния ДКА соответствуют множествам позиций. Начальным состоянием будет состояние firstpos(root), где root - вершина синтаксического дерева регулярного выражения, конечными - все состояния, содержащие позиции, связанные с символом "#". Сначала в Dstates имеется только одно непомеченное состояние firstpos(root). while есть непомеченное состояние T в Dstates do пометить T; for каждого входного символа a<-T do пусть символу a в T соответствуют позиции p1,...,pi, и пусть S=U followpos(pi) i Если S не пусто и S не принадлежит Dstates, то добавить непомеченное состояние S в Dstates (рис. 2.8) Функцию перехода Dtran для T и a определить как Dtran(T,a)=S. end; end; Для примера 2.3 вначале T={1(a),2(b),3(a)}. Последовательность шагов алгоритма приведена на рис. 2.9. В результате будет построен детерминированный конечный автомат, изображенный на рис. 2.10. Состояния автомата обозначаются как множества позиций, например {1,2,3}, конечное состояние заключено в квадратные скобки [1,2,3,6]. a: {1,2,3,4} T={1(a),2(b),3(a)} b: {1,2,3} / / \ v v v {1,2,3} {4} +------------+ +----+ a: {1,2,3,4} T={1(a),2(b),3(a),4(b)} |+----+ | | | b: {1,2,3,5} / / | | ||b | | | | v v v v ||----+------+-+>Sb | {1,2,3} {4} {5} ||{pb}|+----+| |----| |+----+|a || | | a: {1,2,3,4} T={1(a),2(b),3(a),5(b)} | |----++-+>Sa | b: {1,2,3,6} / / | | | |{pa}|| | | v v v v | +----+| | | {1,2,3} {4} {6} +------------+ +----+ a: {1,2,3,4} T={1(a),2(b),3(a),6(#)} b: {1,2,3} / / | v v v {1,2,3} {4} Рис. 2.8 Рис. 2.9 +--------------------b--------------------+ | +-----------a--------------+ | +-+ | +-+ | +----a-----+ | | |b| | |a| | | | | | V | V a V | V V b | b | | ---->{1,2,3}--->{1,2,3,4}----->{1,2,3,5}----->[1,2,3,6] Рис. 2.10 2.4. Построение детерминированного конечного автомата с минимальным числом состояний Рассмотрим теперь алгоритм построения ДКА с минимальным числом состояний, эквивалентного данному ДКА [2]. Алгоритм 2.2. Построение ДКА с минимальным числом состояний. Шаг 1. Строим начальное разбиение П множества состояний из двух групп: заключительное состояние и остальные S-F. Шаг 2. Применяем к П следующую процедуру и получаем новое разбиение Пnew (рис. 2.11): for каждой группы G в П do разбиваем G на подгруппы так, чтобы состояния s и t из G оказались в одной группе тогда и только тогда, когда для каждого входного символа a состояния s и t имеют переходы по a в состояния из одной и той же группы в П; заменяем G в Пnew на множество всех полученных подгрупп end; +---+ +-+ +-+ +-----|s,t|-----+ |s| |t| | +---+ | +-+ +-+ |a a| | | | +---+ | v v +---->| |<----+ +-+ +-+ +---+ | | | | +-+ +-+ Рис. 2.11 Шаг 3. Если Пnew=П, полагаем Пres=П и переходим к шагу 4, иначе повторяем шаг 2 с П:=Пnew. Шаг 4. Выберем по одному состоянию из каждой группы в разбиении Пres в качестве представителя для этой группы. Представители будут состояниями приведенного ДКА М'. Пусть s - представитель. Предположим, что на входе a в M существует переход из t. Пусть r - представитель группы t. Тогда М' имеет переход из a в r по a. Пусть начальное состояние М' - представитель группы, содержащей начальное состояние s0 исходного M, и пусть заключительные состояния М' - представители в F. Отметим, что каждая группа Пres либо состоит только из состояний из F, либо не имеет состояний из F. Шаг 5. Если М' имеет мертвое состояние, т.е. состояние d, которое не является допускающим и которое имеет переходы в себя по любому символу, удалим его из М'. Удалим также все состояния, не достижимые из начального. 2.5. Программирование лексических анализаторов Лексический анализатор, как правило, вызывается как подпрограмма. В результате обращения к ЛА вырабатываются как минимум два результата: тип выбранной лексемы и значение (или указатель на значение) для классов лексем (идентификаторов, чисел, строк и т.д.). Само значение передается, если ЛА не работает с таблицей имен. Если же ЛА сам формирует таблицу имен, то он выдает указатель на имя. Обычно ЛА оформляется как процедура-функция, вырабатывающая тип лексемы и заносящая в некоторую глобальную переменную значение лексемы, если это необходимо. Помимо значения лексемы, эта глобальная переменная может содержать некоторую дополнительную информацию: номер текущей строки, номер символа в строке и другую. Эта информация может использоваться в различных целях, например, для диагностики. Тело ЛА представляет собой диаграмму переходов соответствующего конечного автомата. Отдельная проблема - анализ ключевых слов. Как правило, ключевые слова - это выделенные идентификаторы. Поэтому возможны два основных способа выделения ключевых слов: либо очередная лексема сначала диагностируется на совпадение с каким-либо ключевым словом и в случае неуспеха делается попытка выделить лексему из какого-либо класса, либо, наоборот, после выборки лексемы идентификатора требуется заглянуть в таблицу ключевых слов на предмет сравнения. Подробнее о механизмах поиска в таблицах будет сказано ниже (гл. 7), здесь отметим только, что поиск ключевых слов может вестись либо в основной таблице имен и в этом случае в нее до начала работы ЛА загружаются ключевые слова, либо в отдельной таблице. При первом способе все ключевые слова непосредственно встраиваются в конечный автомат лексического анализатора, во втором конечный автомат содержит только разбор идентификаторов. В некоторых языках (например, ПЛ/1 или Фортран) ключевые слова могут использоваться в качестве обычных идентификаторов. В этом случае работа ЛА не может идти независимо от работы синтаксического анализатора. В Фортране возможны, например, следующие строки: DO 10 I=1,25 и DO 10 I=1.25 В первом случае строка - это заголовок цикла DO, во втором - оператор присваивания. Поэтому, прежде чем можно будет выделить лексему, лексический анализатор должен заглянуть довольно далеко. Еще сложнее дело в ПЛ/1. Здесь возможны такие операторы: IF THEN THEN THEN = ELSE; ELSE ELSE = THEN или DECLARE (ARG1, ARG2, ...., ARGn) ... и только в зависимости от того, что стоит после ")", можно определить, является ли DECLARE именем подпрограммы или объявлением. Длина такой строки может быть сколь угодно большой и уже невозможно отделить фазу синтаксического анализа от фазы лексического анализа. Рассмотрим несколько подробнее вопросы программирования ЛА. Основная операция лексического анализатора, на которую уходит большая часть времени его работы, - это взятие очередного символа и проверка на принадлежность его некоторому диапазону. Например, основной цикл при выборке числа в простейшем случае может выглядеть следующим образом: while (Insym<='9' & Insym>='0') do ... end; Проверки на принадлежность диапазону сравнениями можно заменить проверками на принадлежность диапазону множества: while (Insym in ['0'..'9']) do ... end; Однако с точки зрения качества кода эти программы примерно эквивалентны. Программу можно значительно улучшить следующим образом [2]. Пусть LETTER, DIGIT, BLANK, SLESS - элементы перечислимого типа. Введем массив MAP, входами которого будут символы, значениями - типы символов. Инициализируем массив MAP следующим образом: MAP['A']:=LETTER; ........ MAP['z']:=LETTER; MAP['0']:=DIGIT; ........ MAP['9']:=DIGIT MAP[' ']:=BLANK; MAP['<']:=SLESS; ........ Тогда приведенный выше цикл примет следующую форму: while (Map[Insym]=Digit) do ... end; Выделение ключевых слов может осуществляться после выделения идентификаторов. ЛА работает быстрее, если ключевые слова выделяются непосредственно. +----------+ ------------------->| ключевое | +---+ f +---/не буква и не цифра | слово if | | i |--->| | +----------+ +---\ +---\буква или цифра +---------------+ | \ ---------------->| Идентификатор | n| \ +---------------+ | \ ^ ^ ^ | \ Не f и не t | | | v --------------------------+ | | +---+ Не t | | | |--------------------------------+ | +---+ | t| | v | +---+ Буква или цифра | | |-----------------------------------+ +---+ | Не буква и не цифра v +--------------------+ | Ключевое слово int | +--------------------+ Рис. 2.12 Для этого строится конечный автомат, описывающий множество ключевых слов. На рис. 2.12 приведен фрагмент такого автомата. Рассмотрим пример программирования этого конечного автомата на языке Си, приведенный в [3]: case 'i': if (cp[0]=='f' &&!(map[cp[1]] & (digit | letter))) {cp++; return IF;} if (cp[0]=='n' && cp[1]=='t' &&!(map[cp[2]] & (digit | letter))) {cp+=2; return INT;} Здесь cp - указатель текущего символа. В массиве map классы символов кодируются битами. Поскольку ЛА анализирует каждый символ входного потока, его скорость существенно зависит от скорости выборки очередного символа входного потока. В свою очередь, эта скорость во многом определяется схемой буферизации. Рассмотрим несколько возможных эффективных схем буферизации. В первой схеме используется буфер, размер которого - двойная длина блока обмена N (рис. 2.13). N N +----------------+ +-------------------+ | | | | # | # | +----------------+ +-------------------+ ^ ^ ^ ^ | |Продвижение | |Продвижение |Начало лексемы (cp) |Начало лексемы Рис. 2.13 Рис. 2.14 Чтобы не читать каждый символ отдельно, в каждую из половин буфера одной командой чтения считывается N символов. Если на входе осталось меньше N символов, в буфер помещается специальный символ (eof). На буфер указывают два указателя: продвижение и начало. Между указателями размещается текущая лексема. Вначале они оба указывают на первый символ выделяемой лексемы. Один из них, продвижение, продвигается вперед, пока не будет выделена лексема, и устанавливается на ее конец. После обработки лексемы оба указателя устанавливаются на символ, следующий за лексемой. Если указатель продвижение переходит середину буфера, правая половина заполняется новыми N символами. Если указатель продвижение переходит правую границу буфера, левая половина заполняется N символами и указатель продвижение устанавливается на начало буфера. При каждом продвижении указателя необходимо проверять, не достигли ли мы границы одной из половин буфера. Для всех символов, кроме лежащих в конце половин буфера, требуются две проверки. Число проверок можно свести к одной, если в конце каждой половины поместить дополнительный 'сторожевой' символ '#' (рис. 2.14). В этом случае почти для всех символов делается единственная проверка на совпадение с '#' и только в случае совпадения нужно проверить, достигли ли мы середины или правого конца. В третьей схеме используются три указателя (рис. 2.15). Непросмотренная часть буфера заключена между текущим и границей (граница - это указатель на последний элемент буфера). Анализ очередной лексемы начинается после сканирования незначащих пробелов. Если после этого текущий указывает на '#' в конце буфера, делается перезагрузка буфера (предполагается, что '#' не может входить в состав лексемы). Барьер выбирается таким образом, чтобы между барьером и границей всегда помещалась любая лексема. Если начало очередной лексемы оказывается правее барьера, то часть буфера от текущего до границы переписывается левее буфера и буфер перезагужается. Тем самым начало лексемы конкатенируется с ее концом. Так обрабатывается ситуация, когда граница буфера прошла через лексему. +----------+ +-----+ | N | | N | v v v v +------------------+ +-------------+ | | |\n| | | | #| +------------------+ +-------------+ | | |Граница | | |Граница | |Барьер | |Барьер |Текущий |Текущий а) Пока текущий < барьер б) После чтения Рис. 2.15 В результате большинство входных символов обрабатываются непосредственно в буфере. Копируются только идентификаторы и строковые константы в соответствующие таблицы. 2.6. Конструктор лексических анализаторов LEX Для автоматизации разработки лексических анализаторов было разработано довольно много средств. Как правило, входным языком для них служат либо КС (автоматные) грамматики, либо язык регулярных выражений. Одной из наиболее распространенных систем является LEX, входным языком которого являются регулярные выражения. LEX-программа состоит из трех частей: Объявления %% Правила трансляции %% Вспомогательные процедуры Секция объявлений включает объявления переменных, констант и определения регулярных выражений. Правила трансляции LEX программ имеют вид p1 { действие_1 } p2 { действие_2 } ............... pn { действие_n } где каждое pi - регулярное выражение, а каждое действие_i - фрагмент программы, описывающий, какое действие должен сделать лексический анализатор, когда образец pi сопоставляется лексеме. В LEX действия записываются на Си. Третья секция содержит вспомогательные процедуры, необходимые для действий. Эти процедуры могут транслироваться раздельно и загружаться с лексическим анализатором. Лексический анализатор, сгенерированный LEX, взаимодействует с синтаксическим анализатором следующим образом. При вызове его синтаксическим анализатором лексический анализатор посимвольно читает остаток входа, пока не находит самый длинный префикс, который может быть сопоставлен одному из регулярных выражений pi. Затем он выполняет действие_i. Как правило, действие_i возвращает управление синтаксическому анализатору. Если это не так, т.е. в соответствующем действии нет возврата, то лексический анализатор продолжает поиск лексем до тех, пока действие не вернет управление синтаксическому анализатору. Повторный поиск лексем вплоть до явной передачи управления позволяет лексическому анализатору правильно обрабатывать пробелы и комментарии. Синтаксическому анализатору лексический анализатор возвращает единственное значение - тип лексемы. Для передачи информации о лексеме используется глобальная переменная yylval. Пример 2.4. На рис. 2.16 приведена LEX-программа. %{ /*определения констант LT,LE,EQ,NE,GT, GE,IF,THEN,ELSE,ID,NUMBER,RELOP например через DEFINE или скалярный тип*/ %} /*регулярные определения*/ delim [ \t\n] ws {delim}+ letter [A-Za-z] digit [0-9] id {letter}({letter}|{digit})* number {digit}+(\.{digit}+)?(E[+\-]?{digit}+)? %% {ws} {/* действий и возврата нет */} if {return(IF);} then {return(THEN);} else {return(ELSE);} {id} {yylval=install_id(); return(ID);} {number} {yylval=install_num(); return(NUMBER);} "<" {yylval=LT; return(RELOP);} "<=" {yylval=LE; return(RELOP);} "=" {yylval=EQ; return(RELOP);} "<>" {yylval=NE; return(RELOP);} ">" {yylval=GT; return(RELOP);} ">=" {yylval=GE; return(RELOP);} %% install_id(){/*процедура, которая помещает лексему, на первый символ которой указывает yytext, длина которой равна yyleng, в таблицу символов и возвращает указатель на нее*/ } install_num(){/*аналогичная процедура для размещения лексемы числа*/ } Рис. 2.16. В разделе объявлений, заключенном в скобки %{ и %}, перечислены константы, используемые правилами трансляции. Все, что заключено в эти скобки, непосредственно копируется в программу лексического анализатора lex.yy.c и не рассматривается как часть регулярных определений или правил трансляции. То же касается и вспомогательных процедур третьей секции. На рис. 2.16 это процедуры install_id и install_num. В секцию определений входят также некоторые регулярные определения. Каждое такое определение состоит из имени и регулярного выражения, обозначаемого этим именем. Например, первое определенное имя - это delim. Оно обозначает класс символов { \t\n}, т.е. любой из трех символов: пробел, табуляция или новая строка. Второе определение - разделитель, обозначаемый именем ws. Разделитель - это любая последовательность одного или более символов-разделителей. Слово delim должно быть заключено в скобки, чтобы отличить его от образца, состоящего из пяти символов delim. В определении letter используется класс символов. Сокращение [A-Za-z] означает любую из прописных букв от A до Z или строчных букв от a до z. В пятом определении для id для группировки используются скобки, являющиеся метасимволами LEX. Аналогично, вертикальная черта - метасимвол LEX, обозначающий объединение. В последнем регулярном определении number символ '+' используется как метасимвол "одно или более вхождений", символ '?' как метасимвол "ноль или одно вхождение". Обратная черта используется для того, чтобы придать обычный смысл символу, использующемуся в LEX как метасимвол. В частности, десятичная точка в определении number обозначается как '\.', поскольку точка сама по себе представляет класс, состоящий из всех символов, за исключением символа новой строки. В классe символов [+\-] обратная черта перед минусом стоит потому, что знак минус используется как символ диапазона, как в [A-Z]. Если символ имеет смысл метасимвола, то придать ему обычный свысл можно и по-другому, заключив его в кавычки. Так, в секции правил трансляции шесть операций отношения заключены в кавычки. Рассмотрим правила трансляции, следующие за первым %%. Согласно первому правилу, если обнаружено ws, т.е. максимальная последовательность пробелов, табуляций и новых строк, никаких действий не производится. В частности, не осуществляется возврат в синтаксический анализатор. Согласно второму правилу, если обнаружена последовательность букв 'if', нужно вернуть значение IF, которое определено как целая константа, понимаемая синтаксическим анализатором как лексема 'if'. Аналогично обрабатываются ключевые слова 'then' и 'else' в двух следущих правилах. В действии, связанном с правилом для id, два оператора. Переменной yylval присваивается значение, возвращаемое процедурой install_id. Определение этой процедуры приведено в разделе 3.1. Переменная yylval определена в программе lex.yy.c, выходе LEX, и она доступна синтаксическому анализатору. yylval хранит возвращаемое лексическое значение, поскольку второй оператор в действии, return(ID), может только возвратить код класса лексем. Функция install_id заносит идентификаторы в таблицу символов. Текущая лексема доступна благодаря двум указателям: yytext и yyleng. Переменная yytext - это указатель на первый символ лексемы, yyleng - это целое, дающее длину лексемы. Например, при занесении идентификатора в таблицу могут быть скопированы yyleng символов, начиная с yytext. Аналогично обрабатываются числа в следующем правиле. В последних шести правилах yylval используется для возврата кода операции отношения, возвращаемое же функцией значение - это код лексемы relop. Если, например, в текущий момент лексический анализатор обрабатывает лексему 'if', то этой лексеме соответствуют два образца: 'if' и {id} и более длинной строки, соответствующей образцу, нет. Поскольку образец 'if' предшествует образцу для идентификатора, конфликт разрешается в пользу ключевого слова. Такая стратегия разрешения конфликтов позволяет легко резервировать ключевые слова. Если на входе встречается '<=', то первому символу соответствует образец '<', но это не самый длинный образец, который соответствует префиксу входа. Стратегия выбора самого длинного префикса легко разрешает такого рода конфликты. Глава 3. Синтаксический анализ 3.1. Основные понятия и определения Пусть G=- контекстно-свободная грамматика, где N - множество нетерминальных символов, T - множество терминальных символов, P - множество правил вывода и S - аксиома. Будем говорить, что uxv выводится за один шаг из uAv (и записывать это как uAv=>uxv), если A->x - правило вывода и u и v - произвольные строки из (N U T)*. Если u1=>u2=>...=>un, будем говорить, что из u1 выводится un, и записывать это как u1=>*un. Т.е.: 1) u=>*u для любой строки u, 2) если u=>*v и v=>*w, то u=>*w. Аналогично, "=>+" означает выводится за один или более шагов. Если дана грамматика G с начальным символом S, отношение =>+ можно использовать для определения L(G) - языка, порожденного G. Строки L(G) могут содержать только терминальные символы G. Строка терминалов w принадлежит L(G) тогда и только тогда, когда S=>+w. Строка w называется предложением в G. Если S=>*u, где u может содержать нетерминалы, то u называется сентенциальной формой в G. Предложение - это сентенциальная форма, не содержащая нетерминалов. Рассмотрим выводы, в которых в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала. Такой вывод называется левосторонним. Если S=>*u в процессе левостороннего вывода, то u - левая сентенциальная форма. Аналогично определяется правосторонний вывод. Упорядоченным графом называется пара (V,E), где V обозначает множество вершин, а E - множество линейно упорядоченных списков дуг, каждый элемент которого имеет вид ((v,e1),(v,e2),...,(v,en)). Этот элемент указывает, что из вершины a выходят n дуг, причем первой из них считается дуга, входящая в вершину e1, второй - дуга, входящая в вершину e2, и т.д. Дерево вывода в грамматике G=(N,T,P,S) - это помеченное упорядоченное дерево, каждая вершина которого помечена символом из множества N U T U {e}. Если внутренняя вершина помечена символом A, а ее прямые потомки - символами X1,..., Xn, то A->X1X2...Xn - правило этой грамматики. Упорядоченное помеченное дерево D называется деревом вывода (или деревом разбора) в КС-грамматике G(S)=(N,T,P,S), если выполнены следующие условия: (1) корень дерева D помечен S; (2) каждый лист помечен либо a<-T, либо e; (3) каждая внутренняя вершина помечена нетерминалом; (4) если N - нетерминал, которым помечена внутренняя вершина и X1,...,Xn - метки ее прямых потомков в указанном порядке, то N->X1...Xk - правило из множества P. Автомат с магазинной памятью (сокращенно МП-автомат) - это семерка P=(Q,T,Г,d,q0,Z0,F), где (1) Q - конечное множество символов состояний, представляющих всевозможные состояния управляющего устройства; (2) T - конечный входной алфавит; (3) Г - конечный алфавит магазинных символов; (4) d - функция переходов - отображение множества Qx(T U {e})xГ в множество конечных подмножеств QxГ*, т.е. d:Qx(T U {e})xГ -> {QxГ*}; (5) q0<-Q - начальное состояние управляющего устройства; (6) Z0<-Г - символ, находящийся в магазине в начальный момент (начальный символ); (7) F<=Q - множество заключительных состояний Конфигурацией МП-автомата называется тройка (q,w,u)<-QxT*xГ*, где (1) q - текущее состояние управляющего устройства; (2) w - неиспользованная часть входной цепочки; первый символ цепочки w находится под входной головкой; если w e, то считается, что вся входная лента прочитана; (3) u - содержимое магазина; самый левый символ цепочки u считается верхним символом магазина; если u=e, то магазин считается пустым. Такт работы МП-автомата P будем представлять в виде бинарного отношения |-, определенного на конфигурациях. Будем писать (q,aw,Zu)|-(q',w,vu) если множество d(q,a,Z) содержит (q',v), где q, q'<-Q, a<-T U {e}, w<-T*, Z<-Г, u,v<-Г*. Начальной конфигурацией МП-автомата P называется конфигурация вида (q0,w,Z0), где w<-T*, т.е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно распознать, а в магазине есть только начальный символ Z0. Заключительная конфигурация - это конфигурация вида (q,e,u), где q<-F, u<-Г*. Говорят, что цепочка w допускается МП-автоматом P, если (q0,w,Z0)|-*(q,e,u) для некоторых q<-F и u<-Г*. Языком, определяемым (или допускаемым) автоматом P (обозначается L(P)), называют множество цепочек, допускаемых автоматом P. Иногда допустимость определяют несколько иначе: цепочка w допускается МП-автоматом P, если (q0,w,Z0)|-*(q,e,e). Эти определения эквивалентны. 3.2. Таблично-управляемый предсказывающий разбор 3.2.1. Алгоритм разбора сверху-вниз Основная проблема предсказывающего разбора - определение правила вывода, которое нужно применить к нетерминалу. Процесс предсказывающего разбора (сверху-вниз) с точки зрения построения дерева разбора можно проиллюстрировать рис. 3.1. Фрагменты недостроенного дерева соответствуют сентенциальным формам вывода. Вначале дерево состоит только из одной вершины, соответствующей аксиоме S. В этот момент по первому символу входного потока предсказывающий анализатор должен определить правило S->X1 X2 ..., которое должно быть применено к S. Затем необходимо определить правило, которое должно быть применено к X1, и т.д., до тех пор, пока в процессе такого построения сентенциальной формы, соответствующей левому выводу, не будет применено правило Y->a .... Этот процесс затем применяется для следующего самого левого нетерминального символа сентенциальной формы. S S S / | \ / | \ X1 X2... X1 X2... / / | ........... ............. / / | Y Y | /|\ /|\ Z / ... / ... /|\ a..........$ a...........$ a........b.......$ а) б) в) Рис. 3.1 На рис. 3.2 приведена структура предсказывающего анализатора, который определяет очередное правило из таблицы. Такую таблицу множно построить непосредственно из грамматики. +---------------+ Вход | a | + | b | $ | +---------------+ ^ | +-+ +----------------------+ |X| | Программа предсказы- | Выход Магазин |-|<---| вающего анализатора |---> |Y| +----------------------+ |Z| | |-| v |$| +---------------------+ +-+ | Таблица анализатора | +---------------------+ Рис. 3.2 Таблично-управляемый предсказывающий анализатор имеет входной буфер, таблицу анализа и выход. Входной буфер содержит распознаваемую строку, за которой следует $ - правый концевой маркер, признак конца строки. Магазин содержит последовательность символов грамматики с $ на дне. Вначале магазин содержит начальный символ грамматики на верхушке и $ на дне. Таблица анализа - это двумерный массив M[A,a], где A - нетерминал, и a - терминал или символ $. Анализатор управляется программой, которая работает следующим образом. Она рассматривает X - символ на верхушке магазина и a - текущий входной символ. Эти два символа определяют действие анализатора. Имеются три возможности. 1. Если X=a=$, анализатор останавливается и сообщает об успешном окончании разбора. 2. Если X=a#$, анализатор удаляет X из магазина и продвигает указатель входа на следующий входной символ. 3. Если X - нетерминал, программа заглядывает в таблицу M[X,a]. По этому входу хранится либо правило для X, либо ошибка. Если, например, M[X,a]={X->UVW}, анализатор заменяет X на верхушке магазина на WVU {на верхушке U}. Будем считать, что анализатор в качестве выхода просто печатает использованные правила вывода. Если M[X,a]=error, анализатор обращается к подпрограмме анализа ошибок. Поведение анализатора может быть описано в терминах конфигураций автомата разбора. Алгоритм 3.1. Нерекурсивный предсказывающий анализ. repeat X:=верхний символ магазина; if X - терминал или $ then if X=InSym then удалить X из магазина; InSym:=очередной символ; else error() end else /*X = нетерминал*/ if M[X,InSym]=X->Y1Y2...Yk then удалить X из магазина; поместить Yk,Yk-1,...Y1 в магазин (Y1 на верхушку); вывести правило X->Y1Y2...Yk else error() /*вход таблицы M пуст*/ end end until X=$ /*магазин пуст*/ Рис. 3.3 Вначале анализатор находится в конфигурации, в которой магазин содержит S$, (S - начальный символ грамматики), во входном буфере w$ (w - входная цепочка), переменная InSym содержит первый символ входной строки. Программа, использующая таблицу анализатора M для осуществления разбора, изображена на рис. 3.3. Пример 3.1. Рассмотрим грамматику арифметических выражений: E -> T E' E' -> + T E' | e T -> F T' (*) T' -> * F T' | e F -> ( E ) | id Таблица предсказывающего анализатора для нее изображена на рис. 3.4. Здесь пустые клетки - входы ошибок. Непустые дают правила, по которым делается развертка нетерминала. --------------------------------------------------- Нетер-| Входной символ |-------------------------------------------- минал | id | + | * | ( | ) | $ ------+------+--------+--------+------+-----+------ E |E->TE'| | |E->TE'| | E' | |E'->+TE'| | |E'->e|E'->e T |T->FT'| | |T->FT'| | T' | |T'->e |T'->*FT'| |T'->e|T'->e F |F->id | | |F->(E)| | ----------------------------------------------------- Рис. 3.4 ---------------------------------- Магазин | Вход | Выход --------+-----------+------------- $E | id+id*id$ | $E'T | id+id*id$ | E->TE' $E'T'F | id+id*id$ | T->FT' $E'T'id | id+id*id$ | F->id $E'T' | +id*id$ | E $E' | +id*id$ | T'->e / \ $E'T+ | +id*id$ | E'->+TE' / \ $E'T | id*id$ | T E' $E'T'F | id*id$ | T->FT' /| / | \ $E'T'id | id*id$ | F->id F T' + T E' $E'T' | *id$ | | / | $E'T'F* | *id$ | T'->*FT' id / | $E'T'F | id$ | F T' $E'T'id | id$ | F->id | /|\ $E'T' | $ | id * F T' $E' | $ | T'->e | $ | $ | E'->e id ---------------------------------- Рис. 3.5 Рис. 3.6 На входе id+id*id предсказывающий анализатор совершает последовательность шагов, изображенную на рис. 3.5. Указатель входа указывает на самый левый символ в колонке Вход. Если внимательно проанализировать действия анализатора, то видно, что он осуществляет левый вывод, т.е. правила применяются в соответствии с левым выводом. За уже просмотренными входными символами следуют символы грамматики в магазине (сверху вниз), что соответствует левым сентенциальным формам вывода. Дерево разбора приведено на рис. 3.6. 3.2.2. Множества FIRST и FOLLOW. При построении предсказывающего анализатора полезными оказываются две функции, связанные с грамматикой G. Эти функции, FIRST и FOLLOW, позволяют построить таблицу предсказывающего разбора для G, если, конечно, это возможно. Множества, даваемые этими функциями, могут, кроме того, быть использованы при восстановлении после ошибок. Если u - любая строка символов грамматики, положим FIRST(u) - множество терминалов, с которых начинаются строки, выводимые из u. Если u=>*e, то e также принадлежит FIRST(u). Определим FOLLOW(A) для нетерминала A как множество терминалов a, которые могут появиться непосредственно справа от A в некоторой сентенциальной форме, т.е. множество терминалов a таких, что существует вывод вида S=>*uAav для некоторых u и v. Отметим, что между A и a в процессе вывода могут появиться нетерминальные символы, из которых выводится e. Если A может быть самым правым символом некоторой сентенциальной формы, то $ принадлежит FOLLOW(A). Для построения FIRST(X) для всех символов грамматики X применим следующий алгоритм. Алгоритм 3.2. Построение множеств FIRST для символов грамматики. Шаг 1. Если X - терминал, то FIRST(X) - это {X}; если X - нетерминал, полагаем FIRST(X)={}. Шаг 2. Если имеется правило вывода X->e, то добавить e к FIRST(X). Шаг 3. Пока ни к какому множеству FIRST(X) нельзя уже будет добавить новые элементы или e: если X - нетерминал и имеется правило вывода X- >Y1Y2...Yk, то включить a в FIRST(X), если для некоторого i a<-FIRST(Yi) и e принадлежит всем FIRST(Y1),...,FIRST(Yi-1), т.е. Y1...Yi-1=>*e. Если e принадлежит FIRST(Yj) для всех j=1,2,...,k, то добавить e к FIRST(X). Например, все, что принадлежит FIRST(Y1) принадлежит также и FIRST(X). Если из Y1 не выводится e, то ничего больше не добавляем к FIRST(X), но если Y1=>*e, то добавляем FIRST(Y2), и т.д. Теперь FIRST для любой строки X1X2...Xn можно вычислить следующим образом. Шаг 1. Полагаем FIRST(X1X2...Xn)={}. Шаг 2. Добавим к FIRST(X1X2...Xn) все не e символы из FIRST(X1). Добавим также не e символы из FIRST(X2), если e<-FIRST(X1),не e символы из FIRST(X3), если e принадлежит как FIRST(X1), так и FIRST(X2), и т.д. Наконец, добавим e к FIRST(X1X2...Xn), если e<-FIRST(Xi) для всех i. Для вычисления FOLLOW(A) для нетерминала A применим алгоритм 3.3. Алгоритм 3.3. Построение FOLLOW(X) для всех X - нетерминалов грамматики. Шаг 1. Положить FOLLOW(X)={}. Шаг 2. Поместить $ в FOLLOW(S), где S - начальный символ и $ - правый концевой маркер. Шаг 3. Если eсть правило вывода A->uBv, то все из FIRST(v), за исключением e, добавить к FOLLOW(B). Шаг 4. Пока ничего нельзя будет добавить ни к какому множеству FOLLOW(X): eсли есть правило вывода A->uB или A->uBv, где FIRST(v) содержит e (т.е. v=>*e), то все из FOLLOW(A) добавить к FOLLOW(B). Пример 3.2. Рaссмотрим снова грамматику (*). Для нее FIRST(E) =FIRST(T)=FIRST(F)={(,id} FIRST(E')={+,e} FIRST(T')={*,e} FOLLOW(E)=FOLLOW(E')={),$} FOLLOW(T)=FOLLOW(T')={+,),$} FOLLOW(F)={+,*,),$} Например, id и левая скобка добавляются к FIRST(F) на шаге 3 при i=1, поскольку FIRST(id)={id} и FIRST('(')={'('} в соответствии с шагом 1. На шаге 3 при i=1, в соответствии с правилом вывода T->FT' к FIRST(T) добавляются также id и левая скобка. На шаге 2 в FIRST(E') включается e. На шаге 1 для вычисления множеств FOLLOW в FOLLOW(E) включаем $. На шаге 2, используя правило вывода F->(E), к FOLLOW(E) добавляется также правая скобка. На шаге 3, примененном к правилу E->TE', в FOLLOW(E') включаются $ и правая скобка. Поскольку E'=>*e, они также попадают в FOLLOW(T). В соответствии с правилом вывода E->TE', на шаге 2 в FOLLOW(T) включается все из FIRST(E'), отличное от e. 3.2.3. Конструирование таблиц предсказывающего анализатора Для конструирования таблиц предсказывающего анализатора по грамматике G может быть использован алгоритм, основанный на следующей идее. Предположим, что A->u - правило вывода грамматики и a<-FIRTS(u). Тогда анализатор делает развертку A по u, если входным символом является a. Трудность возникает, когда u=e или u=>*e. В этом случае нужно развернуть A в u, если текущий входной символ принадлежит FOLLOW(A) или если достигнут $ и $<-FOLLOW(A). Алгоритм 3.4. Построение таблиц предсказывающего анализатора. Для каждого правила вывода A->u грамматики выполнить шаги 1 и 2 Шаг 1. Для каждого терминала a из FIRST(u) добавить A->u к M[A,a]. Шаг 2. Если e<-FIRST(u), добавить A->u к M[A,b] для каждого терминала b из FOLLOW(A). Если e<-FIRST(u) и $<- FOLLOW(A), добавить A->u к M[A,$]. Шаг 3. Положить все неопределенные входы равными error. Пример 3.3. Применим алгоритм 3.4 к грамматике (*). Поскольку FIRST(TE')=FIRST(T)={(,id}, в соответствии с правилом вывода E->TE' входы M[E,(] и M[E,id] становятся равными E->TE'. В соответствии с правилом вывода E'->+TE' вход M[E',+] равен E'->+TE'. В соответствии с правилом вывода E'->e входы M[E',)] и M[E',$] равны E'->e, поскольку FOLLOW(E')={),$}. Таблица анализа, построенная алгоритмом 3.4, приведена на рис. 3.4. 3.2.4. LL(1)-грамматики Алгоритм 3.4 для построения таблицы анализа M может быть применен к любой грамматике. Однако для некоторых грамматик M может иметь неоднозначно определенные входы. Например, если грамматика леворекурсивна или неоднозначна, M будет иметь по крайней мере один неоднозначно определенный вход. Грамматики, для которых таблицы анализа не имеют неоднозначно определенных входов, называются LL(1). Первое L означает сканирование входа слева-направо, второе L означает, что строится левый вывод, 1 - что на каждом шаге для принятия решения используется один символ непросмотренной цепочки. Можно показать, что алгоритм 3.4 для каждой LL(1)-грамматики G строит таблицы, по которым распознаются все цепочки из L(G) и только они. LL(1)-грамматики имеют несколько отличительных свойств. Неоднозначная или леворекурсивная грамматика не может быть LL(1). Можно также показать, что грамматика G является LL(1) тогда и только тогда, когда для двух правил вида A->u|v выполняется следующее: 1) ни для какого терминала a одновременно из u и v не выводятся строки, начинающиеся с a; 2) только из одной из строк u или v может выводиться пустая строка; 3) если v=>*e, то из u не выводится никакая строка, начинающаяся с терминала из FOLLOW(A). Эквивалентным является следующее определение: КС-грамматика называется LL(1)-грамматикой, если из существования двух левых выводов (1) S =>* w A u => w v u =>* wx, (2) S =>* w A u => w z u =>* wy, для которых FIRST(x)=FIRST(y), вытекает, что v=z. Это означает, что для данной цепочки wAu и первого символа, выводящегося из Au (или $), существует не более одного правила, которое может быть применено к A, чтобы получить вывод какой-нибудь терминальной цепочки, начинающейся с w и продолжающейся этим первым символом. Язык, для которого можно построить LL(1)-грамматику, называют LL(1)-языком. Если таблица анализа имеет неоднозначно определенные входы, то грамматика не является LL(1). Примером может служить следующая грамматика: St -> if Ex then St | if Ex then St else St | Cont Ex -> ... Эта грамматика неоднозначна, что иллюстрируется рис. 3.7. Поскольку грамматика неоднозначна, она не является LL(1). Проблема, порождает ли грамматика LL-язык, алгоритмически неразрешима. St St /|\ /| \ / | \ / | \ / St \ / St ... / / \ \ / / \ \ / / \ \ / / \ \ if E then if E then S else S if E then if E then S else S а) б) Рис. 3.7 3.2.5. Удаление левой рекурсии Основная трудность при использовании предсказывающего анализа - это написание такой грамматики для входного языка, чтобы по ней можно было построить предсказывающий анализатор. Иногда с помощью некоторых простых преобразований не LL(1)-грамматику можно привести к LL(1)-виду. Среди этих преобразований наиболее очевидными являются левая факторизация и удаление левой рекурсии. Здесь необходимо сделать два замечания. Во- первых, не всякая грамматика после этих преобразований становится LL(1) и, во-вторых, после удаления левой рекурсии и левой факторизации получающаяся грамматика может стать трудно понимаемой. Грамматика леворекурсивна, если в ней имеется нетерминал A такой, что существует вывод A=>+Au для некоторой строки u. Леворекурсивные грамматики не могут анализироваться методами сверху-вниз, поэтому необходимо удаление левой рекурсии. Непосредственную левую рекурсию, т.е. рекурсию вида A->Au, можно удалить следующим способом. Сначала группируем A- правила: A -> Au1 | Au2 | ... | Aum | v1 | v2 | .... | vn где никакая из строк vi не начинается с A. Затем заменяем A- правила на A -> v1A' | v2A' | .... | vnA' A'-> u1A' | u2A' | .... | umA' | e Нетерминал A порождает те же строки, что и раньше, но теперь нет левой рекурсии. С помощью этой процедуры удаляются все непосредственные левые рекурсии, но не удаляется левая рекурсия, включающая два или более шагов. Приведенный ниже алгоритм 3.5 позволяет удалить все левые рекурсии из грамматики. Алгоритм 3.5. Удаление левой рекурсии. Шаг 1. Упорядочиваем нетерминалы в произвольном порядке. Шаг 2. for i:=1 to n do for j:=1 to i-1 do пусть Aj->v1 | v2 | ... | vk - все текущие правила для Aj; заменить все правила вида Ai->Aju на правила Ai->v1u | v2u | ... | vkU; end; удалить непосредственную левую рекурсию в правилах для Ai; end После (i-1)-й итерации внешнего цикла на шаге 2 для любого правила вида Ak->Alu, где kk. В результате на следующей итерации (по i) внутренний цикл (по j) последовательно увеличивает нижнюю границу по m в любом правиле Ai->Amu, пока не будет m>=i. Затем, удаляя непосредственную левую рекурсию для Ai-правил, делаем m больше i. Алгоритм 3.5 применим, если грамматика не имеет циклов (выводов вида A=>+A) и e-правил (правил вида A->e). Как циклы, так и e-правила могут быть удалены предварительно. Получающаяся грамматика без левой рекурсии может иметь e- правила. 3.2.6. Левая факторизация Oсновная идея левой факторизации в том, что, когда неясно, какую из двух альтернатив надо использовать для развертки нетерминала A, нужно переделать A-правила так, чтобы отложить решение до тех пор, пока не будет досточно информации, чтобы принять правильное решение. Если A->uv1 | uv2 - два A-правила и входная строка начинается с непустой строки, выводимой из u, мы не знаем, разворачивать ли по uv1 или по uv2. Однако можно отложить решение, развернув A->uA'. Тогда после анализа того, что выводимо из u, можно развернуть A'->v1 или A'->v2. Левофакторизованные правила принимают вид A -> u A' A' -> v1 | v2 Алгоритм 3.6. Левая факторизация грамматики. Для каждого нетерминала A ищем самый длинный префикс u, общий для двух или более его альтернатив. Если u#e, т.е. существует нетривиальный общий префикс, заменяем все A-правила A->uv1 | uv2 | ... | uvn | z, где z - все альтернативы, не начинающиеся с u, на A -> uA' | z A' -> v1 | v2 | ... | vn Здесь A' - новый нетерминал. Повторно применяем это преобразование, пока никакие две альтернативы не будут иметь общего префикса. Пример 3.4. Рассмотрим вновь грамматику условных операторов: St -> if Ex then St | if Ex then St else St | Cont Ex -> ... После левой факторизации грамматика принимает вид St -> if Ex then St St' | Cont St' -> else St | e Ex -> ... К сожалению, грамматика остается неоднозначной, а значит, и не LL(1), что иллюстрируется рис. 3.8. St / | \ / | \ St / St St' / | \ / / \\ / | \ / / \ \ / St St' / / \ St' / / | \ \ / / \ | / / | \ \ if E then if E then S else S if E then if E then S S' else S а) б) Рис. 3.8 3.2.7. Рекурсивный спуск Выше был рассмотрен таблично-управляемый вариант предсказывающего анализа, когда магазин явно использовался в процессе работы анализатора. Можно предложить другой вариант предсказывающего анализатра, когда каждому нетерминалу сопоставляется, вообще говоря, рекурсивная процедура и магазин образуется неявно при вызовах этих процедур. Процедуры рекурсивного спуска могут быть записаны, как это изображено на рис. 3.9. В процедуре N для случая, когда имеется альтернатива N->ui->*e (не может быть более одной альтернативы, из которой выводится e!), приведены два варианта 1.1 и 1.2. В варианте 1.1 делается проверка, принадлежит ли следующий входной символ FOLLOW(N). Если нет - выдается ошибка. Во втором варианте этого не делается, так что анализ ошибки откладывается на процедуру, вызвавшую N. procedure N;{N -> u1 | u2 | ... | uk} begin if InSym<-FIRST(ui) {только одному!} then if parse(ui) then exit(N->ui) else error() end else Вариант 1: если имеется правило N->ui =>* e то Вариант 1.1 : if InSym<-FOLLOW(N) then exit(N->e) else error() end; Вариант 1.2: exit(N->e) Вариант 2: нет правила N->ui =>*e error() end end; procedure parse(u); {из u не выводится e!} begin v:=u; while v#e do {v=Xz} if X-терминал a then if InSym<>a then return(false) end else {X-нетерминал B} B; end; v:=z end; return(true) end; Рис. 3.9 3.2.8. Диаграммы переходов для рекурсивного спуска Как правило, непосредственное программирование рекурсивного спуска из грамматики приводит к большому числу процедур. Число этих процедур можно уменьшить, заменив в некоторых правилах рекурсию циклом. Для этого можно воспользоваться диаграммой переходов грамматики, которая строится следующим образом. Пусть имеется LL(1)-грамматика. Тогда для каждого нетерминала построение диаграммы включает следующие шаги. Шаг 1. Вводим начальное и заключительное состояния. Шаг 2. Для каждого правила вывода A->X1X2...Xn строим путь из начального в конечное состояние с дугами, помеченными X1,...,Xn. Если анализатор, построенный по диаграмме переходов, оказывается в состоянии s и дуга, помеченная терминалом a, ведет в состояние t, то если очередной входной символ равен a, анализатор продвигает вход на одну позицию вправо и переходит в состояние t. Если же дуга помечена нетерминалом A, анализатор входит в начальное состояние для A без продвижения входа. После того как он достигает заключительного состояния для A, он переходит в состояние t, что означает "чтение" A из входа при переходе из состояния s в состояние t. Наконец, если есть дуга из s в t, помеченная e, то анализатор переходит из s в t, не читая входа. Если следовать программе рекурсивного спуска, то переход по e должен всегда выбираться в качестве последней альтернативы. Диаграммы переходов могут быть упрощены подстановкой одной в другую. Рассмотрим, например, диаграммы для арифметических выражений на рис. 3.10. +---+ T +---+ E'+-----+ +---+ + +---+ T +---+ E'+-----+ E:| 0 |-->| 1 |-->|| 2 ||E':| 3 |-->| 4 |-->| 5 |-->|| 6 || +---+ +---+ +-----+ +---+ +---+ +---+ +-----+ | ^ | e | +------------------------+ +---+ T +---+ E'+-----+ +----+ + +----+ T +----+ E'+----+ E:| 7 |-->| 8 |-->|| 9 ||E':| 10 |-->| 11 |-->| 12 |-->||13|| +---+ +---+ +-----+ +----+ +----+ +----+ +----+ | ^ | e | +---------------------------+ 51 +----+ ( +----+ E +----+ ) +------+ F: | 14 |---->| 15 |---->| 16 |---->|| 17 || +----+ +----+ +----+ +------+ | ^ | id | +---------------------------------+ Рис. 3.10 e +---------------------+ +---------+ | | | T | v | v | +---+ + +---+ T +-----+ +---+ + +---+ E': | 3 |----->| 4 |---->|| 5 || => E':| 3 |---->| 4 | +---+ +---+ +-----+ +---+ +---+ |e |e | +-----+ | +-----+ +-------->|| 6 || +----->|| 6 || +-----+ +-----+ +-------+ +---------+ | T | | + | v | v | e +---+ T +---+ + +---+ +---+ T +---+ +-----+ E: | 0 |-->| 3 |-->| 4 | => E: | 0 |---->| 3 |-->|| 6 || +---+ +---+ +---+ +---+ +---+ +-----+ | e +-----+ +--->|| 6 || +-----+ Рис. 3.11 +---------+ +---------+ | + | | * | v | e v | e +---+ T +---+ +-----+ +---+ F +---+ +------+ E: | 0 |---->| 3 |---->|| 6 || T: | 7 |---->| 8 |--->|| 13 || +---+ +---+ +-----+ +---+ +---+ +------+ +----+ ( +----+ E +----+ ) +------+ F: | 14 |---->| 15 |---->| 16 |---->|| 17 || +----+ +----+ +----+ +------+ | ^ | e | +---------------------------------+ Рис. 3.12 На рис 3.11 приведена эквивалентная диаграмма переходов для E'. Можно подставить диаграмму для E' рис.3.11 в диаграмму для E рис. 3.10. Получится диаграмма рис. 3.11 для E. Наконец, видно, что в этой диаграмме нулевая и четвертая вершины эквивалентны и их можно слить. Так же можно поступить с диаграммами для T и T'. В результате получится набор диаграмм рис. 3.12. Такое преобразование эквивалентно описанию грамматики расширенными формулами Бэкуса-Наура, в которых помимо собственно рекурсивных определений допускаются описания повторений. При программировании рекурсивного спуска такая диаграмма для E записывается очевидным образом: procedure E; repeat T; until InSym<>PLUS; 3.2.9. Восстановление после синтаксических ошибок В приведенных программах рекурсивного спуска использовалась процедура реакции на синтаксические ошибки error(). В простейшем случае эта процедура выдает диагностику и завершает работу анализатора. Но можно попытаться некоторым разумным образом продолжить работу. Для разбора сверху вниз можно предложить следующий простой алгоритм. Если в момент обнаружения ошибки на верхушке магазина оказался нетерминальный символ N и для него нет правила, соответствующего входному символу, то сканируем вход до тех пор, пока не встретим символ либо из FIRST(N), либо из FOLLOW(N). В первом случае разворачиваем N по соответствующему правилу, во втором - удаляем N из магазина. Если на верхушке магазина терминальный символ, то можно выкинуть все терминальные символы с верхушки магазина вплоть до первого (сверху) нетерминального символа и продолжать так, как это было описано выше. 3.3. Разбор снизу-вверх типа сдвиг-свертка 3.3.1. Основа В процессе разбора снизу-вверх типа сдвиг-свертка строится дерево разбора входной строки, начиная с листьев (снизу) к корню (вверх). Этот процесс можно рассматривать как "свертку" строки w к начальному символу грамматики. На каждом шаге свертки подстрока, которую можно сопоставить правой части некоторого правила вывода, заменяется символом левой части этого правила вывода, и если на каждом шаге выбирается правильная подстрока, то в обратном порядке прослеживается правосторонний вывод (рис. 3.13). S S S / | \ X1 X2... / | ............. / | Y Y | /|\ /|\ Z / ... / ... /|\ a.........$ a...........$ a........b.......$ а) б) в) Рис. 3.13 Пример 3.5. Рассмотрим грамматику арифметических выражений, приведенную на рис. 3.14 а). Строка а+b*c может быть сведена к S, как показано на рис. 3.14.б). Дерево этой строки приведено на рис. 3.14 в). В строке a+b*c ищется подстрока, которую можно сопоставить с правой частью некоторого правила вывода. Этому удовлетворяют подстроки a, b и c. Если выбрать самое левое a и заменить его на F - левую часть правила F->id, то получим строку F+b*c. Теперь правой части того же правила можно сопоставить подстроки b и c. Эти свертки представляют собой в обратном порядке правосторонний вывод: E->E+T->E+T*F->E+T*c->E+F*c->E+b*c->T+b*c->F+b*c->a+b*c --- --- - - - - - - E -> E + T а+b*c E E -> T F+b*c /+\ T -> T*F T+b*c E T T -> F E+b*c | |\ F -> id E+F*c T T F E+T*c | | \ E+T*F F F id E+T | | c E a b а) б) в) Рис. 3.14 Подстрока сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода, свертка по которому к левой части правила соответствует одному шагу в обращении правостороннего вывода, называется основой строки. В приведенном выше выводе основы подчеркнуты. Самая левая подстрока, которая сопоставляется правой части некоторого правила вывода A->v, не обязательно является основой, поскольку свертка по правилу A->v может дать строку, которая не может быть сведена к аксиоме. Если, скажем, в примере 3.5 заменить a на F и b на F, то получим строку F+F*c, которая не может быть сведена к S. Формально, основа правой сентенциальной формы z - это правило вывода A->v и позиция в z, в которой может быть найдена строка v такие, что в результате замены v на A получается предыдущая сентенциальная форма в правостороннем выводе z. Таким образом, если S=>*uAw=>uvw, то A->v в позиции, следующей за u, это основа строки uvw. Строка w справа от основы содержит только терминальные символы. Вообще говоря, грамматика может быть неоднозначной, поэтому не единственным может быть правосторонний вывод uvw и не единственной может быть основа. Если грамматика однозначна, то каждая правая сентенциальная форма грамматики имеет в точности одну основу. Замена основы в сентенциальной форме на нетерминал левой части называется отсечением основы. Обращение правостороннего вывода может быть получено с помощью повторного применения отсечения основы, начиная с разбираемой строки w. Если w - слово в рассматриваемой грамматике, то w=Zn, n-я правая сентенциальная форма еще неизвестного правого вывода S = Z0 => Z1 => Z2 => ... => Zn-1 => Zn =w. Чтобы восстановить этот вывод в обратном порядке, выделяем основу Vn в Zn и заменяем Vn на левую часть некоторого правила вывода An -> Vn, получая (n-1)-ю правую сентенциальную форму Zn-1. Затем повторяем этот процесс, т.е. выделяем основу Vn-1 в Zn-1 и сворачиваем эту основу, получая правую сентенциальную форму Zn-2. Если, повторяя этот процесс, мы получаем правую сентенциальную форму, состоящую только из начального символа S, то останавливаемся и сообщаем об успешном завершении разбора. Обращение последовательности правил, использованных в свертках, есть правый вывод входной строки. Таким образом, главная задача анализатора типа сдвиг-свертка - это выделение и отсечение основы. 3.3.2. LR(k)-анализаторы В названии LR(k) символ L означает, что разбор осуществляется слева-направо, R - что строится правый вывод в обратном порядке, k - число входных символов, на которые заглядывает вперед анализатор при разборе. Когда k опущено, имеют в виду 1. LR-анализ привлекателен по нескольким причинам: - LR-анализ - наиболее мощный метод анализа без возвратов типа сдвиг-свертка; - LR-анализ может быть реализован довольно эффективно; - практически LR-анализаторы могут быть построены для всех конструкций языков программирования; - класс грамматик, которые могут быть проанализированы LR- методом, строго включает класс грамматик, которые могут быть анализированы предсказывающими анализаторами (сверху вниз типа LL). +------------------------------+ Вход | A1 | ... | Ai | ... | An | $ | +------------------------------+ ^ | +------+ +-------------+ Выход Магазин | Sm |<---------| LR |--------> |------| | анализатор | | Xm | +-------------+ |------| | | Sm-1 | | |------| +--------+ | Xm-1 | | | |------| v v | .... | +---------------+ |------| | action | goto | | S0 | +---------------+ +------+ Рис. 3.15 Схематически структура LR-анализатора изображена на рис. 3.15. Он состоит из входа, выхода, магазина, управляющей программы и таблицы анализа, которая имеет две части - действий и переходов. Управляющая программа одна и та же для всех анализаторов, разные анализаторы различаются таблицами анализа. Программа анализатора читает символы из входного буфера по одному за шаг. В процессе анализа используется магазин, в котором хранятся строки вида S0X1S1X2S2...XmSm (Sm - верхушка магазина). Каждый Xi - символ грамматики (терминальный или нетерминальный), а Si - символ, называемый состоянием. Каждый символ состояния выражает информацию, содержащуюся в магазине ниже него, а комбинация символа состояния на верхушке магазина и текущего входного символа используется для индексации таблицы анализа и определяет решение о сдвиге или свертке. В реализации символы грамматики не обязательно должны размещаться в магазине. Однако их использование удобно для упрощения понимания поведения LR- анализатора. Таблица анализа состоит из двух частей: действия (action) и переходов (goto). Начальное состояние этого ДКА - это состояние, помещенное на верхушку магазина LR-анализатора в начале работы. Конфигурация-LR анализатора - это пара, первая компонента которой - содержимое магазина, а вторая - непросмотренный вход: (S0 X1 S1 X2 S2 ... Xm Sm, Ai Ai+1 ... An $) Эта конфигурация соответствует правой сентенциальной форме X1 X2 ... Xm Ai Ai+1 ... An Префиксы правых сентенциальных форм, которые могут появиться в магазине анализатора, называются активными префиксами. Активный префикс - это такой префикс правой сентенциальной формы, который не переходит правую границу основы этой формы. Очередной шаг анализатора определяется текущим входным символом Ai и символом состояния на верхушке магазина Sm. Элемент таблицы действий action[Sm,Ai] для состояния Sm и входа Ai, может иметь одно их четырех значений: 1) shift S, сдвиг, где S - состояние, 2) reduce A->w, свертка по правилу грамматики A -> w, 3) accept, допуск, 4) error, ошибка. Конфигурации, получающиеся после каждого из четырех типов шагов, следующие 1. Если action[Sm,Ai]=shift S, то анализатор выполняет шаг сдвига, переходя в конфигурацию (S0 X1 S1 X2 S2 ... Xm Sm Ai S, Ai+1 ... An $) В магазин помещаются как входной символ Ai, так и следующее состояние S, определяемое action[Sm,Ai]. Текущим входным символом становится Ai+1. 2. Если action[Sm,Ai]=reduce A->w, то анализатор выполняет свертку, переходя в конфигурацию (S0 X1 S1 X2 S2 ... Xm-r Sm-r A S, Ai Ai+1 ... An $) где S=goto[Sm-r,A] и r - длина w, правой части правила вывода. Функция goto таблицы анализа, построенная по грамматике G, - это функция переходов детерминированного конечного автомата, распознающего активные префиксы G. Анализатор сначала удаляет из магазина 2r символов (r символов состояния и r символов грамматики), так что на верхушке оказывается состояние Sm-r. Затем анализатор помещает в магазин как A - левую часть правила вывода, так и S - содержимое таблицы goto[Sm-r,A]. На шаге свертки текущий входной символ не меняется. Для LR- анализаторов Xm-r+1 ... Xm - последовательность символов грамматики, удаляемых из магазина, всегда соответствует w - правой части правила вывода, по которому делается свертка. После осуществления шага свертки генерируется выход LR- анализатора, т.е. исполняются семантические действия, связанные с правилом, по которому делается свертка, например печатаются номера правил, по которым делается свертка. 3. Если action[Sm,Ai]=accept, то разбор завершен. 4. Если action[Sm,Ai]=error, анализатор обнаружил ошибку, то выполняются действия по диагностике и восстановлению. Ниже приведен алгоритм LR-анализа. Все LR-анализаторы ведут себя одинаково. Разница между ними заключается в различном содержании таблиц действий и переходов. Алгоритм 3.7. Алгоритм LR-анализа. loop Пусть S - состояние на верхушке магазина; if action[S,InSym]=shift S' then поместить InSym и затем S' на верхушку магазина; прочитать в InSym следующий входной символ else if action[S,InSym]=reduce N->w then удалить из магазина 2*|w| символов; пусть теперь на верхушке магазина состояние S'; поместить на верхушку магазина N, а затем состояние goto[S',InSym]; вывести правило N->w else if action[S,InSym]=accept then return else error() end end end end; Вначале в магазине помещено начальное состояние S0, а в буфере w$, InSym содержит первый символ w$; Анализатор выполняет приведенную ниже программу до тех пор, пока будет достигнуто либо состояние accept, либо состояние error. +--------------------------------------+ |Состо-| action | goto | | яния |------------------+------------| | | id + * $ | E T F | |------+------------------+------------| | 0 | S6 | 1 2 3 | | 1 | S4 acc | | | 2 | R2 S7 R2 | | | 3 | R4 R4 R4 | | | 4 | S6 | 5 3 | | 5 | R1 S7 R1 | | | 6 | R5 R5 R5 | | | 7 | S6 | 8 | | 8 | R3 R3 R3 | | +--------------------------------------+ Рис. 3.16 Пример 3.6. На рис. 3.16 изображены функции action и goto LR- таблиц для грамматики арифметических выражений с бинарными операциями + и * примера 3.5. Здесь Si означает сдвиг и помещение в магазин состояния i, Rj - свертку по правилу номер j, acc - допуск, пустая клетка - ошибку. Значение goto[S,A] для терминала A ищется в поле действия, связанном с действием сдвига по входу A в состоянии S. Поле перехода дает goto[S,A] для нетерминалов A. На входе id+id*id последовательность состояний магазина и входа показаны на рис. 3.17. Например, в первой строке LR- анализатор находится в нулевом состоянии и читает первый входной символ id. Действие S6 в нулевой строке и столбце id в поле action рис. 3.17 означает сдвиг и помещение S6 на верхушку магазина. Это и изображено во второй строке: первый символ id и символ состояния S6 помещаются в магазин и id удаляется из входной строки. Текущим входным символом становится +, и действием в состоянии 6 на вход + является свертка по F->id. Из магазина удаляются два символа (один символ состояния и один символ грамматики). Теперь анализируется нулевое состояние Поскольку goto в нулевом состоянии по символу F - это 3, F и 3 помещаются в магазин. Теперь имеем конфигурацию, соответствующую третьей строке. Остальные шаги определяются аналогично. +---------------------------------------------------------+ |Активный| Магазин | Вход | Действие| |префикс | | | | |--------+-----------------------+--------------+---------| | |0 |id + id * id $| сдвиг | | id |0 id 6 | + id * id $| F -> id | | F |0 F 3 | + id * id $| T -> F | | T |0 T 2 | + id * id $| E -> T | | E |0 E 1 | + id * id $| сдвиг | | E+ |0 E 1 + 4 | id * id $| сдвиг | | E+id |0 E 1 + 4 id 6 | * id $| F -> id | | E+F |0 E 1 + 4 F 3 | * id $| T -> F | | E+T |0 E 1 + 4 T 5 | id $| сдвиг | | E+T* |0 E 1 + 4 T 5 * 7 | id $| сдвиг | | E+T*id |0 E 1 + 4 T 5 * 7 id 6 | $| F -> id | | E+T*F |0 E 1 + 4 T 5 * 7 F 8 | $| T -> T*F| | E+T |0 E 1 + 4 T 5 | $| E -> E+T| | E |0 E 1 | | допуск | +---------------------------------------------------------+ Рис. 3.17 3.3.3. LR-грамматики Грамматики, для которых можно построить таблицу LR-разбора, называются LR-грамматиками. Есть КС-грамматики, не являющиеся LR-грамматиками, однако практически для описания языков программирования достаточно класса LR. Чтобы грамматика была LR, анализатор, работающий слева- направо по типу сдвиг-свертка, должен уметь распознавать основы на верхушке магазина. Но если возможно распознать основу, зная только символы грамматики в магазине, то существует конечный автомат, который может, читая символы грамматики в магазине, начиная с верхушки, определить эту основу. Функцией переходов этого конечного автомата является таблица переходов LR-анализатора. Чтобы не просматривать магазин на каждом шаге анализа, на верхушке магазина всегда хранится то состояние, в котором должен оказаться этот конечный автомат после того, как он прочитал символы грамматики в магазине от дна к верхушке. Для принятия решения о сдвиге или свертке анализатор просматривает очередные k входных символов. Практический интерес представляют случаи k=0 и k=1. Например, в таблице действий рис. 3.16 используется один символ. Грамматика, которая может быть проанализирована LR анализатором, заглядывая на k входных символов на каждом шаге, называется LR(k)-грамматикой. Можно дать другое определение LR(k)-грамматики. Пополненной грамматикой для данной грамматики G называется КС-грамматика, в которой введена новая аксиома S' и правило вывода S'->S. Это дополнительное правило вводится для того, чтобы определить, когда анализатор должет остановить разбор и зафиксировать допуск входа. Таким образом допуск имеет место тогда и только тогда, когда анализатор осуществляет свертку по правилу S'->S. Пополненная грамматика называется LR(k) для k>=0, если из условий (1) S' =>* uAw => uvw, (2) S' =>* zBx => uvy, (3) FIRST(w)=FIRST(y) следует, что uAy=zBx (т.е. u=z, A=B и x=y). Согласно этому определению, если uvw и uvy - правовыводимые цепочки пополненной грамматики, у которых FIRST(w)=FIRST(y) и A->v - последнее правило, использованное в правом выводе цепочки uvw, то правило A->v должно применяться и в правом разборе при свертке uvy к uAy. Так как A дает v независимо от w, то LR(k) условие означает, что в FIRST(w) содержится информация, достаточная для определения того, что uv за один шаг выводится из uA. Поэтому никогда не может возникнуть сомнений относительно того, как свернуть очередную правовыводимую цепочку пополненной грамматики. Кроме того, для LR(k) грамматики известно, когда допускается входная цепочка. Основная разница между LL- и LR-грамматиками заключается в следующем. Чтобы грамматика была LR(k), необходимо распознавать вхождение правой части правила вывода, просмотрев все, что выведено из этой правой части и заглянув на k входных символов вперед. Это требование существенно менее строгое, чем требование для LL(k) грамматики, когда необходимо определить применимое правило, видя только первые k символов, выводимых из его правой части. Класс LL-грамматик является собственным подклассом LR. Рассмотрим теперь конструирование таблиц LR- анализатора. LR(1) ситуацией называется пара [A->u.v,a], где A->uv - правило грамматики, а a - терминал или правый концевой маркер $. "1" указывает на длину второй компоненты ситуации, которая называется аванцепочкой ситуации. Аванцепочка не играет роли в ситуациях вида [A->u.v,a], где v не равно e, но ситуация вида [A->u.,a] ведет к свертке по правилу A->u только если следующим входным символом является a. Таким образом свертка по правилу A->u требуется только для тех входных символов a, для которых [A->u.,a] является LR(1) ситуацией в состоянии на верхушке магазина. Будем говорить, что LR(1)-ситуация [A->u.v,a] допустима для активного префикса z, если существует вывод S=>*yAw=>yuvw, где. z=yu и либо a - первый символ w, либо w равно e и a равно $ (рис. 3.18). S /|\ / | \ / A \ / /\ \ / / \ \ y u v a... ---- ---- z w Рис. 3.18 Будем говорить, что ситуация допустима, если она допустима для какого-либо активного префикса. Пример 3.7. Рассмотрим грамматику S -> BB B -> aB | b Существует правосторонний вывод S=>*aaBab=>aaaBab. Ситуация [B->a.B,a] допустима для активного префикса z=aaa, если в определении выше положить y=aa, A=B, w=ab, u=a, v=B. Существует также правосторонний вывод S*=>BaB=>BaaB. Из этого вывода видно, что для активного префикса Baa допустима ситуация [B->a.B,$]. Центральная идея LR-метода заключается в том, что по грамматике строится детерминированный конечный автомат, распознающий активные префиксы. Для этого ситуации группируются во множества, которые и образуют состояния автомата. Ситуации можно рассматривать как состояния недетерминированного конечного автомата, распознающие активные префиксы, а их группирование на самом деле есть процесс построения детерминированного конечного автомата из недетерминированного. Для конструирования набора множеств допустимых LR(1)- ситуаций будут применяться пополненная грамматика G' и процедуры-функции closure и goto. Рассмотрим ситуацию вида [A->u.Bv,a] из множества ситуаций, допустимых для некоторого активного префикса z. Тогда существует правосторонний вывод S=>*yAax=>yuBvax, где z=yu. Предположим, что из vax выводится терминальная строка bw. Тогда для некоторого правила вывода вида B->q имеется вывод S=>*zBbw=>zqbw. Таким образом [B->.q,b] допустима для z. Здесь либо b может быть первым терминалом, выводимым из v, либо из v выводится e в выводе vax=>*bw и тогда b равно a. Т.е. b принадлежит FIRST(vax). Построение всех таких ситуаций для данного множества ситуаций, т.е. его замыкание, делает процедура closure. Aлгоритм построения множеств LR(1)-ситуаций приведен ниже. Алгоритм 3.8. Конструирование множеств LR(1)-ситуаций. Алгоритм заключается в выполнении главной программы items, которая вызывает процедуры closure и goto. function closure(I);/*I - множество ситуаций*/ begin repeat для каждой ситуации [A->u.Bv,a] из I, каждого правила вывода B->w из G' и каждого терминала b из FIRST(va), такого, что [B->.w,b] нет в I do добавить [B->.w,b] к I; until к I нельзя добавить новых ситуаций; return I; end; В анализаторах типа LR(0) при построении closure не учитываются терминалы из FIRST(va). Если I - множество ситуаций, допустимых для некоторого активного префикса z, то goto(I,X) - множество ситуаций, допустимых для активного префикса zX. function goto(I,X);/*I - множество ситуаций; X - символ грамматики*/ begin Пусть [A->u.Xv,a] принадлежит I; Рассмотрим J - множество ситуаций [A-uX.v,a]; return closure(J) end; Работа алгоритма построения множества LR(1)-ситуаций начинается с того, что берется C - множество ситуаций {closure({[S'->.S,$]})}. Затем из имеющегося множества с помощью операции goto() строятся новые множества ситуаций. По- существу, goto(I,X) - переход конечного автомата из состояния I по символу X. procedure items(G'); begin C:={closure({[S'->.S,$]})}; repeat для каждого множества ситуаций I из C и каждого символа грамматики X такого, что goto(I,X) не пусто и не принадлежит C do добавить goto(I,X) к C until к C нельзя больше добавить множеств ситуаций end; Пример 3.8. Рассмотрим пополненную грамматику примера 3.5. E'-> E 1) E -> E + T 2) E -> T 3) T -> T * F 4) T -> F 5) F -> id Множество ситуаций и переходов для этой грамматики приведены на рис. 3.19. В каждый момент анализа в магазине находится активный префикс, который соответствует последовательности переходов из начального состояния (I0) в текущее. Свертка - это замена суффикса префикса и переход в новое состояние, т.е. как бы возврат по части пути, соответствующей основе, и замена этой части переходом, соответствующим левой части. Рассмотрим теперь, как по множеству LR(1)-ситуаций строятся функции действия и переходов LR(1)-анализатора. Функции действия и переходов представляются таблицей. +-------------+ E +-------------+ + +-------------+ | I0 |--->| I1 |--->| I4 | | E'-> .E, $ | | E'-> E., $ | | E -> E+.T,$ | | E -> .E+T,$ | | E -> E.+T,$ | | E -> E+.T,+ | | E -> .T, $ | | E -> E.+T,+ | | T -> .T*F,$ | | T -> .T*F,$ | +-------------+ | T -> .F, $ | | T -> .F, $ | T +-------------+ | T -> .T*F,+ | | F -> .id, $ |--->| I2 | | T -> .F, + | | E -> .E+T,+ | | E -> T., $ | | F -> .id, $ | | E -> .T, + | | T -> T.*F,$ | | F -> .id, + | | T -> .T*F,+ | | E -> T., + | | T -> .T*F,* | | T -> .F, + | | T -> T.*F,+ | | T -> .F, * | | T -> .T*F,* | | T -> T.*F,* | | F -> .id, * | | T -> .F, * | +-------------+ +-------------+ | F -> .id, * | | F| | | | F -> .id, + |-------+---+ +-------------+ | | +-------------+ | F | | T | | id | +-------------+ | | | +------+ +-+ | * | | | | | v v v v | | +-------------+ +-----------+ +-------------+ | | | I7 | | I3 | | I5 | | | | T -> T*.F,$ | | T -> F.,$ | | E -> E+T.,$ | | | | T -> T*.F,+ | | T -> F.,+ | | E -> E+T.,+ | | | | T -> T*.F,* | | T -> F.,* | | T -> T.*F,$ | | | | F -> .id, $ | +-----------+ * | T -> T.*F,+ | | | | F -> .id, + |<----------------------| T -> T.*F,* | | | | F -> .id,* | id +-------------+ | | +-------------+ +----+ | | F | id | | id | +---------------------------------+ | +------+----------------------------------+ | | | | | | v v v v +-------------+ F +------------+ | I8 | | I6 | | T -> T*F.,$ | | F -> id.,+ | | T -> T*F.,+ | | F -> id.,* | | T -> T*F.,* | | F -> id.,$ | +-------------+ +------------+ Рис. 3.19 Алгоритм 3.9. Построение канонических таблиц LR анализатора. Шаг1. Строим набор множеств LR(1)- ситуаций C={I0,I1,...,In} для G'. Шаг 2. Состояние i анализатора строится из Ii. Действия анализатора для состояния i определяются следующим образом: а) если [A->u.av,b] принадлежит Ii и goto(Ii,a)=Ij, то полагаем action[i,a]="shift j". Здесь a - терминал; б) если [A->u.,a] принадлежит Ii, A#S', то полагаем action[i,a]="reduce A->u"; в) если [S'->S.,$] принадлежит Ii, полагаем action[i,$]="accept". Шаг 3. Переходы для состояния i определяются следующим образом: если goto(Ii,A)=Ij, то goto[i,A]=j (здесь A - нетерминал). Шаг 4. Все входы, не определенные шагами 2 и 3, полагаем равными "error". Шаг 5. Начальное состояние анализатора строится из множества, содержащего ситуацию [S'->.S,$]. Если при применении этих правил возникает конфликт, т.е. в одном и том же множестве может быть более одного варианта действий (либо сдвиг/свертка, либо свертка/свертка), говорят, что грамматика не является LR(1), и алгоритм завершается неуспешно. Таблица, получающаяся из функций анализатора action и goto в результате работы Алгоритма 3.10, называется канонической таблицей LR(1)-анализатора. LR-анализатор, работающий по этой таблице, называется каноническим LR-анализатором. Если функция анализатора action не содержит неоднозначно определенных входов, то грамматика называется LR(1)-грамматикой. 3.3.4. Конфликты разбора типа сдвиг-свертка Если грамматика не является LR(1), то анализатор типа сдвиг- свертка для нее может достигнуть конфигурации, в которой он, зная содержимое магазина и следующий входной символ, не может решить, делать ли сдвиг или свертку (конфликт сдвиг/свертка), или не может решить, какую из нескольких сверток применить (конфликт свертка/свертка). В частности, неоднозначная грамматика не может быть LR. Пример 3.9. Рассмотрим вновь следующую грамматику оператора if-then-else: St -> if Ex then St | if Ex then St else St | ... Если анализатор типа сдвиг-свертка находится в конфигурации Магазин Вход ... if Ex then St else ... $ то нельзя определить, является ли if Ex then St основой, вне зависимости от того, что лежит в магазине ниже. Это конфликт сдвиг/свертка. В зависимости от того, что следует на входе за else, правильной может быть свертка по St -> if Ex then St или сдвиг else, а затем разбор другого St и завершение альтернативы if Ex then St else St. Таким образом нельзя сказать, нужно ли в этом случае делать сдвиг или свертку, так что грамматика не LR(1). Эта грамматика может быть преобразована к LR(1)-виду следующим образом: St -> CondSt | UnCondSt CondSt -> IfThenSt | IfThenElseSt FullSt -> IfThenElseSt | UnCondSt IfThenElseSt -> if Ex then FullSt else St IfThenSt ->if Ex then St 3.3.5. Восстановление после синтаксических ошибок Одним из простейших методов является следующий. При синтаксической ошибке просматриваем магазин от верхушки, пока не найдем состояние s с переходом на выделенный нетерминал A. Затем сканируются входные символы, пока не будет найден такой, который допустим после A. В этом случае на верхушку магазина помещается состояние goto[s,A] и разбор продолжается. Для нетерминала A может иметься несколько таких вариантов. Обычно A - это нетерминал, представляющий одну из основных конструкций языка, например оператор. Тогда s - это, например, точка с запятой или end. При более детальной проработке реакции на ошибки можно в каждой пустой клетке анализатора поставить обращение к своей подпрограмме. Такая подпрограмма может вставлять или удалять входные символы или символы магазина, менять порядок входных символов. Глава 4. Промежуточные представления программы В процессе трансляции программы часто используют промежуточное представление (ПП) программы, предназначенное прежде всего для удобства генерации кода и/или проведения различных оптимизаций программы. Сама форма ПП зависит от целей его использования. Наиболее часто используемыми формами ПП является ориентированный граф (или, в частности, абстрактное синтаксическое дерево), тройки, четверки, префиксная или постфиксная запись, атрибутированное абстрактное дерево. 4.1. Представление в виде ориентированного графа Простейшей формой промежуточного представления является синтаксическое дерево программы. Более полную информацию о входной программе дает ориентированный ациклический граф (ОАГ), в котором в одну вершину объединены вершины синтаксического дерева, представляющие общие подвыражения. Синтаксическое дерево и ОАГ для оператора присваивания a:=b*- c+b*-c приведены на рис. 4.1. На рис. 4.2. приведены два представления в памяти синтаксического дерева на рис. 4.1.а). Каждая вершина кодируется записью с полем для операции и полями для указателей на потомков. На рис. 4.2.б) вершины размещены в массиве записей и индексом (или входом) вершины служит указатель на нее. 4.2. Трехадресный код Трехадресный код- это последовательность операторов вида x:= y op z, где x,y и z - имена, константы или сгенерированные компилятором временные объекты. Здесь op - двуместная операция, например операция плавающей или фиксированной арифметики, логическая или побитовая. В правую часть может входить только один знак операции. := := /\ /\ / \ / \ a + a + / \ / \ / \ | | * * \ / / \ / \ * / \ / \ / \ b - b - / \ | | b - | | | c c | c а) б) Рис. 4.1 66 +------------+ +------------+ 10 | := | | | | | 0 | id | b | | +------+---+-+ |----+---+---| v | 1 | id | c | | +--------+ | |----+---+---| 9 | id | a | | 2 | - | 1 | | +--------+ v |----+---+---| +------------+ 3 | * | 0 | 2 | 7 | + | | | | | |----+---+---| +------+---+-+ 4 | id | b | | +-+ +------------+ |----+---+---| | | 5 | id | c | | v v |----+---+---| +------------+ +------------+ 6 | - | 5 | | 3 | * | | | | 8 | * | | | | | |----+---+---| +----------+-+ +------+---+-+ 7 | + | 3 | 8 | v | v | |----+---+---| +--------+ | +--------+ | 8 | * | 4 | 6 | 0 | id | b | | 4 | id | b | | |----+---+---| +--------+ v +--------+ v 9 | id | a | | +------------+ +------------+ |----+---+---| 2 | - | | | | 6 | - | | | | 10| := | 9 | 7 | +------+-----+ +------+-----+ +------------+ v v +--------+ +--------+ 1 | id | c | 5 | id | c | б) +--------+ +--------+ а) Рис. 4.2 Составные выражения должны быть разбиты на подвыражения, при этом могут появиться временные имена (переменные). Смысл термина "трехадресный код" в том, что каждый оператор обычно имеет три адреса: два для операндов и один для результата. Трехадресный код - это линеаризованное представление синтаксического дерева или ОАГ, в котором явные имена соответствуют внутренним вершинам дерева или графа. Например, выражение x+y*z может быть протранслировано в последовательность операторов t1:=y*z t2:=x+t1 где t1 и t2 - имена, сгенерированные компилятором. В виде трехадресного кода представляются не только двуместные операции, входящие в выражения. В таком же виде представляются операторы управления программы и одноместные операции. В этом случае некоторые из компонент трехадресного кода могут не использоваться. Например, условный оператор if A>B then S1 else S2 может быть представлен следующим кодом: t:=A-B JGT t,S2 ..... Здесь JGT - двуместная операция условного перехода, не вырабатывающая результата. Разбиение арифметических выражений и операторов управления делает трехадресный код удобным при генерации машинного кода и оптимизации. Использование имен промежуточных значений, вычисляемых в программе, позволяет легко переупорядочивать трехадресный код. t1 := -c t1 := -c t2 := b * t1 t2 := b * t1 t3 := -c t5 := t2 + t2 t4 := b * t3 a := t5 t5 := t2 + t1 a := t5 а) б) Рис. 4.3 Представления синтаксического дерева и графа рис. 4.1 в виде трехадресного кода дано на рис. 4.3.а) и 4.3.б), соответственно. Трехадресный код - это абстрактная форма промежуточного кода. В реализации трехадресный код может быть представлен записями с полями для операции и операндов. Рассмотрим три реализации трехадресного кода: четверки, тройки и косвенные тройки. Четверка - это запись с четырьмя полями, которые будем называть op, arg1, arg2 и result. Поле op содержит код операции. В операторах с унарными операциями типа x:=-y или x:=y arg2 не используется. В некоторых операциях (типа "передать параметр") могут не использоваться ни arg2, ни result. Условные и безусловные переходы помещают в result метку перехода. На рис. 4.4 приведены четверки для a:=b*-c+b*- c. Они получены из трехадресного кода рис. 4.3.а. Обычно содержимое полей arg1, arg2 и result - это указатели на входы таблицы символов для имен, представляемых этими полями. Временные имена вносятся в таблицу символов по мере их генерации. Чтобы избежать внесения новых имен в таблицу символов, на временное значение можно ссылаться, используя позицию вычисляющего его оператора. В этом случае трехадресные операторы могут быть представлены записями только с тремя полями: op, arg1 и arg2, как это показано на рис. 4.4.б. Поля arg1 и arg2 - это либо указатели на таблицу символов (для имен, определенных программистом, или констант), либо указатели на тройки (для временных значений). Такой способ представления трехадресного кода называют тройками. Тройки соответствуют представлению синтаксического дерева или ОАГ с помощью массива вершин. Числа в скобках - это указатели на тройки, а имена - это указатели на таблицу символов. На практике информация, необходимая для интерпретации различного типа входов в поля arg1 и arg2, кодируется в поле op или дополнительных полях. Тройки рис. 4.4.б соответствуют четверкам рис. 4.4.а. +----------------------------++------------------------+ | |op |arg1 | arg2 |result|| | op | arg1 | arg2 | |---+----+-----+------+------||-----+----+------+------| |(0)| - | c | | t1 || (0) | - | c | | |(1)| * | b | t1 | t2 || (1) | * | b | (0) | |(2)| - | c | | t3 || (2) | - | c | | |(3)| * | b | t3 | t4 || (3) | * | b | (2) | |(4)| + | t2 | t4 | t5 || (4) | + | (1) | (3) | |(5)| := | t5 | | a || (5) | := | a | (4) | +----------------------------++------------------------+ а) четверки б) тройки Рис. 4.4 Для представления тройками трехместной операции типа x[i]:=y требуется два входа, как это показано на рис. 4.5.а, представление x:=y[i] двумя операциями показано на рис. 4.5.б. +------------------------+ +-------------------------+ | | op | arg1 | arg2 | | | op | arg1 | arg2 | |----+-----+------+------| |-----+-----+------+------| |(0) | []= | x | i | | (0) | =[] | y | i | |(1) | := | (0) | y | | (1) | := | x | (0) | +------------------------+ +-------------------------+ а) x[i]:=y б) x:=y[i] Рис. 4.5 Трехадресный код может быть представлен не списком троек, а списком указателей на них. Такая реализация обычно называется косвенными тройками. Например, тройки рис. 4.4.б могут быть реализованы так, как это изображено на рис. 4.6. +---------------+ +------------------------+ | | оператор | | | op | arg1 | arg2 | |----+----------+ |-----+----+------+------| |(0) | (14) | | |(14) | - | c | | |(1) | (15) | | |(15) | * | b | (14) | |(2) | (16) | | |(16) | - | c | | |(3) | (17) | | |(17) | * | b | (16) | |(4) | (18) | | |(18) | + | (15) | (17) | |(5) | (19) | | |(19) | := | a | (18) | +---------------+ +------------------------+ Рис. 4.6 При генерации объектного кода каждой переменной, как временной, так и определенной в исходной программе, назначается память периода исполнения, адрес которой обычно хранится в таблице генератора кода. При использовании четверок этот адрес легко получить через эту таблицу. Более существенно преимущество четверок проявляется в оптимизирующих компиляторах, когда может возникнуть необходимость перемещать операторы. Если перемещается оператор, вычисляющий x, не требуется изменений в операторе, использующем x. В записи же тройками перемещение оператора, определяющего временное значение, требует изменения всех ссылок на этот оператор в массивах arg1 и arg2. Из-за этого тройки трудно использовать в оптимизирующих компиляторах. В случае применения косвенных троек оператор может быть перемещен переупорядочиванием списка операторов. При этом не надо менять указатели на op, arg1 и arg2. Этим косвенные тройки похожи на четверки. Кроме того, эти два способа требуют примерно одинаковой памяти. Как и в случае простых троек, при использовании косвенных троек выделение памяти для временных значений может быть отложено на этап генерации кода. По сравнению с четверками при использование косвенных троек можно сэкономить память, если одно и то же временное значение используется более одного раза. Например, на рис. 4.6 можно объединить строки (14) и (16), после чего можно объединить строки (15) и (17). 4.3. Линеаризованные представления В качестве промежуточных представлений весьма распространены линеаризованные представления. Линеаризованное представление позволяет относительно легко хранить промежуточное представление на внешней памяти и обрабатывать его в порядке чтения. Самая распространенная форма линеаризованного представления - это запись дерева либо в порядке его обхода снизу-вверх (постфиксная запись, или обратной польской), либо в порядке обхода его сверху-вниз (префиксная запись, или прямой польской). Таким образом, постфиксная запись (обратная польская) - это список вершин дерева, в котором каждая вершина следует непосредственно за своими потомками. Дерево на рис. 4.1 в постфиксной записи может быть представлено следующим образом: a b c - * b c * + := В постфиксной записи вершины синтаксического дерева явно не присутствуют. Они могут быть восстановлены из порядка, в котором следуют вершины и из числа операндов соответствующих операций. Восстановление вершин аналогично вычислению выражения в постфиксной записи с использованием стека. В префиксной записи сначала указывается операция, а затем ее операнды. Например, для приведенного выше выражения имеем := a + * b - c * b - c Рассмотрим детальнее одну из реализаций префиксного представления - Лидер [4]. Лидер - это аббревиатура от 'ЛИнеаризованное ДЕРево'. Это машинно-независимая языково- ориентированная префиксная запись. В этом представлении сохраняются все объявления и каждому из них присваивается свой уникальный номер, который используется для ссылки на объявление. Рассмотрим пример (рис. 4.7). module M; var X,Y,Z: integer; procedure DIF(A,B:integer):integer; var R:integer; begin R:=A-B; return(R); end DIF; begin Z:=DIF(X,Y); end M. Рис. 4.7 Соответствующий образ в Лидере изображен на рис. 4.8. program 'M' var int var int var int procbody proc int int end int var int begin assign var 1 7 end int int mi par 1 5 end par 1 6 end result 0 int var 1 7 end return end begin assign var 0 3 end int icall 0 4 int var 0 1 end int var 0 2 end end end Рис. 4.8 Рассмотрим его более детально: program 'M' Имя модуля используется для редактора связей var int Это образ переменных var X,Y,Z:integer; var int переменным X,Y,Z присваиваются номера var int 1,2,3 на уровне 0 procbody proc Объявление процедуры с двумя int int end целыми параметрами, возвращающей целое. int Процедура получает номер 4 на уровне 0 и параметры имеют номера 5, 6 на уровне 1. var int Локальная переменная R имеет номер 7 на уровне 1 begin Начало тела процедуры assign Оператор присваивания var 1 7 end Левая часть присваивания (R) int Тип присваиваемого значения int mi Целое вычитание par 1 5 end Уменьшаемое (A) par 1 6 end Вычитаемое (B) result 0 Результат процедуры уровня 0 int Результат имеет тип целый var 1 7 end Результат - переменная R return Оператор возврата end Конец тела процедуры begin Начало тела модуля assign Оператор присваивания var 0 3 end Левая часть - переменная Z int Тип присваиваемого значения icall 0 4 Вызов локальной процедуры DIF int var 0 1 end Фактические параметры X и Y int var 0 2 end end Конец вызова end Конец тела модуля 4.4. Организация информации в генераторе кода Чисто синтаксическое дерево несет только информацию о структуре программы. На самом деле в процессе генерации кода требуется также информация о переменных (например, их адреса), процедурах (также адреса, уровни), метках и т.д. Для представления этой информации возможны различные решения. Наиболее распространены два. 1) всю эту информацию можно хранить в таблицах генератора кода; 2) информация хранится в вершинах дерева с соответствующими указателями. Рассмотрим, например, структуру таблиц, которые могут быть использованы в сочетании с Лидер-представлением. Поскольку Лидер-представление не содержит информации об адресах переменных, значит, эту информацию нужно формировать в процессе обработки объявлений и хранить в таблицах. Это касается и описаний массивов, записей и т.д. Кроме того, в таблицах также должна содержаться информация о процедурах (адреса, уровни, модули, в которых процедуры описаны, и т.д.). Таким образом структура таблиц может быть такой, как это изображено на рис. 4.9. Таблица уровней Таблица описаний процедур +-----+ +----------------------------+ | --+--------+ |Для типа:размер | |-----| | |----------------------------| | --+----+ | |Для переменной:указатель на | | ....|.. | | |тип и адрес (смещение) | |-----| | | |----------------------------| | --+--+ | +-->|Для процедуры: адрес, ... | +-----+ | | |----------------------------| | +--> |............................| | | | | |----------------------------| +-------->| | +----------------------------+ Рис. 4.9 При входе в процедуру в таблице уровней процедур заводится новый вход - указатель на таблицу описаний. При выходе указатель восстанавливается на старое значение. Если промежуточное представление - дерево, то информация может храниться в вершинах самого дерева. Например, та же информация может быть представлена, как на рис. 4.10. /\ / \ / \ / \ / \ Раздел описаний / \ / \ \ / \ \ / \ \ Описание Описание Раздел типа переменной операторов +--------+ +--------+ +------+ | |<--+--- |<----------+--- | +--------+ +--------+ +------+ Рис. 4.10 4.5. Уровень промежуточного представления Как видно из приведенных примеров, промежуточное представление программы может в различной степени быть близким либо к исходной программе, либо к машине. Например, промежуточное представление может содержать адреса переменных, и тогда оно уже не может быть перенесено на другую машину. С другой стороны, промежуточное представление может содержать раздел описаний программы, и тогда информацию об адресах можно извлечь из обработки описаний. В то же время ясно, что первое более эффективно, чем второе. Операторы управления в промежуточном представлении могут быть представлены в исходном виде (в виде операторов языка if, for, while и т.д.), а могут содержаться в виде переходов. В первом случае некоторая информация может быть извлечена из самой структуры (например, для оператора for - информация о переменной цикла, которую, может быть, разумно хранить на регистре, для оператора case - информация о таблице меток и т.д.). Во втором случае представление проще и унифицированней. Некоторые формы промежуточного представления лучше годятся для различного рода оптимизаций (например, косвенные тройки - для перемещения кода), некоторые - хуже (например, префиксная запись для этого плохо подходит). Глава 5. Элементы теории перевода 5.1. Преобразователи с магазинной памятью Преобразователем с магазинной памятью (МП-преобразователем) называется восьмерка P=(Q,T,Г,П,Ф,q0,Z0,F), где Q - множество состояний, T - конечный входной алфавит, Г - конечный алфавит магазинных символов, П - конечный выходной алфавит, Ф - отображение множества Qx(T U {e})xГ в множество конечных подмножеств множества QxГ*xП*, q0<-Q - начальное состояние, Z0<-Г - начальный символ магазина, F<-Q - множество заключительных состояний. Определим конфигурацию преобразователя P как четверку (q,x,u,y), где q<-Q - состояние, x<-T* - цепочка на входной ленте, u<-Г* - содержимое магазина, y<-П* - цепочка на выходной ленте, выданная вплоть до настоящего момента. Если Ф(q,a,Z) содержит (r,u,z), то будем писать (q,ax,Zw,y)|- (r,x,uw,yz) для любых x<-A*, w<-Г* и y<-П*. Рефлексивное и транзитивное замыкание отношения |- будем обозначать |-*. Цепочку y назовем выходом для x, если (q0,x,Z0,e)|- *(q,e,u,y) для некоторых q<-F и u<-Г*. Переводом (или преобразованием), определяемым МП-преобразователем P (обозначается t(P)), назовем множество {(x,y)|(q0,x,Z0,e)|- *(q,e,u,y) для некоторых q<-F и u<-Г*}. Будем говорить, что МП-преобразователь P=(Q,T,Г,П,Ф,q0,Z0,F) детерминированный (ДМП-преобразователь), если выполняются следующие условия: 1) для всех q<-Q, a<-T U {e} и Z<-Г множество Ф(q,a,Z) содержит не более одного элемента, 2) если Ф(q,e,Z)#{}, то Ф(q,a,Z)={} для всех a<-T. Пример 5.1. Перевод арифметического выражения в ПОЛИЗ. ПОЛИЗ - Польская инверсная запись или, что то же, постфиксная запись арифметических выражений. Трансляция может определяться следующим ДМП: Q={q0,+,*,),$}; T={буквы,+,*,(,),$}, здесь $ - концевой маркер; Г={Z0,(,+,*}; П={буквы,+,*}; Функция переходов определяется таблицей на рис. 5.1. +------------------------------------------------+ | Г | Q | T || Г* | Q | П | |----+-----+-------||------------+------+------- | | Z0 | q0 | буква || z | q0 | буква | | Z0 | q0 | ( || z( | q0 | | | Z0 | q0 | проч || z | проч | | |----+-----+-------||------------+------+------- | |( | ) | || e | q0 | | |+,* | ) | || e | ) | +,* | |----+-----+-------||------------+------+------- | | + | * | || +* | q0 | | | * | + | || *+ | q0 | | |проч| +,* | || проч {+,*} | q0 | | |----+-----+-------||------------+------+--------| |+,* | $ | || e | $ | +,* | | Z0 | $ | || e | | | +------------------++----------------------------+ Рис. 5.1 76 +--------------------------------+ | Стек |Состояние| Вход |Выход| |------+---------+---------+-----| |Z0 | q0 | a*(b+c)$| a | |Z0 | q0 | *(b+c)$| | |Z0 | * | (b+c)$| | |Z0* | q0 | (b+c)$| | |Z0*( | q0 | b+c)$| | |Z0*( | q0 | +c)$| b | |Z0*( | + | c)$| | |Z0*(+ | q0 | c)$| c | |Z0*(+ | q0 | )$| | |Z0*(+ | ) | $| + | |Z0*( | ) | $| | |Z0* | q0 | $| | |Z0* | $ | | * | |Z0 | $ | | | +--------------------------------+ Рис. 5.2 Последовательность состояний автомата и магазина на строке a*(b+c) изображены в таблице рис. 5.2. 5.2. Синтаксически управляемый перевод Схемой синтаксически управляемого перевода (или трансляции, сокращенно: СУ-схемой) называется пятерка Tr=(N,T,П,R,S), где N - конечное множество нетерминальных символов; T - конечный входной алфавит; П - конечный выходной алфавит; R - конечное множество правил перевода вида A->u, A1=v1, A2=v2, ... , Am=vm, удовлетворяющих следующим условиям: - каждый символ, входящий в v1, ..., vm, либо принадлежит П, либо является Bk для B<-N и B входит в v (здесь k - номер вхождения B в v), - если u имеет более одного вхождения символа B, то каждый символ Bk во всех v соотнесен (верхним индексом) с конкретным вхождением B; S - начальный символ, выделенный нетерминал из N. A->u называют входным правилом вывода, Ai - переводом нетерминала A и Ai=vi - элементом перевода, связанным с этим правилом перевода. Если через P обозначить множество входных правил вывода всех правил перевода, то G=(N,T,P,S) будет входной грамматикой для Tr. Если в СУ-схеме Tr нет двух правил перевода с одинаковым входным правилом вывода, то ее называют семантически однозначной. Выход СУ-схемы определим снизу вверх. С каждой внутренней вершиной n дерева разбора (во входной грамматике), помеченной A, свяжем одну цепочку для каждого Ai. Эта цепочка называется значением (или переводом) символа Ai в вершине n. Каждое значение вычисляется подстановкой значений символов перевода данного элемента перевода Ai=vi, определенных в прямых потомках вершины n. Переводом t(Tr), определяемым СУ-схемой Tr, назовем множество {(x,y)|x имеет дерево разбора во входной грамматике для Tr и y - значение выделенного символа перевода S в корне этого дерева}. Если Tr=(N,T,П,R,S) - СУ-схема, то т(Tr) называется синтаксически управляемым переводом (СУ-переводом). Пример 5.2. Рассмотрим формальное дифференцирование выражений, включающих константы 0 и 1, переменную x и функции sin, cos, + и *. Такие выражения порождает грамматика E -> E+T | T T -> T*F | F F -> (E) | sin(E) | cos(E) | x | 0 | 1 Свяжем с каждым из E, T и F два перевода, обозначенных индексом 1 и 2. Индекс 1 указывает на то, что выражение не дифференцировано, 2 - что выражение продифференцировано. Формальная производная - это E2. Законы дифференцирования таковы: d(f(x)+g(x))=df(x)+dg(x) dx=1 d(f(x)*g(x))=f(x)*dg(x)+g(x)*df(x) d0=0 dsin(f(x))=cos(f(x))*df(x) d1=0 dcos(f(x))=-sin(f(x))df(x) Эти законы реализуются СУ-схемой: E -> E+T E1=E1+T1 F -> cos(E) F1=cos(E1) E2=E2+T2 F2=-sin(E1)*(E2) E -> T E1=T1 F -> x F1=x E2=T2 F2=1 T -> T*F T1=T1*F1 F -> 0 F1=0 T2=T1*F2+T2*F1 F2=0 F -> ( E ) F1=(E1) F -> 1 F1=1 F2=(E2) F2=0 F -> sin(E) F1=sin(E1) F2=cos(E1)*(E2) Дерево вывода для sin(cos(x))+x приведено на рис. 5.3. Теорема 5.1. Если число вхождений каждого нетерминала в слове v не превосходит 1, то t(Tr) является КС-языком. Обратное не всегда верно [5]. Пример 5.2. T=({S,A},{a},{a,b},{S->A,AbAbA;A->a,a;A->aA,aA}. Здесь входной язык {an|n>=1}, выходной {anbanban}. Выходной язык не КС. Теорема 5.2. Для каждого магазинного преобразователя существует эквивалентная СУ-схема [5]. Обратное, вообще говоря, не верно. Определение. Семантически однозначная СУ-схема Tr=(N,T,П,R,S) называется простой, если для каждого правила A->u,v из R соответствующие друг другу вхождения нетерминалов встречаются в u и v в одном и том же порядке. E E1=sin(cos(x))+x / \ E2=cos(cos(x)) E1=sin(cos(x)) / + \ *(-sin(x)*(1))+1 E2=cos(cos(x)) E T *(-sin(x)*(1)) | | T2=1 | | T1=x T1=sin(cos(x)) | | T2=cos(cos(x)) T F F1=x *(-sin(x)*(1)) | | F2=1 | | F1=sin(cos(x)) | | F2=cos(cos(x)) F x *(-sin(x)*(1)) | | sin ( E ) E1=cos(x) | E2=-sin(x)*(1) | T T1=cos(x) | T2=-sin(x)*(1) | F F1=cos(x) | F2=-sin(x)*(1) | cos ( E ) E1=x E2=1 | T T1=x T2=1 | F F1=x F2=1 | x Рис. 5.3 Перевод, определяемый простой СУ-схемой, называется простым синтаксически управляемым переводом (простым СУ-переводом). Теорема 5.3. Пусть Tr=(N,T,П,R,S) - простая СУ-схема. Существует такой МП-преобразователь P, что t(P)=t(Tr) [5]. Таким образом, класс трансляций, определяемых магазинными преобразователями, совпадает с классом простых СУ-переводов. Теорема 5.4. Пусть Tr=(N,T,П,R,S) - семантически однозначная простая СУ-схема, входной грамматикой которой служит LL(k)- грамматика. Тогда перевод {x$,y)|(x,y)<-t(Tr)} можно осуществить детерминированным МП-преобразователем [5]. Существуют семантически однозначные простые СУ-схемы, имеющие в качестве входных грамматик LR(k) грамматики и не реализуемые ни на каком ДМП-преобразователе. Пример 5.3. Рассмотрим простую СУ-схему T с правилами S -> Sa, aSa S -> Sb, bSb S -> e, e Входная грамматика является LR(1) грамматикой, но не существует ДМП-преобразователя, определяющего перевод {(x$,y)|(x,y)<-t(Tr)} [5]. Определение. Назовем СУ-схему Tr=(N,T,П,R,S) постфиксной, если каждое правило из R имеет вид A->u,v, где v<-N*П*. Иными словами, каждый элемент перевода представляет собой цепочку из нетерминалов, за которыми следует цепочка выходных символов. Теорема 5.5. Пусть Tr=(N,T,П,R,S) - семантически однозначная простая постфиксная СУ-схема, входной грамматикой которой служит LR(k)-грамматика. Тогда перевод {(x$,y)|(x,y)<-t(Tr)} можно осуществить детерминированным МП-преобразователем [5]. 5.3. Атрибутные грамматики Среди всех формальных методов описания языков программирования атрибутные грамматики получили, по-видимому, наибольшую известность и распространение. Причиной этого является то, что формализм атрибутных грамматик основывается на дереве разбора программы в КС-грамматике, что сближает его с хорошо разработанной теорией и практикой построения трансляторов. 5.3.1. Определение атрибутных грамматик Пусть G - КС-грамматика: G=(T,N,P,Z), где T, N, P, Z, - соответственно, множество терминальных символов, нетерминальных символов, множество правил вывода и аксиома грамматики. Правила вывода КС-грамматики будем записывать в виде p: X0 -> X1 ... Xn и будем предполагать, что G - редуцированная КС-грамматика, т.е. в ней нет нетерминальных символов, для которых не существует полного дерева вывода , в которое входит этот нетерминал. С каждым символом X <- N U T свяжем множество A(X) атрибутов символа X.Некоторые из множеств A(x) могут быть пусты. Запись a(X) означает, что a <- A(X). С каждым правилом вывода p <- P свяжем множество F семантических правил, имеющих следующую форму: a0
= fpa0 (a1 , ... , aj ), где ik <- [0,np] - номер символа правила p, а ak - атрибут символа Xik , т.е. ak <- A(Xik). В таком случае будем говорить , что a0 "зависит" от a1 ,...,aj или что a0 "вычисляется по" a1 ,...,aj . В частном случае j может быть равно нулю, тогда будем говорить, что атрибут a0 "получает в качестве значения константу". КС-грамматику, каждому символу которой сопоставлено множество атрибутов, а каждому правилу вывода - множество семантических правил, будем называть атрибутной грамматикой (AG). Назовем атрибут a(X0) синтезируемым, если одному из правил вывода p: X0 ->X1 ... Xnp сопоставлено семантическое правило a<0>=fa<0>(...). Назовем атрибут a(Xi) наследуемым, если одному из правил вывода p:X0 -> X1 ... Xi ... Xnp сопоставлено семантическое правило a=fa(...), i <- [1,np]. Множество синтезируемых атрибутов символа X обозначим через S(X), наследуемых атрибутов - через I(X). Будем считать, что значение атрибутов терминальных символов - константы, т.е. их значения определены, но для них нет семантических правил, определеяющих их значения. 5.3.2. Атрибутированное дерево разбора Если дана атрибутная грамматика AG и цепочка, принадлежащая языку, определяемому G, то можно построить дерево разбора этой цепочки в грамматике G. В этом дереве каждая вершина помечена символом грамматики G. Припишем теперь каждой вершине множество атрибутов, сопоставленных символу, которым помечена эта вершина. Атрибуты, сопоставленные вхождениям символов в дерево разбора, будем называть вхождениями атрибутов в дерево разбора, а дерево с сопоставленными каждой вершине атрибутами - атрибутированным деревом разбора. Между вхождениями атрибутов в дерево разбора существуют зависимости, определяемые семантическими правилами, соответствующими примененным синтаксическим правилам. 5.3.3. Язык описания атрибутных грамматик Формализм атрибутных грамматик оказался очень удобным средством для описания семантики языков программирования. Вместе с тем выяснилось, что реализация вычислителей для атрибутных грамматик общего вида сталкивается с большими трудностями. В связи с этим было сделано множество попыток рассматривать те или иные классы атрибутных грамматик, обладающих "хорошими" свойствами. К числу таких свойств относятся прежде всего простота алгоритма проверки атрибутной грамматики на зацикленность и простота алгоритма вычисления атрибутов для атрибутных грамматик данного класса []. Атрибутные грамматики использовались для описания семантики языков программирования и было создано несколько систем автоматизации разработки трансляторов, основанных на формализме атрибутных грамматик. Опыт их использования показал, что "чистый" атрибутный формализм может быть успешно применен для описания семантики языка, но его использование вызывает трудности при создании транслятора. Эти трудности связаны как с самим формализмом, так и с некоторыми технологическими проблемами. К трудностям первого рода можно отнести несоответствие чисто функциональной природы атрибутного вычислителя и связанной с ней неупорядоченностью процесса вычисления атрибутов (что в значительной степени является преимуществом этого формализма) и упорядоченностью элементов программы. Это несоответствие ведет к тому, что приходится идти на искусственные приемы для их сочетания. Технологические трудности связаны с эффективностью трансляторов, генерированных с помощью атрибутных систем. Как правило, качество таких трансляторов довольно низко из-за больших расходов памяти, неэффективности искусственных приемов, о которых было сказано выше. Учитывая это, мы будем вести дальнейшее изложение на языке, сочетающем особенности атрибутного формализма и обычного языка, в котором предполагается возможность управления порядком исполнения операторов. Этот порядок привязывается к обходу атрибутированного дерева разбора сверху вниз слева направо. Все атрибуты должны быть вычислены за один такой обход. Атрибутные грамматики, обладающие таким свойством, называются L-атрибутными. При записи синтаксиса мы будем использовать расширенную БНФ. Элемент правой части синтаксического правила, заключенный в скобки [ ], может отсутствовать. Элемент правой части синтаксического правила, заключенный в скобки ( ), означает возможность повторения один или более раз. Элемент правой части синтаксического правила, заключенный в скобки [()], означает возможность повторения ноль или более раз. В скобках [] или [()] может указываться разделитель конструкций. Ниже дан синтаксис языка описания атрибутных грамматик. Атрибутная грамматика ::= 'ALPHABET' ( ОписаниеНетерминала ) ( Правило ) ОписаниеНетерминала ::= ИмяНетерминала '::' [( ОписаниеАтрибутов / ';')] '.' ОписаниеАтрибутов ::= ( ИмяАтрибута / ',') ':' Тип Правило ::= 'RULE' Синтаксис 'SEMANTICS' Семантика '.' Синтаксис ::= ИмяНетерминала '::=' ПраваяЧасть ПраваяЧасть ::= [( ЭлементовПравойЧасти )] ЭлементПравойЧасти ::= ИмяНетерминала | Терминал | '(' Нетерминал [ '/' Терминал ] ')' | '[' Нетерминал ']' | '[(' Нетерминал [ '/' Терминал ] ')]' Семантика ::= [( ЛокальноеОбъявление ]) [( СемантическоеДействие ]) СемантическоеДействие ::= Присваивание | [ Метка ] Оператор Присваивание ::= Переменная ':=' Выражение Переменная ::= ЛокальнаяПеременная | Атрибут Атрибут ::= ЛокальныйАтрибут | ГлобальныйАтрибут ЛокальныйАтрибут ::= ИмяАтрибута '<' Номер '>' ГлобальныйАтрибут ::= ИмяАтрибута '<' Нетерминал '>' Метка ::= Целое ':' | Целое 'Е' ':' | Целое 'А' ':' Оператор ::= Условный | ОператорПроцедуры | ЦиклПоМножеству | ПростойЦикл | ЦиклСУсловиемОкончания Описание атрибутной грамматики состоит из раздела описания атрибутов и раздела правил. Раздел описания атрибутов определяет состав атрибутов для каждого символа грамматики и тип каждого атрибута. Правила состоят из синтаксической и семантической части. В синтаксической части используется расширенная БНФ. Семантическая часть правила состоит из локальных объявлений и семантических действий. В качестве семантических действий допускаются как атрибутные присваивания, так и составные операторы. Метка в семантической части правила привязывает выполнение оператора к обходу дерева разбора сверху-вниз слева направо. Конструкция "i : оператор" означает, что оператор должен быть выполнен сразу после обхода i-й компоненты правой части. Конструкция "i E : оператор" означает, что оператор должен быть выполнен, только если порождение i-й компоненты правой части пусто. Конструкция "i A : оператор" означает, что оператор должен быть выполнен после разбора каждого повторения i-й компоненты правой части (имеется в виду конструкция повторения). Каждое правило может иметь локальные определения (типов и переменных). В формулах используются как атрибуты символов данного правила (локальные атрибуты) и в этом случае соответствующие символы указываются номерами в правиле (0 для символа левой части, 1 для символа правой части и т.д.), так и атрибуты символов предков левой части правила (глобальные атрибуты). В этом случае соответствующий символ указывается именем нетерминала. Таким образом, на дереве образуются области видимости атрибутов: атрибут символа имеет область видимости, состоящую из правила, в которое символ входит в правую часть, плюс все поддерево, корнем которого является символ, за исключением поддеревьев - потомков того же символа в этом поддереве (рис. 5.4). | ... . N . . / \ . . / \ . . /\ /\ . . / /\ /\ \ . . / -- -- \ . ...N...........N... /\ /\ -- -- Рис. 5.4 Значение терминального символа доступно через атрибут VAL соответствующего типа. Глава 6. Контекстные условия языков программирования 6.1. Описание областей видимости и блочной структуры Задачей контекстного анализа является установление правильности использования объектов. Наиболее часто решаемой задачей является определение существования объекта и соответствия его использования контексту, что осуществляется с помощью анализа типа объекта. Таким образом необходимо хранить объекты, их типы, уметь находить эти объекты и определять их типы, определять характеристики контекста. Совокупность доступных в даной точке объектов будем называть "средой". Обычно среда программы состоит из частично упорядоченного набора компонент E={DS1,...DSn}. Каждая компонента - это множество объявлений, представляющих собой пары <имя,тип>: DSi={<имя,тип>}, где под типом будем подразумевать полное описание свойств объекта (объектом, в частности, может быть само описание типа). Между компонентами DSi и DSj имеет место отношение "DSi включает DSj" тогда и только тогда, когда любой объект из DSi может быть доступен из DSj (конкретный способ доступа определяется правилами видимости языка), но не наоборот. Компоненты образуют дерево. Это дерево соответствует блокам или процедурам (рис. 6.1 +-------------+ | Корневая | | компонента | | (программа) | +-------------+ +---------+ | +--------+ | | | +-----------++-----------++-----------+ | процедура || процедура || процедура | | (блок) || (блок) || (блок) | +-----------++-----------++-----------+ /|\ /|\ /|\ Рис. 6.1 Обычными операциями при работе со средой являются: - включить объект в компоненту среды; - найти объект в среде и получить доступ к его описанию; - образовать в среде новую компоненту, определенным образом связанную с остальными; - удалить компоненту из среды. Компоненты среды могут быть именованы. Поиск в среде обычно ведется с учетом упорядоченности компонент. Среда может включать в себя как компоненты, полученные при трансляции "текущего" текста программы, так и "внешние" компоненты. Для обозначения участков программы, в которых доступны те или иные описания, используются понятия "область действия" и "область видимости". Областью действия описания является процедура (блок), содержащая описание, со всеми входящими в нее (подчиненными по дереву) процедурами (блоками). Областью видимости описания называется часть области действия, из которой исключены те подобласти, в которых по тем или иным причинам описание недоступно. В разных языках понятия области действия и области видимости уточняются по-разному. В дальнейшем изложение ведется на примере языка Модула -2. 6.2. Структура среды Модулы-2 Имеются четыре рода языковых конструкций, которые могут содержать описания: 1) программный модуль или модуль реализации; 2) модуль определения; 3) процедура; 4) локальный модуль. "Корневую" компоненту среды в Модуле-2 образует программный модуль или модуль реализации. Объекты этой компоненты могут быть описаны в самом модуле или могут быть импортированы из других модулей определений. Такой импорт может быть квалифицированным (from M import X,Y, ...;) или не квалифицированным (import M;). Экспортирующий Компонента Импортирующий локальный модуль среды локальный модуль +------------+ +------------+ +------------+ | MODULE M1; | | +----+ | | MODULE X1; | | EXPORT A1;-+--------+-->| A1 |---+--+ | IMPORT A1; | | ......... | | +----+ | | | | +------------+ | | +--+------> A1 | | | +------------+ +--------------+ | | | MODULE M2; | | | +------------+ | EXPORT | | +----+ | | MODULE X2; | | QUALIFIED A2-+------+-->| M2 | | | FROM M2 | | ............ | | +----+ | | IMPORT A2; | +--------------+ | v | +---+---->A2 | | +----+ | | +------------+ | | A2 |---+-+ | +----+ | +-----------------+ | | | MODULE M3; | | +-----+ | | EXPORT M31;-----+---+-->| M31 | | +-------------+ | +-------------+| | +-----+ | | MODULE X3; | | | MODULE M31; || | +-----+ | | IMPORT A31; | | | EXPORT A31;-++---+-->| A31 |--+-----+--> A31 | | | .......... || | +-----+ | | +-------------+ | +-------------+| | | | | ................| | | | +-------------+ +-----------------+ | | | | MODULE X | | | | | IMPORT M31; | | | +--+---> A31 | v v +-------------+ +-------------------+ v v | MODULE M4; | | +-----+ | | EXPORT M41;-------+-+-->| M41 | | +-------------+ | +---------------+| | +-----+ | | MODULE X4; | | | MODULE M41; || | v | | FROM M41 | | | EXPORT || | +-----+ | | IMPORT A41; | | | QUALIFIED A41;|+-+-->| A41 |--+-----+----> A41 | | | .......... || | +-----+ | | +-------------+ | +---------------+| | | | +--------------+ | ..................| | | | | MODULE X | +-------------------+ | | | | IMPORT M41; | | | +--+-->A41 | | | +--------------+ +-----------------+ | +----+ | | MODULE M5; | | | M5 | | +-------------+ | EXPORT | | +----+ | | MODULE X5; | | QUALIFIED M51;--+---+-+ v | | FROM M5 | | +-------------+| | | +-----+ | | IMPORT M51; | | | MODULE M51; || | +->| M51 |-+------+-> M51.A51 | | | EXPORT A51;-++---+-+ +-----+ | +-------------+ | | .......... || | | v | | +-------------+| | | +-----+ | | ................| | +->| A51 | | +-----------------+ | +-----+ | +-------------------+ | +----+ | | MODULE M6; | | | M6 | | +-------------+ | EXPORT | | +----+ | | MODULE X6; | | QULIFIED M61;-----+-+-+ v | | FROM M6 | | +---------------+| | | +-----+ | | IMPORT M61; | | | MODULE M61; || | +->| M61 |-+------+--> M61.A61 | | | EXPORT || | +-----+ | +-------------+ | | QUALIFIED A61;|+-+-+ v | | | ............ || | | +-----+ | | +---------------+| | +->| A61 | | | ..................| | +-----+ | +-------------------+ +------------+ Рис. 6.2 В первом случае импортированные объекты становятся элементами среды данного модуля, во втором - сам импортированный модуль становится элементом среды, а его объекты могут быть доступны через указание имени модуля (M.X). Область действия объектов, описанных в локальном модуле, может состоять из самого этого локального модуля или из охватывающего его блока, если объект экспортируется из локального модуля. Схему импорта в локальный модуль можно пояснить рис. 6.2. Существует предопределенная компонента, объекты которой доступны во всех других компонентах (если они там не переопределены). Эта компонента включает в себя типы данных такие как, integer, real, boolean, char, word, address, proc, константы true, false, nil, процедуры adr, tsize, cap, small, chr, inc, dec, float, halt, hihg, odd, ord, trunc, val, excl, incl, max, min, size, abs. Элементом описания может быть процедура или локальный модуль, имеющие свой список описаний. Процедура образует новую компоненту среды, а локальный модуль - нет (рис. 6.3). Объекты локального модуля являются объектами охватывающей компоненты, но с ограниченными областями видимости. Внутри локального модуля доступны те и только те объекты этой компоненты, которые явно импортированы в локальный модуль. И наоборот: объекты локального модуля могут быть экспортированы в охватывающую компоненту. В то же время объекты процедуры образуют новую компоненту, поскольку объекты этой компоненты могут быть доступны в процедуре. Конфликт имен при этом не противоречит определению компоненты: объект охватывающей компоненты может быть виден (если внутри данной процедуры не описан объект с тем же именем). Модуль (программный или реализации) +------------+ | Среда |<----- Свой модуль определений |------------|<----- Импорт из других | Объявления | модулей определений +------------+ |^ | Импорт || | Видимость +--------+| +-----------+ | +-------+ | v |Экспорт v +------------------+ +-----------+ | Локальный модуль | | Процедура | |------------------| |-----------| | ................ | | ......... | | | | | +------------------+ +-----------+ Рис. 6.3 Среда состоит из отдельных объектов, реализуемых как записи. Состав полей записи вообще говоря зависит от объекта (тип, переменная и т.д.), но есть поля, входящие в запись для любого объекта: Object - категория объекта: тип, переменная, процедура и т.д.; Mode - вид объекта: целый, массив, запись и т.д.; Name - имя объекта; Type - указатель на описание типа. 6.3. Занесение в среду и поиск объектов Поскольку блоки образуют иерархию на дереве разбора программы, при поиске объекта мы можем с помощью атрибута типа "указатель на блок" переходить от блока к охватывающему блоку. Если теперь у каждого блока есть атрибут, указывающий, является ли блок процедурой или модулем, то легко реализовать сочетание блочной структуры со средствами управления видимостью. Кроме того, корень дерева имеет атрибут, соответствующий предопределенной компоненте, так что через этот глобальный атрибут доступны все предопределенные описания (рис. 6.4). Env ^ ^ / \ Env Env ^^ ^^ / \ / \ Env Env Env Env Рис. 6.4 В качестве типов данных атрибутов мы будем использовать множество. Множество может быть упорядоченным или неупорядоченным, ключевым или простым. Элементом ключевого множества может быть запись, одним из полей которой является ключ: SET OF T - простое неупорядоченное множество объектов типа T; KEY K SET OF T - ключевое неупорядоченное множество объектов типа T с ключом K; LIST OF T - простое упорядоченное множество объектов типа T; KEY K LIST OF T - ключевое упорядоченное множество объектов типа T с ключом K; Над объектами типа множества определены следующие операции: Init(S) - создать и проинициализировать переменную S; Include(V,S) - включить объект V в множество S; если множество упорядоченное, то включение осуществляется в качестве последнего элемента; Find(K,S) - выдать указатель на объект с ключом K во множестве S и NIL, если объект с таким ключом не найден. Имеется специальный оператор цикла, пробегающий элементы множества: for V in S do Оператор; Переменная V локализована в теле оператора и пробегает все значения множества. Если множество упорядочено, то элементы пробегаются в этом порядке, если нет - в произвольном порядке. Среда представляет собой ключевое множество с ключом - именем объекта. Каждый локальный модуль имеет атрибут - множество импортируемых объектов и атрибут - множество экспортируемых объектов. Экспортируемые модулем объекты в соответствии с правилами экспорта включаются в компоненту среды, в которую входит сам модуль. Ниже приведен фрагмент описания контекстных условий языка Модула-2 (в фигурные скобки заключены комментарии). ALPHABET Prog:: Env : key Name set of Element. Предопределенная компонента. Идентификаторы имеют тип Name. Block :: Env : key Name set of Element; Kind : boolean; Pred : pointer to Block. Арибут Kind равен true для процедур и false для модулей. Env - множество объявлений блока. Pred - указатель на охватывающий блок. Mod_Head :: Entry : pointer to Element; Imp_Set : set of Import_Pair; Mode:boolean. Imp_Set - множество импортируемых модулем объектов; тип Import_Pair - запись из двух полей: Imp_Name:Name - имя импортируемого объекта, и Name_Set:Set of Name - список импортируемых из модуля объектов, если импорт квалифицированный, и Nil, если неквалифицированный; Entry - указатель на вход для модуля; Mode - признак квалифицированного экспорта. Import :: Imp_Set : set of Name. Imp_Set - список квалифицированного импорта. Export :: Mode:boolean. Mode - признак квалифицированного экспорта. From :: Qual : boolean; Name : NameType. Qual :: Qual : boolean. Ident_List :: Ident_Set : set of Name. Type_Des :: Exit : pointer to Element. Qual - признак квалифицированного импорта; Name - имя модуля, из которого делается импорт; Ident_Set - список идентификаторов; Exit - указатель на описание типа. RULE Declaration ::= 'procedure' Ident [ Formal_Param ] ';' Block ';' SEMANTICS var Entry:pointer to Element; Kind<5>:=true; 2:if Find(Val<2>,Env )<>Nil then Error("Identifire declared twice"); end; Entry:=Include(Val<2>,Env ); Entry@.Object:=ProcObject. Помещение процедуры; ищем объект с данным именем в текущей компоненте; Entry - указатель на вход для процедуры. Если объект с таким именем уже есть, - ошибка. RULE Declaration ::= 'module' Ident Mod_Head Block ';' SEMANTICS var M:Import_Pair; V:Element; if Find(Val<2>,Env )<>Nil then Error("Identifire declared twice") end; Entry<3>:=Include(Val<2>,Env ); Entry<3>@.Object:=LocalModuleObject; Kind<4>:=false; 3: for M in Imp_Set<3> do Inc_Imp(M,Env<4>); end; if (Mode<3>=NotQual) then for V in Entry<3>@.Exp_Set do Export(V,Env ); end end. Помещение модуля; ищем объект с данным именем в текущей компоненте. Если такой уже есть, - ошибка. Заносим в текущую компоненту среды объект-модуль. Множество Imp_Set - это множество импортируемых модулем объектов. Элементы этого множества - пары, первая компонента которых - имя импортируемого модуля, вторая - список импортируемых из него объектов. Если вторая компонента Nil, то импорт неквалифицированный. Если импортируемый объект M - модуль и если M импортируется неквалифицированно (IMPORT M), то процедура Inc_Imp включает M в среду текущего модуля; если импорт квалифицированный (FROM M IMPORT ...), то M имеет список импорта и процедура Inc_Imp включает в текущую компоненту те экспортируемые из M объекты, которые перечислены в списке квалифицированного импорта; если при этом импортируемый объект - в свою очередь модуль, то из M рекурсивно импортируется все его экспортные объекты. Атрибут Mode вычисляется в правиле для экспорта и определяет, осуществляется ли квалифицированный экспорт (EXPORT QUALIFIED ...) или нет (EXPORT ...). Процедура Export в случае неквалифицированного экспорта EXPORT A1,A2,... все объекты экспортного списка модуля заносит в компоненту среды, охватывающую модуль; если Ai - модуль, его экспорт обрабатывается рекурсивно; если экспорт квалифицированный, то в охватывающую модуль компоненту попадает только сам модуль со списком экспорта. RULE Block ::= [( Declaration )] [ Block_St_Seq ] 'end' Ident SEMANTICS 0:Init(Env<0>); Pred<0>:=@ . Атрибут Pred - указатель на охватывающий блок. RULE Mod_Head ::= [ Priority ] ';' [ ( Import ) ] [ Export ] SEMANTICS 4E: Mode<4>:=NotQual; Entry<0>@.Mode:=Mode<4>; Mode<0>:=Mode<4>; 0:Init(Imp_Set<0>). Инициализируется список импорта. Тип экспорта заносится в описание модуля. RULE Import ::= [ From ] 'import' ( Ident /',' ) ';' SEMANTICS var Tmp:Import_Pair; 0:Init(Imp_Set<0>); 1E: Qual<1>:=false; 3A:if Qual<1> then Include(Val<3>,Imp_Set<0>) else Tmp.Name_Set:=Nil; Tmp.Imp_Name:=Name<3>; Include(Tmp,Imp_Set ) end; if Qual<1> then Tmp.Name_Set:=Imp_Set<0>; Tmp.Imp_Name:=Name<1>; Include(Tmp,Imp_Set ) end. Если импорт квалифицированный, то Name<1> - имя модуля, из которого делается импорт. В этом случае Imp_Set<0> - множество импортируемых из него объектов. Идентификатор включается в список импорта из модуля, иначе идентификатор - имя модуля и он включается в список импортируемых модулей. Если импорт квалифицированный, включить в список импорта модуля весь список импортируемых объектов. RULE From ::= 'from' Ident SEMANTICS Qual<0>:=true; Name<0>:=Val<2>. RULE Export ::= 'export' [ Qual ] ( Ident /',' ) SEMANTICS 0: Init(Entry @.Exp_Set); 2Е: Mode<2>:=NotQual; Mode<0>:=Mode<2>; 3A: Include(Val<3>,Entry @.Exp_Set). Включить идентификатор в экспортный список модуля; множество экспортируемых модулем объектов заносится в поле Exp_Set : Key Name Set Of Element в таблице объектов, поскольку при использовании квалифицированного импорта или обращении M.V, где M - имя модуля, а V - имя экспортируемого объекта, необходимо иметь доступ к списку квалифицированного экспорта. RULE Qual ::= 'qualified' SEMANTICS Qual<0>:=Qualified RULE Declaration ::= 'var' ( Var_Decl ). RULE Var_Decl ::= Ident_List ':' Type_Des ';' SEMANTICS var V:Name; for V in Ident_Set<1> do if (Find(V,Env )<>Nil) then Error("Identifire declared twice") end; Include(V,Env ); V@.Object:=VarObject; V@.Type:=Exit<3>; end. V - рабочая переменная для элементов списка. Для каждого идентификатора из множества Ident_Set<1> сформировать объект- переменную в текущей компоненте среды с соответствующими характеристиками. RULE Ident_List ::= ( Ident /',' ) SEMANTICS 0:Init(Ident_Set<0>); 1A:Include(Val<1>,Ident_Set<0>). RULE Type_Des ::= Ident SEMANTICS var P:pointer to Block; P:=Block@; repeat Exit<0>:=Find(Val<1>,P@.Env); if P@.Kind then P:=P@.Pred end; until (Exit<0><>NIL)or(not P@.Kind); if (Exit<0>=NIL) then Exit<0>:=Find(Val<1>,Env ) end; if (Exit<0>=Nil) then Error("тип не найден") else if (Exit<0>@.Object<>TypeObject) then Error("Not type object"); Exit<0>:=Nil; end end. Рабочая переменная P - указатель на ближайший охватывающий блок. Переходя от блока от блоку, ищем объект в его среде. Если не нашли, то, если блок - процедура, перейти к охватывающей. Если дошли до границы модуля, попытаться найти объект в предопределенной компоненте. Если объект нашли, надо убедиться, что он - тип. Зависимости атрибутов на дереве разбора приведены на рис. 6.5. +--------------------+ | | | Block | Env<--------+ | | | | | | | Dec_List | | | | | | | | Declaration | | | \ | | | \ | | | Block | | +---------+---------->Env | v | | | +-----> Imp_Set | Mod_Head | Exp_Set<-+ | | \ | | | \ | | Imp_List \ | | | \ | | +--------------+ Export | | | | | | | Import Import |--------+ | | /| Imp_Set | | | | | / | ^ | | | | | From | | | Ident Ident | | | | | | | | | | | | | | v v | |<--Ident | | | ---------------+ | +-------+ | +--------+ | | | | | | | Ident Ident | Ident Ident | | | | | | | v v | | | | -----------+ v v +------------------------------ Рис. 6.5 Глава 7. Организация таблиц символов компилятора В процессе работы компилятор хранит информацию об объектах программы. Как правило, информация о каждом объекте состоит из двух основных элементов: имени объекта и его свойств. Информация об объектах программы должна быть организована таким образом, чтобы поиск ее был по возможности быстрей, а требуемая память по возможности меньше. Кроме того, со стороны языка программирования могут быть дополнительные требования. Имена могут иметь определенную область видимости. Например, поле записи должно быть уникально в пределах структуры (или уровня структуры), но может совпадать с именем объектов вне записи (или другого уровня записи). В то же время имя поля может открываться оператором присоединения, и тогда может возникнуть конфликт имен (или неоднозначность в трактовке имени). Если язык имеет блочную структуру, то необходимо обеспечить такой способ хранения информации, чтобы, во-первых, поддерживать блочный механизм видимости, а во-вторых - эффективно освобождать память по выходе из блока. В некоторых языках (например, Аде) одновременно (в одном блоке) могут быть видимы несколько объектов с одним именем, в других такая ситуация недопустима. Мы рассмотрим некоторые основные способы организации информации в компиляторах: таблицы идентификаторов, таблицы символов, способы реализации блочной структуры. 7.1. Таблицы идентификаторов и таблицы символов Как уже было сказано, информацию об объекте обычно можно разделить на две части: имя (идентификатор) и описание. Удобно эти характеристики объекта хранить по отдельности. Это обусловлено двумя причинами: 1) символьное представление идентификатора может иметь неопределенную длину и быть довольно длинным; 2) как уже было сказано, различные объекты в одной области видимости и/или в разных могут иметь одинаковые имена и незачем занимать память для повторного хранения идентификатора. Таблицу для хранения идентификаторов называют таблицей идентификаторов, а таблицу для хранения свойств объектов - таблицей символов. В таком случае одним из свойств объекта становится его имя и в таблице символов хранится указатель на соответствующий вход в таблицу идентификаторов. 7.2. Таблицы идентификаторов Если длина идентификатора ограничена (или имя идентифицируется по ограниченному числу первых символов идентификатора), то таблица идентификаторов может быть организована в виде простого массива строк фиксированной длины, как это изображено на рис. 7.1. Некоторые входы могут быть заняты, некторые - свободны. +---------------------------------------+ | | |---------------------------------------| | s | o | r | t | | | | | | |<---- |---+---+---+---+---+---+---+---+---+---| | a | | | | | | | | | |<---- |---+---+---+---+---+---+---+---+---+---| | r | e | a | d | | | | | | |<---- |---+---+---+---+---+---+---+---+---+---| | i | | | | | | | | | |<---- |---------------------------------------| | | +---------------------------------------+ Рис. 7.1 Ясно, что, во-первых, размер массива должен быть не меньше числа идентификаторов, которые могут реально появиться в программе (в противном случае возникает переполнение таблицы); во-вторых, как правило, потенциальное число различных идентификаторов существенно больше размера таблицы. Поиск в такой таблице может быть организован методом повторной расстановки. Суть его заключается в следующем. Пусть число элементов массива равно N. Определим некоторую функцию h (первичную функцию расстановки), определенную на множестве идентификаторов и принимающую значения 0<=h(id)<=N- 1, id - идентификатор. Если элемент таблицы h(id) свободен, то это означает, что идентификатора в таблице нет. Если же занят, то это еще не означает, что идентификатор id в таблицу занесен, поскольку (вообще говоря) много идентификаторов могут иметь одно и то же значение функции расстановки. Для того чтобы определить, нашли ли мы нужный идентификатор, сравниваем id с элементом таблицы h(id). Если они равны - идентификатор нашли, если нет - надо продолжать поиск дальше. Для этого вычисляют вторичную функцию расстановки h2(h). Вновь возможны четыре варианта: либо элемент таблицы свободен, либо нашли идентификатор, либо таблица вся просмотрена и идентификатора нет, либо надо продолжать поиск. Для продолжения поиска применяют вновь функцию h3(h2), и т.д. Как правило, hi=h2 для i>=2. Аргументом функции h2 является целое в диапазоне [0,N-1] и она может быть быть устроена по-разному. Приведем три варианта. 1) h2(i)=(i+1) mod N Берется следующий (циклически) элемент массива. Этот вариант плох тем, что занятые элементы "группируются", образуют последовательные занятые участки и в пределах этого участка поиск становится по-существу линейным. 2) h2(i)=(i+k) mod N, где k и N взаимно просты. По-существу это предыдущий вариант, но элементы накапливаются не в последовательных элементах, а "разносятся". 3) h2(i)=(a*i+c) mod N - "псевдослучайная последовательность". Здесь c и N должны быть взаимно просты, b=а-1 кратно p для любого простого p, являщегося делителем N, b кратно 4, если N кратно 4 [6]. Поиск в таблице можно описать следующим алгоритмом: type Pair=record Yes:boolean; Point:integer end; function Search(id):Pair; var H,H0: integer; begin H:=h(id); H0:=h; loop if T[H]=id then return(true,H) elsif T[H]=Empty then return(false,H) else H:=h2(H); if H=H0 then return(false,NIL); end end end end; Алгоритм вырабатывает: (true,P), если нашли требуемый идентификатор, P - указатель на него; (false,NIL), если искомого идентификатора нет и в таблице нет свободного места; (false,P), если искомого идентификатора нет, но в таблице есть свободный вход P. Занесение идентификатора в таблицу осуществляется следующим алгоритмом: function Insert(id):integer; var P:Pair; begin P:=search(id); with P do if not Yes and Point<>NIL then T[Point]:=id; end; return(Point) end; end; Второй способ организации таблицы идентификаторов - хранение идентификаторов в сплошном массиве символов. В этом случае идентификатору соответствует номер его первого символа в этом массиве, как это изображено на рис. 7.2. Идентификатор в массиве заканчивается каким-либо специальным символом (EOS). Второй возможный вариант - в качестве первого символа идентификатора в массив заносится его длина. Для организации поиска в таком массиве создается таблица расстановки (рис. 7.3). +------------------------------------- | +------------------ | | +---------- | | | +----- | | | | | | | +--------------+ | | | | v v v v ----------------------------------------------------------+ | s | o | r | t |EOS| a |EOS| r | e | a | d |EOS| i |EOS| ----------------------------------------------------------+ Рис. 7.2 +---+ 0 | | |---| |...| |---| +----------+ +--------+ 9 | --+-->| Idenp |--+-->| | x | |---| +----------+ +--------+ |---| v v |...| Указатели на идентификаторы |---| +------------+ 20 | --+-->| Idenp | x | |---| +------------+ |---| v |...| Указатель на идентификатор |---| +--------+ +--------+ +-------+ 32 | --+-->| | -+-->| | -+-->| | x | |---| +--------+ +--------+ +-------+ |...| v v |---| Указатели на идентификаторы 210 | | Рис. 7.3 7.3. Таблицы символов и таблицы расстановки Рассмотрим организацию таблицы символов с помощью таблицы расстановки. Таблица расстановки - это массив указателей на списки указателей на идентификаторы. В каждый такой список входят указатели на идентификаторы, имеющие одно значение функции расстановки (рис. 7.3). Вначале таблица расстановки пуста (все элементы имеют значение NIL). При поиске идентификатора id вычисляется функция расстановки H(id) и просматривается линейный список T[H]. Поиск в таблице может быть описан следующей процедурой: type Element= record IdenP:integer; Next:pointer to Element; end; Pointer=pointer to Element function Search(Id):Pointer; var P:Pointer; begin P:=T[H(Id)]; loop if P=nil then return(nil) elsif IdenTab[P^.IdenP]=Id then return(P) else P:=P^.Next end end; end; IdenTab - таблица идентификаторов. Занесение объекта в таблицу может осуществляться следующей процедурой: function Insert(Id):Pointer; var P,H:Pointer; begin P:=Search(Id); if P<>nil then return(P) else H:=H(Id); new(P); P^.Next:=T[H]; T[H]:=P; P^.Idenp:=Include(Id); end; return(P); end; |--| +------+ +------+ H----->| -+-x---->| |----->| |-----> |--| | +-->+------+ +------+ | | | | |--| | +------------+ | +------+ | +---| |---+ P-------->+------+ Рис. 7.4. Процедура Include заносит идентификатор в таблицу идентификаторов. Алгоритм иллюстрируется рис. 7.4. 7.4. Функции расстановки. Много внимания было уделено тому, какой должна быть функция расстановки. Основные требования к ней очевидны: она должна легко вычисляться и распределять равномерно. Один из возможных подходов заключается в следующем. 1. По символам строки s определяем положительное целое H. Преобразование одиночных символов в целые обычно можно сделать средствами языка реализации. В Паскале для этого служит функция ord, в Си при выполнении арифметических операций символьные значения трактуются как целые. 2. Преобразуем H, вычисленное выше, в номер списка, т.е. целое между 0 и m-1, где m - размер таблицы расстановки, например, взятием остатка при делении H на m. Функции расстановки, учитывающие все символы строки, распределяют лучше, чем функции, учитывающие только несколько символов, например в конце или середине строки. Но такие функции требуют больше вычислений. Простейший способ вычисления H - сложение кодов символов строки. Перед сложением с очередным символом можно умножить старое значение H на константу q. Т.е. полагаем H0=0, Hi=q*Hi- 1+ci для 1<=i<=k, k - длина строки. При q=1 получаем простое сложение символов. Вместо сложения можно выполнять сложение ci и q*Hi-1 по модулю 2. Переполнение при выполнении арифметических операций можно игнорировать. Функция Hashpjw, приведенная ниже [1], вычисляется, начиная с H=0. Для каждого символа c сдвигаем биты H на 4 позиции влево и добавляем c. Если какой-нибудь из четырех старших бит H равен 1, сдвигаем эти 4 бита на 24 разряда вправо, затем складываем по модулю 2 с H и устанавливаем в 0 каждый из четырех старших бит, равных 1. #define PRIME 211 #define EOS '\0' int Hashpjw(s) char *s; { char *p; unsigned H=0, g; for (p=s; *p != EOS; p=p+1) {H=(H<<4)+(*p); if (g = H & 0xf0000000) {H=H^(g>>24); H=H^g; } } return H%PRIME; } Рис. 7.5 7.5. Таблицы на деревьях Рассмотрим еще один способ организации таблиц с использованием двоичных деревьев. Будем считать, что на множестве идентификаторов задан некоторый линейный порядок (например, лексикографический), т.е. задано некоторое отношение '<', транзитивное, антисимметричное и антирефлексивное. Каждой вершине двоичного дерева, представляющего таблицу символов, сопоставлен идентификатор. Вершина может иметь нуль, одного (правого или левого) или двух (правого и левого) потомков. Если вершина имеет левого потомка, то идентификатор, сопоставленный левому потомку, меньше идентификатора, сопоставленного самой вершине; если имеет правого потомка, то ее идентификатор больше. Элемент таблицы изображен на рис. 7.6. +---------------+ TP --->| | | -+--->Ident +-/----\--------+ / \ v v Left Right Рис. 7.6 Поиск в такой таблице может быть описан следующей процедурой: function SearchTree(Id,TP):Pointer; begin if Id=TP^.Ident then return(TP) elsif Id TP^Ident then return(Search_tree(Id,TP^.Right)) else return(nil) end end; Занесение в таблицу осуществляется процедурой function Insert_tree(Id,TP):Pointer; function fill(var P):Pointer; begin if P=nil then P:=new(Element); P^.Ident:=include(Id); P^.Left:=nil; P^.Right:=nil; return(P); else return(Insert_tree(Id,P)) end end; begin if Id=TP^.Ident then return(TP) elsif Id | | -+----->| | -+---->| | | +------+ +------+ +-------+ T1 T2 Tn Рис. 7.11 7.7. Сравнение различных методов реализации таблиц Рассмотрим преимущества и недостатки тех или иных методов реализации таблиц с точки зрения техники использования памяти. Если таблица размещается в массиве, то, с одной стороны, отпадает необходимость использования динамической памяти, а с другой - появляется ряд осложнений. Использование динамической памяти, как правило, довольно дорогая операция, поскольку механизмы поддержания работы с динамической памятью довольно сложны. Необходимо поддерживать списки свободной и занятой памяти, выбирать наиболее подходящий кусок памяти при запросе, включать освободившийся кусок в список свободной памяти и, возможно, склеивать куски свободной памяти в списке. С другой стороны, использование массива требует отведения заранее довольно большой памяти, а это означает, что значительная память вообще не будет использоваться. Кроме того, часто приходится заполнять не все элементы массива (например, в таблице идентификаторов или в тех случаях, когда в массиве фактически хранятся записи переменной длины, например если в таблице символов записи для различных объектов имеют различный состав полей). Обращение к элементам массива может означать использование операции умножения при вычислении индексов, что может замедлить исполнение. Наилучшим, по-видимому, является механизм доступа по указателям и использование факта магазинной организации памяти в компиляторе. Для этого процедура выделения памяти выдает необходимый кусок из подряд идущей памяти, а при выходе из процедуры вся память, связанная с этой процедурой, освобождается простой перестановкой указателя свободной памяти в состояние перед началом обработки процедуры. В чистом виде это не всегда, однако, возможно. Например, локальный модуль в Модуле-2 может экспортировать некоторые объекты наружу. При этом схему реализации приходится "подгонять" под механизм распределения памяти. В данном случае, например, необходимо экспортированные объекты вынести в среду охватывающего блока и свернуть блок локального модуля. Глава 8. Генерация кода Задача генератора кода - построение эквивалентной машинной программы по программе на входном языке. Обычно в качестве входного для генератора кода служит некоторое промежуточное представление программы. В свою очередь, генерация кода состоит из ряда специфических, относительно независимых подзадач: распределение памяти (в частности, распределение регистров), выбор команд, генерация объектного (или загрузочного) модуля. Конечно, независимость этих подзадач относительна: например, при выборе команд нельзя не учитывать схему распределения памяти, и, наоборот, схема распределения памяти (регистров, в частности) необходимо ведет к генерации той или иной последовательности команд. Однако удобно и практично эти задачи все же разделять и при этом особо обращать внимание на их взаимодействие. В какой-то мере схема генератора кода зависит от формы промежуточного представления. Ясно, что генерация кода из дерева отличается от генерации кода из троек, а генерация кода из префиксной записи отличается от генерации кода из ориентированного графа. В то же время все генераторы кода имеют и много общего и основные применяемые алгоритмы отличаются, как правило, только в деталях, связанных с используемым промежуточным представлением. В дальнейшем в качестве промежуточного представления мы будем использовать префиксную нотацию и алгоритмы генерации кода будем излагать в виде атрибутных схем со входным языком Лидер. 8.1. Модель машины При изложении алгоритмов генерации кода мы будем следовать некоторой модели машины, в основу которой положена система команд микропроцессора Motorola 68020. В системе команд используются следующие способы адресации: D - значение находится в регистре данных; А - значение находится в адресном регистре; POST - пост-инкрементная адресация (А)+: исполнительный адрес есть значение адресного регистра и после исполнения команды значение этого регистра увеличивается на длину операнда; PRE - пре-инкрементная адресация -(А): перед исполнением операции содержимое адресного регистра уменьшается на длину операнда, исполнительный адрес равен новому содержимому адресного регистра; DIRECT - прямая адресация через регистры: исполнительный адрес равен значению выражения ADDREG+INDEXREG*SCALE +ADDRDISP - содержимое адресного регистра + содержимое индексного регистра, умноженное на SCALE+адресное смещение; INDPPRE - пре-косвенная через память: (ADDREG+INDEXREG* SCALE+ADDRDISP)+INDEXDISP - выражение в скобках дает адрес ячейки, содержимое которой + индексное смещение дает исполнительный адрес; INDPOST - пост-косвенная через память: (ADDREG+ADDRDISP) +INDEXREG*SCALE+INDEXDISP - выражение в скобках дает адрес ячейки, содержимое которой + содержимое индексного регистра, умноженное на SCALE + индексное смещение, дает исполнительный адрес; DIRPC - прямая через PC (счетчик команд): исполнительный адрес определяется выражением PC+INDEXREG*SCALE+ADDRDISP; INDPREPC - пре-косвенная через PC: (PC+INDEXREG* SCALE+ ADDRDISP)+INDEXDISP - то же, что INDPRE, но в качестве адресного регистра исползуется PC; INDPOSTPC - пост-косвенная через PC: (PC+ADDRDISP)+INDEXREG *SCALE+INDEXDISP то же, что и INDPOST, но в качестве адресного регистра используется PC; ABS - абсолютная; IMM - непосредственный операнд. В дальнейшем изложении будут использованы следующие команды: MOVEA ИА,А - загрузить содержимое по исполнительному адресу ИА на адресный регистр А; MOVE ИА1,ИА2 - содержимое по исполнительному адресу ИА1 переписать по исполнительному адресу ИА2; MOVEM список регистров,ИА - сохранить указанные регистры в памяти по адресу ИА; MOVEM ИА,список регистров - восстановить указанные регистры из памяти по адресу ИА; LEA ИА,А - загрузить исполнительный адрес ИА на адресный регистр А; MUL ИА,D - умножить содержимое по исполнительному адресу ИА на содержимое регистра данных D и результат разместить в D; ADD ИА,D - сложить содержимое по исполнительному адресу ИА с содержимым регистра данных D и результат разместить в D; SUB ИА,D - вычесть содержимое по исполнительному адресу ИА из содержимого регистра данных D и результат разместить в D; CMP ИА,D - содержимое регистра данных D вычитается из содержимого по исполнительному адресу ИА, при этом формируется признак результата, но содержимое регистра D не меняется; TST ИА - выработать код условия по значению, находящемуся по исполнительному адресу ИА; BNE ИА - условный переход по признаку NE (не равно) по исполнительному адресу ИА; BEQ ИА - условный переход по признаку EQ (равно) по исполнительному адресу ИА; BLE ИА - условный переход по признаку LE (меньше или равно) по исполнительному адресу ИА; BGT ИА - условный переход по признаку GT (больше) по исполнительному адресу ИА; BLE ИА - условный переход по признаку KE (меньше или равно) по исполнительному адресу ИА; BLT ИА - условный переход по признаку LT (меньше) по исполнительному адресу ИА; BR ИА - безусловный переход по адресу ИА; JSR ИА - переход с возвратом на подпрограмму по адресу ИА; JMP ИА - безусловный переход по исполнительному адресу; RTD размер локальных - возврат из подпрограммы с указанием размера локальных; LINK A,размер локальных - в стеке сохраняется значение регистра А, в регистр А заносится указатель на это место в стеке и указатель стека продвигается на размер локальных; UNLK A - стек сокращается на размер локальных и регистр А восстанавливается из стека. 8.2. Динамическая организация памяти Рассмотрим схему реализации магазина периода выполнения для простейшего случая (как, например, в языке Паскаль), когда все переменные в магазине (фактические параметры и локальные переменные) имеют известные при трансляции смещения. Магазин служит для хранения локальных переменных (и параметров) и обращения к ним в языках, допускающих рекурсивные определения процедур. Еще одной задачей, которую необходимо решать при трансляции языков с блочной структурой - обеспечение реализации механизмов статической вложенности. Рассмотрим рекурсивную программу рис. 8.1. PROCEDURE P1; +----+ VAR V1; P2 | V2 | PROCEDURE P2; |----| VAR V2; |....| BEGIN P2; |----| V1:=... P2 | V2 | V2:=... |----| END P2; P1 | V1 | BEGIN P2; +----+ END P1; Рис. 8.1 Рис. 8.2 В процессе выполнения этой программы в магазине может сложиться ситуация, изображенная на рис. 8.2. Находясь в процедуре P2, мы должны иметь доступ к последнему экземпляру значений переменных процедуры P2 и к экземляру значений переменных процедуры P1, из которой была вызвана P2. Кроме того, необходимо обеспечить восстановление состояния программы при завершении выполнения процедуры. Мы рассмотрим две возможные схемы динамической организации памяти: схему со статической цепочкой и с дисплеем в памяти. В первом случае все статические контексты связаны в список, который называется статической цепочкой; в каждой записи для процедуры в магазине хранится указатель на запись статически охватывающей процедуры (помимо, конечно, указателя динамической цепочки - указателя на "базу" динамически предыдущей процедуры). Использование той или иной схемы определяется, помимо прочих условий, прежде всего числом адресных регистров. 8.2.1. Организация магазина со статической цепочкой Минимальный адрес +-----------------+<---------+ | Сохраненные | | | регистры | | |-----------------| | Текущий | Локальные |<--+ |Область статический |-----------------| |Disp |последней уровень +--| Предыдущий BP |<--+- BP |вызванной | |-----------------| | |процедуры | | Точка возврата | |Disp | | |-----------------| | | | | Факт. параметры |<--+ | ||-+-----------------+-|<-------+ | | Сохраненные | | | регистры | | |-----------------| LP +-+--| Предыдущий LP |<----+D | | |-----------------| |e Предыдущий | | | Локальные | |l статический| | | | |t уровень | | |-----------------| |a | +->| Предыдущий BP |-----+ v +-----------------+ ................. Максимальный адрес Рис. 8.3 Итак, в случае статической цепочки магазин организован, как это изображено на рис. 8.3. Таким образом, на запись текущей процедуры в магазине указывает регистр BP (Base pointer), с которого начинается динамическая цепочка. На статическую цепочку указывает регистр LP (Link Pointer). В качестве регистров BP и LP в различных системах команд могут использоваться универсальные, адресные или специальные регистры. Локальные переменные отсчитываются от регистра BP вверх, фактические параметры - вниз с учетом памяти, занятой точкой возврата и самим сохраненным регистром BP. Вызов подпрограмм различного уровня производится несколько по-разному. При вызове подпрограммы того же статического уровня, что и вызывающая подпрограмма, выполняются следующие команды: Занесение фактических параметров в магазин JSR A Команда JSR A продвигает указатель SP, заносит PC на верхушку магазина и осуществляет переход по адресу A. После выполнения этих команд состояние магазина становится таким, как это изображено на рис. 8.4. Занесение BP, отведение локальных, сохранение регистров делает вызываемая подпрограмма. +---------------+ |Точка возврата |<---SP |---------------| |Факт. параметры| |+---------------+--| |Сохраненные | |регистры | |---------------| LP +--|Предыдущий LP |<------- | |---------------| Предыдущий | |Локальные | статический| | | уровень | |---------------| BP | |Предыдущий BP |<---- v |---------------| |...............| Рис. 8.4 При вызове локальной подпрограммы необходимо установить указатель статического уровня на текущую подпрограмму, а при выходе - восстановить его на старое значение (охватывающей текущую). Для этого исполняются следующие команды: Занесение фактических в магазин MOVE BP,LP SUB Delta,LP JSR A Здесь Delta - размер локальных вызываемой подпрограммы плюс двойная длина слова. Магазин после этого принимает состояние, изображенное на рис. 8.5. +------------------+ | Точка возврата | |------------------| | Факт. параметры | |--+------------------+--| | Сохраненные | | регистры | |------------------| LP +---| Предыдущий LP |<---+ | |------------------| D | Предыдущий | | | e | статический | | Локальные | l | уровень | | | t | | |------------------| a | | | Предыдущий BP |<---+ v |------------------| | ................ | Рис. 8.5 После выхода из подпрограммы в вызывающей подпрограмме выполняется команда MOVE -Delta(BP),LP которая восстанавливает старое значение статической цепочки. Если выход осуществлялся из подпрограммы 1-го уровня, эту команду выполнять не надо, поскольку для 1-го уровня нет статической цепочки. При вызове подпрограммы меньшего, чем вызывающая, уровня выполняются следующие команды: Занесение фактических параметров в магазин MOVE (LP),LP /*столько раз, какова разность уровней вызывающей и вызываемой ПП*/ JSR A Тем самым устанавливается статический уровень вызываемой подпрограммы. После выхода из подпрограммы выполняется команда MOVE -Delta(BP),LP восстанавиливающая статический уровень вызывающей подпрограммы. Тело подпрограммы начинается со следующих команд: LINK BP,-размер локальных MOVEM -(SP) Команда LINK BP,размер локальных эквивалентна трем командам: MOVE BP,-(SP) MOVE SP,BP ADD -размер локальных,SP Команда MOVEM сохраняет в магазине регистры. В результате выполнения этих команд магазин приобретает вид, изображенный на рис. 8.3. Выход из подпрограммы осуществляется следующей последовательностью команд: MOVEM (SP)+,D0-D7,A0-A7 UNLK BP RTD размер фактических Команда MOVEM восстанавливает регистры из магазина. После ее выполнения магазин выглядит, как это изображено на рис. 8.6. +-----------------+<--SP Текущий | Локальные | уровень |-----------------| | Предыдущий BP |<--BP |-----------------| +------------------+ | Точка возврата | | Точка возврата |<---SP |-----------------| |------------------| | Факт. параметры | | Факт. параметры | |-----------------------| +------------------+ ................. .................. Рис. 8.6 Рис. 8.7 После выполнения команды UNLK BP, которая эквивалентна такой последовательности команд: MOVE BP,SP MOVE (SP),BP ADD #4,BP /*4 - размер слова*/ магазин имеет содержимое, изображенное на рис. 8.7. Наконец, после выполнения команды RTD размер_фактических, которая эквивалентна последовательности ADD размер_фактических, SP JMP -размер_фактических(SP) магазин восстанавливается до состояния, которое было до вызова. В зависимости от наличия локальных переменных, фактических параметров и необходимости упрятывания регистров каждая из этих команд может отсутствовать. 8.2.2. Организация магазина с дисплеем Рассмотрим теперь организацию магазина с дисплеем. Дисплей - это массив (DISPLAY) фиксированного размера, определяющего ограничение на число статических уровней вложенности процедур. i-й элемент этого массива представляет собой указатель на область активации процедуры i-го статического уровня. Доступ к переменным самой внутренней процедуры осуществляется через регистр BP. При вызове процедуры меньшего статического уровня изменений в дисплее не производится. При вызове локальной процедуры в дисплее отводится элемент для текущей (вызывающей) процедуры. При вызове процедуры того же уровня (i) i-й элемент замещается на указатель области активации текущей процедуры и при выходе восстанавливается. Тем самым DISPLAY[i] всегда указывает на область активации последней вызванной процедуры i-го статического уровня. Минимальный адрес <------+ | Сохраненные | | Область | регистры | | последней |------------------| | вызванной Текущий | Локальные | | процедуры статический |------------------| | уровень +--| Предыдущий BP |<-- BP <-+ | |------------------| | | | | Точка возврата | | | | |------------------| | | | | Факт. параметры | | | | |------------------|<------+ | DISPLAY[i] | | Сохраненные | | ---------+ | | регистры | +------* | | |------------------| ---------+ | | предыдущий | | | DISPLAY[i] | | |------------------| Предыдущий | | Локальные | статический | | | уровень | |------------------| +->| Предыдущий BP | |------------------| |..................| Рис. 8.8 Запоминание и восстановление DISPLAY[i] можно не выполнять, если процедура не имеет локальных переменных и параметров или если из процедуры нет вызовов описанных в ней процедур. Структура магазина при использовании дисплея изображена на рис. 8.8. Дисплей может быть реализован либо через регистры (если их достаточно), либо через массив в памяти. |----------------------|<-------------------------+ | Локальные | Область активации | |----------------| текущей процедуры | | Регистры | | |----------------| BP | +-----| Предыдущий BP |<----- | | |----------------| BP предыдущего статического | | | x---+---------> уровня | | | Дисплей .......| BP 1-го статического уровня | | | x---+---------> | | |----------------| | | | Точка возврата | | | |----------------| | | | Фактические | | | |--+----------------+--|<-------------------------+ | | Локальные | | |----------------| | | Регистры | | |----------------| +---->| Предыдущий BP | |----------------| | Дисплей | |----------------| | Точка возврата | |----------------| |--+ Фактические +--| Рис. 8.9. Иногда используется комбинированная схема - дисплей в магазине (рис 8.9). Дисплей хранится в магазине. При вызове процедуры текущего статического уровня он просто копируется в новую область активации. При вызове процедуры более глубокого статического уровня в дисплей добавляется указатель BP вызывающей процедуры. Отдельного рассмотрения требует вопрос о технике передачи фактических параметров. Конечно, в случае простых параметров (например, чисел) проблем не возникает. Однако передача массивов по значению - операция довольно дорогая, поэтому с точки зрения экономии памяти целесообразнее сначала в подпрограмму передать адрес массива, а затем уже из подпрограммы по адресу передать в магазин сам массив. В связи с передачей параметров следует упомянуть еще одно обстоятельство. Рассмотренная схема организации магазина допустима только для языков со статически известными размерами фактических параметров. Однако, например, в языке Модула-2 по значению может быть передан гибкий массив, и в этом случае нельзя статически распределить память для параметров. Обычно в таких случаях заводят так называемый "паспорт" массива, в котором хранится вся необходимая информация, а сам массив размещается в магазине в рабочей области выше сохраненных регистров. 8.3. Назначение адресов Назначение адресов переменным, параметрам и полям записей происходит при обработке соответствующих объявлений. В однопроходном трансляторе это может производиться вместе с построением основной таблицы символов и соответствующие адреса (или смещения) могут храниться в этой же таблице. В промежуточном представлении Лидер объявления сохранены, что делает это промежуточное представление машинно-независимым. Напомним, что в Лидер-представлении каждому описанию соответствует некоторый номер. В процессе работы генератора кодов поддерживается таблица Table, в которой по этому номеру (входу) содержится следующая информация: - для типа - его размер; - для переменной - адрес; - для поля записи - смещение внутри записи; - для процедуры - размер локальных; - для диапазона индексов массива - значение левой границы. Функция IncTab вырабатывает указатель (вход) на новый элемент таблицы, проверяя при этом наличие свободной памяти. Таблица LevelTab - это таблица уровней процедур, содержащая указатели на последовательно вложенные процедуры (см. рис. 4.9). Для вычисления адресов определим для каждого объявления два синтезируемых атрибута: DISP будет обозначать смещение внутри области процедуры (или единицы компиляции), а SIZE - размер. Тогда семантика правила для списка объявлений принимает вид RULE DeclPart ::= ( Decl ) SEMANTICS Disp<1>:=0; 1A: Disp<1>:=Disp<1>+Size<1>; Size<0>:=Disp<1>. Это можно следующим образом изобразить на дереве объявлений (рис. 8.10). DeclPart | Size <----------+ /|\ | / | \ | / | \ | / | \ | / | \ | Decl Decl Decl | Disp----->Disp--------->Disp + Size + Size + Size ^ ^ ^ | | | Рис. 8.10 Все объявления, кроме объявлений переменных, имеют нулевой размер. Размер объявления переменной определяется следующим правилом: RULE Decl ::= 'VAR' TypeDes SEMANTICS var Entry:Tablentry; 0: Entry:=IncTab; Size<0>:=((Table[VAL<2>]+1) DIV 2)*2; { Выравнивание на границу слова } Table[Entry]:=Disp<0>+Size<0>. В качестве примера трансляции определения типа рассмотрим обработку описания записи: RULE TypeDes ::= 'REC' ( TypeDes ) 'END' SEMANTICS var Disp:word; Temp:Tablentry; 0: Entry<0>:=IncTab; Disp:=0; 2A: begin Temp:=IncTab; Table[Temp]:=Disp; Disp:=Disp+Table[Entry<2>]+1) div 2)*2; { Выравнивание на границу слова } end; Table[Entry<0>]:=Disp. 8.4. Трансляция переменных. Переменные отражают все многообразие механизмов доступа в языке. Переменная имеет синтезированный атрибут ADDRESS - это запись, описывающая адрес в команде МС68020. Этот атрибут сопоставляется всем нетерминалам, представляющим значения. В системе команд МС68020 много способов адресации, и они отражены в структуре значения атрибута ADDRESS, имеющего следующий тип: Register= (D0,D1,D2,D3,D4,D5,D6,D7,A0,A1,A2,A3,A4,A5,A6,SP,NO); AddrType=record AddrMode:(D,A,Post,Pre,Direct,IndPre,IndPost, DirPC,IndPrePC,IndPostPC,Abs,Imm); Addreg,IndexREG:Register; IndexDisp,AddrDisp:cardinal; Scale:1..8; end; Значение регистра NO означает, что соответствующий регистр в адресации не используется. Доступ к переменным осуществляется в зависимости от их уровня: глобальные переменные адресуются с помощью абсолютной адресации; переменные процедуры текущего уровня адресуются через регистр базы А6. Если стек организован с помощью статической цепочки, то переменные предыдущего статического уровня адресуются через регистр статической цепочки А5; переменные остальных уровней адресуются "пробеганием" по статической цепочке с использованием вспомогательного регистра. Адрес переменной формируется при обработке структуры переменной слева направо и передается сначала сверху вниз как наследуемый атрибут нетерминала VarTail, а затем передается снизу-вверх как глобальный атрибут нетерминала Variable. Таким образом, правило для обращения к переменной имеет вид (первое вхождение Number в правую часть - это уровень переменной, второе - ее Лидер-номер): RULE Variable ::= VarMode Number Number VarTail SEMANTICS var Temp:integer; AddrTmp1,AddrTmp2:AddrType; 3: if (Val<2>=0) then { Глобальная переменная } Address<4>.AddrMode:=Abs; Address<4>.AddrDisp:=0; else { Локальная переменная } Address<4>.AddrMode:=Direct; if (Val<2>=Level ) then { Переменная текущего уровня } Address<4>.Addreg:=A6 elsif (Val<2>=Level -1) then { Переменная предыдущего уровня } Address<4>.Addreg:=A5; else Address<4>.Addreg :=GetFree(RegSet ); with AddrTmp1 do AddrMode=Direct; Addreg=A5; IndexReg=No; AddrDisp=0; end; Emit2(MOVEA,AddrTmp1,Address<4>.Addreg); AddrTmp1.Addreg;=Address<4>.Addreg; AddrTmp2.AddrMode=A; AddrTmp2.Addreg=Address<4>.Addreg; for Temp:=Level -Val<2> do Emit2(MOVEA,AddrTmp1,AddrTmp2) end end; if (Val<2>=Level ) then Address<4>.AddrDisp:=Table[Val<3>] else Address<4>.AddrDisp:=Table[Val<3>] +Table[LevelTAB[Val<2>]]. end end. Функция GetFree выбирает очередной свободный регистр (либо регистр данных, либо адресный регистр) и отмечает его как использованный в атрибуте RegSet нетерминала Block. Процедура Emit2 генерирует двухадресную команду. Первый параметр этой процедуры - код команды, второй и третий параметры имеют тип Address и служат операндами команды (здесь для упрощения изложения в качестве параметров этой процедуры используются контрукции типа '(А)'; имеется в виду косвенная адресация через адресный регистр). Смещение переменной текущего уровня отсчитывается от базы (А6), а других уровней - от указателя статической цепочки, поэтому оно определяется как алгебраическая сумма LOCALSize и величины смещения переменной (отрицательного!). Если стек организован с помощью дисплея, то трансляция для доступа к переменным может быть осуществлена следующим образом: RULE Variable ::= VarMode Number Number VarTail SEMANTICS var Temp:integer; 3: if (Val<2>=0) then { Глобальная переменная } Address<4>.AddrMode:=Abs; Address<4>.AddrDisp:=0; else { Локальная переменная } Address<4>.AddrMode:=Direct; if (Val<2>=Level ) then { Переменная текущего уровня } Address<4>.Addreg:=A6; Address<4>.AddrDisp:=Table[Val<3>] else with Address<4> do AddrMode=IndPost; Addreg:=NO; IndexREG:=NO; AddrDisp:=DispLAY[Val<2>]; IndexDisp:=Table[Val<3>] end end end. Рассмотрим трансляцию доступа к полям записи. Она описывается следующим правилом (Number - это Лидер-номер описания поля): RULE VarTail ::= 'FIL' Number VarTail SEMANTICS if (Address<0>.AddrMode=Abs) then Address<3>.AddrMode:=Abs; Address<3>.AddrDisp :=Address<0>.AddrDisp+Table[Val<2>]; else Address<3>:=Address<0>; if (Address<0>.AddrMode=Direct) then Address<3>.AddrDisp :=Address<0>.AddrDisp+Table[Val<2>] else Address<3>.IndexDisp :=Address<0>.IndexDisp+Table[Val<2>] end end. Смещение в случае абсолютной и прямой адресации определяется полем AddrDisp, а в остальных случаях - полем IndexDisp. Таким образом, видно, что при обработке полей записей идет только накопление смещения поля без генерации каких-либо команд. Атрибутные зависимости для этого правила могут быть изображены следующим образом (рис. 8.11): VarTail | Disp---------------+ | | / \ | / \ | / \ | +--------Number VarTail | Disp <--+ | ^ | Table | | |-------| | +----------->| Disp |----------------+ |-------| Рис. 8.11 Рассмотрим теперь выборку элемента массива. Лидер-синтаксис обращения к элементу массива следующий: VarTail ::= 'ARR' Number Typexpr VarTail Здесь Number - Лидер номер описания диапазона индексов; Typexpr - индексное выражение. По адресу левой части правила, представляющей переменную-массив, от которого берется индекс, и по индексному выражению, представленному нетерминалом Typexpr, мы должны сформировать адрес элемента массива. В приведенной ниже таблице решений функция GetAddr выбирает очередной свободный адресный регистр. Тип адресации VarTail левой части: IndPre or Direct (IndPost or Abs) or IndexReg=NO ((Direct or IndPre) & (IndexReg<>NO)) --------------------------------------------------------- ElSize<3>= | AddrDisp<4>:= |AddrDisp<4>:= 1,2,4,8 | AddrDisp<0> |-Left<2>*ElSize<3> AddrMode<3>=D | -Left<2>*ElSize<3> |AddrMode<4>:=IndPost | Addreg<4>:=Addreg<0>|Addreg<4>:= | IndexReg<4>:= |if Addreg<0> рабочий | Addreg<3> |then Addreg<0> | AddrMode<4>:=IndPost|else GetAddr | Scale<4>:=ElSize<3> |IndexReg<4>:= | | Addreg<3> | |Scale<4>:=ElSize<3> | |------------------- | |LEA Address<0>, | | Address<4> --------------------------------------------------------- --------------------------------------------------------- ElSize<3> | AddrDisp<4>:= | AddrDisp<4>:= <>1,2,4,8 | AddrDIP<0>- | -Left<2>*ElSize<3> AddrMode<3>=D| Left<2>*ElSize<3> | AddrMode<4>:=IndPost | Addreg<4>:=Addreg<0>| Addreg<4>:= | IndexReg<4>:= | if Addreg<0> рабочий | Addreg<3> | then Addreg<0> | Scale<4>:=1 | else GetAddr | AddrMode<4>:=IndPost| IndexReg<4>:= |---------------------| Addreg<3> | MUL ElSize<3>, | Scale:=1 | Addreg<3> |------------------- | | LEA Address<0>, | | Address<4> | | MUL ElSize<4>, | | IndexReg<4> --------------------------------------------------------- --------------------------------------------------------- ElSize<3>= |AddrDisp<4>:= | AddrDisp<4>:= 1,2,4,8 |AddrDisp<0>- | -Left<2>*ElSize<3> AddrMode<3><>D|Left<2>*ElSize<3> | AddrMode<4>:=IndPost |Addreg<4>:=Addreg<0>| Addreg<4>:= |IndexReg<4>:=GetFree| if Addreg<0> рабочий |AddrMode<4>:=IndPost| then Addreg<0> |Scale<4>:=ElSize<3> | else GetAddr |--------------------| IndexReg<4>:=GetFree |MOVE Address<3>, | Scale<4>:=ElSize<3> | IndexReg<4> |------------------- | | LEA Address<0>, | | Address<4> | | MOVE Address<3>, | | IndexReg<4> -------------------------------------------------------- --------------------------------------------------------- ElSize<3> |AddrDisp<4>:= | AddrDisp<4>:= <>1,2,4,8 |AddrDisp<0>- | -Left<2>*ElSize AddrMode<3><>D|Left<2>*ElSize<3> | AddrMode<4>:=IndPre |Addreg<4>:=Addreg<0>| Addreg<4>:= |IndexReg<4>:=GetFree| if Addreg<0> рабочий | AddrMode<4>:=IndPre| then Addreg<0> | Scale<4>:=ElSize<3>| else GetAddr |--------------------| IndexReg<4>:=GetFree |MOVE Address<3>, | Scale<4>:=1 | IndexReg<4> |---------------- | MUL ElSize<3>, | LEA Address<0>, | IndexReg<4> | Address<4> | | MOVE Address<3>, | | IndexReg<4> | | MUL ElSize<3>, | | IndexReg<4> -------------------------------------------------------- Под "рабочим" регистром в таблице решений имеется в виду регистр, значение которого может быть испорчено (примером "не рабочего" регистра может служить регистр А6 или регистр А5, если он используется как указатель процедуры предыдущего статического уровня). MaxReg - максимальный номер адресного регистра, которым можно пользоваться как рабочим. Все адресные регистры разделены на два множества: имеющие номера, большие MaxReg, заняты предварительным распределением, остальные - рабочие. Функция GetAddr выдает очередной свободный рабочий адресный регистр. Приведенная таблица реализуется следующим правилом: RULE VarTail ::= 'ARR' Number Typexpr VarTail SEMANTICS Size:integer; Flag:boolean; AddrTmp1,AddrTmp2:AddrType; Flag:= ((Address<0>.AddrMode=IndPre) or (Address<0>.AddrMode=Direct)) and (Address<0>.IndexReg=NO); Size:=Table[Val<2>]; if (Address<3>.AddrMode=D) then IndexReg<4>:=Addreg<3> else IndexReg<4>:=GetFree; end; AddrMode<4>:=IndPre; if Flag then Address<4>.AddrDisp :=Address<0>.AddrDisp -Table[Val<2>]*Size; Addreg<4>:=Addreg<0>; else Address<4>.AddrDisp:= -Table[Val<2>]*Size; if (Address<0>.Addreg<=MaxReg) then Addreg<4>:=Addreg<0> else Addreg<4>:=GetAddr; end end; if (Size in [2,4,8]) then Address<4>.Scale:=Size) else Address<4>.Scale:=1; end; AddrTmp1.AddrMode:=D; AddrTmp1.Addreg:=IndexReg<4>; if Flag then Emit2(LEA,Address<0>,Address<4>) end; if (Address<3>.AddrMode<>D) then Emit2(MOVE,Address<3>,AddrTmp1); end; AddrTmp2.AddrMode:=IMM; AddrTmp2.AddrDisp:=ElSize<3>; if not (Size IN [1,2,4,8]) then Emit2(MUL,AddrTmp2,AddrTmp1); end. 8.5. Трансляция целых выражений Трансляция выражений различных типов управляется синтаксически благодаря наличию указателя типа перед каждой операцией. Мы рассмотрим некоторые наиболее характерные проблемы генерации кода для выражений. Система команд МС68020 обладает двумя особенностями, сказывающимися на генерации кода для арифметических выражений (то же можно сказать и о генерации кода для выражений типа "множества"): 1) один из операндов выражения (правый) должен при выполнении операции находиться на регистре, поэтому если оба операнда не на регистрах, то перед выполнением операции один из них надо загрузить на регистр; 2) система команд довольно "симметрична", т.е. нет специальных требований к регистрам при выполнении операций (таких, например, как пары регистров или требования четности и т.д.). Поэтому выбор команд при генерации арифметических выражений определяется довольно простыми таблицами решений. Например, для целочисленного сложения такая таблица приведена на рис.8.12. Правый операнд А2 R V +-----------------------------+ Левый | R | ADD A1,A2 | ADD A2,A1 | операнд |-----+-----------+-----------| A1 | V | ADD A1,A2 | MOVE A1,R | | | | ADD A2,R | +-----------------------------+ Рис. 8.12 Здесь имеется в виду, что R - операнд на регистре, V - операнд - переменная или константа. Такая таблица решений должна также учитывать коммутативность операций. Эта таблица решений реализуется следующим правилом: RULE IntExpr ::= 'PLUS' IntExpr IntExpr SEMANTICS if (Address<2>.AddrMode<>D) and (Address<3>.AddrMode<>D) then Address<0>.AddrMode:=D; Address<0>.Addreg:=GetFree(RegSet ); Emit2(MOVE,Address<2>,Address<0>); Emit2(ADD,Address<2>,Address<0>); else if (Address<2>.AddrMode=D) then Emit2(ADD,Address<3>,Address<2>); Address<0>:=Address<2>); else Emit2(ADD,Address<2>,Address<3>); Address<0>:=Address<3>); end end. 8.6. Распределение регистров при вычислении арифметических выражений Одной из важнейших задач при генерации кода является распределение регистров. Рассмотрим хорошо известную технику распределения регистров при трансляции арифметических выражений, называемую алгоритмом Сети-Ульмана. Пусть система команд машины имеет неограниченное число универсальных регистров, в которых выполняются арифметические команды. Рассмотрим, как можно сгенерировать код, используя для данного арифметического выражения минимальное число регистров. | / \ R1 /\ \ -- /\ R2 /\ \ -- /\ Rn /\ \ -- \ /\LR L/\/\R ---- Рис. 8.13 Предположим сначала, что распределение регистров осуществляется по простейшей схеме слева-направо, как изображено на рис. 8.13. Тогда к моменту генерации кода для поддерева LR занято n регистров. Пусть поддерево L требует nl регистров, а поддерево R - nr регистров. Если nl=nr, то при вычислении L будет использовано nl регистров и под результат будет занят n+1-й регистр. Еще nr (=nl) регистров будет использовано при вычислении R. Таким образом, общее число использованных регистров будет равно n+nl+1. Если nl>nr, то при вычислении L будет использовано nl регистров. При вычислении R будет использовано nr =lr Рис. 8.14 Рис. 8.15 2) если вершина имеет прямых потомков с метками l1 и l2, то в качестве метки этой вершины выбираем большее из чисел l1 или l2 либо число l1+1, если l1=l2. Эта разметка позволяет определить, какое из поддеревьев требует большего количества регистров для своего вычисления. Затем осуществляется распределение регистров для результатов операций. Правила распределения регистров: 1) Корню назначается первый регистр. 2) Если метка левого потомка меньше метки правого, то левому потомку назначается регистр на единицу больший, чем предку, а правому - с тем же номером (сначала вычисляется правое поддерево и его результат помещается в регистр R). Если же метка левого потомка больше или равна метке правого потомка, то наоборот, сначала вычисляется левое поддерево и его результат помещается в регистр R (рис. 8.15). После этого формируется код по следующим правилам. Правила генерации кода: 1) если вершина - правый лист с меткой 1, то ей соответствует код LOAD X,R, где R - регистр, назначенный этой вершине, а X - адрес переменной, связанной с вершиной (рис. 8.16.б); 2) если вершина внутренняя и ее левый потомок - лист с меткой 0, то ей соответствует код Код правого поддерева Op X,R где снова R - регистр, назначенный этой вершине, X - адрес переменной, связанной с вершиной, а Op - операция, примененная в вершине (рис. 8.16.а); 3) если непосредственные потомки вершины не листья и метка правой вершины больше метки левой, то вершине соответствует код Код правого поддерева Код левого поддерева Op R+1,R где R - регистр, назначенный внутренней вершине, и операция Op, вообще говоря, не коммутативная (рис. 8.17 б)). R R R R | | | | / \ / \ / \ / \ / \R R / \ R/ \R+1 R+1/ \R X /\ /\ X /\ /\ /\ /\ (0) -- -- (1) -- -- -- -- а) б) а) б) Рис. 8.16 Рис. 8.17 Если метка правой вершины меньше или равна метке левой вершины, то вершине соответствует код Код левого поддерева Код правого поддерева Op R,R+1 MOVE R+1,R Последняя команда генерируется для того, чтобы получить результат в нужном регистре (в случае коммутативной операции операнды операции можно поменять местами и избежать дополнительной пересылки)(рис. 8.17 а)). Рассмотрим атрибутную грамматику, реализующую эти правила генерации кода. В этой атрибутной грамматике генерация кода происходит не непосредственно в процессе обхода дерева, как раньше, а из-за необходимости переставлять поддеревья код строится в виде текста с помощью операции конкатенации. Практически, конечно, это нецелесообразно: разумнее управлять обходом дерева непосредственно, однако для простоты мы будем пользоваться конкатенацией. RULE Expr ::= IntExpr SEMANTICS Reg<1>:=1; Left<1>:=true. RULE IntExpr ::= Term AddOp IntExpr SEMANTICS Left<1>:=true; Left<3>:=false; Label<0>:=if Label<1>=Label<3> then Label<1>+1 else Max(Label<1>,Label<3>); Reg<1>:=if Label<1> < Label<3> then Reg<0>+1 else Reg<0>; Reg<3>:=if Label<1> < Label<3> then Reg<0> else Reg<0>+1; Code<0>:=if Label<1>=0 then Code<3>||Code<2> ||Code<3>||","||Reg<0> else if Label<1> < Label<3> then Code<3>||Code<1>||Code<2>|| Reg<0>+1||","|| Reg<0> else Code<1>||Code<3>||Code<2>|| Reg<0>||","||Reg<0>+1 ||"MOVE"||Reg<0>+1 ||","||Reg<0>. IntExpr ::= Term => Left<1>:=Left<0>; Code<0>:=Code<1>; Label<0>:=Label<1>; Reg<1>:=Reg<0>. RULE Term::= Factor MultOp Term SEMANTICS Left<1>:=true; Left<3>:=false; Label<0>:=if Label<1>=Label<3> then Label<1>+1 else Max(Label<1>,Label<3>); Reg<1>:=if Label<1> < Label<3> then Reg<0>+1 else Reg<0>; Reg<3>:=if Label<1> < Label<3> then Reg<0> else Reg<0>+1; Code<0>:=if Label<1>=0 then Code<3>||Code<2> ||Code<3>||",""||Reg<0> else if Label<1> < Label<3> then Code<3>||Code<1>||Code<2>|| Reg<0>+1||","|| Reg<0> else Code<1>||Code<3>||Code<2>|| Reg<0>||","||Reg<0>+1 ||"MOVE"||Reg<0>+1 ||","||Reg<0>. RULE Term ::= Factor SEMANTICS Left<1>:=Left<0>; Code<0>:=Code<1>; Label<0>:=Label<1>; Reg<1>:=Reg<0>. RULE Factor ::= Ident SEMANTICS Label<0>:=if Left<0> then 0 else 1; Code<0>:=if not Left<0> then "LOAD"||Reg<0>||","||Val<1> else Val<1>. RULE Factor ::= ( IntExpr ) SEMANTICS Left<2>:=Left<0>; Code<0>:=Code<2>; Label<0>:=Label<2>; Reg<2>:=Reg<0>. RULE AddOp ::= '+' SEMANTICS Code<0>:="ADD". RULE AddOp ::= '-' Code<0>:="SUB". RULE MultOp ::= '*' SEMANTICS Code<0>:="MUL". RULE MultOp ::= '/' SEMANTICS Code<0>:="DIV". Expr | IntExpr / | \ Left=true / | \Label=2 / | \Reg=1 Term AddOp IntExpr / | \ Left=true| / | \ Left=false / | \Label=1 | / | \Label=2 / | \Reg=2 | / | \ / | \ + / | \ Factor MultOp Term Factor MultOp Term |Left=true | |Left=false |Left=true | |Left=false |Label=0 | |Label=1 |Label=0 | |Label=1 |Reg=2 * |Reg=3 |Reg=1 * |Reg=1 Ident Ident Ident Factor A B C | Left=false | Label=1 ----------------- Reg=1 /|\ ( | ) IntExpr / | \ Left=false / | \Label=1 / | \Reg=1 Term AddOp IntExpr |Left=true | | Left=false |Label=0 | | Label=1 |Reg=2 + | Reg=1 Factor Term |Left=true | Left=false |Label=0 | Label=1 |Reg=2 | Reg=1 Ident Factor D | Left=false | Label=1 | Reg=1 Ident E Рис. 8.18. Атрибутированное дерево для выражения A*B+C*(D+E) приведено на рис. 8.18. При этом будет сгенерирован следующий код: LOAD E,R1 ADD D,R1 MUL C,R1 LOAD B,R2 MUL A,R2 ADD R2,R1 Приведенная атрибутная схема требует двух проходов по дереву выражения. Рассмотрим теперь другую атрибутную схему, в которой достаточно одного обхода для генерация программы для выражений с оптимальным распределением регистров [9]. Пусть мы произвели разметку дерева разбора так же, как и в предыдущем алгоритме. Назначение регистров будем производить в соответствии со схемой рис. 8.19. Левому потомку всегда назначается регистр, равный его метке, а правому - его метке, если она не равна метке его левого брата, и метке +1, если метки равны. Поскольку более сложное поддерево всегда вычисляется раньше более простого, его регистр результата имеет больший номер, чем любой регистр, используемый при вычислении более простого поддерева, что гарантирует правильность использования регистров. | ^ | | Label / \ / \ / \ Left=0 /Label-->Left\ /\ /\ Reg<0>:=if (Left<0>=Label<0>) / \ / \ &(Left<0>#0) / \ / \ then Label<0>+1 / \ /\ /\ else Label<0> / \ / \ / \ ---------- ---- ---- Рис. 8.19. Приведенные соображения реализуются следующей атрибутной схемой: RULE Expr ::= IntExpr SEMANTICS Code<0>:=Code<1>; Left<1>:=true. RULE IntExpr ::= Term AddOp IntExpr SEMANTICS Left<1>:=true; Left<3>:=false; Label<0>:=if Label<1>=Label<3> then Label<1>+1 else Max(Label<1>,Label<3>); Code<0>:=if Label<3> > Label<1> then if Label<1>=0 then Code<3>||Code<2>||Code<1> ||","||Label<3> else Code<3>||Code<1>||Code<2>|| Label<1>||","||Label<3> else if Label<3> < Label<1> then Code<1>||Code<3>||Code<2>|| Label<1>||","||Label<3>|| "MOVE"||Label<3>||","|| Label<1> else {Label<3>=Label<1>} Code<3>||"MOVE"||Label<3>|| ","||Label<3>+1||Code<1>|| Code<2>||Label<1>||","|| Label<1>+1. RULE IntExpr ::= Term SEMANTICS Left<1>:=Left<0>; Code<0>:=Code<1>; Label<0>:=Label<1>. RULE Term ::= Factor MultOp Term SEMANTICS Left<1>:=true; Left<3>:=false; Label<0>:=if Label<1>=Label<3> then Label<1>+1 else Max(Label<1>,Label<3>); Code<0>:=if Label<3> > Label<1> then if Label<1>=0 then Code<3>||Code<2>||Code<1> ||","||Label<3> else Code<3>||Code<1>||Code<2>|| Label<1>||","||Label<3> else if Label<3> < Label<1> then Code<1>||Code<3>||Code<2>|| Label<1>||","||Label<3>|| "MOVE"||Label<3>||","|| Label<1> else {Label<3>=Label<1>} Code<3>||"MOVE"||Label<3>|| ","||Label<3>+1||Code<1>|| Code<2>||Label<1>||","|| Label<1>+1. RULE Term ::= Factor SEMANTICS Left<1>:=Left<0>; Code<0>:=Code<1>; Label<0>:=Label<1>. RULE Factor ::= Ident SEMANTICS Label<0>:=if Left<0> then 0 else 1; Code<0>:=if Left<0> then Val<1> else "LOAD"||Val<1>||"R1". RULE Factor ::= ( IntExpr ) SEMANTICS Left<2>:=Left<0>; Code<0>:=Code<2>; Label<0>:=Label<2>. RULE AddOp ::= '+' SEMANTICS Code<0>:="ADD". RULE AddOp ::= '-' SEMANTICS Code<0>:="SUB". RULE MultOp ::= '*' SEMANTICS Code<0>:="MUL". RULE MultOp ::= '/' SEMANTICS Code<0>:="DIV". Команды пересылки требуются для согласования номеров регистров, в которых осуществляется выполнение операции, с регистрами, в которых должен быть выдан результат. Это имеет смысл, когда эти регистры разные. Получиться это может из-за того, что по приведенной схеме результат выполнения операции всегда находится в регистре с номером метки, а метки левого и правого поддеревьев могут совпадать. Для выражения A*B+C*(D+E) будет сгенерирован следующий код: LOAD E,R1 - загрузить E на 1 регистр ADD D,R1 - сложить D и E и результат заслать в 1 регистр MUL C,R1 - умножить C на D+E с результатом в 1 регистре MOVE R1,R2 - переслать результат в регистр R2 LOAD B,R1- загрузить B в 1 регистр MUL A,R1 - умножить A на B с результатом в 1 регистре ADD R1,R2 - сложить A*B и C*(D+E) и результат заслать во 2 регистр В приведенных атрибутных схемах предполагалось, что регистров достаточно, чтобы правильно странслировать любое выражение. Если это не так, приходится усложнять схему трансляции и при необходимости сбрасывать содержимое регистров в память (или магазин). 8.7. Трансляция логических выражений Логические выражения, включающие логическое умножение, логическое сложение и отрицание, можно вычислять как непосредственно, используя таблицы истинности, так и с помощью условных выражений, пользуясь очевидными правилами: A & B эквивалентно if A then B else False, A v B эквивалентно if A then True else B. Если в качестве компонент выражений могут входить функции с побочным эффектом, то, вообще говоря, результат вычисления может зависеть от способа вычисления. В некоторых языках программирования не оговаривается, каким способом должны вычисляться логические выражения (например, в Паскале), в некоторых требуется, чтобы вычисления производились тем или иным способом (например, в Модуле-2 требуется, чтобы выражения вычислялись по приведенным формулам), в некоторых языках есть возможность явно задать способ вычисления (Си, Ада). Вычисление логических выражений непосредственно по таблицам истинности аналогично вычислению арифметических выражений, поэтому мы не будем их рассматривать отдельно. Рассмотрим подробнее способ вычисления с помощью приведенных выше формул (будем называть его "вычисления с условными переходами"). Иногда такой способ рассматривают как оптимизацию вычисления логических выражений. Рассмотрим следующую атрибутную грамматику со входным языком логических выражений: RULE Expr ::= BoolExpr SEMANTICS FalseLab<1>:=False; TrueLab<1>:=True. RULE BoolExpr ::= BoolExpr '&' BoolExpr SEMANTICS FalseLab<1>:=FalseLab<0>; TrueLab<1>:=NodeLab<3>; FalseLab<3>:=FalseLab<0>; TrueLab<3>:=TrueLab<0>. RULE BoolExpr ::= BoolExpr 'V' BoolExpr SEMANTICS TrueLab<1>:=TrueLab<0>; FalseLab<1>:=NodeLab<3>; FalseLab<3>:=FalseLab<0>; TrueLab<3>:=TrueLab<0>. RULE BoolExpr ::= F SEMANTICS GOTO FalseLab<0>. RULE BoolExpr ::= T SEMANTICS GOTO TrueLab<0>. Здесь предполагается, что все вершины дерева занумерованы и номер вершины дает атрибут NodeLab. Метки вершин передаются, как это изображено на рис. 8.20. TrueLab TrueLab FalseLab\ FalseLab\ / | \\ /| \\ / / \ \\ // \ \\ / / & \ \\ // V \ \\ / / \ \\ // \ \\ FalseLab / \ \TrueLab TrueLab/ \ \TrueLab / \FalseLab / \ FalseLab TrueLab<-------NodeLabel FalseLab<---NodeLabel Рис. 8.20. Сопоставим каждому атрибутированному дереву в этой атрибутной грамматике текст (трансляцию), полученный следующим образом в результате обхода дерева сверху вниз слева направо: при входе в вершину будем генерировать ее номер, в вершине F будем генерировать текст GOTO значение атрибута FalseLab<0>, в вершине T - GOTO значение атрибута TrueLab<0>. Например, для выражения F V ( F & T & T ) V T получим атрибутированное дерево и трансляцию, изображенные на рис. 8.21 и 8.22.: F V ( F & T & T ) V T | FalseLab=False 1 TrueLab=True / TrueLab=True / V \ FalseLab=2 / \ FalseLab=False F 2 TrueLab=True / \ TrueLab=True / V \ FalseLab=3 / \ / \ 4 3 / \ | TrueLab=5 / & \ T FalseLab=3 / \ TrueLab=True / \ FalseLab=3 F 5 / \ TrueLab=6 / & \ 1: GOTO 2 FalseLab=3 / \ TrueLab=True 2: / \ FalseLab=3 4: GOTO 3 T 6 5: GOTO 6 | 6: GOTO True T 3: GOTO True Рис. 8.21 Рис. 8.22 Эту линеаризованную запись можно трактовать как программу вычисления логического значения: каждая строка может быть помечена номером вершины и содержать либо переход на другую строку, либо переход на True или False, что соответствует значению выражения true или false, либо пусто. Будем говорить, что полученная программа вычисляет (или интерпретирует) значение выражения, если в результате ее выполнения (от первой строки) мы придем к строке, содержащей GOTO True или GOTO False. Утверждение 1. Для каждого набора входных данных любого логического выражения программа, полученная в результате обхода дерева этого выражения, завершается со значением логического выражения в обычной интерпретации, т.е. осуществляется переход на True для значения, равного T, и переход на метку False для значения F. Это утверждение является частным случаем следующего. Утверждение 2. В результате интерпретации поддерева с некоторыми значениями атрибутов FalseLab и TrueLab в его корне выполняется команда GOTO TrueLab, если значение выражения истинно, и команда GOTO FalseLab, если значение выражения ложно. Доказательство можно провести индукцией по высоте дерева. Для деревьев высоты 1, соответствующих правилам BoolExpr ::= F и BoolExpr ::= T, утверждение очевидно из правил грамматики. Пусть дерево имеет высоту n>1. Зависимость атрибутов для дизъюнкции и конъюнкции приведена на рис. 8.23 | FalseLab0 | TrueLab0 / \ / & \ FalseLab1=FalseLab0 / \ FalseLab2=FalseLab0 TrueLab1=NodeLab2 / \ TrueLab2=TruLab0 /\ /\ / \ / \ ---- ---- 147 | FalseLab0 | TrueLab0 / \ / V \ FalseLab1=NodeLab2 / \ FalseLab2=FalseLab0 TrueLab1=TruLab0 / \ TrueLab2=TruLab0 /\ /\ / \ / \ ---- ---- Рис. 8.23 Если для конъюнкции значение левого поддерева ложно и по индукции вычисление левого поддерева завершается командой GOTO FalseLab1, то и интерпретация всего дерева завершается командой GOTO FalseLab0 (=FalseLab1). Если значение левого поддерева истинно, то его интерпретация завершается командой GOTO TrueLab1 (=NodeLab2). Если значение правого поддерева ложно, то интерпретация всего дерева завершается командой GOTO FalseLab0 (=FalseLab2). Если же оно истинно, интерпретация всего дерева завершается командой GOTO TrueLab0 (=TrueLab2). Аналогично - для дизъюнкции. Доказательство утверждения 1 следует из того, что метками вершины дерева логического выражения являются TrueLab=True и FalseLab=False. Добавим теперь новое правило в предыдущую грамматику: BoolExpr ::= Ident SEMANTICS else GOTO FalseLab<0>>; Тогда, например, для предыдущего выражения получим следующую программу: 1: if Ident=T then GOTO True else GOTO 2 2: 4: if Ident=T then GOTO 5 else GOTO 3 5: if Ident=T then GOTO 6 else GOTO 3 6: if Ident=T then GOTO True else GOTO 3 3: if Ident=T then GOTO True else GOTO False При каждом конкретном наборе данных эта программа превращается в программу вычисления логического значения. Утверждение 3. В каждой строке программы, сформированной предыдущей атрибутной схемой, одна из меток совпадает с меткой следующей строки. Действительно, по правилам наследования атрибутов TrueLab и FalseLab, в правилах для дизъюнкции и конъюнкции либо FalseLab, либо TrueLab принимает значение метки следующего поддерева. Кроме того, как значение FalseLab, так и значение TrueLab, передаются в правое поддерево от предка. Таким образом, самый правый потомок всегда имеет одну из меток TrueLab или FalseLab, равную метке правого брата соответствующего поддерева. Учитывая порядок генерации команд, получаем утверждение. Дополним теперь атрибутную грамматику следующим образом: RULE Expr ::= BoolExpr SEMANTICS FalseLab<1>:=False; TrueLab<1>:=True; Sign<1>:=false. RULE BoolExpr ::= BoolExpr & BoolExpr SEMANTICS FalseLab<1>:=FalseLab<0>; TrueLab<1>:=NodeLab<3>; FalseLab<3>:=FalseLab<0>; TrueLab<3>:=TrueLab<0>; Sign<1>:=false; Sign<3>:=Sign<0>. RULE BoolExpr ::= BoolExpr V BoolExpr SEMANTICS TrueLab<1>:=TrueLab<0>; FalseLab<1>:=NodeLab<3>; FalseLab<3>:=FalseLab<0>; TrueLab<3>:=TrueLab<0>; Sign<1>:=true; Sign<3>:=Sign<0>. RULE BoolExpr ::= not BoolExpr SEMANTICS FalseLab<1>:=TrueLab<0>; TrueLab<1>:=FalseLab<0>; Sign<1>:=not Sign<0>. RULE BoolExpr ::= F SEMANTICS GOTO FalseLab<0>. RULE BoolExpr ::= T SEMANTICS GOTO TrueLab<0>. RULE BoolExpr ::= Ident SEMANTICS if Sign<0> then else GOTO FalseLab<0>> else else GOTO TrueLab<0>>; Правила наследования атрибута Sign приведены на рис. 8.24. false | true | false | true | or or and and /\ /\ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ true false true true false false false true true | false | | | not not | | | | false true Рис. 8.24 Программу желательно сформировать таким образом, чтобы else- метка была как раз меткой следующей вершины. Как это можно сделать, следует из утверждения 4. Утверждение 4. В каждой терминальной вершине, метка ближайшего правого для нее поддерева равна значению атрибута FalseLab этой вершины, тогда и только тогда, когда значение атрибута Sign этой вершины равно true, и наоборот, метка ближайшего правого для нее поддерева равна значению атрибута TrueLab этой вершины, тогда и только тогда, когда значение атрибута Sign равно false. Эти два утверждения позволяют заменить последнее правило атрибутной грамматики следующим образом: RULE BoolExpr ::= Ident SEMANTICS if Sign<0> then > else >. В свою очередь, при генерации машинных команд это правило можно заменить на следующее: RULE BoolExpr ::= Ident SEMANTICS ; if Sign<0> then > else >. Если элементом логического выражения является сравнение, то генерируется команда, соответствующая знаку сравнения (beq для =, bne для <>, bge для >= и т.д.), если атрибут sign соответствующей вершины имеет значение true, и отрицание (bne для =, beq для <>, blt для >= и т.д.), если атрибут sign имеет значение false. Приведем несколько примеров. Выражение A AND (B OR C) транслируется в последовательность команд рис. 8.25. Выражение (NOT((A=B)OR(C<>D)))AND(not((E H))) транслируется в последовательность команд рис. 8.26. TST A CMP A,B BEQ False BEQ False TST B CMP C,D BNE True BNE False TST C CMP E,F BEQ False BGE False True: CMP G,H False:. . . BGT False True: False: Рис. 8.25 Рис. 8.26 8.8. Выделение общих подвыражений Выделение общих подвыражений проводится на линейном участке и основывается на двух положениях. 1. Поскольку на линейном участке переменной может быть несколько присваиваний, то при выделении общих подвыражений необходимо различать вхождения переменных до и после присваивания. Для этого каждая переменная снабжается номером. Вначале номера всех переменных устанавливаются равными 0. При каждом присваивании переменной ее номер увеличивается на 1. 2. Выделение общих подвыражений осуществляется при обходе дерева выражения снизу вверх слева направо. При достижении очередной вершины (пусть операция, примененная в этой вершине, есть бинарная 'op'; в случае унарной операции рассуждения те же) просматриваем общие подвыражения, связанные с op. Если имеется выражение, связанное с op и такое, что его левый операнд есть общее подвыражение с левым операндом нового выражения, а правый операнд - общее подвыражение с правым операндом нового выражения, то объявляем новое выражение общим с найденным и в новом выражении запоминаем указатель на найденное общее выражение. Базисом построения служит переменная: если операндами обоих выражений являются одинаковые переменные с одинаковыми номерами, то они являются общими подвыражениями. Если выражение не выделено как общее, оно заносится в список операций, связанных с op (рис. 8.27). |<-----| op |<-------| / \ / \ / \ / \ +---->/\ /\<-----+ +-----/\ /\---+ | / \ / \ | | / \ / \ | | ---- ---- | | ---- ---- | | +-+---------------+ +--------------------+ Рис.8.27 Рассмотрим теперь реализацию алгоритма выделения общих подвыражений. Поддерживаются следующие глобальные переменные: Table - таблица переменных; для каждой переменной хранится ее номер (Count) и указатель на вершину дерева выражений, в которой переменная встретилась в последний раз в левой части (Last); OpTable - таблица списков общих подвыражений, связанных с каждой операцией (Addr - указатель на вершину дерева, List - продолжение списка); С каждой вершиной дерева выражения связана запись: NodeType = record Left -- левый потомок вершины; Right -- правый потомок вершины; Comm -- указатель на предыдущее общее подвыражение; Flag -- признак, является ли поддерево общим подвыражением; Varbl -- признак, является ли вершина переменной; VarCount -- номер переменной; end; Все общие подвыражения собраны в список (с типом элемента LisType), начинающийся с OpTable[Op], как это изображено на рис. 8.28. |<------------|<-------------|<---------| | Op / \ / \ / \ OpTable / \ / \ / \ /\ /\ /\ /\ /\ /\ / \ / \ / \ / \ / \ / \ ---- ---- ---- ---- ---- ---- Рис. 8.28 Выделение общих подвыражений и построение дерева осуществляются приведенными ниже правилами. Атрибут Entry нетерминала Variable дает указатель на переменную в таблице. Атрибут Val символа Op дает код операции. Атрибут Node символов IntExpr и Assignment дает указатель на запись типа NodeType соответствующего нетерминала. RULE Assignment ::= Variable IntExpr SEMANTICS Table[Entry<1>].Count:=Table[Entry<1>].Count+1. {Увеличить счетчик присваиваний переменной} RULE IntExpr ::= Variable SEMANTICS with Node<0>^ do with Table[Entry<1>] do if Last<>NIL { Переменная уже была использована } and Last^.VarCount = Count then { С тех пор переменной не было присваивания } Flag:=true; { Переменная - общее подвыражение } Comm:=Last; { Указатель на общее подвыражение } else Flag:=false; end; Last:=^Node<0>; {Указатель на последнее использование переменной} VarCount:=Count; {Номер использования переменной} Varbl:=true; {Выражение - переменная} end end. RULE IntExpr ::= Op IntExpr IntExpr SEMANTICS var L:pointer to Listype; {Тип списков операции} if Node<2>^.Flag and Node<3>^.Flag then { И справа, и слева - общие подвыражения } L:=OpTable[Val<1>]; { Начало списка общих подвыражений для операции } while L<>nil do if (Node<2>=L^.Left) and (Node<3>=L^.Right) { Левое и правое поддеревья совпадают } then exit else L:=L^.List;{Следующий элемент списка} end end else L:=nil; {Не общее подвыражение} end; with Node<0>^ do Varbl:=false; { Не переменная } Comm:=L; {Указатель на предыдущее общее подвыражение или nil} if L<>nil then Flag:=true; {Общее подвыражение} Left:=Node<2>; { Указатель на левое поддерево } Right:=Node<3>; { Указатель на правое поддерево } else Flag:=false; { Данное выражение не может рассматриваться как общее } { Если общего подвыражения с данным не было, включить данное в список для операции } new(L); L^.Addr:=^Node<0>; L^.List:=OpTable[Val<1>]; OpTable[Val<1>]:=L; end end. Рассмотрим теперь некоторые простые правила распределения регистров при наличии общих подвыражений. Если число регистров ограничено, можно выбрать один из следующих двух вариантов. 1. При обнаружении общего подвыражения с подвыражением в уже просмотренной части дерева (и, значит, с уже распределенными регистрами) проверяем, расположено ли его значение на регистре. Если да, и если регистр после этого не менялся, заменяем вычисление поддерева на значение в регистре. Если регистр менялся, то вычисляем подвыражение заново. 2. Вводим еще один проход. На первом проходе распределяем регистры. Если в некоторой вершине обнаруживается, что ее поддерево общее с уже вычисленным ранее, но значение регистра потеряно, то в такой вершине на втором проходе необходимо сгенерировать команду сброса регистра в рабочую память. Выигрыш в коде будет, если стоимость команды сброса регистра + доступ к памяти в повторном использовании этой памяти не превосходит стоимости заменяемого поддерева. Поскольку стоимость команды MOVE известна, можно сравнить стоимости и принять оптимальное решение: то ли метить предыдущую вершину для сброса, то ли вычислять полностью поддерево. 8.9. Генерация оптимального кода методами синтаксического анализа 8.9.1. Сопоставление образцов Техника генерации кода, рассмотренная выше, основывалась на однозначном соответствии структуры промежуточного представления и описывающей это представление грамматики. Для генерации более качественного кода может быть применен подход, изложенный в настоящей главе. Этот подход основан на понятии "сопоставления образцов": командам машины сопоставляются некоторые "образцы", вхождения которых ищутся в промежуточном представлении программы, и делается попытка "покрыть" промежуточную программу такими образцами. Если это удается, то по образцам восстанавливается программа уже в кодах. := | ------------- / \ + + / \ / \ / \ / \ const(a) const(x) @ const(5) | | + / \ / \ + @ / \ | / \ | const(b) const(y) + / \ / \ const(i) const(z) Рис. 8.29 На рис. 8.29 показано промежуточное дерево для оператора a:=b[i]+5, где a,b,i - локальные переменные, хранимые со смещениями x,y,z в областях данных с одноименными адресами. Элемент массива b занимает память в одну машинную единицу. 0-местная операция const возвращает значение атрибута соответствующей вершины промежуточного дерева, указанного на рисунке в скобках после оператора. Одноместная операция '@' означает косвенную адресацию и возвращает содержимое регистра или ячейки памяти, имеющей адрес, задаваемый аргументом оператора. +------------------------------------------------------+ |Но-| Образец |Машинная команда |Стоимость| |мер| |Правило грамматики| | |---+---------------------+----------------------------| | 1 | const(c) | MOV #c,Ri | 2 | | | | Reg->Const | | |---+---------------------+-----------------------+----| | 2 | := | MOV Rj,c(Ri) | 4 | | | / \ | | | | | / \ | | | | | + reg(j) | | | | | / \ | Stat->':=' '+' Reg | | | |reg(i) const(c) | Const Reg | | |---+---------------------+-----------------------+----| | 3 | @ | MOV c(Rj),Ri | 4 | | | | | | | | | + | | | | | / \ | | | | | / \ |Contents -> '@' '+' Reg| | | | reg(j) const(c) | Const | | |---+---------------------+-----------------------+----| | 4 | + | ADD #c,Ri | 3 | | | / \ | | | | | / \ | | | | | reg(i) const(c) |Reg -> '+' Reg Const | | |---+---------------------+-----------------------+----| | 5 | + | ADD Rj,Ri | 2 | | | / \ | | | | | / \ | | | | | reg(i) reg(j) | Reg -> '+' Reg Reg | | |---+---------------------+-----------------------+----| | 6 | + | ADD c(Rj),Ri | 4 | | | / \ | | | | | / \ | | | | |reg(i) @ | | | | | | | Reg -> '+' Reg '@' | | | | + | '+' Reg Const | | | | / \ | | | | | reg(j) const(c) | | | |---+---------------------+-----------------------+----| | 7 | @ | MOV (R),R | 2 | | | | | | | | | Reg | Reg -> Contents | | +------------------------------------------------------+ Рис. 8.30 ----------[stat]---------------------------------- |2 := | | / \ | | + \ | | / \ \ | |reg(Ra) const(x) \ | |const(a) \ | | ------------------[reg(Rb)]------------------ | | | 4 + | | | | / \ | | | | / const(5) | | | | / | | | | ---------------[reg(Rb)]------------------ | | | | | 7 @ | | | | | | | | | | | | | -------------[reg(Rb)]---------------- | | | | | | |6 + | | | | | | | | / \ | | | | | | | | / \ | | | | | | | | ------[reg(Rb)]---- \ | | | | | | | | |4 + | @ | | | | | | | | | / \ | | | | | | | | | | | / \ | | | | | | | | | | | reg(Rb) const(y)| + | | | | | | | | | const(b) | / \ | | | | | | | | ------------------- / \ | | | | | | | | / \ | | | | | | | | reg(Ri) const(z) | | | | | | | | const(i) | | | | | | | -------------------------------------- | | | | | ------------------------------------------ | | | ---------------------------------------------- | -------------------------------------------------- Рис. 8.31 На рис.8.30 показан пример сопоставления образцов машинным командам. Приведены два варианта задания образца: в виде дерева и в виде правила контекстно-свободной грамматики. Для каждого образца указана машинная команда, реализующая этот образец, и стоимость этой команды. Стоимость может определяться различными способами, и здесь мы не рассматриваем этого вопроса. На рис. 8.31 приведен пример покрытия промежуточного дерева рис. 8.29 образцами рис. 8.30. В рамки заключены фрагменты дерева, сопоставленные образцу правила, номер которого указывается в левом верхнем углу рамки. В квадратных скобках указаны результирующие вершины. Приведенное покрытие дает такую последовательность команд: MOVE b,Rb ADD #y,Rb MOVE i,Ri ADD z(Ri),Rb MOV (Rb),Rb ADD #5,Rb MOVE a,Ra MOV Rb,x(Ra) Как правило, одни и те же конструкции исходной (или промежуточной) программы можно реализовать различными последовательностями машинных команд. Это соответствует тому, что имеются различные покрытия промежуточного представления. Задача выбора команд состоит в том, чтобы выбрать наилучший способ реализации того или иного действия или последовательности действий, т. е. выбрать в некотором смысле оптимальное покрытие. Для выбора оптимального покрытия было предложено несколько интересных алгоритмов, в частности использующих динамическое программирование [10,11]. Мы здесь рассмотрим алгоритм [12], комбинирующий возможности синтаксического анализа и динамического программирования, в основу которого положен синтаксический анализ неоднозначных грамматик (модифицированный алгоритм Кока, Янгера и Касами [13,14]) более эффективный в реальных приложениях. Этот же метод может быть применен и тогда, когда в качестве промежуточного представления используется дерево. 8.9.2. Синтаксический анализ для T-грамматик Обычно код генерируется из некоторого промежуточного языка с довольно жесткой структурой. В частности, для каждой операции известна ее размерность (число операндов). Назовем грамматики, удовлетворяющие этим ограничениям, T-грамматиками. Образцы, соответствующие машинным командам, задаются правилами грамматики (вообще говоря, неоднозначной). Генератор кода анализирует входное префиксное выражение и строит одновременно все возможные деревья разбора. После окончания разбора выбирается дерево с наименьшей оценкой. Затем по этому единственному оптимальному дереву генерируется код. Для T-грамматик все цепочки, выводимые из любого нетерминала A, являются префиксными выражениями с фиксированной арностью операций. Длины всех выражений из входной цепочки a1...an можно предварительно вычислить. Поэтому можно проверить, сопоставимо ли правило с подцепочкой ai...ak входной цепочки a1...an, проходя слева-направо по ai...ak. В процессе прохода по цепочке предварительно вычисленные длины префиксных выражений используются для того, чтобы перейти от одного терминала к следующему терминалу, пропуская подцепочки, соответствующие нетерминалам правой части правила. Цепные правила не зависят от операций, следовательно, их необходимо проверять отдельно. Применение одного цепного правила может зависеть от применения другого цепного правила. Следовательно, применение цепных правил необходимо проверять циклически до тех пор, пока нельзя применить ни одно из цепных правил. Мы предполагаем, что в грамматике нет циклов в применении цепных правил. Тип Titem в алгоритме 8.1 ниже служит для описания ситуаций (т.е. правил вывода и позиции внутри правила). Тип Tterminal - это тип терминального символа грамматики, тип Tproduction - тип для правила вывода. r[i]={A->aiV1...Vm} | /\ | / \ | 1 /\ /\m | / \ / \ |---------|----------------|-----| ai l[i] Рис. 8.32 Алгоритм 8.1: var a:array[1..n] of Tterminal; r:array[1..n] of set of Tproduction; l:array[1..n] of INTEGER; (* l[i] - длина a[i]-выражения*) h:Titem; (* используется при поиске правил, сопоставимых с текущей подцепочкой*) begin (* Предварительные вычисления *) Для каждой позиции i вычислить длину a[i]-выражения l[i]; (* Распознование входной цепочки *) for i:=n downto 1 do for для каждого правила A -> a[i] y из P do if l[i]>0 then j:=i+1; if l[i]>1 then (*Первый терминал a[i] уже проверен*) h:=[A->a[i].y]; repeat (*Сопоставимы ли a[i]y и a[i]..a[i+l[i]-1]*) Пусть h=[A->u.Xv] if X в T then if X=a[j] then j:=j+1 else exit end else (* X в N *) if X->w в r[j] then j:=j+l[j] else exit end end; h:=[A->uX.v]; (* Перейти к следующему символу*) until j=i+l[i]; end (*l[i]>1*); end (*l[i]>0*); if j=i+l[i] then r[i]:=r[i]+{(A->a[i]y)} end end (*for*); (* Проверить цепные правила *) while существует правило C->A из P такое, что имеется некоторый элемент (A->w) в r[i] и нет элемента (C->A) в r[i] do r[i]:=r[i]+{(C->A)} end end; (* for i *) Проверить, принадлежит ли (S->w) множеству r[1] end Работа алгоритма иллюстрируется рис. 8.32. Множества r[i] имеют размер O(|P|). Очевидно, что алгоритм имеет временную и емкостную сложность O(n). Рассмотрим вновь пример рис. 8.29. В префиксной записи приведенный фрагмент программы записывается следующим образом: := + a x + @ + + b y @ + i z 5 На рис. 8.33 приведен результат работы алгоритма. Правила вычисления стоимости приведены в разделе 8.9.3. +-----------------------------+ |Операция|Длина| Правила | | | | (стоимость) | |--------+-----+--------------| | := | 14 | 2(22) | | + | 2 | 4(5) 5(6) | | a | 0 | 1(2) | | x | 0 | 1(2) | | + | 9 | 4(16) 5(17)| | @ | 8 | 7(13) | | + | 7 | 5(15) 6(11)| | + | 2 | 4(5) 5(6) | | b | 0 | 1(2) | | y | 0 | 1(2) | | @ | 3 | 3(6) 7(7) | | + | 2 | 4(5) 5(6) | | i | 0 | 1(2) | | z | 0 | 1(2) | | 5 | 0 | 1(2) | +-----------------------------+ Рис. 8.33 Пусть G - это T-грамматика. Для каждой цепочки z из L(G) можно построить дерево выражения. Мы можем переписать алгоритм так, чтобы он работал с деревьями выражений, а не с префиксными выражениями. Этот вариант алгоритма приведен ниже. В этом алгоритме дерево выражения обходится сверху вниз и в нем ищутся поддеревья, сопоставимые с правыми частями правил из G. Обход дерева осуществляется процедурой PARSE. После обхода поддерева данной вершины в ней применяется процедура MATCHED, которая пытается найти все образцы, сопоставимые поддереву данной вершины. Для этого каждое правило-образец разбивается на компоненты в соответствии с встречающимися в нем операциями. Дерево обходится справа налево только для того, чтобы иметь соответствие с порядком вычисления в алгоритме 8.1. Очевидно, что можно обходить дерево вывода и слева направо. Структура данных, представляющая вершину дерева, имеет следующую форму: PTnode=^Tnode; Tnode=record op:Tterminal; son:array[1..MaxArity] of PTnode; rules:set of Tproduction end; В комментариях указаны соответствующие фрагменты алгоритма 8.1. Алгоритм 8.2: var root:PTnode; procedure PARSE(n:PTnode); procedure MATCHED(n:PTnode; h:Titem); var matching:boolean; begin пусть h=[A->u.Xvy], v= v1 v2 ... vm, m=Arity(X) if X in T then (* сопоставление правила *) if m=0 then (*if l[i]=0*) if X=n^.op (*if X=a[j]*) then return(true) else return(false) end else (* m>0 *) (*if l[i]>0*) if X=n^.op then (*if X=a[j]*) matching:=true; for i:=1 to m do (*j:=j+l[j] *) matching:=matching and (*until j=i+l[i]*) MATCHED(n^.son[i],[A->uXv'.vi v"y]) end; return(matching) (*h:=[A->uX.v]*) else return(false) end end else (*X in N*) (* поиск подвывода *) if в n^.rules имеется правило X->w in then return(true) else return(false) end end end (* match *) begin (*PARSE*) for i:=Arity(n^.op) downto 1 do (*for i:=n downto1*) PARSE(n^.son[i]) end; n^.rules:={}; for каждого правила A->bu из P такого, что b=n^.op do if MATCHED(n,[A->.bu]) (*if j=i+l[i]*) then n^.rules:=n^.rules+{(A->bu)} end end; (* Сопоставление цепных правил *) while существует правило C->A из P такое, что некоторый элемент (A->w) в n^.rules и нет элемента (C->A) в n^.rules do n^.rules:=n^.rules+{(C->A)} end end;(*PARSE*) begin (* Предварительные вычисления *) Построить дерево выражения для входной цепочки z; root:= указатель дерева выражения; (* Распознать входную цепочку *) PARSE(root); Проверить, принадлежит ли S->w множеству root^.rules; end Выходом алгоритма является дерево выражения для z, вершинам которого сопоставлены применимые правила. Если T-грамматика неоднозначная, то можно построить несколько различных выводов для заданной входной цепочки. Алгоритмы 8.1 и 8.2 "универсальные" в том смысле, что конкретные грамматики выражений и образцов являются, по- существу, параметрами этих алгоритмов. Для каждой конкретной грамматики можно написать свой алгоритм поиска образцов. Например, в случае нашей грамматики выражений и приведенных на рис. 8.30 образцов алгоритм 8.2 может быть представлен атрибутной грамматикой, приведенной ниже. Для каждого правила имеется два типа образцов: "внутренние", соответствующие правилам-образцам, и "внешние", приходящие сверху через атрибут Match предка. Атрибут Match представлен как вектор образцов вида . Каждый из образцов имеет вид либо , где op - оперция в данной вершине, а op-list - список ее операндов, либо образец - это нетерминал N. В первом случае op-list "распределяется" по потомкам вершины для дальнейшего сопоставления, во втором сопоставление считается успешным, если есть правило N->w, где w - состоит из образцов, успешно сопоставленных потомкам данной вершины. Помимо атрибута Match, образцы могут задаваться и в соответствии с правилами, возможно применимыми в данной вершине. Эти два множества образцов могут пересекаться. Синтезируемый атрибут Pattern (также вектор) дает результат сопоставления по вектору-образцу Match. Rule Stat ::= Expr ':=' Expr Этому правилу соответствует один образец 2. Поэтому в качестве образцов потомков через их атрибуты Match передаются, соответственно, <'+' Reg Const> и . Semantics Match<2>:=<'+' Reg Const>: Match<3>:= ; Pattern<0>[1]:=Pattern<2>[1]&Pattern<3>[1]. Rule Expr ::= '+' Expr Expr Образцы, соответствующие этому правилу, следующие: (4) Reg -> '+' Reg Const (5) Reg -> '+' Reg Reg (6) Reg -> '+' Reg '@' '+' Reg Const. Атрибутам Match второго и третьего символов в качестве образцов при сопоставлении могут быть переданы векторы и >, соответственно. Из анализа других правил можно заключить, что при сопоставлении образцов предков левой части данного правила атрибуту Match символа левой части может быть передан образец <'+' Reg Const> (из образцов 2,3,6) или образец Reg. Semantics Match<2>:= ; Match<3>:= >; P:=Pattern<2>&Pattern<3>; if Match<0> содержит образец <'+' Reg Const> в i-й позиции Pattern<0>[i]:=Pattern<2>[1]&Pattern<3>[1]; if Match[0] содержит Reg в j-й позиции Pattern<0>[j]:=(Pattern<2>[1]&Pattern<3>[1]) |(Pattern<2>[2]&Pattern<3>[2]) |(Pattern<2>[3]&Pattern<3>[3]); Остальным значениям Pattern<0> присвоить false. Rule Expr ::= '@' Expr Образцы, соответствующие этому правилу, следующие: (3) Reg -> '@' '+' Reg Const (7) Reg -> '@' Reg Соответственно, атрибуту Match второго символа в качестве образцов при сопоставлении могут быть переданы <'+' Reg Const> (образец 3) или (образец 7). Из анализа других правил можно заключить, что при сопоставлении образцов предков левой части данного правила атрибуту Match могут быть переданы образцы <'@' '+' Reg Const> (из образца 6) и Reg. Semantics Match<2>:=<<'+' Reg Const>,Reg>; if Match<0> содержит <'+' Reg Const> в i-й позиции Pattern<0>[i]:=Pattern<2>[1]; if Match<0> содержит Reg в j-й позиции Pattern<0>[j]:=Pattern<2>[1]|Pattern<2>[2]; Остальным значениям Pattern<0> присвоить false. Rule Expr ::= Const Semantics if Pattern<0> содержит Const в j-й позиции Pattern<0>[j]:=true; Остальным значениям Pattern<0> присвоить false. Для дерева рис. 8.29 получим значения атрибутов, приведенные на рис. 8.34. Здесь M обозначает Match, P - Pattern, C - Const, R - Reg. 8.9.3. Выбор дерева вывода наименьшей стоимости T-грамматики, описывающие системы комад, обычно являются неоднозначными. Чтобы сгенерировать код для некоторой входной цепочки, необходимо выбрать одно из возможных деревьев вывода. Это дерево должно представлять желаемое качество кода, например размер кода и/или время выполнения. Для выбора дерева из множества всех построенных деревьев вывода можно использовать атрибуты стоимости, атрибутные формулы, вычисляющие их значения, и критерии стоимости, которые оставляют для каждого нетерминала единственное применимое правило. Атрибуты стоимости сопоставляются всем нетерминалам, атрибутные формулы - всем правилам T-грамматики. M=<':=' '+' R C R> := P= | ------------- M=<<'+' R C>, / \ <'+' R R>, + + <'+' R <'@' '+' R C>> / \ / \P= / \ / \ const(a) const(x) @ const(5) M= M= > '+' R C>> | P= P= P= | | |M=<<'@' '+' R C, M=<'+' R C>, | <'@' R>> <'+' R R>, |P= <'+' R <'@' '+' R C>>| P= + / \ / \ M=<<'+' R C> / \ M=<<'@' '+' R C, <'+' R R> + @ <'@' R>> <'+' R <'@' / \ | P= '+' R C>> / \ | P= / \ | const(b) const(y) | M=<<'+' R C>, M= M= , P= <'@''+'R C>>+ <'+' R <'@' '+' R C>> P= / \P= / \ const(i) const(z) M= M= > P= P= Рис. 8.34 Предположим, что для вершины n обнаружено применимое правило p:A::=z0 X0 z1...Xk zk, где zi из T* для 0<=i<=k и Xj из N для 1<=j<=k. Вершина n имеет потомков n1,...,nk, которые соответствуют нетерминалам X1,...,Xk. Значения атрибутов стоимости вычисляются в порядке снизу вверх. Вначале атрибуты стоимости инициализируются неопределенным значением UndefinedValue. Предположим, что значения атрибутов стоимости для всех потомков n1,...,nk вершины n вычислены. Если формула A.a:=f(Xi.b,Xj.c,...) для 1<=i,j<=k сопоставлена правилу p, то выполняется формула n.a:=f(ni.b,nj.c,...), вычисляющая для правила p значение атрибута a нетерминала A в вершине n. Для всех примененных правил ищется такое, которое дает минимальное значение стоимости. Отсутствие примененных правил обозначается через undefined, значение которого полагается большим любого определенного значения. Добавим в алгоритм 8.2 реализацию атрибутов стоимости, формул их вычисления и критериев отбора. Из алгоритма можно исключить поиск подвыводов, соответствующих правилам, для которых значение атрибута стоимости не определено. Структура данных, представляющая вершину дерева, принимает следующий вид: PTnode=^Tnode; Tnode=record op:Tterminal; son:array[1..MaxArity] of PTnode; nonterm: array[Tnonterminal] of record CostAttr : ADDRESS; Production : Tproduction; end OperatorAttributes: ... end; Тело процедуры PARSE принимает вид begin for i:=Arity(n^.op) downto 1 do PARSE(n^.son[i]) end; for каждого A из N do WITH n^.nonterm[A] CostAttr:=UndefinedValue; production:=Undefined; end; for каждого правила A->bu из P такого, что b=n^.op do if MATCHED(n,[A->.bu]) then ВычислитьАтрибутыСтоимостиДля(A,n,(A->bu)); ПроверитьКритерийДля(A,n^.nonterm[A].CostAttr); if (A->bu) лучше, чем ранее обработанное правило для A then Модифицировать(n^.nonterm[A].CostAttr) n^.nonterm[A].production:=(A->bu) end end end; (* Сопоставить цепные правила *) while существует правило C->A из P, которое лучше, чем ранее обработанное правило для A do ВычислитьСатрибутыДля(C,n,(C->A)); ПроверитьКритерийДля(C,n^.nonterm[C].CostAttr); if (C->A) is better then Модифицировать(n^.nonterm[C].CostAttr) n^.nonterm[C].production:=(C->A) end end end; Когда выбрано дерево вывода "наименьшей" стоимости, вычисляются значения атрибутов, сопоставленных вершинам дерева вывода, и генерируются соответствующие машиннные команды. Вычисление значений атрибутов, генерация кода осуществляются в процессе обхода выбранного дерева вывода сверху вниз, слева направо. Обход выбранного дерева вывода выполняется процедурой вычислителя атрибутов, на вход которой поступают корень дерева выражения и аксиома грамматики. Процедура использует правило p:A::=z0 X0 z1...Xk zk, связанное с указанной вершиной n, и заданный нетерминал A, чтобы определить соответствующие им вершины n1,...,nk и нетерминалы X1,...,Xk. Затем вычислитель рекурсивно обходит каждую вершину ni, имея на входе нетерминал Xi. Глава 9. Системы автоматизации построения трансляторов Системы автоматизации построения трансляторов (САПТ) предназначены для автоматизации процесса разработки трансляторов. Очевидно, что для того, чтобы описать транслятор, необходимо иметь формализм для описания. Этот формализм затем реализуется в виде входного языка САПТ. Как правило, формализмы основаны на атрибутных грамматиках. Ниже описаны две САПТ, получившие распространение: СУПЕР и Yacc. В основу первой системы положены LL(1)-грамматики и L-атрибутные вычислители, в основу второй - LALR(1)-грамматики и S- атрибутные вычислители. 9.1. Система Супер Программа на входном языке Супер ("метапрограмма") состоит из следующих разделов: - Заголовок; - Раздел констант; - Раздел типов; - Алфавит; - Раздел файлов; - Раздел библиотеки; - Атрибутная схема. Заголовок определяет имя атрибутной грамматики, первые три буквы имени задают расширение имени входного файла для реализуемого транслятора. Раздел констант содержит описание констант, раздел типов - описание типов. Алфавит содержит перечисление нетерминальных симоволов и классов лексем, а также атрибутов (и их типов), сопоставленных этим символам. Классы лексем являются терминальными символами с точки зрения синтаксического анализа, но могут иметь атрибуты, вычисляемые в процессе лексического анализа. Определение класса лексем состоит в задании имени класса, имен атрибутов для этого класса и типов этих атрибутов. В разделе определения нетерминальных символов содержится перечисление этих символов с указанием приписанных им атрибутов и их типов. Аксиома грамматики указывается первым символом в списке нетерминалов. Раздел библиотеки содержит заголовки процедур и функций, используемых в формулах атрибутной грамматики. Раздел файлов содержит описание файловых переменных, используемых в формулах атрибутной грамматики. Файловые переменные можно рассматривать как атрибуты аксиомы. Атрибутная схема состоит из списка синтаксических правил и сопоставленных им семантических правил. Для описания синтаксиса языка используется расширенная форма Бэкуса-Наура. Терминальные символы в правой части заключаются в кавычки, классы лексем и нетерминалы задаются их именами. Для задания в правой части необязательных символов используются скобки [], для задания повторяющихся конструкций используются скобки (). В этом случае может быть указан разделитель символов (после /). Например, A ::= B [ C ] ( D ) ( E / ',' ) Первым правилом в атрибутной схеме должно быть правило для аксиомы. Каждому синтаксическому правилу могут быть сопоставлены семантические действия. Каждое такое действие - это оператор, который может использовать атрибуты как символов данного правила (локальные атрибуты), так и символов, могущих быть предками (динамически) символа левой части данного правила в дереве разбора (глобальные атрибуты). Для ссылки на локальные атрибуты символы данного правила (как терминальные, так и нетерминальные) нумеруются от 0 (для символа левой части). При ссылке на глобальные атрибуты надо иметь в виду, что атрибуты имеют области видимости на дереве разбора. Областью видимости атрибута вершины, помеченной N, является все поддерево N, за исключением его поддеревьев, также помеченных N. Исполнение операторов семантической части правила привязывается к обходу дерева разбора сверху вниз слева направо. Для этого каждый оператор может быть помечен меткой, состоящей из номера ветви правила, к выполнению которой должен быть привязан оператор, и, возможно, одного из суффиксов A, B, E, M. Суффикс A задает выполнение оператора перед каждым вхождением синтаксической конструкции, заключенной в скобки повторений (). Суффикс B задает выполнение оператора после каждого вхождения синтаксической конструкции, заключенной в скобки повторений (). Суффикс M задает выполнение оператора между вхождениями синтаксической конструкции, заключенной в скобки повторений (). Суффикс E задает выполнение оператора в том случае, когда конструкция, заключенная в скобки [], отсутствует. Атрибутные зависимости в случае повторяющегося нетерминала показаны на рис. 9.1. +---+ | A |<---------------+ +---+ | | | +------------------------------+ | | | | | | v v v v | +---+ +---+ +---+ +---+ +---+ | +---+ ->| B |-->| X |-->| X |-->...-->| X |-->| X |--->| C |- +---+ +---+ +---+ +---+ +---+ +---+ | ^ ^ ^ ^ | | | | | +-------------------------------------+ Рис. 9.1 Пример. Использование меток атрибутных формул. D ::= 'd' => $0.y:=$0.x+1;. A ::= B (C) [D] => $2.x:=1; 2M:$2.x:=$2.x+1; $3.x:=$2.x; 3E:$3.y:=$3.x; 3 :writeln($3.y);. Процедура WRITELN напечатает число вхождений символа C в C- список, если D опущено. В противном случае напечатанное число будет на единицу больше. 9.2. Система Yacc В основу системы Yacc положен синтаксический анализатор типа LALR(1), генерируемый по входной (мета) программе. Эта программа состоит из трех частей: %{ Си-текст %} %token Список имен лексем %% Список правил трансляции %% Служебные Си-подпрограммы Си-текст (который вместе с окружающими скобками %{ и %} может отсутствовать) обычно содержит Си-объявления (включая #include и #define), используемые в тексте ниже. Этот Си-текст может содержать и объявления (или предобъявления) функций. Список имен лексем содержит имена, которые преобразуются Yacc-препроцессором в объявления констант (#define). Как правило, эти имена используются как имена классов лексем и служат для определения интерфейса с лексическим анализатором. Каждое правило трансляции имеет вид Левая-часть : альтернатива_1 {семантические действия 1} | альтернатива_2 {семантические действия 2} |... | альтернатива_n {семантические действия n} ; Каждое семантическое действие - это последовательность операторов Си. При этом каждому нетерминалу может быть сопоставлен один синтезируемый атрибут. На атрибут нетерминала левой части ссылка осуществляется посредством значка $$, на атрибуты символов правой части - посредством значков $1, $2 ,..., причем номер соответствует порядку элементов правой части, включая семантические действия. Каждое семантическое действие может вырабатывать значение в результате выполнения присваивания $$=Выражение. Исполнение текого оператора в последнем семантическом действии определяет значение атрибута символа левой части. В некоторых случаях допускается использование грамматик, имеющих конфликты. При этом синтаксический анализатор разрешает конфликты следующим образом: - конфликты типа свертка/свертка разрешаются выбором правила, предшествующего во входной метапрограмме; - конфликты типа сдвиг/свертка разрешаются предпочтением сдвига. Поскольку этих правил не всегда достаточно для правильного определения анализатора, допускается определение старшинства и ассоциативности терминалов. Например, объявление %left '+' '-' определяет + и -, имеющими одинаковый приоритет и имеющими левую ассоциативность. Операцию можно определить как правоассоциативную в результате объявления %right '^' Бинарную операцию можно определить как неассоциативную (т.е. не допускающую появления объединения двух подряд идущих знаков операции): %nonassoc '<' Символы, перечисленные в одном объявлении, имеют одинаковое старшинство. Старшинство выше для каждого последующего объявления. Конфликты разрешаются путем присваивания старшинства и ассоциативности каждому правилу грамматики и каждому терминалу, участвующим в конфликте. Если необходимо выбрать между сдвигом входного символа s и сверткой по правилу A->w, свертка делается, если старшинство правила больше старшинства s или если старшинство одинаково, а правило левоассоциативно. В противном случае делается сдвиг. Обычно за старшинство правила принимается старшинство самого правого терминала правила. В тех случаях, когда самый правый терминал не дает нужного приоритета, этот приоритет можно назначить следующим объявлением: %prec терминал Старшинство и ассоциативность правила в этом случае будут такими же, как у указанного терминала. Yacc не сообщает о конфликтах, разрешаемых с помощью ассоциативности и приоритетов. Восстановление после ошибок управляется пользователем с помощью введения в грамматику "правил ошибки" вида A->error w. Здесь error - ключевое слово Yacc. Когда встречается синтаксическая ошибка, анализатор трактует состояние, набор ситуаций для которого содержит правило для error, некоторым специальным образом: символы из стека выталкиваются до тех пор, пока на верхушке стека не будет обнаружено состояние, для которого набор ситуаций содержит ситуацию вида [A-> . error w]. После чего в стек фиктивно помещается символ error, как если бы он встретился во входной строке. Если w пусто, делается свертка. После этого анализатор пропускает входные символы, пока не найдет такой, с которым можно продолжить нормальный разбор. Если w не пусто, просматривается входная строка и делается попытка свернуть w. Если w состоит только из терминалов, эта строка ищется во входном потоке. Литература 1. Aho A., Sethi R., Ullman J. Compilers: principles, techniques and tools. N.Y.: Addison-Wesley, 1986. 2. Грис Д. Построения компиляторов для цифровых вычислительных машин. М.: Мир, 1975. 3. Fraser C.W., Hanson D.R. A Retargetable compiler for ANSI C.// SIGPLAN Notices. 1991. V 26. 4. Надежин Д.Ю., В.А.Серебряков, В.М.Ходукин. Промежуточный язык Лидер (предварительное сообщение)//Обработка символьной информации.М.: ВЦ АН СССР, 1987. С. 50-63. 5. Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978. 6. Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы. М.: Мир, 1976. 7. Лавров С.С., Гончарова Л.И. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971. 8. Адельсон-Вельский Г.М., Ландис Е.М. Один алгоритм организации информации// ДАН СССР. 1962. Т. 146. N 2. С. 263-266. 9. Курочкин В.М. Алгоритм распределения регистров для выражений за один обход дерева вывода//2 Всес. конф "Автоматизация производства ППП и трансляторов". 1983. С. 104-105. 10. Emmelman H.,Schroer F.W.,Landweher R. BEG-a generator for efficient back-ends// ACM SIGPLAN. 1989. V.11. N 4.p.227-237 11. Aho A.U.,Ganapathi M.,Tjiang S.W. Code generation using tree matching and dynamic programing// ACM Trans. Program. Languages and Systems.1989. V.11.N 4. 12. A. Bezdushny, V. Serebriakov. The use of the parsing method for optimal code generation and common subexpression elimination//Techn. et Sci. Inform. 1993. V.12. N.1. P.69-92. 13. Graham S.L., Harrison M.A., Ruzzo W.L. Am improved context-free recognizer// ACM Trans. Program. Languages and Systems. 1980. N.2. 14. Harrison M.A. Introduction to formal language theory. Reading, Mass.: Addison-Wesley, 1978.