CODOPT7 (Материалы к контрольным работам)

8.9. Генерация оптимального кода методами синтаксического анализа

8.9.1. Сопоставление образцов

Техника генерации кода, рассмотренная выше, основывалась на однозначном соответствии структуры промежуточного представления и описывающей это представление грамматики. Для генерации более качественного кода может быть применен подход, изложенный в настоящей главе.

Этот подход основан на понятии "сопоставления образцов": командам машины сопоставляются некоторые "образцы", вхождения которых ищутся в промежуточном представлении программы, и делается попытка "покрыть" промежуточную программу такими образцами. Если это удается, то по образцам восстанавливается программа уже в кодах.

=



+ +


const(a) const(x) @ const(5)


+


+ @


const(b) const(y) +


const(i) const(z)

Рис. 8.29

На рис. 8.29 показано промежуточное дерево для оператора a=b[i]+5, где a,b,i - локальные переменные, хранимые со смещениями x,y,z в областях данных с одноименными адресами.

Элемент массива b занимает память в одну машинную единицу. 0-местная операция const возвращает значение атрибута соответствующей вершины промежуточного дерева, указанного на рисунке в скобках после оператора. Одноместная операция '@' означает косвенную адресацию и возвращает содержимое регистра или ячейки памяти, имеющей адрес, задаваемый аргументом оператора.

Н о- Образец Машинная команда Стои-
мер Правило грамматики мость

1 const(c) MOV #c,Ri 2
Reg->Const

2 = MOVE Rj,c(Ri) 4


+ reg(j)
Stat->'=' '+' Reg
reg(i) const(c) Const Reg

3 @ MOVE c(Rj),Ri 4

+

Contents -> '@' '+' Reg
reg(j) const(c) Const

4 + ADD #c,Ri 3


reg(i) const(c) Reg -> '+' Reg Const

5 + ADD Rj,Ri 2


reg(i) reg(j) Reg -> '+' Reg Reg

6 + ADD c(Rj),Ri 4


reg(i) @
| Reg -> '+' Reg '@'
+ '+' Reg Const

reg(j) const(c)

7 @ MOVE (R),R 2
|
Reg Reg -> Contents

Рис. 8.30

На рис.8.30 показан пример сопоставления образцов машинным командам. Приведены два варианта задания образца: в виде дерева и в виде правила контекстно-свободной грамматики. Для каждого образца указана машинная команда, реализующая этот образец, и стоимость этой команды. Стоимость может определяться различными способами, и здесь мы не рассматриваем этого вопроса. На рис. 8.31 приведен пример покрытия промежуточного дерева рис. 8.29 образцами рис. 8.30. В рамки заключены фрагменты дерева, сопоставленные образцу правила, номер которого указывается в левом верхнем углу рамки. В квадратных скобках указаны результирующие вершины.

[stat]
2 =

+

reg(Ra) const(x)
const(a)
[reg(Rb)]
4 +

const(5)

[reg(Rb)]
7 @

[reg(Rb)]
6 +


[reg(Rb)]
4 + @


reg(Rb) const(y) +
const(b)


reg(Ri) const(z)
const(i)





Рис. 8.31

Приведенное покрытие дает такую последовательность команд:

MOVE b,Rb
ADD #y,Rb
MOVE i,Ri
ADD z(Ri),Rb
MOVE (Rb),Rb
ADD #5,Rb
MOVE a,Ra
MOVE Rb,#x(Ra)

Как правило, одни и те же конструкции исходной (или промежуточной) программы можно реализовать различными последовательностями машинных команд. Это соответствует тому, что имеются различные покрытия промежуточного представления. Задача выбора команд состоит в том, чтобы выбрать наилучший способ реализации того или иного действия или последовательности действий, т. е. выбрать в некотором смысле оптимальное покрытие.

Для выбора оптимального покрытия было предложено несколько интересных алгоритмов, в частности использующих динамическое программирование [10,11]. Мы здесь рассмотрим алгоритм [12], комбинирующий возможности синтаксического анализа и динамического программирования, в основу которого положен синтаксический анализ неоднозначных грамматик (модифицированный алгоритм Кока, Янгера и Касами [13,14]) более эффективный в реальных приложениях. Этот же метод может быть применен и тогда, когда в качестве промежуточного представления используется дерево.

8.9.2. Синтаксический анализ для T-грамматик

Обычно код генерируется из некоторого промежуточного языка с довольно жесткой структурой. В частности, для каждой операции известна ее размерность (число операндов). Назовем грамматики, удовлетворяющие этим ограничениям, T-грамматиками.

Образцы, соответствующие машинным командам, задаются правилами грамматики (вообще говоря, неоднозначной). Генератор кода анализирует входное префиксное выражение и строит одновременно все возможные деревья разбора. После окончания разбора выбирается дерево с наименьшей оценкой. Затем по этому единственному оптимальному дереву генерируется код.

Для T-грамматик все цепочки, выводимые из любого нетерминала A, являются префиксными выражениями с фиксированной арностью операций. Длины всех выражений из входной цепочки a₁...a_n можно предварительно вычислить (под длиной выражения имеется ввиду длина подстроки, начинающейся с символа кода операции и заканчивающейся последним символом, входящим в выражение для этой операции). Поэтому можно проверить, сопоставимо ли некоторое правило с подцепочкой a_i...a_k входной цепочки a₁...a_n, проходя слева-направо по a_i...a_k. В процессе прохода по цепочке предварительно вычисленные длины префиксных выражений используются для того, чтобы перейти от одного терминала к следующему терминалу, пропуская подцепочки, соответствующие нетерминалам правой части правила.

Цепные правила не зависят от операций, следовательно, их необходимо проверять отдельно. Применение одного цепного правила может зависеть от применения другого цепного правила. Следовательно, применение цепных правил необходимо проверять до тех пор, пока нельзя применить ни одно из цепных правил. Мы предполагаем, что в грамматике нет циклов в применении цепных правил. Построение всех вариантов анализа для T-грамматики дано ниже в алгоритме 8.1. Тип Titem в алгоритме 8.1 ниже служит для описания ситуаций (т.е. правил вывода и позиции внутри правила). Тип Tterminal - это тип терминального символа грамматики, тип Tproduction - тип для правила вывода.

Алгоритм 8.1:
Tterminal a[n];
setofTproduction r[n];
int l[n]; // l[i] - длина a[i]-выражения
Titem h;// используется при поиске правил,
//сопоставимых с текущей подцепочкой
// Предварительные вычисления
Для каждой позиции i вычислить длину a[i]
-выражения l[i];
// Распознование входной цепочки
for (int i=n-1;i>=0;i--)
{for (для каждого правила A -> a[i] y из P)
{//считаем,что l[i]=0 для символов-не знаков
//операций
int j;
if (l[i]>0)
{j=i+1;

h=[A->a[i].y];
do //Сопоставимы ли a[i]y и a[i]..a[i+l[i]-1]
{Пусть h==[A->u.Xv]
if (X в T)
if (X==a[j]) j=j+1; else break;
else // X в N
if (X->w в r[j]) j=j+l[j];
else break;
h=[A->uX.v];
}// Перейти к следующему символу
while( j!=i+l[i]);
r[i]=r[i]+{(A->a[i]y)};
}//for
// Проверить цепные правила
while (существует правило C->A из P такое, что
имеется некоторый элемент (A->w) в r[i]
и нет элемента (C->A) в r[i])
r[i]=r[i]+{(C->A)};
Проверить, принадлежит ли (S->w) множеству r[0];

r[i]={A->a_iV₁...V_m}


1 m


a_i l[i]

Рис. 8.32

Работа алгоритма иллюстрируется рис. 8.32. Множества r[i] имеют размер O(|P|). Очевидно, что алгоритм имеет временную и емкостную сложность O(n).

Рассмотрим вновь пример рис. 8.29. В префиксной записи приведенный фрагмент программы записывается следующим образом:

= + a x + @ + + b y @ + i z 5

На рис. 8.33 приведен результат работы алгоритма. Правила вычисления стоимости приведены в разделе 8.9.3.

Операция Длина Правила
(стоимость

= 14 2(22)
+ 2 4(5) 5(6)
a 0 1(2)
x 0 1(2)
+ 9 4(16) 5(17)
@ 8 7(13)
+ 7 5(15) 6(11)
+ 2 4(5) 5(6)
b 0 1(2)
y 0 1(2)
@ 3 3(6) 7(7)
+ 2 4(5) 5(6)
i 0 1(2)
z 0 1(2)
5 0 1(2)


Рис. 8.33

Пусть G - это T-грамматика. Для каждой цепочки z из L(G) можно построить дерево выражения. Мы можем переписать алгоритм так, чтобы он работал с деревьями выражений, а не с префиксными выражениями. Этот вариант алгоритма приведен ниже. В этом алгоритме дерево выражения обходится сверху вниз и в нем ищутся поддеревья, сопоставимые с правыми частями правил из G. Обход дерева осуществляется процедурой PARSE. После обхода поддерева данной вершины в ней применяется процедура MATCHED, которая пытается найти все образцы, сопоставимые поддереву данной вершины. Для этого каждое правило-образец разбивается на компоненты в соответствии с встречающимися в нем операциями. Дерево обходится справа налево только для того, чтобы иметь соответствие с порядком вычисления в алгоритме 8.1. Очевидно, что можно обходить дерево вывода и слева направо.

Структура данных, представляющая вершину дерева, имеет следующую форму: