Применение методов синтаксического анализа для автоматической генерации оптимального кода. А.Н. Бездушный, В.А.Серебряков Вычислительный центр Академии наук РФ, Вавилова 40, Москва, 117333. Аннотация. В первой части статьи исследуются системы TWIG и BEG автоматической генерации оптимального кода, использующие метод сопоставления с образцом для выборки машинных команд. Рассматриваются принципы их работы, обеспечивающие высокую скорость генерации и оптимальность кода. Во второй части статьи приведена модификация алгоритма синтаксического анализа Кока, Янгера и Касами для древовидных грамматик, позволяющая использовать его для генерации оптимального кода. Задача выборки команд сводится к синтаксичесгому анализу для неоднозначных древовидных грамматик, а задача выбора оптимальной последовательности команд - к задаче выбора наилучшего с точки зрения генерации кода дерева разбора. Алгоритмы систем BEG и TWIG являются частными случаями такой модификации алгоритма Кока, Янгера и Касами. В третей части статьи изучаются задачи выбора команд и распределения регистров, когда во внимание принимаются общие подвыражения. 1. Введение и основные понятия Процесс компиляции можно разбить на две фазы. На первой фазе(front-end) выполняется лексический, синтаксический, контекстный анализ, формируется промежуточное представление исходной программы, содержащее только те компоненты исходной программы, которые необходимы в дальнейшем. Вторая фаза(back-end) состоит в генерации объектного кода, выполнении машинно-зависимой оптимизации, формировании загрузочного модуля. Проблемы первой фазы компиляции достаточно хорошо изучены. Имеются алгоритмы и средства автоматического построения соответствующих компонент компилятора по декларативному описанию языка. Из проблем второй фазы задача генерации кода является наиболее трудной, что связано со сложностью соответствующих алгоритмов, необходимостью учитывать архитектуру конкретного компьютера. Только в последнее время стали вырабатываться общие методы, алгоритмы построения генераторов кода для универсальных компьютеров. Хороший обзор подходов к решению этой проблемы приведен в [1]. Исследование теоретических аспектов и практических алгоритмов можно найти в [2]. При построении генератора объектного кода необходимо решить следующие задачи. 1) Выбор промежуточного представления исходной программы. 2) Распределение памяти в объектной программе. 3) Выбор машинных команд. 4) Распределение регистров. 5) Оптимизация программы. 6) Формирование загрузочного модуля. В данной работе основное внимание будет уделено п. 3. Выбор промежуточного представления тесно связан с классом входных языков, организацией компьютера. Известно несколько вариантов промежуточного представления исходной программы: последовательность команд абстрактного компьютера, последовательность триад или тетрад, лес атрибутированных деревьев, последовательность линеаризованных деревьев[3]. Большинство методов генерации кода используют древовидную форму представления промежуточной программы. При выборе промежуточного представления существенным является вопрос о включении в него описаний объектов, их типов. Оставляя понятия типа в промежуточном представлении, мы получаем машинно-независимое представление[4]. Иначе необходимо использовать некоторую абстракцию памяти компьютера и провести ее распределение на первой фазе компиляции. Это позволяет приступить к выбору машинных команд на первом же этапе второй фазы компиляции, лучше реализовать те конструкции исходного языка, которые не отражены в промежуточном представлении. Задача распределения памяти для традиционных языков состоит в выделении памяти для хранения значений переменных, организации доступа к ним, реализации механизмов процедур и передачи параметров. Существует ряд хорошо себя зарекомендовавших и почти стандартных методов решения этой задачи. Они хорошо согласуются с такими этапами первой фазы компиляции, как обработка описаний, генерация промежуточного представления. Далее мы будем считать, что промежуточное представление - последовательность префиксных выражений или деревьев выражений, в которых операторы имеют фиксированное число операндов. Операторы могут иметь атрибуты, значения которых определяются на первой фазе процесса компиляции. Распределение памяти выполняется так же на первой фазе. Запись a0e1e2...ek - это префиксное выражение, в котором оператор a0 размерности k=Arity(a0) применяется к выражениям e1,e2,...,ek. Если a0...an является префиксным выражением и оператор a0 имеет размерность k, то существует единственная запись этого выражения как a0e1e2...ek для некоторых префиксных выражений e1,e2,...,ek. Поэтому для каждой позиции i (i=0,n) в префиксном выражении a0...an мы можем вычислить позицию (i+j) такую, что ai...am=aie1e2...el , m=i+j-1 и l=Arity(ai). Запись ai...am будем называть ai-выражением, имеющим длину j. Для каждого префиксного выражения можно построить соответствующее ему дерево выражения. Если оператор a0 размерности Arity(a0)=k применен к выражениям e1,e2,...,ek (z=a0e1e2...ek), то соответствующее ему дерево выражения T0 показано на рис. 1, где T1,T2,...,Tk - это деревья выражений e1,e2,...,ek соответственно. (a0) T0 / | \ / | \ / | \ /\ / \ ... /\ /T1\ /T2 \ /Tk\ ---- ----- ---- Рис. 1. Дерево выражения z=a0e1e2...ek. На рис._2 показано дерево выражения для прeдложения a:=b[i]+5, где a,b,i - локальные переменные, хранимые со смещениями x,y,z в областях данных, указываемых регистрами Ra,Rb,Rz соответственно. Элемент массива b занимает память емкостью в одну машинную единицу. 0-местные операторы reg, const возвращают значения, которые являются значениями атрибутов (на рисунке указываются в скобках после оператора) соответствующих вершин промежуточного дерева. Оператор contents возвращает содержимое ячейки памяти, имеющей адрес, задаваемый аргументом оператора. := | ------------- / \ + + / \ / \ / \ / \ reg(Ra) const(x) contents const(5) | | + / \ / \ + contents / \ | / \ | reg(Rb) const(y) + / \ / \ reg(Ri) const(z) Рис. 2. Дерево выражения для прeдложения a:=b[i]+5. Центральная проблема при разработке генератора кода - это задача выбора последовательности машинных команд, реализующих промежуточное представление исходной программы. В современных компьютерах одни и те же действия можно реализовать многими способами. Задача выбора команд состоит в том, чтобы выбрать наилучший способ реализации того или иного действия, последовательности действий. Простейший алгоритм генерации кода заключается в обходе промежуточного дерева в обратном порядке и выборе команды для каждой вершины отдельно. Получающийся код будет очень плохой, так как часто одна команда может быть использована для "реализации" нескольких вершин промежуточного дерева. Например, команда MOV 10(R0),20(SP) выполняет вычисление адреса источника, извлечение из памяти его значения и пересылку этого значения по вычисленному ею же адресу приемника. Поэтому генератор кода должен комбинировать узлы промежуточного дерева, чтобы произвести одну машинную команду. Последние исследования методов формализации генерации кода показали, что применение метода "сопоставления образцов" (pattern matching) для решения задачи выбора команд дает наилучшие результаты [11,12]. Первым предложил этот метод С.Г. Васильев [5]. Идея метода заключается в следующем. Машинные команды и/или их последовательности описываются посредством "образцов поддеревьев" (tree patterns). Выбор команд эквивалентен нахождению покрытия промежуточного дерева этими образцами. Образцы поддеревьев задаются в правилах выбора команд образец_поддерева '->' результирующая_вершина [ машинная_команда ] Образцы поддеревьев наряду с вершинами промежуточного дерева могут содержать в качестве листьев новые вершины, которые отсутствуют в промежуточном дереве. Эти вершины появляются вследствие применения правил выбора, в которых эти вершины являются результирующими и используются для выражения взаимосвязи между образцами поддеревьев. Они называются метками правил выбора[12] или нетерминалами[11], а вершины промежуточного дерева - операторами. Результирующая вершина представляет результат, вычисляемый командой, связанной с этим образцом. На рис. 3 показан пример правил выбора. Правила выбора можно рассматривать как правила преобразования промежуточного дерева, когда сопоставленный образцу фрагмент дерева заменяется на результирующую вершину. Преобразование продолжается, пока применимы правила выбора, т.е. пока не будет получена единственная вершина (stat). Рис. 4 содержит пример покрытия промежуточного дерева рис. 2 правилами выбора рис. 3. В рамки заключены фрагменты дерева, сопоставленные образцу правила, номер которого указывается в левом верхнем углу рамки. В квадратных скобках указаны результирующие вершины. Такое покрытие дает следующую последовательность команд. ADD #y,Rb ADD z(Ri),Rb MOV (Rb),Rb ADD #5,Rb MOV Rb,x(Ra) Другая трактовка правил выбора заключается в том, что они "сжимают" вершины промежуточного дерева, входящие в образцы правил выбора, в единственную вершину дерева, которая помечается номером правила выбора. Результирующее дерево называют покрывающим деревом [11]. Данный подход позволяет сохранить структуру дерева для последующих этапов генерации кода, например, для распределения регистров. Обойдя покрывающее дерево в обратном порядке и используя метки вершин, мы можем выдать код для каждой вершины отдельно. Пример покрывающего дерева для покрытия, отличного от покрытия рис._4, показан на рис. 5. Назовем покрывающее дерево t промежуточного дерева T A-покрытием T, если корень t помечен правилом, имеющим результирующую вершину A. Например, покрывающее дерево рис._5 является stat-покрытием. Процесс нахождения покрывающего дерева недетерминированный, так как можно построить множество возможных покрытий для одного и того же промежуточного дерева. Задачей выбора команд становится нахождение "подходящего" покрытия, соответствующего "лучшему" способу реализации того или иного действия, последовательности действий. 1: const(c) -> reg(i) 2 MOV #c,Ri 2: := -> stat 4 MOV Rj,c(Ri) / \ / \ + reg(j) / \ reg(i) const(c) 3: contents -> reg(i) 3 MOV c(Rj),Ri | + / \ / \ reg(j) const(c) 4: + -> reg(i) 3 ADD #c,Ri / \ / \ reg(i) const(c) 5: + -> reg(i) 2 ADD Rj,Ri / \ / \ reg(i) reg(j) 6: + -> reg(i) 4 ADD c(Rj),Ri / \ / \ reg(i) contents | + / \ reg(j) const(c) 7: contents -> reg(i) 2 MOV (Ri),Ri | reg(i) правило выбора вес машинная команда Рис. 3. Правила выбора для некоторых машинных команд. +---------[stat]---------------------------------+ ¦2 := ¦ ¦ / \ ¦ ¦ + \ ¦ ¦ / \ \ ¦ ¦reg(Ra) const(x) \ ¦ ¦ +------------------[reg(Rb)]-----------------+ ¦ ¦ ¦ 4 + ¦ ¦ ¦ ¦ / \ ¦ ¦ ¦ ¦ / const(5) ¦ ¦ ¦ ¦ / ¦ ¦ ¦ ¦ +--------------[reg(Rb)]-----------------+ ¦ ¦ ¦ ¦ ¦ 7 contents ¦ ¦ ¦ ¦ ¦ ¦ | ¦ ¦ ¦ ¦ ¦ ¦ +------------[reg(Rb)]---------------+ ¦ ¦ ¦ ¦ ¦ ¦ ¦6 + ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ / \ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ / \ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ +-----[reg(Rb)]---+ \ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦4 + ¦ contents ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ / \ ¦ | ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ / \ ¦ | ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ reg(Rb) const(y)¦ + ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ +-----------------+ / \ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ / \ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ reg(Ri) const(z) ¦ ¦ ¦ ¦ ¦ ¦ ¦ +------------------------------------+ ¦ ¦ ¦ ¦ ¦ +----------------------------------------+ ¦ ¦ ¦ +--------------------------------------------+ ¦ +------------------------------------------------+ Рис. 4. Покрытие промежуточного дерева рис. 2. Правило 2 | Правило 5 / \ Правило 7 Правило 1 | Правило 5 / \ Правило 4 Правило 2 Рис. 5. Покрывающее дерево для промежуточного дерева рис.2. Было предложено несколько методов для нахождения "подходящего" покрытия. Для этого может вводиться понятие "веса" ("стоимости"), связываемое с правилом выбора и определяющее качество генерируемого кода, например, скорость, размер кода. Грем и Глэнвилл [6,7,8] использовали LR-анализатор для нахождения "подходящего" покрытия. Вершины образца правила выбора записываются в прямом порядке. Эта запись рассматривается как правая часть, а результирующая вершина - как левая часть правила контекстно-свободной грамматики. Промежуточное дерево записывается в прямом порядке и поступает на вход LR-анализатору, построенному по этой грамматике. Как правило, грамматика получается не только LR(1)-грамматикой, но и оказывается неоднозначной. В конструктор LR-анализаторов встраиваются специальные действия для разрешения конфликтов и неоднозначностей грамматики, например, предпочтение сдвига свертке, свертки по более длинному правилу - свертке по более короткому. Фиксированность реакции на конфликты, неучет контекста иногда приводят к неправильному поведению, возможны случаи, когда анализатор попадает в ошибочное состояние на правильной программе. Чтобы это избежать, грамматика вручную преобразуется перед началом построения таблиц. Требуется детальное знание внутренних алгоритмов синтаксического анализа, чтобы написать спецификацию, которая даст хороший генератор кода. Ганапати и Фишер [2,9] обобщили идею Грем и Глэнвилла, дополнив КС-грамматику атрибутами, т.е. использовали атрибутную грамматику для описания генератора кода. Чтобы снять нагрузку с КС-грамматики, они предложили исключить из синтаксического описания генератора явное указание некоторых свойств компьютера, например, способов адресации операндов, типов операндов и т.п., и реализовать их посредством атрибутов, чтобы упростить КС-грамматику. Неоднозначности разрешаются с помощью предикатов правил выбора, управляющих разбором. Разбор становится контекстно-зависимым. Сравнение чисто синтаксического подхода Грем и Глэнвилла с атрибутным подходом Ганапати и Фишера показало значительно более низкую эффективность последнего. Другое обобщение метода Грем и Глэнвилла [10] исходит из того, что детерминированность алгоритма разбора не позволяет выбрать лучшую из возможных последовательностей команд для заданного дерева. Поэтому предлагается заменить LR(1)-анализатор алгоритмом анализа Эрли, который может вести разбор по неоднозначной грамматике, затрачивая на разбор цепочки длины n время O(n3) и память емкостью O(n2). Анализатор строит более лучший код, но затрачивает слишком много ресурсов. Чтобы избежать проблем, возникающих при использовании детерминированного анализатора, в последних работах по генерации кода [11,12] используется общий метод сопоставления с образцом, гарантирующий, что будет получено наилучшее возможное покрытие. Генераторы кода, формируемые системами BEG[11], Twig[12], комбинируют быстрый алгоритм сопоставления образцов с алгоритмом динамического программирования для вычисления минимального покрытия. Алгоритмы сопоставления образцов работают сверху-вниз(Twig) или снизу-вверх(BEG). Алгоритм динамического программирования решает задачу генерации кода для выражения E, разбивая ее на k меньших подзадач генерации оптимального кода для k подвыражений Ei выражения E. Решения подзадач сохраняются в таблицах и никогда не вычисляются заново. В системе BEG, в отличие от системы Twig, алгоритмы сопоставления с образцом и нахождения оптимального кода непосредственно включаются в формируемый генератор кода и не используют каких-либо таблиц управления. Рассмотрим более детально эти две реализации систем построения генeраторов кода по строго декларативному описанию генератора кода. На текущий момент это лучшие реализации подобных систем. 2. Система BEG В системе BEG правила выбора имеют следующую форму: RULE образец '->' результирующая вершина; [ CONDITION условие_применимости_правила;] COST целое_число-вес_команды; [ EMIT машинная_команда или/и формулы_вычисления_атрибутов;] Например, правило выбора для команды INC RULE + reg const -> reg ; CONDITION (const.value=1); COST 1; EMIT { вывод команды INC Ri, где Ri=reg.register } где через "." указываются атрибуты операторов. Атрибуты операторов, определяемые на этапе генерации промежуточного дерева, можно использовать в условиях применимости, EMIT-действиях. EMIT-действия генерируют машинный код или/и вычисляют значения синтезированных атрибутов в течение вывода кода. Синтезированные атрибуты доступны только внутри EMIT-действий и используются, например, для вычисления кода способа адресации операндов. Как правило, компьютер допускает несколько способов адресации операндов, которые можно использовать в большом числе команд. Обычно используется отдельный нетерминал для каждого способа адресации, и задается правило выбора для каждой комбинации способа адресации и машинной команды, что приводит к огромному количеству правил выбора. Чтобы избежать этого, в системе BEG введено понятие цепных правил выбора - правил, где образец состоит из единственного нетерминала. Создается одно правило выбора для каждой машинной команды, в котором операнды описываются нетерминалами, представляющими все или часть способов адресации. Нетерминалы, представляющие отдельные способы адресации, выводятся из первых с помощью цепных правил. Задача, нахождения оптимального покрытия промежуточного дерева решается следующим образом. Для каждой вершины n промежуточного дерева T и для каждого нетерминала A вычисляются значения cost(n,A) - вес минимального A-покрытия поддерева Tn с корнем n, rule(n,A) - номер правила выбора, которым помечен корень A-покрытия. Если A-покрытие не существует, то cost(n,A) имеет значение представляющее бесконечность, а значение rule(n,A) не определено. Значения cost(n,A), rule(n,A) вычисляются снизу-вверх, начиная с листьев промежуточного дерева T. Для каждой вершины n вначале рассматриваются все нецепные правила выбора, имеющие образец сопоставимый с поддеревом Tn, корнем которого является вершина n. Пусть r такое правило с результирующей вершиной A и образцом, в который входят нетерминалы A1,A2,...,Ak и операторы O1,O2,...,Op. r: O0 O1 A1 O2 A2 ... Op Ak -> A В результате предыдущих шагов процесса вычисления покрытия вершинам n1,n2,...,nk сопоставлены нетерминалы A1,A2,...,Ak и вычислены значения cost(ni,Ai) (рис._6). ... | n O0 -> A / \ / \ / \ / \ m1 ... mp O1 ... Op /\ /\ /\ /\ / \ / \ / \ / \ (n1) m2 ... (nk) A1 O2 ... Ak ... /\ ... /\ / \ / \ (n2) ... A2 ... ... Рис. 6. Поддерево и сопоставимый с ним образец правила r. Вершины m1,m2,...,mp промежуточного дерева помечены операторами O1,O2,...,Op соответственно. Вес A-покрытия поддерева t вычисляется как C(r)=вес_правила_r+cost(n1,A1)+...+cost(nk,Ak) Пусть r0 правило выбора, где значение C(r) минимально. Положим cost(n,A)=C(r0), rule(n,A)=r0. После того как рассмотрены все нецепные правила выбора, исследуется применимость цепных правил. Цепные правила обрабатываются, пока существуют правила r: A -> B имеющие стоимость Cr, такие, что Cr+cost(n,A) < cost(n,B) для которых выполняется cost(n,B)=C(r), rule(n,B)=r. Стоимость B-покрытия, состоящего из цепного правила r и A-покрытия, меньше стоимости B-покрытия, полученного до этого. В системе BEG значения cost и rule вычисляются параллельно с построением промежуточного дерева и сохраняются в его вершинах, описываемых как Tnode=POINTER TO Tnoderec; Tnoderec=RECORD op :Toperator; son :ARRAY[1..MaxOpArity] of Tnode; cost:ARRAY[Tnonterminal] of Integer; rule:ARRAY[Tnonterminal] of Trulenum END; Для каждого оператора O0 создается процедура, которая добавляет в промежуточное дерево вершину с меткой O0, вычисляет значения cost(n,A), rule(n,A) и возвращает указатель на построенное дерево. В процедуру помещается код обработки всех правил выбора, имеющих образец с корнем O0. PROCEDURE операторO0(операнды:Tnode):Tnode; VAR node:Tnode; c:INTEGER; BEGIN Создать вершину n (node указывает на нее) и связать ее с поддеревьями операндов. Проинициализировать cost значением, представляющим бесконечность (MaxInt/MaxNontInPat). IF (m1^.op=O1)AND(m2^.op=O2)... AND (mp^.op=Op) THEN c=вес_правила_r+n1^.cost[A1]+...+nk^.cost[Ak]; IF node^.cost[A] > c THEN IF условие_применимости_правила_выбора_r THEN node^.cost[A]:=c; node^.rule[A]:=r END END END; MatchChainRules(node); RETURN node END; Здесь ni,mi представляют код path(ni), path(mi), осуществляющий доступ к соответствующей вершине и определяемый как path(n)=node, если вершина f - отец вершины l и l - i-й сын f, то path(l)=path(f)^.son[i]. Например, n2=node^.son[1]^.son[2]^.son[1] . Процедура MatchChainRules(node) содержит код, исследующий применимость цепных правил. Она вызывается один раз для каждого оператора, так как цепные правила не зависят от операторов. Код, генерируемый для цепных правил, аналогичен коду нецепных правил. Каждому оператору r: A -> B сопоставляется код IF node^.cost[B] > node^.cost[A]+вес_правила_r THEN node^.cost[B]:= node^.cost[A]+вес_правила_r; node^.rule[B]:= r END; Чтобы избежать повторное тестирование применимости цепных правил, система BEG формирует последовательности цепных правил, гарантирующих, что после их выполнения никакие другие цепные правила не будут применены. 3. Система Twig В системе Twig сопоставление образцов осуществляется таблично-управляемым автоматом. Хоффман и Доннелл [20] предложили алгоритм сопоставления образцов, в основе которого лежит расширение алгоритма Ахо-Корасика [21] поиска ключевых слов в строке. Автомат поиска ключевых слов строится из TRIE-структуры для множества ключевых слов и функции перехода по ошибке. TRIE-структура для одного ключевого слова a__1_a__2_...a__m=w - диаграмма переходов с m+1 состояниями, где каждое состояние соответствует префиксу ключевого слова w. a1 a2 am (0)---->(1)---->...---->(m+1) Начальное состояние 0 соответствует пустой строке, завершающее состояние m+1 - всему ключевому слову. Функция перехода по ошибке f определена на всех состояниях, кроме начального. Пусть u и v префиксы w, с ними связаны состояния su и sv соответственно. Равенство f(su)=sv имеет место, тогда и только тогда, если v является самым длинным суффиксом u (w=uw' w=vw" u=u'v). TRIE-структура для множества ключевых слов получается в результате следующего расширения понятия TRIE-структуры для одного ключевого слова. Каждое состояние в TRIE-структуре соответствует префиксу одного или более ключевых слов. Начальное состояние соответствует пустой строке. Состояние, соответствующее какому-нибудь ключевому слову, является завершающим. Дополнительно определяется переход из начального состояния в само себя для всех символов, которые не являются первыми символами ключевых слов. Аналогично доопределяется функция перехода по ошибке. Автомат поиска ключевых слов из множества ключевых слов K находит все их вхождения в строку x за время O(|K|+|x|). Идея расширения этого автомата до автомата сопоставления образцов исходит из того, что дерево характеризуется множеством записей путей из корня дерева к листьям, если ветви вершин пронумерованы слева-направо, начиная с 1. Например, правила выбора 1,5,6 рис. 3 имеют следующее множество записей путей. const + 1 reg + 2 reg + 2 contents + 1 reg + 2 contents + 2 const Запись +1reg представляет самый левый путь в образцах правил 5 и 6. Из множества записей путей, рассматриваемых как множество ключевых слов, строится автомат. Пусть по множеству правил выбора R={ti -> A_i}, где t_i - образец, A_i - нетерминал, построен автомат с функцией перехода succ(q,x), возвращающий состояние, достижимое из состояния q при входном символе x. Вершины промежуточного дерева описываются следующим образом Tnode=POINTER TO Tnoderec; Tnoderec=RECORD op :Toperator; state :Tstate; parent:Tnode; son :ARRAY[1..MaxOpArity] of Tnode; cost :ARRAY[Tnonterminal] of Integer; rule :ARRAY[Tnonterminal] of Trulenum; b :ARRAY[1..NumOfRules] of BITSET; END; Процедура Visit(root,0) обходит в прямом порядке промежуточное дерево, вычисляет состояния для каждой вершины дерева и вызывает процедуру PostProcess. PROCEDURE Visit(n:Tnode; k:CARDINAL); BEGIN IF k=0 (* n - корень дерева *) THEN n^.state:=succ(0,n^.op) (* где 0 - начальное состояние автомата *) ELSE n^.state:=succ(succ(n^.parent^.state,k),n^.op) (* n является k-м сыном вершины n^.parent *) END; FOR i:=1 TO Arity[n^.op] DO Visit(n^.son[i],i) END; PostProcess(n,k) END; Если n^.state - завершающее состояние, то в вершине n обнаружен конец записи пути какого-то образца. Вершину, в которой начинается путь, можно обнаружить, двигаясь от n вверх к корню дерева. Образец сопоставим с поддеревом Tn, имеющим корень в вершине n, если в этой вершине начинаются все пути этого образца. Чтобы обнаружить поддеревья, сопоставимые с образцами правил выбора, с каждой вершиной n промежуточного дерева связывается битовая строка n^.b[i] для каждого образца ti. Длина битовой строки равна длине самого длинного пути в ti плюс один. Биты строки пронумерованы справа-налево, начиная с 0. Смысл битовой строки состоит в следующем: если бит j строки n^.b[i] установлен, то вершина n промежуточного деревa соответствует вершине образца ti, расположенной на глубине j. Отметим, что путь в образце ti длиной j представляется записью пути длиной 2j+1. Вычисление допустимых покрытий осуществляется снизу-вверх. При обработке вершины n промежуточного дерева, у которой n^.state содержит завершающее состояние, соответствующее концу записи пути в образце ti длиной 2j+1, в строке n^.b[i] устанавливается бит j. Шаг индукции следует из того, что вершина n промежуточного деревa соответствует вершине образца ti, расположенной на глубине j-1, если ее сыновья m_k соответствуют вершинам образца ti, расположенным на глубине j, то есть битовую строку n^.b[i] вершины n можно вычислить, сдвигая вправо на один бит строки mk^.b[i] ее сыновей, вычисляя их побитовое произведение и складывая по битам его с текущим значением n^.b[i]. Процедура PostProcess определяет допустимые сопоставления образцов. PROCEDURE PostProcess(n:Tnode; k:CARDINAL); BEGIN FOR i:=1 TO NumOfRules DO n^.b[i]:={} END; IF n^.state - завершающее состояние THEN SetPartial(n,n^.state) END; FOR i:=1 TO NumOfRules DO b:={}; FOR j:=1 TO Arity[n^.op] DO b:=b*ShiftRight1Bit(n^.son[j]^.b[i]) END; n^.b[i]:=n^.b[i]+b END; DoReduce(n,k) END; Процедура SetPartial устанавливает бит j в строке n^.b[i] для каждой записи пути в образце ti длиной 2j+1, соответствующей завершающему состоянию. PROCEDURE SetPartial(n:Tnode,q:Tstate); BEGIN FOR i:=1 TO NumOfRules DO IF состояние q соответствует концу записи пути в образце ti длиной 2j+1 THEN n^.b[i]:=n^.b[i]+{j} END END END; Образец ti сопоставим с поддеревом, имеющим корень n, тогда и только тогда, если 0-й бит n^.b[i] установлен, т.е. n соответствует корню ti - вершине образца ti, расположенной на глубине 0. Затем, если обнаружено поддерево, сопоставимое с образцом ti, необходимо "заменить" его на результирующую вершину Ai образца ti, чтобы найти покрытия, включающие такой образец, то есть, чтобы найти поддеревья, сопоставимые с образцом tj, в который в качестве листа входит Ai. Процедура DoReduce "модифицирует" промежуточное дерево, вычисляет веса "подходящих" покрытий и сохраняет номера правил выбора, используемых при его построении. Функция cost(ti,n) вычисляет вес применения правила выбора t_i->A_i в вершине n. Веса A_i-покрытий, номера правил выбора t_i->A_i сохраняются в n^.cost[Ai] и n^.rule[Ai] соответственно. Предполагается, что до вызова процедуры visit, для всех вершин n поля n^.cost[Ai] проинициализированы значением, представляющим бесконечность, а n^.rule[Ai] - нулем. PROCEDURE DoReduce(n:Tnode; K:CARDINAL); BEGIN FOR i:=1 TO NumOfRules DO IF 0 in n^.b[i] THEN (* n соответствует корню ti *) IF cost(ti,n)=0. 2._Правая часть любого правила A->w из P должна быть префиксным выражением с операторами из T и операндами из N. Назовем грамматики такого вида Д-грамматиками (tree grammar). Машинные команды описываются правилами АГ. Код генерируется атрибутными формулами, сопоставленными правилам АГ. Нетерминалы в правой части синтаксического правила представляют результаты выполнения предыдущих команд, а нетерминал левой части - результат выполнения описываемой команды. На рис. 7 показано дерево для префиксного выражения := @ + CONST(a) BASE(a) + CONST(5) @ + CONST(a) BASE(a) соответствующего прeдложению a:=a+5, где a - локальная переменная, хранимая со смещением CONST(a) в области данных, указываемой регистром BASE(a). Значения атрибутов операторов указаны в скобках. Оператор @ преобразует свой аргумент в адрес памяти. := / \ / \ @ + | / \ + CONST(5) @ / \ | CONST(a) BASE(a) + / \ CONST(a) BASE(a) Рис. 7. Дерево промежуточного представления цепочки a:=a+5. На рис. 8 показаны правила АГ, необходимые при генерации кода для выражения рис. 7. Генератор кода анализирует входное префиксное выражение и строит дерево разбора. В процессе обхода дерева разбора вычисляются атрибуты и генерируется код в соответствии с семантическими формулами правил, примененных в дереве разбора. Как правило, Д-грамматики, описывающие машинные команды, являются неоднозначными грамматиками. Для каждой входной цепочки можно построить несколько выводов, отражающих код разного качества. Чтобы указать качество генерируемого кода (например, размер кода или время выполнения), система СУПЕР позволяет сопоставить нетерминалам специальные атрибуты стоимости (С-атрибуты), а синтаксическим правилам атрибутные формулы (С-формулы) для их вычисления. С-атрибуты вычисляются одновременно с синтаксическим анализом префиксного выражения. Неоднозначности синтаксического разбора разрешаются в соответствии с критерием стоимости (С-критерий). Каждому нетерминалу сопоставляется свой С-критерий. Используя значения С-атрибутов, С-критерий определяет правило, которое необходимо приметить к нетерминалу в текущем контексте дерева вывода. Правило, выбранное для аксиомы грамматики, определяет единственное дерево вывода. Когда выбрано наиболее подходящее дерево вывода, вычисляются значения атрибутов, сопоставленных его вершинам, и генерируются соответствующие машиннные команды. (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. Рис. 8. Правила, необходимые при генерации кода для выражения рис. 7. 4.1. Алгоритм синтаксического анализа Кока-Янгера-Касами Пусть 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___1a___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} Это означает, что j символов входной цепочки z, начиная с i-го символа, выводятся из A. Цепочка z принадлежит L(G) тогда и только тогда, когда существует объект вида [S->w__.], принадлежащий h[1,n]. Рассмотрим алгоритм Кока-Янгера-Касами. На первом шаге вычисляются множества 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]. Алгоритм 1: VAR a :ARRAY[1..n] of Tterminal;(*ai обозначает a[i] *) h :ARRAY[1..n],[0..n] OF SET OF Titem; BEGIN FOR i:=1 TO n DO h[i,0]:={ [A->.w] | A->w IN 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=ai+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; (* замыкание *) WHILE существует [A->.Bv] IN h[i,0] такое, что [B->w.] IN h[i,j] и нет [A->B.v] IN h[i,j] DO h[i,j]:=h[i,j]+{[A->B.v]} END; END; END; Проверить, принадлежит ли [S->w.] множеству h[1,n] END Вычисляя множества h[i,1],...,h[i,n-i+1] для каждой позиции i, алгоритм распознает все выводы цепочки ai...ak (k<=n-i+1). Объект [A->w.] включается в множество h[i,k-i+1], если найден некоторый вывод A_=>*_ai...ak Алгоритм Кока-Янгера-Касами строит n(n+1)/2 множеств h[i,j], т.е. ему требуется объем памяти O(n2), где n - длина входной цепочки. Множество h[i,j] имеет O(|P|) объектов. Алгоритм выполняет O(j) шагов, чтобы обработать все пары (h[i,k],h[i+k,j-k]) для kua_pwa_r...a_qv (ua_p=>*a_i...) которые сопоставимы с подцепочкой ai...ap...ar...aq...ak цепочки a1a2...an, где через ap,ar...,aq обозначены все терминалы правой части правила, а u,v,...,w принадлежат N*. То есть проверяется, существует ли вывод u'apw'ar...aqv' =>* ai...ap...ar...aq...ak для некоторых u',w',...,v' из N* при |u'|=|u|,...,|v'|=|v|. Решая вторую задачу, алгоритм исследует, существует ли вывод A => z0Bz1C...Dzm =>* z0z1'z1...zm'zm = ai...ak такой, что правило A => z0Bz1C...Dzm сопоставимо с цепочкой ai...ak и B =>* z1', C =>* z2', ... , D =>* zm' являютя подвыводами, распознанными в процессе вычисления множеств 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, чтобы разделить данные первого и второго процессов и облегчить поиск подвыводов, соответствующих сопоставимому с ai...ak правилу. Вместо таблицы разбора h[i,j] мы будем использовать линейную таблицу h'[i] и только для поиска правил, сопоставимых с подцепочками. Основной цикл алгоритма 2 выполняется для позиций от n до 1 для того, чтобы на i-й итерации вычислить все фразы, имеющие левый край в i-й позиции входной цепочки. Выводы A_=>_*al...aj распознаются, когда все выводы B_=>_*ai...am (lw.] из h[i,j] алгоритма 1 пара (A->w,j) принадлежит r[i] *) BEGIN FOR i:=n DOWNTO 1 DO h'[0]:={[A->.w]| A->w IN P}; FOR j:=1 TO n-i+1 DO (*сопоставление правил*) h'[j]:= { [A->ub.v]| [A->u.bv] IN h'[j-1], b=ai+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; (* Замыкание *) WHILE существует [A->.Bv] IN h'[0] такое, что [B->w.] IN h'[j] и нет [A->B.v] IN h'[j] DO h'[j]:=h'[j]+{[A->B.v]} END; 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 Алгоритм 2 можно существенно улучшить, если имеется возможность реализовать следующее преобразование. Для каждой пары (i,j) предварительно вычислить m (m=m(i,j)) такие, что только пары (h[i,k1],h[i+k_1,j-k_1]),...,(h[i,k__m],h[i+k__m,j-k_ _m]) используются при вычислении h[i,j]. Цикл по k алгортма_2 заменить на вызов некоторой процедуры COMP(i,j), которая для всех i и j вычисляет h[i,j]:=F(h[i,k_1],h[i+k_1,j-k__1],...,h[i,k__m],h[i+k__m,j-k___m]) используя предварительно вычисленные значения k1...km. До начала разбора алгоритм сохраняет множества предварительно вычисленных значений k1...km в некоторой структуре. В процессе разбора процедура COMP(i,j) выбирает из нее необходимые k1...km. Преобразование имеет смысл, если временная сложность предварительных вычислений не превышает O(n2) и фиксированное время требуется на выборку k1...km. Если предварительные вычисления можно выполнить за время O(n), то можно вычислить только O(n) множеств значений k1...km. Следовательно, алгоритм должен вычислить только O(n) множеств h[i,j], и его временная сложность становится O(n). 4.2. Синтаксический анализ для Д-грамматик Модифицируем алгоритм 2 так, чтобы он работал только для Д-грамматик. Все цепочки, выводимые из любого нетерминала A в Д-грамматике G=(N,T,P,S), являются префиксными выражениями. Если S_=>*_a1...an, то для любых подвыводов A_=>*_ai...ak и B_=>*_ai...al имеет место равенство k=l. Длины всех выражений из входной цепочки a1...an можно предварительно вычислить, например, одновременно с ее записью в таблицу a. Поэтому можно проверить, сопоставимо ли правило с подцепочкой ai...ak входной цепочки a1...an, проходя слева направо по ai...ak. В процессе прохода по цепочке предварительно вычисленные длины префиксных выражений используются для того, чтобы перейти от одного терминала к следующему терминалу, пропуская подцепочки, соответствующие нетерминалам правой части правила. Вычисляя l[i] длины ai-выражений для каждой позиции i, мы посуществу предварительно вычисляем значения k1...km для каждой пары (i,l[i]). Алгоритм 3 вычисляет на i-м шаге все фразы, начинающиеся с i-го символа. Процедура MATCH(j,h") просматривает цепочку a_ja_j+1...a_j+l[j]-1 и сравнивает ее с aj-выражениями, указанными в объектах из h". Параметр h" представляет такое множество {[A->u'a_j__.v]}, что если на i-м шаге алгоритма объект [A->u__.v] в h", то u=>*a_i...a_j. Обрабатывая подвыражение v_k выражения a_jv_1...v_m (m=Arity(aj)), процедура вычисляет множества 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;(*ai обозначает a[i] *) l : ARRAY[1..n] OF INTEGER;(* l[i]=длина ai-выражения*) 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->uaj.vw]}, m=Arity(aj) *) (* v=v1v2...vk-1vkvk+1...vm=v'vkv" *) IF h"<>{} THEN p:=j+1; (*пропустить aj=a[j] *) FOR k:=1 TO m DO (*сопоставить{v1,v2,...,vm}*) h2:={[A->uajv'B. v"w]| [A->uajv'.B v"w] IN h", vk=B, B->y IN r[p] }; h1:={[A->uajv'ap.xv"w]| [A->uajv'.apxv"w] IN h", vk=apx, ap=a[p] }; MATCH(p,h1); (* сопоставить {vk} *) h":=h1+h2; END; END; j:=j+l[j]; (* пропустить aj-выражение*) END MATCH; BEGIN (* Предварительные вычисления k1...,km *) Для каждой позиции i=1,n вычислить длину ai-выражения l[i] (* Распознавание входной цепочки *) FOR i:=n DOWNTO 1 DO h":={[A->ai.v]| (A->aiv) IN P, ai=a[i]}; j:=i; MATCH(j,h"); (* Сопоставление нецепных правил*) (* Сопоставление цепных правил *) WHILE существует (A->B) из P такое, что [B->w.] IN h" и нет [A->B.] IN h" DO h":=h"+{[A->B.]} END; 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 с префиксными выражениями {a_jv} из множества исследуемых правил {A->ua_jvy}, и ищет подвыводы, соответствующие этому правилу. Следовательно, если правило A->w сопоставимо с поддеревом вершины m, то префиксное выражение, соответствующее ему, выводится из A, и правило A->w может быть применено в этом выводе. Мы считаем, что нетерминалы являются операторами 0-й размерности. Структура данных, представляющая вершину дерева, имеет следующую форму: PTnode=^Tnode; Tnode=RECORD op : Tterminal; son : ARRAY[1..MaxArity] OF PTnode; rules: SET OF Tproduction END; Алгоритм, обрабатывающий деревья выражений, приведен ниже. Алгоритм 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->uaj.vw]}, m=Arity(aj), aj=n^.op *) (* v=v1v2...vk-1vkvk+1...vm=v'vkv" *) IF h"<>{} THEN (* сопоставление v1,v2,...,vm *) FOR k:=1 TO m DO WITH n^.son[k]^ DO h2:={[A->uajv' B.v"w] | [A->uajv' .Bv"w] IN h", vk=B, (B->y) IN rule }; h1:={[A->uajv'ap.xv"w] | [A->uajv'.apxv"w] IN h", vk=apx, ap=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->ai.v]| (A->aiv) IN P, ai=n^.op}; MATCH(n,h"); (* Сопоставление цепных правил *) WHILE существует (A->B) IN P такое, что [B->w.] IN h" и нет [A->B.] IN h" DO h":=h"+{[A->B.]} END; n^.rules:={(A->w)| [A->w.] in h"} (* Сопоставленные правила*) END PARSE; BEGIN (* Предварительные вычисления k1,...,km*) Построить дерево выражения для входной цепочки z; root:= указатель_дерева_выражения;(* Распознать входную цепочку *) PARSE(root); Проверить, принадлежит ли S->w множеству root^.rules; END; Выходом алгоритма 4 является дерево выражения для z, вершинам которого сопоставлены применимые правила. Если Д-грамматика неоднозначная, то можно построить несколько различных выводов для заданной входной цепочки. Все возможные выводы можно построить, используя для этого декорированное дерево выражения алгоритма 4 или таблицу r применимых правил и таблицу l длин префиксных выражений алгоритма 3. 4.3. Выбор дерева вывода наименьшей стоимости Д-грамматики, описывающие системы комад компьютеров, обычно являются неоднозначными грамматиками. Чтобы сгенерировать код для некоторой входной цепочки, необходимо выбрать одно из возможных деревьев вывода. Это дерево должно представлять желаемое качество кода, например размер кода и/или время выполнения. Мы предлагаем выбирать дерево вывода с помощью атрибутов стоимости, атрибутных формул, вычисляющих их значения, и критериев стоимости, которые оставляют для каждого нетерминала единственное применимое правило, анализируя значения атрибутов стоимости. С-атрибуты сопоставляются всем нетерминалам, С-формулы - всем правилам Д-грамматики. Если вершина n дерева вывода помечена нетерминалом A, то с ней связываются С-атрибуты нетерминала A. Их значения вычисляются параллельно с разбором входной цепочки. Значения С-атрибутов должны отражать некоторые свойства выводов из A. Предположим, что для вершины n обнаружено применимое правило p:_A->z_0X_1z_1...X_kz__k, где z__i из T__* для 0<=i<=k и X_j из N для 1<=j<=k. С-формулы, соответствующие правилу p, выполняются следующим образом. В соответствии с применимым правилом вершина n имеет потомков n_1,...,n_k, которые соответствуют нетерминалам X_1,...,X_k соответственно. Значения С-атрибутов дерева вывода вычисляются в порядке снизу вверх. Вначале С-атрибуты инициализируются неопределенным значением UndefinedValue. Предположим, что значения С-атрибутов для всех потомков n1,...,nk вершины n вычислены. Если С-формула A_.a:=f(Xi_.b,Xj_.c,...) для 1<=i,j<=k сопоставлена правилу p, то выполняется формула n_.a:=f(ni_.b,nj_.c,...) вычисляющая для правила p значение атрибута a нетерминала A в вершине n. К нетерминалу A в вершине n может быть применено несколько правил. С-критерий дает возможность выбрать из них единственное. Для этого используются ранее вычисленные значения С-атрибутов нетерминала A в вершине n и значения, только что вычисленные по С-формулам текущего правила (С-значения). Если С-критерий указывает, что текущее правило лучше, чем ранее обработанное правило, или значения С-атрибутов не определены, то С-значения присваиваются С-атрибутам, а соответствующее правило связывается с вершиной n. Когда разбор завершен, правило, связанное с корнем дерева вывода, определяет искомое дерево вывода. Добавим в алгоритм 4 реализацию С-атрибутов, С-формул и С-критериев, чтобы он выбирал единственное дерево вывода. Структура данных, представляющая вершину дерева, принимает следующий вид: 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->ai.v]| (A->aiv) in P, ai=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; (* Сопоставить цепные правила *) WHILE существует (A->B) IN P такое, что [B->w.] IN h" и нет [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->z_0X_1z_1...X_kz_k, связанное с указанной вершиной n, и заданный нетерминал A, чтобы определить соответствующие им вершины n1,...,nk и нетерминалы X1,...,Xk. Затем вычислитель рекурсивно обходит каждую вершину ni, имея на входе нетерминал Xi. 4.4. Пример генератора кода формируемого системой СУПЕР Алгоритмы, используемые системами BEG[11] и TWIG[12] для нахождения минимального покрытия, аналогичны модифицированному алгоритму 4. В системе BEG алгоритмы сопоставления образцов и нахождения оптимального кода непосредственно включаются в формируемый генератор кода. Какие-либо таблицы управления не используются. Система TWIG строит таблично-управляемый автомат сопоставления образцов. Обе системы выбирают наименьшее покрытие промежуточного дерева с помощью простого критерия минимизации стоимости. Каждому правилу приписывается фиксированная стоимость. Стоимость поддерева - это сумма стоимостей, примененных в нем правил. В система СУПЕР использует описанные методы для формирования эффективных генераторов кода. Алгоритмы сопоставления образцов и нахождения оптимального кода (модифицированный алгоритм 4) непосредственно включаются в формируемый генератор кода. Для правил рис._7 система сгенерирует следующую программу на языке Модула-2: 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:... (*для значений Сатрибутов текущего правила*) BEGIN WITH n^.nonterm[ Reg ] DO CASE (pn-BaseN) OF (*вычислить значения С-атрибутов*) |0:CostAttrValue ... :=CostAttributeRuleForAlterN0 | . . . |6:CostAttrValue ... :=CostAttributeRuleForAlterN6 END; EvaluateCriterionReg; (*проверить С-критерий для Reg*) IF pn лучше, чем 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); BEGIN EvalReg(7,n) END matchConst; . . . PROCEDURE matchPlus(n:PTnode); CONST NumAlternatives=3; (* число правил начинающихся с + *) 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 указывает на узел для + *) matched:=Cmatched; (* предположим все сопоставимы *) 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); (* Cопоставить нецепные правила*) MatchChainProductions(n); (* Cопоставить цепные правила*) END END PARSE; В области значений С-атрибутов входит значение UndefinedValue. С-критерии должны игнорировать правило, если одно из С-значений равно UndefinedValue. Поэтому из алгоритм исключен поиск подвыводов, соответствующих исследуемому правилу. Процеруры сопоставления (match...) проверяют каждое подвыражение vk aj-выражения ajv1...vm (m=Arity(aj)) независимо от результата сопоставления с v1,...,vk-1. Код процедуры MatchChainProductions(n) включает вычисление значений С-атрибутов и проверку С-критериев для цепных правил. Поскольку цепные правила не зависят от операторов, их необходимо проверять отдельно для каждого оператора. Применение одного цепного правила может зависеть от применения другого цепного правила, следовательно для каждого нетерминала можно статически вычислить последовательность применения цепных правил. Эти последовательности гарантируют, что после их выполнения никакие правила нельзя больше примененить. 6. Выделение общих подвыражений, раcпределение регистров и генерация команд с учетом стоимости команд В этом разделе речь идет о генерации кода с учетом стоимости команд и наличии общих подвыражений. Рассматриваются эффективные алгоритмы для выделения общих подвыражений, которые принимают во внимание стоимость команд и распределение регистров. Изложенные ниже алгоритмы основаны на следующих результатах. 1) Выделение общих подвыражений может быть выполнено на первом обходе дерева [22]. 2) Вычисление стоимости вариантов генерации кода также может быть выполнено на первом обходе дерева [11,12]. 3) Генерация оптимальной последовательности команд без учета наличия общих подвыражений может быть сделана на втором обходе дерева [11,12]. 4) Задача оптимального распределения регистров при учете общих подвыражений NP-полна [23]. 5.1. Выделение общих подвыражений Выделение общих подвыражений проводится на линейном участке и основывается на двух положениях. 1. Поскольку на линейном участке переменной может быть несколько присваиваний, то при выделении общих подвыражений необходимо различать вхождения переменных до и после присваивания. Для этого каждая переменная снабжается номером. Вначале номера всех переменных устанавливаются равными 0. При каждом присваивании переменной ее номер увеличивается на 1. 2. Выделение общих подвыражений осуществляется при обходе дерева выражения снизу вверх слева направо. При достижении очередной вершины (пусть операция, примененная в этой вершине, есть бинарная 'op'; в случае унарной операции рассуждения те же) просматриваем общие подвыражения, связанные с op. Если имеется выражение, связанное с op и такое, что его левый операнд есть общее подвыражение с левым операндом нового выражения, а правый операнд - общее подвыражение с правым операндом нового выражения, то объявляем новое выражение общим с найденным и в новом выражении запоминаем указатель на найденное общее выражение. Базисом построения служит переменная: если операндами обоих выражений являются одинаковые переменные с одинаковыми номерами, то они являются общими подвыражениями. Если выражение не выделено как общее, оно заносится в список операций, связанных с op (рис. 9). +----+ +<-----¦ op +<-------+ ¦ +----+ ¦ / \ / \ / \ / \ +---->/\ /\<----+ +-----/\ /\---+ ¦ / \ / \ ¦ ¦ / \ / \ ¦ ¦ ---- ---- ¦ ¦ ---- ---- ¦ ¦ +-+----------------+ +--------------------+ Рис. 9. Список операций, связанных с op. 5.2. Реализация Поддерживаются следующие глобальные переменные. TABLE - таблица переменных; для каждой переменной хранится ее номер (NUMBER) и указатель на вершину дерева выражений, в которой переменная встретилась в последний раз (LAST); OPTABLE - таблица списков общих подвыражений, связанных с каждой операцией (ADDR - указатель на вершину дерева, LIST - продолжение списка); REGSTATE - таблица состояний регистров; содержит указатель на последнюю вершину дерева выражений, значение которой загружено в регистр; VARLIST - список указателей на TABLE для всех использованных на линейном участке переменных (ADDR - указатель на вершину дерева, LIST - продолжение списка). Этот список нужен для быстрого "освобождения" после окончания линейного участка всех переменных, отмеченных как общие в процессе работы. С каждой вершиной дерева выражения связана запись: NODETYPE = RECORD LEFT -- левый потомок вершины; RIGHT -- правый потомок вершины; COMM -- указатель на предыдущее общее подвыражение; SIGN -- признак, является ли поддерево общим подвыражением; STACK -- смещение в стеке, если регистр был сброшен; REGS -- указатель на REGSTATE для регистра, выделенного для значения вершины; VARBL -- признак, является ли вершина переменной; VARNUM -- номер переменной; VAREF -- ссылка на TABLE с описанием переменной; END; Связь между переменными изображена схематически на рис._10 и 11. Все общие подвыражения собраны в список, начинающийся с OPTABLE[OP]. Выделение общих подвыражений и построение дерева осуществляются следующими правилами. Структура поддерева записана перед разделителем "=>", а после него записана семантика. В семантической части ссылка вида "$I.NAME" означает атрибут NAME i-го символа правила ($0 - для символа левой части, $1 - для первого символа правой части и т.д.). Вершина дерева выражения +--------------------------------------------------+ ¦LEFT¦RIGHT¦COMM¦SIGN¦STACK¦REGS¦VARBL¦VARNUM¦VAREF¦ +--------------------------------------------------+ ^ ^ ^ +------+ ¦ ¦ ¦ ADDR ¦ ¦ ¦ +------¦ ¦ +----------+ ¦ LIST +-->... ¦ ¦ +------+ ¦ V ^ ¦ +--------+ +------+ +----+ ¦ +----+ ¦ ¦ LAST ¦ ¦ LIST +-->... ¦ OP +-+ ¦ +<---+ ¦ NUMBER +<--¦ ADDR ¦ +----+ +----+ +--------+ +------+ ^ ¦ OPTABLE REGSTATE TABLE VARLIST Рис. 10. Схема связи между переменными. +---+ +<-------------<--------------<------¦ ¦ OP / \ / \ / \ +---+ / \ / \ / \ OPTABLE /\ /\ /\ /\ /\ /\ / \ / \ / \ / \ / \ / \ ---- ---- ---- ---- ---- ---- Рис. 11. Список общих подвыражения для op. Атрибут ENTRY нетерминала VARIABLE дает указатель на переменную в таблице. Атрибут VAL символа OP дает код операции. Атрибут NODE символов INTEXPR и ASSIGNMENT дает указатель на запись типа NODETYPE соответствующего нетерминала. ASSIGNMENT ::= VARIABLE INTEXPR => TABLE[$1.ENTRY].NUMBER:=TABLE[$1.ENTRY].NUMBER+1; {Увеличить счетчик присваиваний переменной} INTEXPR ::= VARIABLE => WITH $0.NODE DO WITH TABLE$1.ENTRY] BEGIN IF LAST<>NIL { Переменная уже была использована } AND LAST^.VARNUM = NUMBER THEN { С тех пор переменной не было присваивания } BEGIN FLAG:=TRUE; { Переменная - общее подвыражение } COMM:=LAST; { Указатель на общее подвыражение } END ELSE FLAG:=FALSE; VAREF:=$1.ENTRY; { Вход в TABLE } LAST:=^$0.NODE; {Указатель на последнее использование переменной} VARNUM:=NUMBER; {Номер использования переменной} VARBL:=TRUE; {Выражение - переменная} END; INTEXPR ::= OP INTEXEPR INTEXPR => VAR P,L:LISTYPE; {Тип списков операции} R:BOOLEAN; IF $2.NODE.FLAG AND $3.NODE.FLAG THEN { И справа, и слева - общие подвыражения } BEGIN L:=OPTABLE[$1.VAL]; { Начало списка общих подвыражений для операции } R:=L<>NIL; WHILE R DO IF (^$2.NODE=L.LEFT^.ADDR) { Левые поддеревья совпадают } AND (^$3.NODE=L.RIGHT^.ADDR) { Правые поддеревья совпадают } THEN R:=FALSE ELSE BEGIN L:=L^.LIST; {Следующий элемент списка} R:=L<>NIL; {Окончен ли список} END END ELSE L:=NIL; {Не общее подвыражение} WITH $0.NODE^ DO BEGIN VARBL:=FALSE; { Не переменная } COMM:=L; {Указатель на предыдущее общее подвыражение или NIL} IF L<>NIL THEN BEGIN FLAG:=TRUE; {Общее подвыражение} LEFT:=^$2.NODE; { Указатель на левое поддерево } RIGHT:=^$3.NODE; { Указатель на правое поддерево } END ELSE BEGIN FLAG:=FALSE; { Данное выражение не может рассматриваться как общее } { Если общего подвыражения с данным не было, включить данное в список для операции } NEW(P); P^.ADDR:=^$0.NODE; P^.LIST:=OPTABLE[$1.VAL]; OPTABLE[$1.VAL]:=P; END END; 5.3. Оценка стоимости команд и распределение регистров Рассмотрим теперь, как объединить оценку стоимости генерируемых команд, распределение регистров и выделение общих подвыражений. При этом надо учитывать следующее. 1. Как производится подсчет вариантов стоимости различных покрытий. Здесь возможны два пути. 1.1. Подсчет стоимости производить без учета наличия общих подвыражений. Тогда выделение общих подвыражений и подсчет стоимости могут быть осуществлены за один обход снизу вверх слева направо; 1.2. При подсчете стоимости учитывать наличие общих подвыражений. Если предположить неограниченное число регистров, это можно сделать за два обхода: на первом выделить общие подвыражения, на втором подсчитать стоимость. Сгенерированный код будет оптимальным. Среди вариантов кода может быть такой, что если общее подвыражение встречается первый раз, то результат его вычисления сохраняется в регистре, и в последующем это значение используется для общих подвыражений. Иногда может оказаться не выгодно специально помещать результат на регистр. Это иллюстрируется ниже на примере. 2. Если число регистров ограничено, можно выбрать один из следующих двух вариантов. 2.1. В процессе движения сверху вниз слева направо при нахождении оптимального покрытия, попадая в очередную вершину, смотрим, является ли эта вершина общим подвыражением с подвыражением в уже покрытой части дерева (и значит, с уже распределенными регистрами), значение которого расположено на регистре. Если да и если регистр после этого не менялся, заменяем вычисление поддерева на значение в регистре. Стоимость такого дерева не больше стоимости вычисления полного дерева. Если регистр менялся, то вычисляем подвыражение заново (т.е. продолжаем движение вниз по дереву). Генерацию кода и распределение регистров делаем при обратном движении снизу вверх. 2.2. Поскольку генерация кода и распределение регистров происходят при движении снизу вверх, недостаточно одного прохода для одновременно и распределения регистров, и генерации команд, так как в этом случае в тот момент, когда мы выясняем, что значение регистра потеряно, код для соответствующего поддерева уже вычислен. Поэтому приходится вводить еще один проход и распределение работы по проходам следующее. На первом проходе при движении сверху вниз находим оптимальное покрытие и при движении снизу вверх распределяем регистры. Если в некоторой вершине обнаруживается, что ее поддерево - общее с уже вычисленным ранее, но значение регистра потеряно, то отмечаем вершину предыдущего общего подвыражения как такую, в которой нужно сохранить значение регистра. В такой вершине необходимо сгенерировать команду сброса регистра в рабочую память. Выигрыш в коде будет, если стоимость команды сброса регистра + доступ к памяти в повторном использовании этой памяти не превосходит стоимости заменяемого поддерева. Поскольку стоимость команды MOVE_R,-(SP) известна, на проходе сверху вниз, на котором стоимость поддерева уже тоже известна, можно сравнить стоимости и принять оптимальное решение: то ли метить предыдущую вершину для сброса, то ли вычислять полностью поддерево. Код генерируется на втором проходе. Рассмотрим пример, показывающий, что иногда лучше сгенерировать код, загружающий значение на регистр, а иногда лучше перевычислить выражение, в зависимости от числа общих подвыражений. Пусть заданы образцы рис. 12, где '@' обозначает операцию адресного сложения. Пусть надо сгенерировать код для последовательности операторов присваивания A:=V B:=V где V - локальная переменная (т.е. ее смещение отсчитывается от верхушки стека). Дерево линейного участка изображено на рис. 13. Выражение Операнд /\ MOVE Операнд,Память | / := \ Стоимость 2 | Стоимость 0 / \ | Память Операнд ( Регистр ) ( Регистр ) /\ ADD Смещение,Регистр / @ \ Стоимость 2 / \ Смещение Регистр Операнд Регистр /\ | MOVE SP,Регистр / \ Стоимость 1 | Стоимость 1 / \ | Смещение Регистр Стек или стек Рис. 12 Фрагмент описания генератора кода. Линейный участок /\ / \ / \ /\ /\ / \ / \ A /@\ B /@\ / \ / \ V SP V SP Рис. 13. Дерево линейного участка A:=V; B:=V . Если не выделять общее подвыражение в адресной части, то будет сгенерирован код: MOVE V(SP),A | 3 MOVE V(SP),B | 3 -- 6 со стоимостью 6. Это соответствует покрытию дерева, изображенному на рис. 14. Линейный участок / \ / \ Выражение Выражение /\ MOVE V(SP),A /\ MOVE V(SP),B / := \ Стоимость 2 / := \ Стоимость 2 / \ / \ Память Операнд Память Операнд A /\ B /\ / \ Стоимость 1 / \Стоимость 1 / \ / \ Смещение Стек Смещение Стек V V Рис. 14 Покрытие дерева без учета общих подвыражений. Если выделить это общее подвыражение, то будет сгенерирован код: MOVE SP,R | 1 ADD V,R | 2 MOVE (R),A | 2 MOVE (R),B | 2 -- 7 со стоимостью 7. Соответствующий вариант покрытия изображен на рис. 15. Линейный участок / \ / \ Выражение Выражение /\ MOVE (R),A /\ MOVE (R),B / := \ Стоимость 1 / := \ Стоимость 1 / \ / \ Память Операнд Память Операнд A | | |Стоимость 0 |Стоимость 0 (Регистр) (Регистр) /\ ADD V,R / \ Стоимость 1 / \ Смещение Регистр V | MOVE SP,R | Стоимость 1 | Стек Рис. 15. Покрытие дерева с учетом общих подвыражений. Таким образом, в этом случае невыгодно выделять общее подвыражение. Заметим, что если V встречается три раза, то стоимости сравниваются, а если четыре, выгоднее это общее подвыражение выделять. 6. Заключение Мы исследовали алгоритмы генерации кода систем BEG и Twig. Модифицировали алгоритм Кока-Янгера-Касами так, чтобы он работал линейное время для Д-грамматик. Алгоритмы, используемые системами BEG и TWIG для нахождения минимального покрытия, аналогичны модифицированному алгоритму Кока-Янгера-Касами. Предложен метод, позволяющий совместить выделение общих выражений, оценку стоимости выбираемых команд и распределение регистров. Основные преимущества нашего метода состоят в следующем: (а) генерация кода осуществляется с помощью традиционных атрибутной техники и техники синтаксического разбора, (б) генератор кода описывается атрибутной грамматикой, (в) предложена эффективная реализация генератора кода. Литература 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. Надежин Д.Ю.,Серебряков В.А.,Ходукин В.М. Промежуточный язык Лидер (предварительное сообщение). Обработка символьной информации. М.: ВЦ АН СССР,1987. 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,V.4, N.7,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. 18.Бездушный А.Н. К вопросу об автоматической генерации кода. Автоматизация программирования. М.: ВЦ АН СССР,1991. 19.A.Bezdushny, V.Serebriakov The use of the parsing method for optimal code generation and common subexpression elimination. Proceedings of the first French-Soviet Symposium on theoretical computer science and methods of compilation and program construction,1991. 20.Hoffman C.W., O'Donnell M.J. Pattern mathing trees. J.ACM, V.29,N.1,1989. 21.Aho A.U.,Corasick M.J. Efficient string matching:An aid to bibliographic search. Comm.ACM,V.18,N.6,1975. 22.Aho A., Sethi R., Ullman J.D. Compilers: Principles, Techniques and Tools, Addison-Wesly, 1986. 23.Aho A.V, Johnson S.C., Ullman J.D. Code Generation for Expressions with Common Subexpressions // J.ACM, 24:1, p. 146-160.