Содержание к диссертации
Введение
ГЛАВА I. Атрибутные грамматики и их использование при описании языков программирования 9
1.1. Методы формального описания языков программирования и их классификация 9
1.2. Описание и реализация языков программирования атрибутными грамматиками 18
1.3. Основные определения и обозначения 26
ГЛАВА II. Проверка цикличности атрибутных грамматик 35
2.1. Формальное описание алгоритма Кнута для проверки цикличности атрибутных грамматик 36
2.2. Исключение лишних графов 40
2.3. Определение оптимального порядка выбора правил грамматики 44
2.4. Экономия памяти при проверке цикличности атрибутных грамматик 52
2.5. Реализация алгоритма проверки цикличности 59
ГЛАВА III. Вычисление семантических атрибутов 62
3.1. Основные алгоритмы вычисления семантических атрибутов 63
3.2. Алгоритм преобразования семантических функций 70
3.3. Вычисление семантических атрибутов методом сортировки. 74
ГЛАВА ІV. Некоторые оптимизационные задачи, применяемые при реализации атрибутных грамматик 82
4.1. Задача оптимизации на множестве перестановок 82
4.2. Генерация оптимального кода для арифметических выражений 92
4.3. Реализация алгоритма генерации объектного кода с помощью атрибутной грамматики 106
Заключение 109
Литература
- Описание и реализация языков программирования атрибутными грамматиками
- Определение оптимального порядка выбора правил грамматики
- Алгоритм преобразования семантических функций
- Генерация оптимального кода для арифметических выражений
Описание и реализация языков программирования атрибутными грамматиками
Применение АГ для описания некоторого языка программирования позволяет фактически описать транслятор с этого языка. Такая практическая направленность АГ и привлекла внимание разработчиков трансляторов, а также разработчиков языков. АГ стали применяться при описании различных языков программирования и их подмножеств, алгоритмов трансляции и оптимизации, а также систем построения трансляторов.
В настоящем разделе приведем краткий обзор основных результатов, касающихся развития самого метода АГ, а также основные направления его практического применения.
Сужения и обобщения АГ. Одно из первых сужений АГ - это АГ, допускающие вычисление всех атрибутов произвольного дерева вывода за один обход слева направо (ІЛП) [54] или за несколько таких обходов (НЛП). Как обобщение этого метода в работе [62] предлагается так называемый альтернирующий семантический вычислитель (НАО), который при выборе оптимальной стратегии вычисления допускает чередование обходов слева направо и справа налево.
П.Льюис, Д.Розенкранц и Р.Стирнз [70] выделяют также два подкласса АГ - это L -атрибутные грамматики (I—А), совпадающие с классом ІЛП атрибутных грамматик, и S -атрибутные грамматики (S-A), допускающие только синтезированные атрибуты, которые вычисляются при обходе дерева снизу вверх, т.е. одновременно с восходящим синтаксическим анализом.
В работе [63] выделяется подкласс корректных атрибутных грамматик, называемых упорядоченными АГ (УАГ). АГ называется упорядоченной, если для каждого ее символа можно задать некоторое отношение частичного порядка на множестве его атрибутов и в любом контексте (дереве вывода) атрибуты этого символа можно вычислить в порядке, включающем заданный частичный порядок. Приводится алгоритм полиномиальной сложности для проверки на упорядоченность произвольной корректной АГ.
Другой класс АГ, одновизитные (ОАГ), предлагается в работе [56] . Атрибутная грамматика называется одновизитной, если вычисление всех атрибутов произвольного дерева вывода можно осу-щесьвить, обходя дерево таким образом, что любое его поддерево посещается один единственный раз.
Обобщение одновизитных АГ предлагается в работе [78] введением К -визитных атрибутных грамматик. АГ называется К -визитной, если для любого дерева вывода возможно вычисление всех его атрибутов путем установления такого порядка обхода этого дерева, при котором любая его вершина посещается не более К раз. Показывается, что любая корректная атрибутная грамматика является К -визитной для некоторого целого К . Более того, доказывается, что для заданной корректной АГ и заданного целого К задача проверки АГ на к-визитность алгоритмически разрешима. Приво -дится пример атрибутной грамматики, являющейся К-визитной для некоторого целого К и доказывается, что не существует ( К-1 )-визитная АГ, определяющая такую же семантику с использованием тех же семантических значнний и функций. Таким образом устанав ливается своего рода иерархия К -визитных АГ по к .
На основе первоначального "ошибочного" алгоритма проверки цикличности АГ, приведенного Д.Кнутом в работе [65] , выделен широкий класс атрибутных грамматик для которых могут быть построены эффективные алгоритмы вычисления атрибутов, так называемые TW -вычислители [64] .
Иерархическая классификация всех выделенных классов АГ приведена на рис. I. Наличие дуги (пути) между классами К± и «2 ( К4 -+ - - К ) означает строгое включение К2. С К\ . Отсутствие дуги (пути) означает несравнимость этих классов.
Приведенная схема частично доказана в работах [56,63] . Остается рассмотреть лишь соотношение одновизитных и упорядоченных АГ, а также одновизитных и НЛП (НАО) атрибутных грамматиках. Имеет место
Теорема 1.2.I. Класс упорядоченных атрибутных грамматик строго включает в себя класс одновизитных атрибутных грамматик.
Доказательство. Покажем сначала, что произвольная однови-зитная АГ является упорядоченной АГ. Действительно, согласно определению одновизитной АГ, для любого ее правила о:Х0 ХХ2.«Ха. существует перестановка 1 ,1 ,,,,, L чисел 1,2,...,/1 такая, что при перестановке вершин Х , Xz , -,, Хд. произвольного дерева, соответствующие правилу л , в порядке Х[,, X/ ,.. , X/ возможно будет вычисление всех атрибутов этого дерева за один его обход слева направо.
Определение оптимального порядка выбора правил грамматики
В алгоритме А на порядок выбора правил грамматики не налагается никаких ограничений - правила выбираются в произвольном порядке. Однако, порядок рассмотрения правил может повлиять на сходимость алгоритма. Например, I) если известно, что при вычислении ZfX ) используются некоторые графы из Z(Xj) , а при вычислении 5TfXj) графы из Г(Х[) не используются, то целесообразно сначала вычислить множество 5Г(Х ) и только после этого начать вычисление Т(Х[) ; 2) если в процессе итеративного пополнения множеств Z1 можно утверждать, что начиная с определенного момента множество Г(ХЛ дальше не меняется, то при последующих итерациях можно обходить ее вычисление, т.е. не рассматривать правила, содержащие Хг в левой части.
Таким образом, для грамматики в целом целесообразно установить такой порядок выбора правил, при котором максимально учитывались бы указанные выше предложения. Эта задача решается путем сведения к известной задаче о построении топологичес ки упорядоченного фактор-графа (графа Герца) для произвольного ориентированного графа [16,34] .
К вершинам графа Гер применяем следующий алгоритм топологической сортировки: АЛГОРИТМ В. 81. Положить [-1 82. Выбрать произвольную вершину графа, не имеющую выходящих дуг и присвоить ей приоритет (порядковый номер) с . Если -таких вершин нет, процесс закончить. ВЗ. Исключить все входящие в помеченную вершину дуги, увеличить і на единицу и переходить к шагу В2.
В результате работы алгоритма В все вершины фактор-графа Гт , т.е. все компоненты сильной связности графа FQ получат определенные приоритеты, которые задают некоторую топологическую сортировку графа / . Обозначим через L максимальный приоритет, присвоенный алгоритмом В ( С совпадает с числом компонент сильной связности графа lq ), а через () приоритет, присвоенный вершине А/
В таблице 2 приводится одна возможная сортировка вершин графа Гр , полученная алгоритмом В, для графа IQ грамматики Gf Лемма 2.3.1. Класс К[ , приоритет которого (р(;) = С состоит из единственного элемента - аксиомы грамматики.
Доказательство. Так как грамматика Q приведенная, ее аксиома не может появляться в правой части никакого правила, а значит в вершине графа Гл , соответствующей аксиоме, не заходит ни одна дуга. Лемма доказана.
Лемма 2.3.2. Если t L. /(. и если $1 произвольное дерево с корнем )([ , тогда jf не имеет вершину, помеченную некоторым символом X/ Є Ks для у(К5 ) (р(Кг) .
Доказательство. Если в графе Пр не существует путь, соединяющий Kt с As » тогда никакое дерево вывода с корнем X/ 6 А не будет содержать вершин, помеченных символами Xjє/($. Это вытекает из определений графов IQ и Гр
Допустим, что в некотором дереве tf[ с корнем Х/Є Kz существует вершина, помеченная Хг-К3 и ір(К) Ц(К ), Тогда в графе Гер существует путь, ведущий из К?_ в Ks , а значит алгоритм В сначала выберет /Cs , а потом К . Получаем Ср(к ) (р(К ъ) , что противоречит предположению. Лемма доказана. Доказательство. При построении графов Г л для множества 1/ = , (p(K z)=L , согласно лемме 2.3.2, могут использоваться только графы, принадлежащие множествам Т. для символов из s » (p(Ks) 4(K- Таким образом, все множества X. , полученные алгоритмом М2А совпадают с соответствующими множествами Z , полученными алгоритмом MIA, для всех нетерминалов грамматики Q. Следовательно, алгоритм М2А рассматривает то же самое множество графов / р , что и алгоритм MIA. Теорема доказана.
Рассмотрим множество тех графов из ZfX/) , Х[_Кчі J которые впоследствии окажутся суграфами некоторых других графов и будут исключены из .fX) . Алгоритм Ml А будет рассматривать всевозможные комбинации этих графов, в частности, и для всех XjKs , tf(Ks) (рС г) . Полученные в результате таких вычислений графы для (Xj) также окажутся суграфами. В отличие от алгоритма MIA, алгоритм М2А эти комбинации не рассматривает.
По отношению к алгоритму Ml А, алгоритм М2А не дает никакого эффекта только в том случае, если граф Г сильно связный. Для реальных языков программирования это далеко не так. Например, в графе fq стандарта языка ПЛ/І [74] выделяются 167 компонент сильной связности.
Алгоритм преобразования семантических функций
Все алгоритмы, основанные на жесткой стратегии обхода отличаются простотой реализации и детерминированностью. Основной недостаток таких алгоритмов - это постоянное присутствие в памяти ЭВМ семантического и синтаксического деревьев. Применение таких вычислителей к грамматикам, для которых количество обходов зависит от исходной программы, очевидно неэффективно. Вопросы удаления тождеств и висячих цепочек в рамках алгоритмов с жесткой стратегией обхода нигде не рассматриваются.
В работе [70] исследуются вопросы совмещения процесса вычисления семантических атрибутов за один обход дерева с известными синтаксическими анализаторами. Определяются атрибутные и S - атрибутные грамматики и машины, что является обобщением хорошо известных классов LL(K) И LR(fc) грамматик. На основе этого, авторам [70] удалось строго доказать, что нисходящий синтаксический анализ обладает более мощными семантическими возможностями, чем восходящий.
Вычислитель системы DELTA . В системе построения трансляторов DELTA [71] во время синтаксического анализа, используя списки зависимостей Ъо.1 строится семантическое дерево из которого далее удаляются тождества и висячие цепочки. Полученное в результате таких преобразований семантическое дерево используется для генерации программы вычисления атрибутов. Эта программа будет не что иным, как одно из возможных топологических сортировок семантического дерева. На основе зависимостей между атрибутами в DELTA разработан и метод выделения и освобождения памяти в процессе вычисления атрибутов. Память, занимаемая некоторым вхождением атрибута, освобождается сразу как только это вхождение дальше не будет использоваться. Алгоритм удаления тождеств совмещен с алгоритмом синтаксического анализа и это обстоятельство не позволяет удалить все тождества [71] .
Вычислитель системы СУПЕР [323 . В системе построения трансляторов СУПЕР используется алгоритм вычисления семантических атрибутов, предложенный В.М.Курочкиным [19] . Вычисление атрибутов происходит недетерминированно и не зависит от синтаксического анализатора. Используя отношения зависимости между атрибутами, в процессе синтаксического анализа для каждого вхождения атрибута создается дополнительно список атрибутов, использующие данный атрибут в качестве аргумента. Это позволяет в момент вычисления некоторого вхождения атрибута скорректировать отношения зависимости для всех атрибутов, входящих в соответствующий дополнительный список, что позволяет без задержки вычислить любой атрибут, как только станут известными все его аргументы, а также освобождать память, занимаемую атрибутами, которые далее нигде не будут использоваться.
Таким образом, алгоритм требует дополнительных расходов памяти для хранения вспомогательных списков, а также дополнительные действия, связанные с доопределением этих списков в момент очередной редукции. Часть тождеств исключается в системе СУПЕР в результате использования глобальных атрибутов. Что касается алгоритма удаления висячих цепочек, то его реализация в рамках метода сопряжена определенными трудностями.
Перспективным представляется реализация такого алгоритма на многопроцессорных ЭВМ, допускающих автоматическое распараллеливание вычислительного процесса.
Как было отмечено в предыдущем параграфе, основной недостаток алгоритмов вычисления семантических атрибутов с использованием жесткого обхода дерева заключается в том, что в процессе вычисления необходимо постоянное присутствие в памяти ЭВМ всего синтаксического дерева. Кроме того, для некоторых АГ количество необходимых обходов может зависеть от выводимой цепочки. В этом случае целесообразно выбрать другой метод вычисления или модифицировать алгоритм обхода с учетом этих особенностей.
В этом параграфе предлагается алгоритм, который при очередном обходе дерева осуществляет преобразование некоторых семантических функций, чтобы при последующем обходе вычислить все оставшиеся атрибуты дерева.
Генерация оптимального кода для арифметических выражений
Пусть имеется дискретный технологический комплекс, состоящий из /і производственных узлов и I -ый узел постоянно занимает Д[ общих приборов. Задано также некоторое множество допустимых расписаний, задающее порядок технологического процесса. Для выполнения специального заказа, при соблюдении тех же допустимых расписаний, [ -ый узел требует выделения /7? дополнительных приборов, которые сразу же после выполнения всех операций узла, освобождаются. Среди всевозможных допустимых расписаний выбрать то, которое для заданного заказа займет минимальное количество дополнительных приборов.
Проанализируем сложность предложенных алгоритмов. Основ ные этапы алгоритмов следующие: 1) упорядочение вершин в порядке убывания характеристик формирование и удаление подграфа Ffl) для каждой выб ранной вершины перестановки
Этап I можно выполнить за 0(Пко іг) операций, а) операций, где /I - количество вершин, а а -количество дуг исходного графа. Таким образом, общая сложность алгоритма построения оптимальной перестановки составляет операций.
Проблема генерации объектного кода занимает важное место в процессе трансляции. Особое внимание при этом уделяется генерации оптимального кода для арифметических выражений в смысле минимизации его длины, эффективного использования регистров и рабочей памяти [2,5,80] .
В данном параграфе рассматривается алгоритм генерации оптимального кода для арифметических выражений, предложенный Р.Сети и Дж.Ульманом [80] и приводится модификация этого алгоритма, позволяющая сгенерировать оптимальный код, используя минимально возможное число рабочих ячеек.
Рассмотрим абстрактную вычислительную машину [5] с Л/ 1 быстрыми регистрами и операциями четырех типов: I) LOAD Р, А - загрузка регистра А , т.е. содержимое рабочей ячейки Р засылается в регистр А . 2) STORE A; P содержимое регистра А засылается в рабо чую ячейку Р ; 3) А, Р, С - результат выполнения бинарной операции над содержимыми регистра А и ячейки памяти Р засылается в регистр С ; 4) А , В, С - результат выполнения бинарной операции над содержимыми регистров А и В , А Ф Ъ звсылается в регистр С . . Регистры А и С не обязательно различны. Первый операнд и результат для операций типов 3) и 4) обязательно находятся в регистре.
Относительно рассматриваемых арифметических выражений предполагается, что все входящие в них операнды различны и что каждое выражение представимо в виде двоичного дерева. Цусть Т -двоичное дерево арифметического выражения. С любой внутренней вершиной п. дерева связана некоторая бинарная операция 5 = ОР(ГІ) . Все листья дерева помечены различными именами переменных (ячейки рабочей памяти). Если П- (или П-1 ) - внутренняя вершина дерева, то через n , /Z (или /2[ , ґіг ) обозначим соответственно ее левый и правый прямые потомки.
Первоначально значения имеются только у листьев дерева. Значение внутренней вершины - это результат применения операции ОР(я) к потомкам П и /L, данной вершины. Здесь порядок операндов существенен: первым операндом всегда будет rig , а вторым -/ . Значением всего дерева будем считать значение его корня. Под программой будем понимать последовательность операций, вычисляющую значение данного двоичного дерева.
Будем считать, что имеется достаточный объем рабочей памяти и поэтому не возникнет необходимость обращения к внешней памяти. Основу алгоритма Сети-Ульмана составляет следующий метод разметки дерева. Всем вершинам рекурсивно, начиная снизу, присваиваются целочисленные метки L : - если п - лист, тогда С I, если п является левым потомком своего прямого L(n)= J предка или /г - корень; L 0, в противном случае; - если /г - внутренняя вершина, тогда
Внутренняя вершина /I называется старшей, если 1.(4) ъ-N и 1.(/1) А/ . Вершина называется младшей, если она является листом и левым прямым потомком своего прямого предка.
Приведем теперь алгоритм Сети-Ульмана (алгоритм II.2 из 5, гл. II), описание которого необходимо для дальнейшего изложения. Входной информацией для алгоритма служит помеченное двоичное дерево! и регистры Д. , Ад ,..., А и . Алгоритм описан с помощью рекурсивной процедуры CODE , обращения к которой имеют вид CODE (Ті, О » гДе П- - вершина дерева, &А[,А {» ..., А/у - допустимые в данный момент регистры. При необходимости алгоритм обращается к функции newtemp , которая вырабатывает новую рабочую ячейку.
