.OUTPUT(LPT E+ S0).INPUT(B#).PARAGRAPH(F% S0 P3 I3).OPTION(E- T- P-) .MARGIN(L0 R62) .COUNT 26 .FORM([/$30'- 'PN:1' -'//L42]) К ВОПРОСУ ОБ АВТОМАТИЧЕСКОЙ ГЕНЕРАЦИИ КОДА А.Н.#Бездушный % Процесс компиляции можно разбить на две фазы. На первой фазе выполняется лексический, синтаксический, контекстный анализ, формируется промежуточное представление исходной программы, содержащее только те компоненты исходной программы, которые необходимы на второй фазе процесса компиляции. Вторая фаза состоит в генерации объектного кода, выполнении машинно-зависимой оптимизации, формировании загрузочного модуля. % Проблемы первой фазы компиляции достаточно хорошо изучены. Имеются алгоритмы и средства автоматического построения соответствующих компонент компилятора по декларативному описанию языка. Из проблем второй фазы задача генерации кода является наиболее трудной, что связано со сложностью соответствующих алгоритмов, необходимостью учитывать архитектуру конкретного компьютера. Только в последнее время стали вырабатываться общие методы, алгоритмы построения генераторов кода для универсальных компьютеров. Хороший обзор подходов к решению этой проблемы приведен в [1]. Исследование теоретических аспектов и практических алгоритмов можно найти в [2]. % При построении генератора объектного кода необходимо решить следующие задачи. .PARAGRATH(U3).MARGIN(L3) %1)#Выбор промежуточного представления исходной программы. %2)#Распределение памяти в объектной программе. %3)#Выбор машинных команд. %4)#Распределение регистров. %5)#Оптимизация программы. %6)#Формирование загрузочного модуля. .PARAGRATH.MARGIN В данной работе основное внимание будет уделено п.#3. % Выбор промежуточного представления тесно связан с классом входных языков, организацией компьютера. Известно несколько вариантов промежуточного представления исходной программы: последовательность команд абстрактного компьютера, последовательность триад или тетрад, лес атрибутированных деревьев, последовательность линеаризованных деревьев#[3]. Большинство методов генерации кода используют древовидную форму представления промежуточной программы. При выборе промежуточного представления существенным является вопрос о включении в него описаний объектов, их типов. Оставляя понятия типа в промежуточном представлении, мы получаем машинно-независимое представление#[4]. Иначе необходимо использовать некоторую абстракцию памяти компьютера и провести ее распределение на первой фазе компиляции. Это позволяет приступить к выбору машинных команд на первом же этапе второй фазы компиляции, лучше реализовать те конструкции исходного языка, которые не отражены в промежуточном представлении. % Задача распределения памяти для традиционных языков состоит в выделении памяти для хранения значений переменных, организации доступа к ним, реализации механизмов процедур и передачи параметров. Существует ряд хорошо себя зарекомендовавших и почти стандартных методов решения этой задачи. Они хорошо согласуются с такими этапами первой фазы компиляции, как обработка описаний, генерация промежуточного представления. % Далее мы будем считать, что промежуточное представление - последовательность деревьев выражений, в которых операторы имеют фиксированное число операндов. Операторы могут иметь атрибуты, значения которых определяются на первой фазе процесса компиляции. Распределение памяти выполняется так же на первой фазе. % На рис.#1 показано промежуточное дерево для прeдложения a:=b[i]+5, где a,b,i - локальные переменные, хранимые со смещениями x,y,z в областях данных, указываемых регистрами Ra,Rb,Rz соответственно. Элемент массива b занимает память емкостью в одну машинную единицу. 0-местные операторы reg, const возвращают значения, которые являются значениями атрибутов (на рисунке указываются в скобках после оператора) соответствующих вершин промежуточного дерева. Оператор contents возвращает содержимое регистра или ячейки памяти, имеющей адрес, задаваемый аргументом оператора. .PAGE 23 := | ------------- / \ + + / \ / \ / \ / \ reg(Ra) const(x) contents const(5) | | + / \ / \ + contents / \ | / \ | reg(Rb) const(y) + / \ / \ reg(Ri) const(z) Рис.#1.#Промежуточное дерево для прeдложения a:=b[i]+5 % Центральная проблема при разработке генератора кода - это задача выбора последовательности машинных команд, реализующих промежуточное представление исходной программы. В современных компьютерах одни и те же действия можно реализовать многими способами. Задача выбора команд состоит в том, чтобы выбрать наилучший способ реализации того или иного действия, последовательности действий. % Простейший алгоритм генерации кода заключается в обходе промежуточного дерева в обратном порядке и выборе команды для каждой вершины отдельно. Получающийся код будет очень плохой, так как часто одна команда может быть использована для "реализации" нескольких вершин промежуточного дерева. Например, команда MOV#10(R0),20(SP) выполняет вычисление адреса источника, извлечение из памяти его значения и пересылку этого значения по вычисленному ею же адресу приемника. Поэтому генератор кода должен комбинировать узлы промежуточного дерева, чтобы произвести одну машинную команду. % Последние исследования методов формализации генерации кода показали, что применение метода "сопоставления образцов" (pattern matching) для решения задачи выбора команд дает наилучшие результаты [11,12]. Первым предложил этот метод С.Г. Васильев [5]. Идея метода заключается в следующем. Машинные команды и/или их последовательности описываются посредством "образцов поддеревьев" (tree patterns). Выбор команд эквивалентен нахождению покрытия промежуточного дерева этими образцами. % Образцы поддеревьев задаются в правилах выбора команд .PAGE 2 образец_поддерева '->' результирующая_вершина [ машинная_команда ] Образцы поддеревьев наряду с вершинами промежуточного дерева могут содержать в качестве листьев новые вершины, которые отсутствуют в промежуточном дереве. Эти вершины появляются вследствие применения правил выбора, в которых эти вершины являются результирующими и используются для выражения взаимосвязи между образцами поддеревьев. Они называются метками правил выбора[12] или нетерминалами[11], а вершины промежуточного дерева - операторами. Результирующая вершина представляет результат, вычисляемый командой, связанной с этим образцом. На рис.#2 показан пример правил выбора. % Правила выбора можно рассматривать как правила преобразования промежуточного дерева, когда сопоставленный образцу фрагмент дерева заменяется на результирующую вершину. Преобразование продолжается, пока применимы правила выбора, т.е. пока не будет получена единственная вершина (stat). Рис.#3 содержит пример покрытия промежуточного дерева рис.#1 правилами выбора рис.#2. В рамки заключены фрагменты дерева, сопоставленные образцу правила, номер которого указывается в левом верхнем углу рамки. В квадратных скобках указаны результирующие вершины. Такое покрытие дает следующую последовательность команд. .PAGE 5 ADD #y,Rb ADD z(Ri),Rb MOV (Rb),Rb ADD #5,Rb MOV Rb,x(Ra) .PAGE 42 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) правило выбора вес машинная команда Рис.#2.#Правила выбора для некоторых машинных команд .PAGE 33 ----------[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) | | | | | | | -------------------------------------- | | | | | ------------------------------------------ | | | ---------------------------------------------- | -------------------------------------------------- Рис.#3.#Покрытие промежуточного дерева рис.#1 % Другая трактовка правил выбора заключается в том, что они "сжимают" вершины промежуточного дерева, входящие в образцы правил выбора, в единственную вершину дерева, которая помечается номером правила выбора. Результирующее дерево называют покрывающим деревом [11]. Данный подход позволяет сохранить структуру дерева для последующих этапов генерации кода, например, для распределения регистров. Обойдя покрывающее дерево в обратном порядке и используя метки вершин, мы можем выдать код для каждой вершины отдельно. Пример покрывающего дерева для покрытия, отличного от покрытия рис.#3, показан на рис.#4. % Назовем покрывающее дерево t промежуточного дерева T A-покрытием T, если корень t помечен правилом, имеющим результирующую вершину A. Например, покрывающее дерево рис.#4 является stat-покрытием. .PAGE 12 Правило 2 | Правило 5 / \ Правило 7 Правило 1 | Правило 5 / \ Правило 4 Правило 2 Рис.#4.#Покрывающее дерево для промежуточного дерева рис.#1 % Как мы видим, процесс нахождения покрывающего дерева недетерминированный, так как можно построить множество возможных покрытий для одного и того же промежуточного дерева. Было предложено несколько методов для нахождения "подходящего" покрытия. Для этого может вводиться понятие "веса", связываемое с правилом выбора и определяющее качество генерируемого кода, например, скорость, размер кода. %Грем и Глэнвилл [6,7,8] использовали LR-анализатор для нахождения "подходящего" покрытия. Вершины образца правила выбора записываются в прямом порядке. Эта запись рассматривается как правая часть, а результирующая вершина - как левая часть правила контекстно-свободной грамматики. Промежуточное дерево записывается в прямом порядке и поступает на вход LR-анализатору, построенному по этой грамматике. Как правило, грамматика получается не только LR(1)-грамматикой, но и оказывается неоднозначной. В конструктор LR-анализаторов встраиваются специальные действия для разрешения конфликтов и неоднозначностей грамматики, например, предпочтение сдвига свертке, свертки по более длинному правилу - свертке по более короткому. Фиксированность реакции на конфликты, неучет контекста иногда приводят к неправильному поведению, возможны случаи, когда анализатор попадает в ошибочное состояние на правильной программе. Чтобы это избежать, грамматика вручную преобразуется перед началом построения таблиц. Требуется детальное знание внутренних алгоритмов синтаксического анализа, чтобы написать спецификацию, которая даст хороший генератор кода. % Ганапати и Фишер [2,9] обобщили идею Грем и Глэнвилла, дополнив КС-грамматику атрибутами, т.е. использовали атрибутную грамматику для описания генератора кода. Чтобы снять нагрузку с КС-грамматики, они предложили исключить из синтаксического описания генератора явное указание некоторых свойств компьютера, например, способов адресации операндов, типов операндов и т.п., и реализовать их посредством атрибутов, чтобы упростить КС-грамматику. Неоднозначности разрешаются с помощью предикатов правил выбора, управляющих разбором. Разбор становится контекстно-зависимым. Сравнение чисто синтаксического подхода Грем и Глэнвилла с атрибутным подходом Ганапати и Фишера показало значительно более низкую эффективность последнего. % Другое обобщение метода Грем и Глэнвилла [10] исходит из того, что детерминированность алгоритма разбора не позволяет выбрать лучшую из возможных последовательностей команд для заданного дерева. Поэтому предлагается заменить LR(1)-анализатор алгоритмом анализа Эрли, который может вести разбор по неоднозначной грамматике, затрачивая на разбор цепочки длины n время O(n*n*n) и память емкостью O(n*n). Анализатор строит более лучший код, но затрачивает слишком много ресурсов. % Чтобы избежать проблем, возникающих при использовании детерминированного анализатора, в последних работах по генерации кода [11,12] используется общий метод сопоставления с образцом, гарантирующий, что будет получено наилучшее возможное покрытие. % Генераторы кода, формируемые системами BEG[11], Twig[12], комбинируют быстрый алгоритм сопоставления образцов с алгоритмом динамического программирования для вычисления минимального покрытия. Алгоритмы сопоставления образцов работают сверху-вниз(Twig) или снизу-вверх(BEG). Алгоритм динамического программирования решает задачу генерации кода для выражения E, разбивая ее на k меньших подзадач генерации оптимального кода для k подвыражений Ei выражения E. Решения подзадач сохраняются в таблицах и никогда не вычисляются заново. В системе BEG, в отличие от системы Twig, алгоритмы сопоставления с образцом и нахождения оптимального кода непосредственно включаются в формируемый генератор кода и не используют каких-либо таблиц управления. % Рассмотрим более детально эти две реализации систем построения генeраторов кода по строго декларативному описанию генератора кода. На текущий момент это лучшие реализации подобных систем. % В системе BEG правила выбора имеют следующую форму: .PAGE 4 RULE образец '->' результирующая вершина ; [ CONDITION условие_применимости_правила ;] COST целое_число-вес_команды ; [ EMIT машинная_команда или/и формулы_вычисления_атрибутов ;] Например, правило выбора для команды INC .PAGE 4 RULE + reg const -> reg ; CONDITION (const.value=1); COST 1; EMIT { вывод команды INC Ri, где Ri=reg.register } где через "." указываются атрибуты операторов. % Атрибуты операторов, определяемые на этапе генерации промежуточного дерева, можно использовать в условиях применимости, EMIT-действиях. EMIT-действия генерируют машинный код или/и вычисляют значения синтезированных атрибутов в течение вывода кода. Синтезированные атрибуты доступны только внутри EMIT-действий и используются, например, для вычисления кода способа адресации операндов. % Как правило, компьютер допускает несколько способов адресации операндов, которые можно использовать в большом числе команд. Обычно используется отдельный нетерминал для каждого способа адресации, и задается правило выбора для каждой комбинации способа адресации и машинной команды, что приводит к огромному количеству правил выбора. Чтобы избежать этого, в системе BEG введено понятие цепных правил выбора - правил, где образец состоит из единственного нетерминала. Создается одно правило выбора для каждой машинной команды, в котором операнды описываются нетерминалами, представляющими все или часть способов адресации. Нетерминалы, представляющие отдельные способы адресации, выводятся из первых с помощью цепных правил. % Задача, нахождения оптимального покрытия промежуточного дерева решается следующим образом. % Для каждой вершины n промежуточного дерева T и для каждого нетерминала A вычисляются значения .BREAK .PAGE 4 cost(n,A) - вес минимального A-покрытия поддерева Tn с корнем n, rule(n,A) - номер правила выбора, которым помечен корень A-покрытия. .BREAK Если A-покрытие не существует, то cost(n,A) имеет значение представляющее бесконечность, а значение rule(n,A) не определено. % Значения cost(n,A), rule(n,A) вычисляются снизу-вверх, начиная с листьев промежуточного дерева T. Для каждой вершины n вначале рассматриваются все нецепные правила выбора, имеющие образец сопоставимый с поддеревом Tn, корнем которого является вершина n. Пусть r такое правило с результирующей вершиной A и образцом, в который входят нетерминалы A1,A2,...,Ak. .BREAK r:#O0#O1#A1#O2#A2...OpAk#->#A .BREAK В результате предыдущих шагов процесса вычисления покрытия вершинам n1,n2,...,nk сопоставлены нетерминалы A1,A2,...,Ak и вычислены значения cost(ni,Ai). Вес A-покрытия поддерева t вычисляется как .BREAK C(r)=вес_правила_r+cost(n1,A1)+...+cost(nk,Ak) .BREAK Пусть r0 правило выбора, где значение C(r) минимально. Положим .BREAK .PAGE 2 cost(n,A)=C(r0), rule(n,A)=r0. % После того как рассмотрены все нецепные правила выбора, исследуется применимость цепных правил. Цепные правила обрабатываются, пока существуют правила .BREAK r: A -> B, .BREAK имеющие стоимость Cr, такие, что .BREAK Cr+cost(n,A) < cost(n,B), .BREAK для которых выполняется .BREAK .PAGE 2 cost(n,B)=C(r), rule(n,B)=r. .BREAK Стоимость B-покрытия, состоящего из цепного правила r и A-покрытия, меньше стоимости B-покрытия, полученного до этого. .PAGE 17 ... | n O0 -> A / \ / \ / \ / \ m1 ... mp O1 ... O2 /\ /\ /\ /\ / \ / \ / \ / \ (n1) m2 ... (nk) A1 O2 ... Ak ... /\ ... /\ / \ / \ (n2) ... A2 ... ... Рис.#5.Поддерево и сопоставимый с ним образец правила r0. Вершины m1,m2,...,mp промежуточного дерева помечены операторами O1,O2,...,Op соответственно % В системе BEG значения cost и rule вычисляются параллельно с построением промежуточного дерева и сохраняются в его вершинах, описываемых как .BREAK .PAGE 7 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. .PAGE 7 PROCEDURE операторO0(операнды:Tnode):Tnode; VAR node:Tnode; c:INTEGER; BEGIN Создать вершину n (node указывает на нее) и связать ее с поддеревьями операндов. Проинициализировать cost значением, представляющим бесконечность (MaxInt/MaxNontInPat). .PAGE 12 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 условие_применимости_правила_выбора THEN node^.cost[A]:=c; node^.rule[A]:=r END END END; MatchChainRules(node); RETURN node END; Здесь ni,mi представляют код path(ni), path(mi), осуществляющий доступ к соответствующей вершине и определяемый как .BREAK .PAGE 3 path(n)=node, если вершина f - отец вершины l и l - i-й сын f, то path(l)=path(f)^.son[i]. .BREAK Например, n2=node^.son[1]^.son[2]^.son[1]#. % Процедура MatchChainRules(node) содержит код, исследующий применимость цепных правил. Она вызывается один раз для каждого оператора, так как цепные правила не зависят от операторов. Код, генерируемый для цепных правил, аналогичен коду нецепных правил. Каждому оператору r:#A#->#B сопоставляется код .BREAK .PAGE 4 IF node^.cost[B] > node^.cost[A]+вес_правила_r THEN node^.cost[B]:= node^.cost[A]+вес_правила_r; node^.rule[B]:= r END; .BREAK Чтобы избежать повторное тестирование применимости цепных правил, система BEG формирует последовательности цепных правил, гарантирующих, что после их выполнения никакие другие цепные правила не будут применены. % В системе Twig сопоставление образцов осуществляется таблично-управляемым автоматом. Хоффман и Доннелл [13] предложили алгоритм сопоставления образцов, в основе которого лежит расширение алгоритма Ахо-Корасика [14] поиска ключевых слов в строке. Автомат поиска ключевых слов строится из TRIE-структуры для множества ключевых слов и функции перехода по ошибке. % TRIE-структура для одного ключевого слова a1#a2#...am=w - диаграмма переходов с m+1 состояниями, где каждое состояние соответствует префиксу ключевого слова w. .BREAK .PAGE 2 a1 a2 am (0)---->(1)---->...---->(m+1) .BREAK Начальное состояние 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 рис.#2 имеют следующее множество записей путей. .BREAK .PAGE 5 const + 1 reg + 2 reg + 2 contents + 1 reg + 2 contents + 2 const .BREAK Запись +1reg представляет самый левый путь в образцах правил 5 и 6. Из множества записей путей, рассматриваемых как множество ключевых слов, строится автомат. .COMMENT Из выше приведенного множества записей путей будет построен .COMMENT следующий автомат. .COMMENT Рис.# #Автомат сопоставления образцов. % Пусть по множеству правил выбора R={ti#->#Ai}, где ti - образец, Ai - нетерминал, построен автомат с функцией перехода succ(q,x), возвращающий состояние, достижимое из состояния q при входном символе x. %Вершины промежуточного дерева описываются следующим образом .BREAK .PAGE 10 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. .BREAK .PAGE 14 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, если ее сыновья mk соответствуют вершинам образца ti, расположенным на глубине j, то есть битовую строку n^.b[i] вершины n можно вычислить, сдвигая вправо на один бит строки mk^.b[i] ее сыновей, вычисляя их побитовое произведение и складывая по битам его с текущим значением n^.b[i]. Процедура PostProcess определяет допустимые сопоставления образцов. .BREAK .PAGE 16 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, соответствующей завершающему состоянию. .BREAK .PAGE 8 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) вычисляет вес применения правила выбора ti->Ai в вершине n. Веса Ai-покрытий, номера правил выбора ti->Ai сохраняются в n^.cost[Ai] и n^.rule[Ai] соответственно. Предполагается, что до вызова процедуры visit, для всех вершин n поля n^.cost[Ai] проинициализированы значением, представляющим бесконечность, а n^.rule[Ai] - нулем. .BREAK .PAGE 16 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)