.OUTPUT(LPT E+ S0).INPUT(B#).PARAGRAPH(F% S0 P3 I3).OPTION(E- T- P-) .MARGIN(L0 R62) .COUNT 25 .FORM([/$30'- 'PN:1' -'//L42]) ГЕНЕРАЦИЯ КОДА СРЕДСТВАМИ СИНТАКСИЧЕСКОГО АНАЛИЗА А.Н. Бездушный 1. Введение и основные понятия Процесс компиляции состоит из двух фаз. На первой фазе (front-end) выполняются лексический, синтаксический, контекстный анализы, формируется промежуточное представление исходной программы, содержащее только те компоненты исходной программы, которые необходимы в дальнейшем. На второй фазе (back-end) промежуточное представление программы преобразуется в объектный код. Проблемы первой фазы компиляции достаточно хорошо изучены. Имеются алгоритмы и средства автоматического построения соответствующих компонент компилятора по декларативному описанию языка. Из проблем второй фазы задача генерации кода является наиболее трудной, что связано со сложностью соответствующих алгоритмов, необходимостью учитывать архитектуру конкретного компьютера. Только в последнее время стали вырабатываться общие методы, алгоритмы построения генераторов кода для универсальных компьютеров. Хороший обзор подходов к решению этой проблемы приведен в [1]. Исследование теоретических аспектов и практических алгоритмов можно найти в [2]. Много факторов определяют выбор промежуточного представления. Например, класс входного языка, организация компьютера. Известно несколько вариантов промежуточного представления исходной программы: последовательность команд абстрактного компьютера, последовательность триад или тетрад, лес атрибутированных деревьев, последовательность линеаризованных деревьев#[3]. Мы предполагаем, что промежуточное представление - это последовательность префиксных выражений, в которых операторы имеют фиксированное число операндов. Операторы могут иметь атрибуты, значения которых определяются на первой фазе процесса компиляции. Распределение памяти выполняется также на первой фазе. Запись a0#e1#e2...ek - это префиксное выражение, в котором оператор a0 размерности k=Arity(a0) применяется к выражениям e1,e2,...,ek. Если a0...an является префиксным выражением и оператор a0 имеет размерность k, то существует единственная запись этого выражения как a0#e1#e2...ek для некоторых префиксных выражений e1,e2,...,ek. Поэтому для каждой позиции i (i=0,n) в префиксном выражении a0...an мы можем вычислить позицию m такую, что ai...am=ai#e1#e2...ek и k=Arity(ai). Запись ai..am будем называть ai-выражением, имеющим длину j=m-i+1. Для каждого префиксного выражения можно построить соответствующее ему дерево выражения. Если оператор a0 размерности Arity(a)=k применен к выражениям e1,e2,...,ek (z=a0#e1e2...ek), то соответствующее ему дерево выражения T0 показано на рис. 1, где T1,T2,...,Tk - это деревья выражений e1,e2,...,ek соответственно. (a0) T0 / | \ / | \ / | \ /\ / \ ... /\ /T1\ /T2 \ /Tk\ ---- ----- ---- Рис. 1. Дерево выражения z=a0 e1 e2...ek На рис. 2 показано дерево префиксного выражения := @ + CONST(a) BASE(a) + CONST(5) ^ @ + CONST(a) BASE(a) для прeдложения a:=a+5, где a - локальная переменная, хранимая со смещением CONST(a) в области данных, указываемой регистром BASE(a). Значения атрибутов операторов указаны в скобках. Оператор @ преобразует свой аргумент в адрес памяти. Оператор ^ возвращает содержимое ячейки памяти с адресом, задаваемым аргументом оператора. Основная проблема при разработке генератора кода - это задача выбора последовательности машинных команд, реализующих промежуточное представление исходной программы. В современных компьютерах одни и те же действия можно реализовать многими способами. Простейший алгоритм генерации кода заключается в обходе промежуточного дерева в обратном порядке и выборе команды для каждой вершины отдельно. Получающийся код будет очень плохой, так как обычно одна команда может быть использована для "реализации" нескольких вершин промежуточного дерева. .PAGE := / \ / \ @ + | / \ + CONST(5) @ / \ | CONST(a) BASE(a) + / \ CONST(a) BASE(a) Рис. 2. Дерево промежуточного представления цепочки a:=a+5 Например, команда MOV 30(R0),40(SP) выполняет вычисление адреса источника, извлечение из памяти его значения и пересылку этого значения по вычисленному ею же адресу приемника. Поэтому генератор кода должен комбинировать узлы промежуточного дерева, чтобы произвести одну машинную команду. Последние исследования методов формализации генерации кода показали, что применение метода "сопоставления образцов" (pattern matching) для решения задачи выбора команд дает наилучшие результаты [11,12]. Первым предложил этот метод С.Г.#Васильев#[5]. Идея метода заключается в следующем. Машинные команды и/или их последовательности описываются посредством "образцов поддеревьев" (tree patterns). Выбор команд эквивалентен нахождению покрытия промежуточного дерева этими образцами. Образцы поддеревьев задаются в правилах выбора команд: .BREAK образец_поддерева '->' результирующая_вершина [ машинная_команда ] .BREAK Образцы поддеревьев наряду с вершинами промежуточного дерева могут содержать в качестве листьев новые вершины, отсутствующие в промежуточном дереве, - это результирующие вершины, используемые для выражения взаимосвязи между образцами поддеревьев. Результирующая вершина представляет результат, вычисляемый командой, связанной с этим образцом. Правило выбора можно рассматривать как правило преобразования промежуточного дерева, при котором вершины промежуточного дерева, сопоставленные образцу, "сжимаются" в единственную вершину дерева. Эта результирующая вершина помечается номером соответствующего правила выбора. Преобразование продолжается, пока применимы правила выбора. Код генерируется в процессе обхода в обратном порядке получившегося дерева. Необходимая машинная команда определяется по номеру правила выбора, являющемуся меткой вершины. Процесс нахождения покрывающего дерева недетерминированный, так как можно построить множество возможных покрытий для одного и того же промежуточного дерева. Задачей выбора команд становится нахождение "подходящего" покрытия, соответствующего "лучшему" способу реализации того или иного действия, последовательности действий. Поэтому вводится понятие "стоимости", связываемое с правилом выбора и определяющее качество генерируемого кода, например, скорость выполнения программы, размер ее кода. Было предложено несколько методов нахождения "подходящего" покрытия. Грем и Глэнвилл [6,7,8] использовали LR-анализатор. Метод состоит в следующем. Вершины образца правила выбора записываются в прямом порядке. Эта запись рассматривается как правая часть, а результирующая вершина - как левая часть правила КС-грамматики. Промежуточное дерево записывается в прямом порядке и поступает на вход LR-анализатора, построенного по этой грамматике. В конструктор LR-анализаторов встраиваются специальные действия для разрешения конфликтов и неоднозначностей грамматики, например, предпочтение сдвига свертке, свертки по более длинному правилу - свертке по более короткому. Фиксированность реакции на конфликты, неучет контекста иногда приводят к неправильному поведению анализатора даже на правильной программе. Требуется детальное знание внутренних алгоритмов синтаксического анализа, чтобы написать спецификацию, которая даст хороший генератор кода. Ганапати и Фишер [2,9] обобщили идею Грем и Глэнвилла, дополнив КС-грамматику атрибутами, т.е. использовали атрибутную грамматику для описания генератора кода. Неоднозначности разрешаются с помощью предикатов правил выбора, управляющих разбором. Генераторы кода, формируемые системами BEG[11], Twig[12] (см. [4]), комбинируют быстрый алгоритм сопоставления образцов с алгоритмом динамического программирования для вычисления минимального покрытия. Алгоритм динамического программирования решает задачу генерации кода для выражения E, разбивая ее на k меньших подзадач генерации оптимального кода для k подвыражений Ei выражения E. Решения подзадач сохраняются в таблицах и никогда не вычисляются заново. В генераторах кода, формируемых системой автоматизации построения СУПЕР[16,17], используется алгоритм, полученный из алгоритма синтаксического анализа Кока, Янгера и Касами[13,14]. В работе мы покажем, как можно модифицировать алгоритм Кока-Янгера-Касами, чтобы использовать его для генерации кода. Покажем, что алгоритмы систем [11,12] являются частными случаями такой модификации алгоритма Кока-Янгера-Касами. Генератор кода определяется неоднозначной атрибутной грамматикой (АГ). Синтаксическая грамматика АГ должна принадлежать специальному классу операторных грамматик. Грамматика G=(N,T,P,S) должна удовлетворять следующим свойствам. 1.#Каждый оператор a из T должен иметь фиксированную размерность Arity(a)>=0. 2.#Правая часть любого правила A->w из P должна быть префиксным выражением с операторами из T и операндами из N. Назовем грамматики такого вида Д-грамматиками (tree grammar). Машинные команды описываются правилами АГ. Код генерируется атрибутными формулами, сопоставленными правилам АГ. Нетерминалы в правой части синтаксического правила представляют результаты выполнения предыдущих команд, а нетерминал левой части - результат выполнения описываемой команды. На рис. 3 показаны правила АГ, необходимые при генерации кода для выражения рис. 2. Генератор кода анализирует входное префиксное выражение и строит дерево разбора. В процессе обхода дерева разбора вычисляются атрибуты и генерируется код в соответствии с семантическими формулами правил, примененных в дереве разбора. Как правило, Д-грамматики, описывающие машинные команды, являются неоднозначными грамматиками. Для каждой входной цепочки можно построить несколько выводов, отражающих код разного качества. Чтобы указать качество генерируемого кода .PAGE (1) Оператор ::= ':=' '@' Рег(R1) Рег(R2) => выдать: MOV R2,@R1 . (2) Рег(R0) ::= '+' Рег(R1) Рег(R2) => выдать: ADD R1,R0 если R2=R0 . (3) Рег(R0) ::= '+' CONST(X) Рег(R1) => выдать: ADD #X,R0; если R1=R0] . (4) Рег(R0) ::= '+' Рег(R1) '@' '+' CONST(X) Рег(R2) => выдать: ADD X(R2),R0; если R1=R0 . (5) Рег(R0) ::= '@' '+' CONST(X) Рег(R1) => выдать: MOV X(R1),R0 . (6) Рег(R0) ::= '@' Рег(R1) => выдать: MOV @R1,R0 . (7) Рег(R0) ::= CONST(X) => выдать: MOV #X,R0 . (8) Рег(R0) ::= BASE(I) => R0:=I . Рис. 3. Правила, необходимые при генерации кода для выражения рис. 2. (например, размер кода или время выполнения), система СУПЕР позволяет сопоставить нетерминалам специальные атрибуты стоимости (С-атрибуты), а синтаксическим правилам атрибутные формулы (С-формулы) для их вычисления. С-атрибуты вычисляются одновременно с синтаксическим анализом префиксного выражения. Неоднозначности синтаксического разбора разрешаются в соответствии с критерием стоимости (С-критерий). Каждому нетерминалу сопоставляется свой С-критерий. Используя значения С-атрибутов, С-критерий определяет правило, которое необходимо приметить к нетерминалу в текущем контексте дерева вывода. Правило, выбранное для аксиомы грамматики, определяет единственное дерево вывода. Когда выбрано наиболее подходящее дерево вывода, вычисляются значения атрибутов, сопоставленных его вершинам, и генерируются соответствующие машиннные команды. 2. Алгоритм синтаксического анализа Кока-Янгера-Касами Пусть G=(N,T,P,S) - КС-грамматика. V обозначает множество N+T. Элементы множества N будем обозначать через A,B,C,D,E, элементы T - посредством a,b,c,d, а элементы V - как X,Y,Z. Элементы V* будем обозначать через u,v,w,x,y, а элементы T* - посредством z. Символ e представляет пустую цепочку. Пусть G - КС-грамматика без e-правил и z=a[1]#a[2]...a[n] - цепочка, которую необходимо распознать. Оригинальный алгоритм Кока-Янгера-Касами предполагет, что КС-грамматика представлена в нормальной форме Хомского. Алгоритм можно модифицировать так, чтобы он работал для произвольной КС-грамматики [13,14]. Алгоритм Кока-Янгера-Касами строит таблицу разбора h. Имя h[i,j] представляет элементы таблицы h при 1<=i<=n и 0<=j<=n-i+1. В отличие от оригинального алгоритма, мы будем считать, что h[i,j] содержит объекты вида [A->uv.w], а не символы грамматики. h[i,j]={[A->u.v] | A->uv из P и u=>*a[i]...a[i+j-1]} .BREAK Это означает, что j символов входной цепочки z, начиная с i-го символа, выводятся из A. Цепочка z принадлежит L(G) тогда и только тогда, когда S принадлежит h[1,n]. Рассмотрим алгоритм Кока-Янгера-Касами. Алгоритм 1: VAR a :ARRAY[1..n] of Tterminal; h :ARRAY[1..n],[0..n] OF SET OF Titem; BEGIN (* == обозначает реккурентное соотношение, *) (* реализуемое оператором WHILE *) FOR i:=1 TO n DO h[i,0]:={ [A->.w] | A->w из P }; END; FOR всех 1<=i<=n, 1<=j<=n-i+1 DO h[i,j]:={}; END; FOR j:=1 TO n DO(*Увеличивая длину распознаваемой цепочки*) FOR i:=1 TO n-j+1 DO h[i,j]:=h[i,j]+ {[A->ub.v]| [A->u.bv] in h[i,j-1], b=a[i+j-1]} (*1*) FOR k:=1 TO j-1 DO h[i,j]:=h[i,j]+ {[A->uB.v]| [A->u.Bv] in h[i,k], (*2*) [B->w.] in h[i+k,j-k]} END; h[i,j]==h[i,j]+{[A-> B.v]| [A-> .Bv] in h[i,0], [B->w.] in h[i,j]} END; END; Проверить, принадлежит ли [S->w.] множеству h[1,n] END На первом шаге вычисляются множества h[i,0]. Основной цикл алгоритма заключается в формировании множеств h[i,j] из ранее вычисленных h[i,k] для всех 1<=i<=n и 1<=j<=n-i+1 при 0<=k<=j-1. На последнем шаге проверяется, принадлежит ли аксиома S множеству h[1,n]. Вычисляя множества h[i,1],...,h[i,n-i+1] для каждой позиции i, алгоритм распознает все выводы цепочки a[i]...a[k] (k<=n-i+1). Объект [A->w.] включается в множество h[i,k-i+1], если найден некоторый вывод A=>*a[i]...a[k]. Алгоритм Кока-Янгера-Касами строит n*(n+1)/2 множеств h[i,j], т.е. ему требуется объем памяти O(n*n), где n - длина входной цепочки. Множество h[i,j] имеет O(|P|) объектов. Алгоритм выполняет O(j) шагов, чтобы обработать все пары (h[i,k],h[i+k,j-k]) для ku a[p] w a[r]...a[q] v (u a[p]=>*a[i]...), .BREAK которые сопоставимы с подцепочкой a[i]...a[p]...a[r]...a[q]...a[k] цепочки a[1]#a[2]...a[n], где через a[p],a[r],...,a[q] обозначены все терминалы правой части правила, а u,v,...,w принадлежат N*. То есть проверяется, существует ли вывод u'a[p] w'a[r]...a[q] v'=>*a[i]...a[p]...a[r]...a[q]...a[k] .BREAK для некоторых u',w',...,v' из N* при |u'|=|u|,...,|v'|=|v|. Решая вторую задачу, алгоритм исследует, существует ли вывод A => z0 B z1 C...D zm =>* z0 z1' z1...zm' zm = a[i]...a[k] .BREAK такой, что правило A->z0 B z1 C...D zm сопоставимо с цепочкой a[i]...a[k] и B =>* z1', C =>* z2',..., D =>* zm' .BREAK являютя подвыводами, распознанными в процессе вычисления множеств h[p,q] для p>i и qu.v] из h[i,m] (v<>e) используются только в процессе вычисления множеств h[i,j] (m<=j) при решении первой задачи. Объекты [A->w.] из h[i,m] необходимы при решении второй задачи, когда множества h[l,j] (l<=i,m<=j) уже вычислены. Организуем множества r[i] объектов вида [A->w.] для каждой позиции i, чтобы разделить данные первого и второго процессов и облегчить поиск подвыводов, соответствующих сопоставимому с a[i]...a[k] правилу. Вместо таблицы разбора h[i,j] мы будем использовать линейную таблицу h'[i] и только для поиска правил, сопоставимых с подцепочками. Основной цикл алгоритма 2 выполняется для позиций от n до 1 для того, чтобы на i-й итерации вычислить все фразы, имеющие левый край в i-й позиции входной цепочки. Выводы A=>*a[l]...a[j] распознаются, когда все выводы B=>*a[i]...a[m] (lw.] из h[i,j] алгоритма 1 пара (A->w,j) принадлежит r[i] *) BEGIN FOR i:=n DOWNTO 1 DO h'[0]:={[A->.w]| A->w из P}; FOR j:=1 TO n-i+1 DO (*сопоставление правил*) h'[j]:= { [A->ub.v]| [A->u.bv] in h'[j-1], b=a[i+j-1] } FOR k:=1 TO j-1 DO (* поиск выводов *) h'[j]:=h'[j]+{[A->uB.v]| [A->u.Bv] in h'[k], (B->w,j-k) in r[i+k]} END; h'[j]==h'[j]+{[A-> B.v]| [A-> .Bv] in h'[0], [B->w. ] in h'[j]}; END; FOR j:=1 TO n-i+1 DO (* сопоставимые правила*) r[i]:=r[i]+{(A->w,j)| [A->w.] in h'[j]} END; END; Проверить, принадлежит ли (S->w,n) множеству r[1] END Множества r[i] имеют размер O(n). Поэтому алгоритмы 1 и 2 имеют одинаковые емкостную и временную сложности. Алгоритм 2 можно существенно улучшить, если имеется возможность реализовать следующее преобразование. Для каждой пары (i,j) предварительно вычислить все значения k1...km ( m = m(i,j) ) такие, что только пары (h[i,k1],h[i+k1,j-k1]),...,(h[i,km],h[i+km,j-km]) используются при вычислении h[i,j]. Цикл по k заменить на вызов некоторой процедуры COMP(i,j), которая для всех i и j вычисляет h[i,j]:=F(h[i,k1],h[i+k1,j-k1],...,h[i,km],h[i+km,j-km]), используя предварительно вычисленные значения k1...km. До начала разбора алгоритм сохраняет множества предварительно вычисленных значений k1...km в некоторой структуре. В процессе разбора процедура COMP(i,j) выбирает из нее необходимые k1...km. Преобразование имеет смысл, если временная сложность предварительных вычислений не превышает O(n*n) и фиксированное время требуется на выборку k1...km. Если предварительные вычисления можно выполнить за время O(n), то можно вычислить только O(n) множеств значений k1...km. Следовательно, алгоритм должен вычислить только O(n) множеств h[i,j], и его временная сложность становится O(n). 3. Синтаксический анализ для Д-грамматик Модифицируем алгоритм 2 так, чтобы он работал только для Д-грамматик. Все цепочки, выводимые из любого нетерминала A в Д-грамматике G=(N,T,P,S), являются префиксными выражениями. Если S=>*a1...an, то для любых подвыводов A=>*ai...ak и B=>*ai...al имеет место равенство k=l. Длины всех выражений из входной цепочки a[1]...a[n] можно предварительно вычислить, например, одновременно с ее записью в таблицу a. Поэтому можно проверить, сопоставимо ли правило с подцепочкой a[i]...a[k] входной цепочки a[1]...a[n], проходя слева направо по a[i]...a[k]. В процессе прохода по цепочке предварительно вычисленные длины префиксных выражений используются для того, чтобы перейти от одного терминала к следующему терминалу, пропуская подцепочки, соответствующие нетерминалам правой части правила. Алгоритм 3 вычисляет на i-м шаге все фразы, начинающиеся с i-го символа. Процедура MATCH(j,h") просматривает цепочку a[j]...a[j+l[j]-1] и сравнивает ее с a[j]-выражениями, указанными в объектах из h". Параметр h" представляет такое множество {[A->u'a[j].v]}, что если на i-м шаге алгоритма объект [A->u.v] в h", то u=>*a[i]...a[j]. Обрабатывая подвыражение vk выражения a[j]#v1...vm (m=Arity(a[j])), процедура вычисляет множества h1 и h2. Присваивания переменным h1 и h2 соответствует операторам 1 и 2 алгоритма 1 при j=(p-i)+1 и k=p-i, j=k+l[p] соответственно. Цепные правила не зависят от операторов, следовательно, их необходимо проверять отдельно. Применение одного цепного правила может зависеть от применения другого цепного правила. Следовательно, применение цепных правил необходимо проверять циклически до тех пор, пока нельзя применить ни одно из цепных правил. Мы предполагаем, что в грамматике нет циклов в применении цепных правил. Алгоритм 3: VAR a : ARRAY[1..n] OF Tterminal; l : ARRAY[1..n] OF INTEGER;(* l[i]=длина a[i]-выражения*) r : ARRAY[1..n] OF SET OF Tproduction; (* Для каждого объекта [A->w.] из h[i,j] алгоритма 1 элемент (A->w) принадлежит r[i], j=l[i] *) h": SET OF Titem; PROCEDURE MATCH(VAR j:INTEGER; VAR h": SET OF Titem); VAR p: INTEGER; h1,h2: SET OF Titem; BEGIN (* h" равен {[A->uc.vw]}, m=Arity(c), c=a[j], *) (* v=v1 v2... vk ...vm=v' vk v" *) IF h"<>{} THEN p:=j+1; (*пропустить a[j] *) FOR k:=1 TO m DO (*сопоставить {v1,v2,...,vm}*) h2:={[A->ucv'B. v"w]| [A->ucv'.B v"w] in h", vk=B, B->y in r[p] }; h1:={[A->ucv'b.xv"w]| [A->ucv'.bxv"w] in h", vk=bx, b=a[p] }; MATCH(p,h1); (* сопоставить {vk} *) h":=h1+h2; END; END; j:=j+l[j]; (* пропустить a[j]-выражение*) END MATCH; BEGIN (* Предварительные вычисления *) Для каждой позиции i вычислить длину a[i]-выражения l[i] FOR i:=n DOWNTO 1 DO (* Распознавание входной цепочки *) h":={[A->b.v]| (A->bv) in P, b=a[i]}; j:=i; MATCH(j,h"); (* Сопоставление нецепных правил*) (* Сопоставление цепных правил *) h"==h"+{[A-> B.]| (A->B) in P, [B->w.] in h"}; r[i]:= {(A->w) | [A->w.] in h"} END; Проверить, принадлежит ли (S->w) множеству r[1] END Множества r[i] имеют размер O(|P|). Очевидно, что алгоритм 3 имеет временную и емкостную сложность O(n). Алгоритм 3 можно применять для генерации кода в компиляторе, не использующем оптимизирующие преобразования компилируемой программы. В этом случае наилучшим промежуточным представлением является последовательность префиксных выражений, что обусловлено его компактной формой. Мы предполагаем, что фазе генерации кода предшествуют оптимизирующие преобразования последовательности деревьев выражений. Следующие алгоритмы будут обрабатывать деревья выражений, но их можно легко переделать для работы с префиксными выражениями. Пусть G - Д-грамматика. Для каждой цепочки z из L(G) можно построить дерево выражения. Мы можем переписать алгоритм 3 так, чтобы он работал с деревьями выражений, а не с префиксными выражениями. Следующий алгоритм обходит дерево выражения сверху вниз, справа налево и ищет в нем поддеревья, сопоставимые с правыми частями правил из G. Процедура MATCH(n,h") обходит в прямом порядке некоторую окрестность поддерева вершины n, начиная с нее. Процедура проверяет, сопоставимо ли поддерево вершины n с префиксными выражениями {av} из множества исследуемых правил {A->uavy}, и ищет подвыводы, соответствующие этому правилу. Следовательно, если правило A->w сопоставимо с поддеревом вершины m, то префиксное выражение, соответствующее ему, выводится из A, и правило A->w может быть применено в этом выводе. Мы считаем, что нетерминалы являются операторами 0-й размерности. Структура данных, представляющая вершину дерева, имеет следующую форму: PTnode=^Tnode; Tnode=RECORD op : Tterminal; son : ARRAY[1..MaxArity] OF PTnode; rules: SET OF Tproduction END; Алгоритм, обрабатывающий деревья выражений, приведен ниже. .PAGE Алгоритм 4: VAR root:PTnode; h": SET OF Titem; PROCEDURE PARSE(n:PTnode); PROCEDURE MATCH(n:PTnode; h":SET OF Titem); VAR h1,h2: SET OF Titem; BEGIN (* h" = {[A->uc.vw]}, m=Arity(c), c=a[j] *) (* v=v1v2...vk...vm=v'vkv" *) IF h"<>{} THEN (* сопоставление v1,v2,...,vm *) FOR k:=1 TO m DO WITH n^.son[k]^ DO h2:={[A->ucv' B.v"w] | [A->ucv' .Bv"w] in h", vk=B, (B->y) in rule}; h1:={[A->ucv'b.xv"w] | [A->ucv'.bxv"w] in h", vk=bx, b=op }; MATCH(n^.son[k],h1); (* сопоставление {vk} *) h":=h1+h2 END END END END MATCH; BEGIN FOR k:=Arity(n^.op) DOWNTO 1 DO(*FOR i:=n DOWNTO 1*) PARSE(n^.son[k]) END; h":= {[A->a.v]| (A->av) in P, a=n^.op}; MATCH(n,h"); h"== h"+{[A-> B.]| (A->B) in P, [B->w.] in h"}; n^.rules:={(A->w)| [A->w.] in h"} END PARSE; BEGIN (* Предварительные вычисления k1,...,km*) Построить дерево выражения для входной цепочки z; root:= указатель_дерева_выражения; (* Распознать входную цепочку *) PARSE(root); Проверить, принадлежит ли S->w множеству root^.rules; END; .PAGE Выходом алгоритма 4 является дерево выражения для z, вершинам которого сопоставлены применимые правила. Если Д-грамматика неоднозначная, то можно построить несколько различных выводов для заданной входной цепочки. Все возможные выводы можно построить, используя для этого декорированное дерево выражения алгоритма 4 или таблицу r применимых правил и таблицу l длин префиксных выражений алгоритма 3. 4. Выбор дерева вывода наименьшей стоимости Д-грамматики, описывающие системы комад компьютеров, обычно являются неоднозначными грамматиками. Чтобы сгенерировать код для некоторой входной цепочки, необходимо выбрать одно из возможных деревьев вывода. Это дерево должно представлять желаемое качество кода, например размер кода и/или время выполнения. Мы предлагаем выбирать дерево вывода с помощью атрибутов стоимости, атрибутных формул, вычисляющих их значения, и критериев стоимости, которые оставляют для каждого нетерминала единственное применимое правило, анализируя значения атрибутов стоимости. С-атрибуты сопоставляются всем нетерминалам, С-формулы - всем правилам Д-грамматики. Если вершина n дерева вывода помечена нетерминалом A, то с ней связываются С-атрибуты нетерминала A. Их значения вычисляются параллельно с разбором входной цепочки. Значения С-атрибутов должны отражать некоторые свойства выводов из A. Предположим, что для вершины n обнаружено применимое правило p:A::=z0 X0 z1...Xk zk, где zi из T* для 0<=i<=k и Xj из N для 1<=j<=k. С-формулы, соответствующие правилу p, выполняются следующим образом. В соответствии с применимым правилом вершина n имеет потомков n1,...,nk , которые соответствуют нетерминалам X1,...,Xk соответственно. Значения С-атрибутов дерева вывода вычисляются в порядке снизу вверх. Вначале С-атрибуты инициализируются неопределенным значением UndefinedValue. Предположим, что значения С-атрибутов для всех потомков n1,...,nk вершины n вычислены. Если С-формула A.a:=f(Xi.b,Xj.c,...) для 1<=i,j<=k .BREAK сопоставлена правилу p, то выполняется формула n.a:=f(ni.b,nj.c,...), .BREAK вычисляющая для правила p значение атрибута a нетерминала A в вершине n. К нетерминалу A в вершине n может быть применено несколько правил. С-критерий дает возможность выбрать из них единственное. Для этого используются ранее вычисленные значения С-атрибутов нетерминала A в вершине n и значения, только что вычисленные по С-формулам текущего правила (С-значения). Если С-критерий указывает, что текущее правило лучше, чем ранее обработанное правило, или значения С-атрибутов не определены, то С-значения присваиваются С-атрибутам, а соответствующее правило связывается с вершиной n. Когда разбор завершен, правило, связанное с корнем дерева вывода, определяет искомое дерево вывода. Добавим в алгоритм 4 реализацию С-атрибутов, С-формул и С-критериев, чтобы он выбирал единственное дерево вывода. В области значений С-атрибутов входит значение UndefinedValue. С-критерии должны игнорировать правило, если одно из С-значений равно UndefinedValue. Поэтому из алгоритма можно исключить поиск подвыводов, соответствующих исследуемому правилу. Структура данных, представляющая вершину дерева, принимает следующий вид: PTnode=^Tnode; Tnode=RECORD op : Tterminal; son : ARRAY[1..MaxArity] OF PTnode; nonterm: ARRAY Tnonterminal OF RECORD CostAttr : ADDRESS; Production : Tproduction; END; OperatorAttributes: ... END; В общем случае поле CostAttr указывает на область памяти, выделенную для С-атрибутов соответствующего нетерминала. Если для С-атрибутов требуется не более одного машинного слова, они размещаются непосредственно в этом поле. Каждый оператор может иметь атрибуты, значения которых вычислены на предыдущих фазах компиляции. Эти значения сохраняются в поле OperatorAttributes. Тело процедуры PARSE принимает вид: BEGIN FOR k:=Arity(n^.op) DOWNTO 1 DO PARSE(n^.son[k]) END; FOR каждого A из N DO WITH n^.nonterm[A] DO CostAttr:=UndefinedValue; production:=Undefined; END END; h":={ [A->a.v]| (A->av) in P, a=n^.op }; MATCH(n,h"); FOR каждого A->w из P такого, что [A->w.] in h" DO ВычислитьСатрибутыДля(A,n,(A->w)); ПроверитьКритерийДля(A,n^.nonterm[A].CostAttr); IF (A->w) лучше, чем n^.nonterm[A].production THEN Модифицировать(n^.nonterm[A].CostAttr) n^.nonterm[A].production:=(A->w) END END; (* Сопоставить цепные правила h"== h"+{[A-> B.]| (A->B) in P, [B->w.] in h"}; *) WHILE существует правило (A->B) из P такое, что [B->w.] in h" AND no [A->B.] in h" DO ВычислитьСатрибутыДля(A,n,(A->B)); ПроверитьКритерийДля(A,n^.nonterm[A].CostAttr); IF (A->B) лучше, чем n^.nonterm[A].production THEN Модифицировать(n^.nonterm[A].CostAttr) n^.nonterm[A].production:=(A->B) END; h":=h"+{[A->B.]} END END; Когда выбрано "наименьшей" стоимости дерево вывода, вычисляются значения атрибутов, сопоставленных вершинам дерева вывода, и генерируются соответствующие машинные команды. Вычисление значений атрибутов, генерация кода осуществляются в процессе обхода выбранного дерева вывода сверху вниз, слева направо. Обход выбранного дерева вывода выполняется процедурой вычислителя атрибутов, на вход которой поступают корнь дерева выражения и аксиома грамматики. Процедура использует правило p:A::=z0 X0 z1...Xk zk, связанное с указанной вершиной n, и заданный нетерминал A, чтобы определить соответствующие им вершины n1,...,nk и нетерминалы X1,...,Xk. Затем вычислитель рекурсивно обходит каждую вершину ni, имея на входе нетерминал Xi. Алгоритмы, используемые системами BEG[11] и TWIG[12] для нахождения минимального покрытия, аналогичны модифицированному алгоритму 4. В системе BEG алгоритмы сопоставления образцов и нахождения оптимального кода непосредственно включаются в формируемый генератор кода. Какие-либо таблицы управления не используются. Система TWIG строит таблично-управляемый автомат сопоставления образцов. Обе системы выбирают наименьшее покрытие промежуточного дерева с помощью простого критерия минимизации стоимости. Каждому правилу приписывается фиксированная стоимость. Стоимость поддерева - это сумма стоимостей, примененных в нем правил. TYPE TprodNum = [1..NumProd]; Tnonterminal = (Operator,...,Reg); Tterminal = (const,base,assign,indr,plus); TYPE TEvalProc = PROCEDURE(TprodNum,PTnode); PROCEDURE EvalOperator(pn:TprodNum;n:PTnode);... . . . PROCEDURE EvalReg(pn:TprodNum; n:PTnode); CONST BaseN=2; VAR CostAttrValue:... (*for currently computed cost-attributes values*) BEGIN WITH n^.nonterm[ Reg ] DO CASE (pn-BaseN) OF (*compute cost-attributes values*) |0:CostAttrValue ... :=CostAttributeRuleForAlterN0 | . . . |6:CostAttrValue ... :=CostAttributeRuleForAlterN6 END; EvaluateCriterionReg; (*evaluate cost-criterion for Reg*) IF pn is better then production THEN (* update fields *) CostAttr:=CostAttrValue; production:=pn END; END END EvalReg; PROCEDURE notMatched(pn:TprodNum;n:PTnode);BEGIN END notMatched; PROCEDURE matchConst(n:PTnode); ... END matchConst; BEGIN EvalReg(6,n) END matchConst; . . . PROCEDURE matchPlus(n:PTnode); CONST NumAlternatives=3; (* the number of productions started with operator + *) TYPE Tmatched=ARRAY[1..NumAlternatives] OF TEvalProc; TprodN =ARRAY[1..NumAlternatives] OF TprodNum; CONST Cmatched=Tmatched(EvalReg,EvalReg,EvalReg); ProdN =TprodN (2 ,3 ,4 ); VAR matched:Tmatched; BEGIN WITH n^ DO (* n points to node for + *) matched:=Cmatched; (* assume all matched *) IF son[1]^.op<>const THEN matched[2]:=notMatched END; WITH son[2]^ DO IF op<>indr THEN matched[3]:=notMatched ELSE IF son[1]^.op<>plus THEN matched[3]:=notMatched END END END; FOR i:=1 TO NumAlternatives DO matched[i](ProdN[i],n) END; END END matchPlus; TYPE TmatchProc =PROCEDURE(PTnode); TmatchArr =ARRAY Terminal OF TmatchProc; CONST matchNode=TmatchArr(matchConst,...,matchPlus); PROCEDURE PARSE(n:PTnode); BEGIN WITH n^ DO FOR k:=1 TO Arity[op] DO PARSE(son[k]) END; matchNode[op](n); (* Match unchain productions *) MatchChainProductions(n); END END PARSE; 5. Заключение Мы исследовали алгоритм Кока-Янгера-Касами, модифицировали его, чтобы он работал линейное время для Д-грамматик. Показали, что известные алгоритмы сопоставления образцов являются частными случаями алгоритм Кока-Янгера-Касами, модифицированного для работы с Д-грамматиками. Основные преимущества нашего метода состоят в следующем: (а) генерация кода осуществляется с помощью традиционных атрибутной техники и техники синтаксического разбора, (б) генератор кода описывается атрибутной грамматикой, (в) предложена эффективная реализация генератора кода. .PAGE Литература 1. Бирюков А.Н. Методы построения генераторов кода. Прикладная информатика, М.:Финансы и статистика,1987. 2. Ganapathy M.,Fischer C.N.,Hennessy J. Retargetable code generation // ACM Comp.Surveys,1982,V.14,N.4. 3. Chow F.C.,Ganapathy M. Intermidiate languages in compiler construction - a bibliography // ACM SIGPLAN Not.,1982,V.18,N.11. 4. Бездушный А.Н. К вопросу об автоматической генерации кода. Автоматизация программирования. М.: ВЦ АН СССР,1990. 5. Wasielew S.G. A compiler writing system with optimization capabilities for complex order structures. Ph.D.Th., Northwestern University,Evanston,1972. 6. Glanville R.S. A machine independent algorithm for code generation and its use in retargetable compilers. Ph.D.Th, Univ.of California,Berkeley,1977. 7. Graham S.L.,Glanville R.S. A new method for compiler code generation // Proc.of the 5th ACM Symp.on Principles of programing languages, ACM,1978. 8. Graham S.L.,Henry R.R.,Schulman R.A. An Experiment in table driven code generation // ACM SIGPLAN Not.,1982,V.17,N.6. 9. Ganapathy M.,Fischer C.N. Description driven code generation using attribute grammars // Proc.of the 9th ACM Symp.on Principles of programming languages, ACM,1982. 10. Christopher T.W.,Hatcher P.J.,Kukuk P.C. Using dynamic programing to generate optimal code in Graham-Glanville style code generation // ACM SIGPLAN Not.,1982,V.19,N.6. 11. Emmelman H.,Schroer F.W.,Landweher R. BEG - a generator for efficient back-ends // ACM SIGPLAN Not. 1989, pp.227-237. 12. Aho A.U.,Ganapathi M.,Tjiang S.W. Code generation using tree matching and dynamic programing // ACM transaction of programing languages and systems,1989,V.11,N.4. 13. Graham S.L., Harrison M.A., Ruzzo W.L. Am improved context-free recognizer // ACM transaction on programming language systems, 1980, N.2. 14. Harrison M.A. Introduction to formal language theory. Addison-Wesley, Reading, Mass., 1978. 15. Hoffman C.W.,O'Donnell M.J. Pattern mathing trees // J.ACM,1989,V.29,N.1. 16. Бездушный А.Н. Серебряков В.А. Входной язык системы автоматизации построения трансляторов СУПЕР. М.: ВЦ АН СССР,1986. 17. A.Bezdushny, V.Serebriakov, SUPER: A practical attributed compiler writing system, Proceedings Bilateral Workshop on Compiler Construction, University of Twente, Enschede, The Netherlands, 1990.