АКАДЕМИЯ НАУК СССР ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР На правах рукописи Серебряков Владимир Алексеевич Системы автоматизации построения трансляторов и их применение для эффективной реализации языков программирования Специальность 05.13.11 "Математическое и программное обеспечение вычислительных машин и систем Автореферат диссертации на соискание ученой степени доктора физико-математических наук МОСКВА 1989 Работа выполнена в Вычислительном Центре АН СССР Официальные оппоненты: Королев Л.Н., член-корреспондент АН СССР, доктор физико-математических наук Иванников В.П., член-корреспондент АН СССР, доктор физико-математических наук Подшивалов Д.Б., доктор физико-математических наук Актуальность проблемы С появлением языков программирования возникла задача трансляции программ и средств формального описания языков и трансляторов и поддержки этих формализмов в виде систем построения трансляторов. На протяжении более, чем двадцати лет были разработаны самые различные формализмы для описания языков программирования. Среди них стоит отметить Венский метод, грамматики Ван Вейнгаардена, аксиоматический подход, денотационный подход, атрибутные грамматики. Было предпринято огромное число попыток создать на основе развиваемых формализмов такие программные средства, которые бы позволяли по формальному описанию языка строить транслятор (или интерпретатор) с него. Как правило, эти попытки носили чисто экспериментальный характер и задачи создания средств, позволяющих создавать качественные высокоэффективные трансляторы не ставилось. В то же время ясно, что проблема разработки трансляторов остается актуальной и требуются практические системы, позволяющие создавать качественные трансляторы Задача исследования ставилась так: на основе накопленного опыта как в области теории описания языков программирования, методов трансляции, так и в области практики создания трансляторов, разработать такую систему и методы ее применения, которые позволили бы строить трансляторы, качество которых не уступало бы написанным вручную. Научная новизна работы Впервые в практике система автоматизации построения трансляторов применена для полного описания транслятора: описания входного языка (и полной проверки контекстных условий), генерации в промежуточный язык и генерации кода. Разработанный промежуточный язык позволяет применять систему для построения машинно-независимых трансляторов. Разработанные методы трансляции включают в себя: обработку сложных структур данных, средств явного управления видимостью, генерации промежуточного представления, атрибутных методов генерации кода, в том числе методов локальной оптимизации. Разработаны методика и методы использования системы. Таким образом осуществлено теоретическое обобщение мирового опыта разработки средств автоматизации построения трансляторов и решена крупная, имеющая важное народо-хозяйственное значение проблема создания системы, позволяющей эффективно реализовывать языки программирования. Методы исследования В результате анализа различных методов описания языков программирования выбор был сделан на атрибутном формализме. Основная причина этого заключается в том, что этот формализм хорошо согласуется с широко применяемыми на практике методами трансляции, и прежде всего с методами, в основе которых лежит контекстно-свободный анализ. Этот формализм достаточно технологичен и естествен. Конечно, реальное применение атрибутных методов сталкивается со значительными трудностями, поэтому на атрибутные грамматики наложены некоторые ограничения. С другой стороны, практика применения атрибутных систем показала, что для того, чтобы они стали эффективным средством, требуются различные расширения. На основе этого была разработана система автоматизации построения трансляторов Супер. Практическая ценность Система Супер применялась для трансляторов с различных языков программирования. Созданная с ее помощью система программирования Модула-2 имеет весьма высокие характеристики, ничем не уступающие разработанным вручную как по скорости трансляции, так и по качеству генерируемого кода. Система Супер и разработанные методы трансляции и методика применения системы с успехом могут быть использованы для разработки и других систем программирования. Апробация работы Результаты работы докладывались на всесоюзных и международных конференциях, на двух советско-французских семинарах. Система успешно применяется в ряде организаций, что подтверждается актами внедрения. С помощью системы Супер реализована система программирования Модула-2, имеющая высокие качественные показатели. Объем диссертации 240 страниц. Диссертация состоит из введения, пяти глав, заключения и списка литературы из 66 наименований. В I главе дается краткий обзор методов определения языков программирования и систем автоматизации разработки трансляторов. Среди них особо рассматриваются вопросы формализации описания контекстных условий и генерации кода. Рассматриваются вопросы применения атрибутных грамматик, в частности проблемы, возникающие в практике их использования. Дается обзор наиболее развитых систем, разработанных как в СССР, так и за рубежом. Приводятся примеры использования этих систем для описания различных языков программирования. В II главе дается описание входного языка системы автоматизации построения трансляторов Супер. III глава посвящена разработанному промежуточному языку Лидер, используемому в дальнейшем для формализации описания языка Модула-2. IV глава посвящена разработке методов применения системы Супер для описания языка высокого уровня (Модулы-2). Она включает в себя как описание входного языка, генерацию промежуточного представления, так и генерацию кода. В V главе приводится общая структура системы программирования Модула-2 и ее основные характеристики. В заключении делаются основные выводы из проделанной работы. Средства определения языков программирования: обзор Теория и практика описания и реализации языков программирования делят описание на четыре уровня: лексический, контекстно-свободный, контекстно-зависимый и семантический. Семантику языка можно определить двумя основными способами: интерпретацией, т.е. в терминах поведения некоторой абстрактной машины, или трансляцией, т.е. в терминах другого языка, семантика которого считается определенной. Наибольший интерес представляет собой трансляция в машинные команды, поскольку именно это является, как правило, целью описания языка. Вопросам автоматизации генерации кода в мире уделялось много внимания и краткий обзор работ в этом направлении приведен в разделе II.2. Определение контекстных условий Для трансляторов с языков программирования одной из задач является определение правильности транслируемой программы. Существенным является то, что проверить правильность произвольной программы с точки зрения ее поведения на всем допустимом множестве входных данных для сколько-нибудь разумного языка программирования невозможно. Поэтому свойство "правильности" программы традиционно подразделяют на "статическую" правильность и "динамическую" правильность. Под статической правильностью понимают обычно ряд достаточно простых, не зависящих от конкретных входных данных разрешимых свойств, которые проверяются на этапе трансляции, а по динамической правильностью - правильность поведения программ на множестве входных данных. Отметим, что даже в отношении конкретного языка программирования проведение этой грани не является однозначным. В свою очередь, статически разрешимые свойства языков программирования традиционно делят на два класса: принадлежность некоторому контекстно-свободному языку и все прочие, которые называют "контекстно-зависимыми". Связано такое разделение с ясностью формулировки и относительной простотой определения принадлежности КС-языку. Поэтому в основе практически всех формализмов определения языков лежит КС-синтаксис. Обязательным требованием к множеству программ P с правильными контекстно-зависимыми условиями является разрешимость этого множества. Само понятие контекстных условий неотрывно связано с формализмом их задания. Здесь возможны два пути. Во-первых, сам формализм может быть таков, что с его помощью можно описывать только разрешимые множества. Во-вторых, формализм может быть универсальным (т.е. описывать все рекурсивно- перечислимые множества) и на автора описания ложится ответственность за его использование. Были предложены как формализмы первого рода, так и второго. К формализмам первого рода относятся прежде всего грамматики с ограничениями на вывод: контекстные (неукорачивающие) грамматики, программные грамматики, индексные грамматики. Применение грамматик с ограничениями на вывод для описания языков программирования оказалось весьма неудобным и, кроме того, сложность анализа пратически неприемлемой. К формализмам второго рода можно отнести двухуровневые грамматики (грамматики Ван Вейнгардена и логический подход. Автоматизация генерации кода. Вопросам автоматизации генерации кода уделялось много внимания. При этом можно выделить два основных подхода. В первом строится так называемое "Описание машины", в котором указывается структура памяти, команд, регистров и т.д. Конструктор генераторов кодов затем по этому описанию, зная формат промежуточного представления, строит собственно генератор кодов. Второй подход заключается в том, что предлагается специализированный язык по описанию генераторов кодов. На этом языке задается соответствие между системой команд машины и промежуточным представлением. В этом случае в качестве "Конструктора генератора кодов" выступает по-существу транслятор с этого языка. Процесс генерации кода можно разделить на несколько тесно связанных между собой, но все же относительно самостоятельных этапов: выбор команд, распределение памяти (в частности, регистров), генерация кода для операторов, генерация кода для выражений и другие. Существенную роль в формализации процесса генерации кода играет и промежуточное представление: линейное представление (часто префиксное или постфиксное), в виде дерева, графа и т.д. Основой процесса генерации кода является установление соответствия между конструкциями промежуточного языка и последовательностями команд, реализующими эти конструкции, т.е. собственно процесс выбора команд. В обзоре рассмотрены системы построения трансляторов, разрабатываемые за рубежом: HLP'78/HLP'84/TOOLS, HLP/SZ, HLP/PAS, PROF-LP, FNC-2, GAG, MUG 2, OPTRAN, MARVIN, YACC, а также системы, разрабатываемые в СССР:Эльма (Таллин), Тарту, САГЕТ (Гомель), Кросс (Новосибирск) Приведены примеры атрибутных описаний языков программирования: Алгол-68, Ада, Паскаль, Евклид. Основные выводы Из приведенного краткого обзора можно сделать следующие основные выводы. Для описания контекстных условий языков программирования применялись различные формализмы: грамматики с ограничениями на вывод, аксиоматический, атрибутный и другие. Имеющийся в мире опыт позволяет говорить лишь об экспериментах по описанию языков, не претендующих на их эффективную реализацию. Наиболее близко к возможности такой реализации стоит атрибутный формализм, в чистом виде, однако, обладающий следующими недостатками: с одной стороны, в общем виде реализация атрибутных грамматик требует существенных затрат, поэтому желательно в практической системе использовать какой-то подкласс, с другой - требуются некоторые расширения языка атрибутных грамматик (не выводящие из этого подкласса, например, глобальные атрибуты). Особое внимание должно быть уделено описанию семантики, в частности генерации кода, поскольку мирового опыта применения атрибутных систем для генерации кода практически нет. Здесь основное внимание должно быть уделено промежуточному представлению, позволяющему, с одной стороны, полностью использовать возможности атрибутной трансляции, с другой - получать качественный код. Возникает вопрос о многопроходной атрибутной трансляции, то есть о соединении нескольких атрибутных грамматик в одну таким образом, что результат одной является входом другой. Составные атрибутные грамматики. Как можно видеть из обзора, довольно простые по идее атрибутные грамматики требуют сложных вычислителей атрибутов Если посмотреть на классы АГ с точки зрения нашей основной цели - получения эффективных вычислителей, то главным источником неэффетивности служит необходимость посещать некоторые вершины многократно. Практически это означает, что либо атрибутированное дерево программы необходимо держать в оперативной памяти, что требует очень большой памяти, либо многократно перекачивать его на внешнюю память и с нее. Одновизитные грамматики позволяют вычислять атрибуты за один обход дерева, но в порядке, вновь требующем прямого доступа к вершинам дерева. Для преодоления этих трудностей возможны два пути. Во-первых, можно хранить значение атрибутов дерева на внешней памяти, и при необходиости обращаться к ним и записывать на внешнюю память вновь Это ведет к очень значительной потере эффективности. Путь второй заключается в следующем. Пусть мы имеем две атрибутные граматики G1 и G2. Наряду с обычными формулами вычисления атрибутов вида a0:=f(a1,..,an) введем "синтаксические" атрибуты X<-N2 U T2 и "синтаксические" правила вычисления атрибутов вида X0:=p(X1,..,Xn), где p<-P2. Такое правило представляет собой поддерево с вершиной X0, построенное из поддеревьев с вершинами X1,...,Xn. Если в качестве Xi выступает не синтаксический, а семантический атрибут G2, oн рассматривается как терминальная вершина. Разрешим также формулы вычисления атрибутов вида Xi.a:=f(a1,...an), где X - синтаксический атрибут, если a<-A(Xi). Результатом вычисления в G1 будем считать значение выделеного ситаксического атрибута аксиомы. Такую пару грамматик будем называть "парной" атрибутной грамматикой. Если парными АГ являются , , ..., , то будем называть "составной" АГ. Пусть мы имеем простую k-перестановочную АГ G. Тогда для каждого нетерминала X существует разбиение его атрибутов A1(X),...,Ak(X) такое, что на i-ом обходе дерева вычисляются атрибуты Ai и для каждого правила p:X0->X1...Xn существует последовательность П=<п1,..пk> перестановок символов правой части такиx, что при входе в поддерево с вершиной X0, в которой применено правило p, на i-ом обходе дерева потомки X1,..Xn посещаются в порядке пi. Рассмотрим теперь следующую составную грамматику. G1 для каждого нетерминала имеет атрибуты A(X) и синтаксический атрибут S1x, каждому правилу p:X0->X1...Xn соответствуют семантические правила вычисления атрибутов A1(X) для каждого X и одно синтаксическое Sx0:=п1(Sx1,...,Sxn), а также правила Sxi.a:=Xi.a для a<-A1(Xi). В АГ Gk каждому правилу p:X0->X1...Xn соответствуют семантические правила вычисления атрибутов Ak(X) для каждого X и одно синтаксическое Sx0:=пk(Sx1,...,Sxn), а также правила Sxi.a:=Xi.a для a<-A1(Xi Ak(Xi). Теорема. Так построенная составная АГ эквивалентна исходой АГ G в том смысле, что в Gk будут вычислены все атрибуты и они получат те же значения, что и G. Таким образом, простая k-перестановочная АГ преобразуется в k L-атрибутных. В чем преимущество такого преобразования? Для вычисления всех атрибутов k-перестановочной АГ требуется либо держать все дерево в памяти, либо иметь прямой доступ к атрибутам на внешней памяти. Первое не реально для обычных программ, второе приводит к резкому замедлению транслятора. Преобразование k-перестановочной грамматики в k L-атрибутных позволяет в какой-то степени избежать этих трудностей. Частично атрибутированное промежуточное представление считывается один раз из последовательного файла. Кроме того, такой подход допускает возможность того, что синтаксис промежуточного представления не совпадает с исходным, что позволяет решать более эффективно многие задачи трансляции. Глобальные атрибуты Введем понятие области действия атрибута в дереве как множество ветвлений, в которых допустимо использование в формулах данного атрибута. При использовании определения АГ, приведенном выше, областью действия каждого из атрибутов являются два ветвления, в которые входит нетерминал, которому приписан атрибут (или одно для термиального символа). Назовем такие атрибуты локальными. Использование только таких атрибутов не всегда удобно при определении языков программирования. Например, переменная может быть использована в любом операторе. Если пользоваться только локальными атрибутами, то атрибут, хранящий список описаний, нужно сначала "протянуть вверх" через описания, а затем спустить вниз до каждого использования переменной. Для того, чтобы избежать этих трудностей, определим область действия атрибутов нетермнала N следующим образом. Если среди потомков N1 нет вершин N, то областью действия a<-A(N1) будем считать все ветвления поддерва с вершиной N1, а также ветвление, в которое N1 входит в правую часть. Если же среди потомков N1 есть еще вершина N2, то областью действия будем считать все ветвления поддерева N1 за исключением поддеревьев, вершинами которых являются потомки N2, а также ветвление, к которое N1 входит в правую часть. Схематично это изображено на рисунке 1. Пересечение областей действи N2 не вызывает противоречия при использовании атрибутов т.к. всегда можно указать, идет ли речь об атрибутах символов данного правила или символов- предков. При использовании атрибутов будем употреблять термин "локальный атрибут, если речь идет об атрибутах данного правила, и термин "глобальный" атрибут, если речь идет об атрибутах символа-предка Подчеркнем, что при таком определении нет деления самих атрибутов на локальные и глобальные. Все атрибуты дерева имеют область действия, данную определением. Деление на локальные и глобальные относится к использованию атрибутов. Введение глобальных атрибутов требует рассмотрения вопроса о сохранении возможности статической проверки корректности АГ. АГ (с глобальными атрибутами) будем называть корректной, если 1. Не существует такого дерева вывода, в котором атрибут используется вне своей области действия. 2. Не существует такого дерева вывода, в котором атрибуту не присваивается значения в его области действия 3. Не существует такого дерева вывода, в котором атрибуту в его области действия присваивается значение более одного раза. 4. АГ не зациклена. Теорема. Существует алгоритм проверки корректности всякой АГ (с глобальными атрибутами). | | | | N1 /|\ /|\ - / | \ / | \ | / | \ / | \ | /|\N /|\ | / | \ / | \ | / | \ / | \ |0 | /|\ - N2 /|\ | / | \ | / | \ - / | \ | / | \ /|\ N | /|\ / | \ | / | \ / | \ / | \ PN Рис. 1. Рис. 2. Структурные атрибуты. Будем называть атрибут структурным, если: 1) он представляет собой совокупность величин, называемых полями структурного атрибута; 2) среди семантических формул данной АГ имеются формулы, при выполнении которых вычисляются или используются значения отдельных полей структурного атрибута. Назовем атрибутами типа 1 такие структурные атрибуты, у которых ко всем полям возможен прямой доступ. Примерами атрибутов такого типа могут служить массивы, записи и т.д. У атрибутов типа 2 прямой доступ ко всем полям невозможен. Типичными примерами таких атрибутов являются файлы с поледовательным доступом, стеки. Атрибутами типа 1.1 назовем таке структурные атрибуты типа 1, у которых число полей можно установить по виду АГ. В качестве примера приведем записи и статические массивы и их комбинации. Атрибуты типа 1.2 - это стуктурные атрибуты типа 1, число полей которых по виду АГ установить нельзя. Простейшим примером могут служить динамические массивы, размеры которых определяются значениями некоторых атрибутов (или их полей) и тем самым зависят от конкретного дерева вывода. Атрибуты типа 1.1.1 - это атрибуты типа 1.1, обладающие следующим свойством: в данной АГ во всех формулах вычисления атрибутов типа 1.1 по виду АГ, т.е. статически, можно установить, какие именно поля атрибутов типа 1.1 входят в формулу. К атрибутам типа 1.1.2, напротив, отнесем все структурные атрибуты типа 1.1, для которых в данной АГ имеется хотя бы одна формула вычисления такая, что по виду АГ нельзя установить, значение какого именно поля вычисляется или используется. АГ со структурными атрибутами обладают следующими свойствами. Утверждение 1 Существует алгоритм, позволяющий для всякой АГ, включающей только атрибуты типа 1.1.1, по виду АГ проверить ее корректность. Утверждение 2 Не существует алгоритма, позволяющего для произвольной АГ, включающей атрибуты типа 1.1.2 и/или 1.2 проверить ее корректность. Утверждение 3 Если АГ включает только структуные атрибуты типа 1 и корректна, то значения, полученные атрибутрами, не зависят от порядка выполнения формул. Статически и динамически управляeмая видимость. При описании контекстных условий языков программирования с блочной структурой практически недостаточно и таким образом определенных глобальных атрибутов, поскольку блоки могут быть вложены друг в друга. Поэтому в системе Супер введен третий класс атрибутов - атрибуты с динамической видимостью, в отличие от локальных и глобальных атрибутов, которые мы будем называть атрибутами со статически определенной видимостью. Если N - нетерминал, то разрешим атрибуты типа POINTER TO N - указатели на нетерминал N. Если нетерминал N имеет атрибут А а нетерминал M - потомок N имеет атрибут PN типа POINTER TO N, которому присвоено значение PN:=@N, то к тому атрибуту A символа N можно обратиться как PN@.A. Если сам символ N имеет атрибут типа PОINTER TO N, то все символы N связаны в список, как это изображено на рис. 2. Про такие атрибуты будем говорить, что они имеют "динамическую видимость". Область (динамической) видимости такого атрибута - все поддерево с вершиной N. Входной язык системы автоматизации построения трансляторов Супер. Описание транслятора состоит из заголовка, раздела описаний и схемы перевода. В разделе описаний определяются объекты, которые используются в схеме перевода. В заголовке указывается имя транслятора и перечисляются его параметры. В списке внешних файлов указываются имена файлов, связывающих транслятор с его окружением. В разделе описаний определяется алфавит атрибутной грамматики языка и объекты, используемые в описании транслятора. Это константы, типы, процедуры и функции. В язык введено понятие ключевое множество. Если множество является ключевым (присутствует ключевое слово key), то базовым типом должен быть тип записи, в состав которой на верхнем уровне входит поле с именем ИмяПоля. Типом этого поля может быть INTEGER, CARDINAL или ARRAY [..] OF CHAR. Значения типа список - это упорядоченная последовательность произвольной длины компонент одного типа. Значения типа массив - это упорядоченный набор фиксированного числа компонент одного и того же типа. Упорядоченность задается описанием типа, называемого типом индекса. Значение типа запись - это совокупность фиксированного числа именованных компонент, возможно различных типов. Компоненты записи называются полями. Описание типа запись состоит из перечисления типов полей и имен, обозначающих поля внутри записи Значения типа запись могут иметь несколько вариантов структуры. Алфавит Алфавит содержит описание разделителей, классов лексем, нетерминалов, атрибутов, сопоставленных символам грамматик и типов этих атрибутов. В разделе нетерминальных символов должны быть описаны все нетерминалы КС-грамматики языка. Описание нетерминала заключается в определении его имени, списка атрибутов и типов атрибутов В разделе процедур и функций должны быть описаны заголовки всех процедур и функций, используемых в семантических формулах атрибутной грамматики. Схема перевода. Схема перевода содержит описание синтаксиса и семантики реализуемого языка. Синтаксическое правило состоит из левой и правой частей. Левая часть - нетерминал, описанный в разделе нетерминалов. И наоборот, каждый из нетерминалов, описанных в этом разделе, должен встречаться в левой части хотя бы одного синтаксического правила. Правая часть правила состоит из последовательности элементов, каждый из которых может быть именем нетерминала или класса лексем, ограничителем, нетерминалом, заключенным в метаскобки. Ограничитель обозначается строкой, не содержащей пробелов. Нетерминал должен быть описан в разделе нетерминалов, класс лексем - в разделе классов лексем. Имеется два вида метаскобок: квадратные и круглые. Квадратные скобки используются тогда, когда конструкция, порождаемая нетерминалом, заключенным в эти скобки, может быть опущена. Круглые скобки используются для обозначения повторяющихся конструкций. Внутри метаскобок '(', ')' через метасимвол '/' можно указывать один разделитель повторяющихся конструкций. Комбинация круглых и квадратных скобок используется для описания повторяющихся конструкций с разделителем в случае, когда конструкция, порождаемая нетерминалом, может быть опущена. Семантика правила строится из отдельных семантичеких действий. Выполнение семантических действий связывается с обходом синтаксического дерева сверху-вниз слева-направо. В процессе такого обхода каждая вершина дерева посещается n+1 раз, где n - число ее потомков. Пусть в данной вершине применено правило A ::= B C ... и длина цепочки BC ... равна n. Вход в вершину А сверху будем называть 0-м посещением, вход после обхода первого и потомков BC ... - первым посещением и т.д. Метки служат для возможности планирования выполнения семантических действий в связи с посещениями правила. Семантическое действие, помеченное меткой i, выполняется при i-м посещении правила. Семантические действия делятся на формулы и операторы. Формула представляет собой присваивание, в правой части которого стоит выражение, составленное из объектов. Объектом может быть либо атрибут, либо переменная, либо ссылка на нетерминал, либо компонента другого объекта. Если левая часть представляет собой совокупность объектов, заключенную в '<>', то правой частью должно быть либо составное выражение, и тогда осуществляется последовательное присваивание объектам левой части компонент составного выражения, либо значение типа запись, и тогда объектам левой части последовательно присваиваются значения полей записи верхнего уровня. Объект-атрибут представляется указанием символа, атрибут которого рассматривается, и указанием самого атрибута. Указанием символа может быть либо целое число, либо идентификатор. Если указанием символа служит целое число i, то имеется в виду атрибут i-го символа синтаксического правила, которому сопоставлена формула, включающая использование рассматриваемого атрибута, при нумерации символов слева-направо (0-для символа левой части, 1 - для первого символа правой части и т.д.). Если указанием символа служит идентификатор, то имеется в виду атрибут ближайшего в дереве разбора предка символ левой части с указанным именем. Компоненты объекта указываются с помощью обозначения объекта, за которым следует указание, задающее самое компоненту. Если обозначением объекта является идентификатор, то это означает что объект - это либо локальная переменная правила, либо имя нетерминала либо поле объекта типа запись (под оператором присоединения). Если объект имеет вид A@, где A - нетерминал, то это означает указатель на ближайший предок символа левой части данного правила с именем А. Операторы служат для задания последовательностей семантических действий. Имеются следующие операторы: оператор вызова процедуры, оператор выбора, условный оператор, оператор присоединения, циклы FOR, WHILE, RЕPEAT, составной оператор. Планирование семантических действий Как уже было сказано, выполнение каждого семантического действия связывается с посещением правила в процессе обхода дерева разбора сверху-вниз слева-направо. Поэтому информация по дереву не может передаваться справа-налево, т.е. в качестве аргумента формулы, вычисляющей значение атрибута i-го символа (i>0), не может входить атрибут j-го символа, если j>i. Выполнение семантического действия, помеченного меткой i, планируется на i-е посещение. Поэтому оно не может зависеть от атрибутов k-го символа, если k>i, и, в случае формулы, не может определять значение атрибута j-го символа, если j<=i, j>0. Если i-й символ A синтаксического правила заключен в квадратные метаскобки и некоторое семантическое действие помечено меткой iE, то выполнение этого действия планируется на i-е посещение и тот случай, когда конструкция, порождаeмая A будет опущена. Причем порядок выполнения спланированных таким образом действий определяется зависимостями атрибутов, задаваемых этими действиями. На зависимости атрибутов действия, помеченного iE, накладываются те же ораничения, что и на действие, помеченное меткой i, с тем исключением, что аргументами рассматриваемого действия могут быть еще атрибуты i-го символа. Если i-й символ A синтаксического правила заключен в круглые метаскобки, то семантическое действие, помеченное iM, выполняется между последовательными разворачиваниями поддеревьев, корнями которых служит A. Такие действия-формулы вычисляют значения атрибутов символов A при некотором разворачивании поддерева для A в зависимости от значений атрибутов при предыдущем разворачивании. В качестве аргументов в этих семантических действиях нельзя использовать атрибуты j-го символа, если j>i. Семантическое действие, помеченное iB, выполняется до каждого разворачивания поддерева, корнем которых служит A. Семантическое действие, помеченное iA, выполняется после каждого разворачивания поддерева, корнем которых служит A. Рассмотрим теперь планирование непомеченных семантических действий. Форвулы, определяющие значение атрибута i-го символа, если i>0, планируется на i-1 посещение. Формулы, задающие значения глобальных атрибутов или атрибутов символа левой части синтаксического правила, планируются следующим образом. Среди аргументов формулы могут быть 1) локальные и глобальные атрибуты, значения которых определяются формулами данного правила; 2) локальные и глобальные атрибуты, значения которых не задаются формулами данного правила. Вычисление каждого из аргументов первой группы планируется на то или иное посещение правила. Пусть максимальное значение из номеров этих посещений есть k. Пусть наибольший из индексов символов локальных атрибутов второй группы есть j. Если нет атрибутов в первой группе, то считается, что k=0, а если во вторую группу не входят локальные атрибуты, то j=0 Тогда выполнение формулы планируется на посещение с номером max(k,j). Непомеченные операторы планируются на последнее посещение правила. Порядок выполнения независящих друг от друга семантических действий спланированных на одно и то же посещение, определяется порядком их написания в семантической части правила. Промежуточный язык Лидер. Основной задачей промежуточного языка Лидер является представление исходной программы в таком виде, чтобы с одной стороны из этого представления легко можно было получать код а с другой - чтобы это представление было максимально машинно- независимым. Для того, чтобы решить первую задачу в Лидере, во-первых, все операции типизованы (например, целое сложение, сложение множеств и т.д.), а во-вторых, ссылки на все объекты прямые. Чтобы добиться машинной независимости в программе на Лидере не использутся такие машинно-зависимые понятия, как размер переменной, адрес переменной и другие. Эти требования противоречивы и противоречия разрешаются следующим образом. Для того, чтобы в самом языке не вводить адресов и размеров переменных, в нем оставлены все описания. Генератор кодов (транслятор с Лидера в коды конкретной ЭВМ), обрабатывая эти описания, сам определяет адреса и размеры переменных. Для того, чтобы иметь прямые ссылки на объекты, но в то же время не оперировать с этими ссылками как с адресами используется понятие "номера объекта". В процессе обработки программы на Лидере некоторым конструкциям программы (например, типам, переменным и т.д.) приписываются номера, по которым затем делаются ссылки на них. Такой номер может быть абсолютным, номером внутри видимой процедуры заданного уровня и номером относительно текущего значения счетчика. При входе в процедуру увеличивается на 1 номер уровня процедур и утанавливается в 0 счетчик относительных ссылок. Поскольку предполагается, что программа на Лидере обрабатывается синтаксически управляемым транслятором, в основу записи программ положена префиксная запись. Таким образом программа представляет собой ЛИнеаризованное ДЕРево. Реализация контекстных условий. Формализация описания контекстных условий дается на примере языка Модула-2, обладающего такими характерными для современных языков качествами, как строгая типизация, блочная структура, явное управление видимостью,раздельная компиляция. Структура среды Модулы-2. "Корневую" компоненту среды в Модуле-2 образует программный модуль или модуль реализации. Объекты этой компоненты могут быть описаны в самом модуле или могут быть импортированы из других модулей определений. Существует предопределенная компонента, объекты которой доступны во всех других компонентах (если они там не переопределены). Элементом описания может быть процедура или локальный модуль имеющие свой список описаний. Компонента среды локального модуля не включается в компоненту среды в которой локальный модуль объявлен, поскольку внутри локального модуля доступны те и только те объекты охвытывающей компоненты, которые явно импортированы в локальный модуль. И наоборот, компоненты среды локального модуля могут быть экспортированы в охватывающую компоненту. В то же время компонента среды процедуры включается в охватывающую компоненту, поскольку объекты этой компоненты могут быть доступны в процедуре. Объект охватывающей компоненты может быть виден (если внутри данной процедуры не описан объект с тем же именем). Основой описания являются атрибуты Среда, приписанные блокам и имеющие тип ключевое множество записей. Блочная и модульная структура реализованы в терминах атрибутов с динамической видимостью. В качестве примера рассмотрим правило Правило: Type_Des ::= Ident Семантика: Var P; {указатель на объект} P:=Block@; {указатель на ближайший охватывающий блок} repeat $0.Exit:=Find($1.Val,P@.Env); {найти объект} if P@.Kind then P:=Pred(P) {если процедура, перейти к охватывающей} until ($0.Exit<>NIL)or(not P@.Kind); {либо нашли объект, либо дошли до границы модуля if ($0.Exit=NIL) then $0.Exit:=Find($1.Val,$Prog.Env); {найти объект в предопределенной компоненте} if ($0.Exit=Nil) then Error(тип не найден) else if ($0.Exit@.Object<>Тип) then begin Error(объект не тип) $0.Exit:=Nil end; Трансляция в промежуточное представление. Трансляция в промежуточное представление (Лидер) рассматривается как преобразование дерева входной программы в дерево в новой атрибутной грамматике. Основой такого преобразования являются средства получения перестановки поддеревьев в рамках L-атрибутной грамматики Трансляция логических выражений. По требованию языка Модула-2 логические выражения должны вычисляться с помощью операторов перехода. Рассмотри следующую атрибутную грамматику: S -> B => $1.F:=FALSE; $1.T:=TRUE; $1.SIGN:=false; B -> B & B => $1.F:=$0.F; $1.T:=$3.номер; $3.F:=$0.F; $3.T:=$0.T; $1.SIGN:=false; $3.SIGN:=$0.SIGN; B -> B V B => $1.T:=$0.T; $1.F:=$3.номер; $3.F:=$0.F; $3.T:=$0.T; $1.SIGN:=true; $3.SIGN:=$0.SIGN; B -> not B => $1.F:=$0.T; $1.T:=$0.F; $1.SIGN:=not $0.SIGN; B -> I => if $0.SIG then else ;; Теорема Для всякого набора входных данных любого логического выражений в программе, сгенерированной по этой атрибутной грамматике осуществляется переход по true для истинного выражения и переход по false для ложного (в обычной интерпретации) В терминах команд СМ-4 последнее правило выглядит следующим образом: B -> I => ; Если элементом логического выражения является сравнение, то генерируется команда, соответствующая знаку сравнения (beg для =, bne для <>, bge для >= и т.д.), если атрибут sign соответствующей вершины имеет значение true, и отрицание (bne для =, beq для <>, blt для >= и т.д.), если атрибут sign имеет значение false Трансляция операций над множествами Для рассмотрения реализации операций над множествам введем модель машины, достаточно близкую к системе комад СМ-4. Рассмотрим систему команд, в которой команды имеют вид либо R1xR2->R2 (т.е. оба операнда на регистре и результат во втором из них), либо MxR->R (левый операнд в памяти, правый в регистре, результат в регистре), либо S[i]xR->R (левый операнд в стеке, правый на регистре, результат на регистре, при этом стек сокращется), либо команда MOV M,R (загрузить регистр из памяти), либо команда MOV R,S[i] (загрузить стек из регистра, при этом стек увеличивается). Число регистров ограничено MAX. Следующая атрибутная грамматика реализует бинарные операции в такой системе команд: S -> E => $1.Spil:=false; $1.Reg:=1; E -> E op E => $1.Spil:=$0.Spil; $3.Spil:=$0.Spil V $1.A=R; $1.Reg:=$0.Reg; $3.Reg:=if $1.A=R then $0.Reg+1 else $0.Reg; $0.A:=F($1.A,$3.A); E -> M => $0.A:=M; Здесь F - таблица решений Теорема Приведенная атрибутная грамматика использует минимальное число регистров (еcли не допускается перестановка подвыражений), генерирует самую короткую последовательность команд, использует память в магазинном режиме и использует минимальное число элеменов магазина. Трансляция арифметических выражений Система команд СМ-4 требует пар смежных регистров для выполнения некоторых операций. При этом задача оптимального распределения регистров становится NP-полной. Мы рассмотрим приближенное решение задачи за один обход дерева выражения сверху-вниз слева-направо одновременно с генерацией кода. Система команд СМ-4 позволяет выполнять некоторые операции с верхушкой стека. Поэтому при необходимости освобождения занятых регистров для выполнения операции их можно сбрасыват в стек. Необходимо отметить, что высокое быстродействие современных систем ОЗУ не снимает всех перечисленных выше проблем, поскольку, как было отмечено, некоторые команды требуют определенных регистров, а сознательно сбрасывать промежуточные результаты в память значит сознательно ухудшать качество кода. В качестве модели машины примем следующую систему команд: SxR->R (стек x регистр -> стек), R1xR2->R2 (регистр x регистр), MxR->R (память x регистр), MOV M,R (загрузить из памяти в регистр), MOV R,S (загрузить из регистра в стек). Некоторые команды требуют обязательно нечетного регистра. В командах типа SxR->R стек сокращается, в командах MOV R,S - увеличивается. В приводимой ниже атрибутной схеме атрибуты имеют следующий смысл: REGSET - наследуюмый атрибут, дающий шкалу свободны регистров EVSP - наследуемый атрибут, указывающий, какой из четны регистров может быть в случае необходимости сброшен; атрибут EVSP помимо значений собственн регистров может также принимать значение NO означающее, что такого регистра нет ODSP - наследуемый атрибут, указывающий, какой из нечетных регистров может быть в случа необходимости сброшен; атрибут ODSP помимо значений собственно регистров может также принимать значение NO, означающее, что такого регистра нет S -> E => $1.Evsp:=NO; $0.Odsp:=NO; $1.Reg_Set:=[1..MAX]; E -> M => $0.A:=M E -> E op E => $1.Odsp:=$0.Odsp; $1.Evsp:=$0.Evsp $3.Odsp:=if $1.A=нечетный_регистр then $1.A else $0.Odsp $3.Evsp:=if $1.A=четный_регистр then $1.A else $0.Evsp $1.Reg_Set:=$0.Reg_Set; $3.Reg_Set:=if $1.A=регистр then $0.Reg_Set else $0.Reg_Set-[$1.A]; $0.A:=F($1.A,$3.A,$2.Op); Здесь F - таблица решений, учитывающая требования к регистрам со стороны операции. Теорема Память используется в магазином режиме, т.е. если при входе в поддерево было использовано i ячеек, то при выходе, если R=Evsp (Odsp), то вeрхний элемент имеет номер i+1, иначе состояние памяти не меняется. Трансляция операторов Рассматриваются вопросы трансляции основных операторов: вызовов, условных, присоединения, цикла, переключателей. В связи с этим рассматриваются вопросы организации памяти периода выполнения и различных оптимизаций. Вопросы оптимизации кода. Оптимизация - это качественная трансляция. Поэтому когда говорят об оптимизации, имеют в виду способы получения качественного кода ("методы оптимизации"). Как правило такие методы делят на машинно-независимые, т.е. такие, которые можно выполнить вне зависимости от системы команд, и машинно-зависимые т.е. такие, которые строго зависят от системы команд. В то же время и машинно-независимые оптимизации в конечном итоге реализуются через машинные команды, так что между ними трудно провести четкую границу. Рассмотрим с этой точки зрения изложенные в работе методы генерации кода. Логические выражения. Вычисление логических выражений с помощью переходов - один из способов оптимизации их вычисления. Предложенные в работе атрибутные методы зависят от системы команд только на "нижнем" уровне при выборе конкретных команд сравнений и переходов, так что самое технику трансляции логических выражений можно считать машинно-независимой. Операции над множествами и арифметические операции. Предложенные методы трансляции можно разделить на два уровня: атрибуты и их зависимости на дереве промежуточного представления и таблицы решений, реализующие в конкретной системе команд ту или иную комбинацию значений атрибутов. Ясно, что сама техника трансляции, основанная на учете занятости регистров, информации о возможностях сброса регистров и магазинной органиции рабочей памяти применим практически к любой системе команд (а лучше всего к системам с аппаратно поддерживаемым магазином). Таблицу решений можно рассматривать как функцию с параметрами атрибутами, реализуемую по-разному в каждом конкретном случае. Вызовы подпрограмм. В основе трансляции вызовов подпрограмм лежит организация памяти периода выполнения. Предложенные алгоритмы позволяют обойтись минимальным количеством регистров, отводимых для организации доступа к переменным (если в данной точке программы имеется доступ только к переменным программного модуля (или модуля реализации), и подпрограмме первого уровня, то занят только один регистр указатель стека. Во всех остальных случаях, занимается еще один регистр - указатель статической цепочки. Прямо доступны глобальные переменные, переменные текущего и предыдущего статических уровней. Операторы цикла и присоединения Основная проблема при трансляции операторов цикла и присоединения - хранение переменной цикла (или адреса переменной) в регистре В предлагаемом подходе выбрана гибкая схема: эти значения сохраняются в стеке и заносятся в регистр. Если к моменту обращения этот регистр испорчен, его значение может быть восстановлено из стека. Оператор переключатель. При трансляции оператора-переключателя делается анализ того, какой код короче: вычисление с помощью сравнений и переходов или прямо по таблице адресов. Таким образом, осуществляется оптимизация длины программы. Длинные и короткие переходы. Одной из серьезных проблем при выборе команд - это выбор команды короткого или длинного перехода при трансляции перехода вперед. В рассматриваемом трансляторе этот выбор делается для всех структурных операторов (циклов, условных и т.д.). Всегда длинными переходами реализуются операторы RETURN и EXIT. Система программирования Модула-2-Супер. Система состоит из трех трансляторов: транслятора модулей определений, транслятора программных модулей (модулей реализации в промежуточное представление и генератора кодов (в объектный файл). В языке сделаны следующие расширения: - добавлен еще один тип модулей (определений) - Фортран-модули для обеспечения связи с программами, транслированными в соответствии с соглашениями связей по Фортрану - соответственно добавлены два новых типа данных - FUNCTION и SUBROUTINE. Переменной такого типа может быть присвоена подпрограмма или функция Фортрана; - введена возможность назначения абсолютного адреса глобальной переменной; - введена возможность инициализации глобальных переменных; - константы могут быть структурными (массивами и записями); - имеется русско-язычная версия транслятора; - введены псевдокомментарии управления трансляцией (см. ниже); Управление трансляцией осуществляется или псевдокомментариями или ключами при запуске транслятора. Имеются следующие возможности: - включать (отключать) подготовку листинга; - включать (отключать) проверки диапазонов индексов массивов; - включать (отключать) проверки диапазонов; - включать (отключать) проверки границ стека; - генерировать код для системы команд FIS или FPP. В состав системы программирования входят следующие стандартные модули - TTIO - модуль терминального ввода-вывода; - CRTNS - модуль организации работы с сопрограммами; - STORAGE - модуль органиции динамической памяти; - MATHLIB0 - основные математические функции; - DMATHLIB0 - основные математические функции с двойной точностью; - FILECTRL - управление файлами; - TEXTFILE - работа с текстовыми файлами; - ASCII - константы ASCII-кода. Характеристики. Размеры трансляторов для ЭВМ СМ-4 (1420) следующие: - транслятор модулей определений - 81 Кб - транслятор программных модулей (модулей реализации) - 118 Кб - генератор кода - 92 Кб Скорость трансляции на ЭВМ СМ-1420 примерно 300 строк в минут (примерно в два раза быстрее, чем штатный транслятор с Паскаля). Результаты работы можно резюмировать следующим образом: 1) Проведен анализ мирового опыта разработки и использования систем автоматизации построения трансляторов. 2) Разработан язык системы автоматизации построения трансляторов, в основу которого положены атрибутные грамматики со следующими основными расширениями - глобальные атрибуты; - структурные атрибуты; - атрибуты с динамически управляемой видимостью. Доказаны свойства атрибутных схем с учетом этих расширений. 3) Показано удобство входного языка Супер для описания трансляции, в частности: - формализации контекстных условий языков программирования; - создания многопроходных трансляторов; - генерации кода. 4) На основе этого входного языка реализована система автоматизации построения трансляторов, обеспечивающая реализацию высокоэффективных трансляторов (в частности, многопроходных на основе составных атрибутных грамматик). 5) Разработаны методы атрибутной трансляции, включающие - описание контекстных условий современных языков программирования, в частности с блочной структурой и явным управлением видимостью; - генерацию промежуточного представления на основе технологии использования составных атрибутных грамматик; - генерацию кода, включая логические выражения, арифметические выражения, распределение регистров, вызов подпрограмм, различные операторы. Доказана правильность предложенных методов. 6) Разработан промежуточный язык Лидер, ориентированный н синтаксически управляемую трансляцию в составных атрибутны грамматиках. 7) С помощью системы Супер реализован транслятор с язык Модула-2, обладающий высокими параметрами, ничем не уступающими трансляторам, написанным вручную. Основные результаты опубликованы в следующих работах 1. Бирюков А.Н., Курочкин В.М., Серебряков В.А Система построения трансляторов, основанная на однородном и универсальном подходе. В кн.: Труды 1-й Весоюзной конференции по технологии программирования. Киев, 1979 2. Бирюков А.Н., Курочкин В.М., Серебряков В.А Вопросы реализации языков программирования. - Препринт - М., ВЦ АН СССР, 1980. - 12 стр. 3. Серебряков В.А. Основные особенности реализации СПТ Супер. - В кн. Автоматизация производства ППП, Таллинн, 1980. 4. Бирюков А.Н., Курочкин В.М., Серебряков В.А Глобальные атрибуты и их применение при определени языков программирования. - ЖВМ и МФ, 1980, n 5 - стр. 1284-1293 5. Бирюков А.Н., Курочкин В.М., Серебряков В.А Структурные атрибуты и их реализация в системе построения трансляторов Супер. - Программирование, 1981, n 2 - стр. 52-55 6. Серебряков В.А. Основные особенности входного языка и реализации СПТ Супер. - Программирование, 1982, n 1 7. Лихачев В.М., Пржиялковский В.В., Серебряков В.А. - В кн. Вопросы автоматического построения языковых процессоров для специализированных микро-ЭВМ с применением методики синтаксически управляемого перевода. Автоматизация программирования аналого-цифровых и микропроцессорных систем. 1982 8. Бездушный А.Н., Серебряков В.А. Определение подмножества языка Паскаль средствам обобщенных атрибутных грамматик. - В кн. Автоматизация производства ППП и трансляторов. Таллинн, 1983 9. Бирюков А.Н., Курочкин В.М., Серебряков В.А Архитектура и реализация СПТ Супер. - В кн. Обработка символьной информации, ВЦ АН СССР, 1984. 10. Серебряков В.А Методы атрибутной трансляции - В кн. Языки программирования. М., Наука, 1985 - стр. - 47-78 11. Серебряков В.А., Бездушный А.Н Входной язык системы автоматизации построения трансляторов Супер - Препринт ВЦ АН СССР, 1986 - 64 стр 12. Серебряков В.А Классы атрибутных грамматик и алгоритмы вычисления атрибутов (обзор). - В Сб. Обработка символьной информации. М., ВЦ АН СССР, 1986 13. Серебряков В.А Система автоматизации построения трансляторов Супер: состояние, проблемы и перспективы. - В кн. Методы трансляции и конструирования программ. ВЦ СО АН СССР, 1987. 14. Курочкин В.М., Серебряков В.А. Вопросы разработки и использования атибутных систе построения трансляторов. В кн. Проблемы прикладной математики и информатики, Наука, 1987. 15. Надежин Д.Ю., Серебряков В.А., Ходукин В.М Промежуточный язык Лидер (предварительное сообщение) - В Сб. Обработка симольной информации, М., ВЦ АН СССР,1··1987. 16. Серебряков В.А Атрибутная трансляция арифметических выражений - В кн. Обработка символьной информации, ВЦ АН СССР, 1987. 17. Серебряков В.А Атрибутная трансляция логических выражений - Программирование, 1988, n 1. 18. Serebriakov V.A. Construction of Efficient Multi-Stage Compilers with the Attribute TWS. - Compiler Construction and High Spee Compilation. Proceedings of the Workshop, Berlin, Oct. 10-14 1989, pp. 63-74. 19. Вооглайд А.О., Серебряков В.А. Применение систем автоматизации разработки трансляторов. - В кн. Прикладная информатика, Финансы и статистика, 1989 20. Серебряков В.А Применение систем автоматизации разработки трансляторов для разаботки эффективных трансляторов - В кн. Труды рабочей группы РГ-23 КНВВТ, Таллинн, 1989. 21. Serebriakov V.A. Attribute Visibility Control in CWS Super an Implementation of Import-Export Facilities in Modula-2 Front-End. Informatics'89 - Proceedings of the Soviet- French Symposium, Tallinn, May 29-June 2, 1989.