Практическое применение СУ-схем

СУ-схемы предполагают существование отображения f: P₁ —> P₂ множества правил грамматики исходного языка в множество пра­вил грамматики объектного языка.

Выделяют два метода построения объектной программы путем преобразования исходной программы:

1 СУ-компиляция – строит объектную программу по ходу синтаксического анализа. В этом случае строить полное дерево разбора исходной программы, а тем более сохранять его после синтаксического анализа не требуется.

2 СУ-перевод – строит объектную программу после синтаксического анализа по его результату, представленным в виде дерева разбора.

Рассмотрим метод построения объектной про­граммы на основе СУ-перевода. В основу метода положено преобразование дерева разбора строки со во входной грамматике G_BX в дерево разбора выходной строки у в грамматике G_BbIХ. Метод позволяет получить перевод (w, у) любой входной строки w пу­тем последовательного решения следующих трех задач:

- построить дерево разбора w в грамматике G_BX;

- преобразовать полученное дерево в дерево разбора соответствующей строки у в грамматике G_BbIX, используя правила СУ-схемы;

- получить выходную строку у, взяв крону дерева разбора строки у.

Алгоритм преобразования дерева разбора входной строки

Обозначим: А — произвольный нетерминал СУ-схемы, А —> — правило входной грамматики, где = n₁…n_k . Пусть нетерминалу А соответствует узел А дерева разбора (нетерминальный узел). Тогда узлы n₁,n₂ , . . ., n_k - прямые потомки узла А. Преобразование дерева разбора начинается с его корня и состоит в следующем:

1) выбрать очередной нетерминальный узел А дерева разбора
входной строки; если все узлы обработаны, завершить работу;

2) устранить листья из множества узлов n₁…n_k (вершины,
помеченные терминалами или );

3) найти в СУ-схеме правило вида (А —> , ) и переставить
оставшихся прямых потомков узла А в соответствии с их размещением в строке (поддеревья перемещать вместе с их корнями);

4) добавить в качестве прямых потомков узла А листья так,
чтобы метки всех его прямых потомков образовали цепочку ;

5) повторять п. 1—4 для всех прямых нетерминальных потом­
ков узла А по порядку, слева направо.

ПримерДана СУ-схема Т₂ = ({0, 1}, {S, A}, {a, b), R, S),где R содержит правила:

1) S->0AS,SAa 2) A->0SA,ASa 3) S->1,b 4) A->1,b.

На рис. 5.1.2а показано дерево разбора входной строки 00111. При­менение алгоритма преобразования к корню S этого дерева устраняет левый лист, помеченный 0 (шаг 2).

Рисунок 5.2 - Преобразование дерева разбора: а - дерево входной строки;

б - дерево после однократного применения алгоритма;

в - дерево выходной строки

Далее, так как корню соответ­ствует правило S -> 0AS и для этого правила = SAa, нужно поме­нять местами оставшихся прямых потомков корня (шаг 3). Затем сле­дует добавить а в качестве самого правого, третьего, прямого потом­ка (шаг 4). Результатом будет дерево, показанное на рис. 5.1.2б. Снова применяем алгоритм, теперь уже к первым двум потомкам корня. Обработка второго из них приводит еще к двукратному повторению алгоритма. Окончательный результат показан на рис. 5.1.2в, это дере­во разбора выходной строки bbbaa. Из анализа правил СУ-схемы Т₂ следует, что она является не простой постфиксной схемой.

20.Генератор промежуточной программы для М-языка

Каждый элемент в ПОЛИЗе - это лексема, т.е. пара вида (номер_класса, номер_в_классе). Нам придется расширить набор лексем:

1) будем считать, что новые операции (!, !F, R, W) относятся к классу ограничителей, как и все другие операции модельного языка;

2) для ссылок на номера элементов ПОЛИЗа введем лексемы класса 0, т.е. (0,p) - лексема, обозначающая p-ый элемент в ПОЛИЗе;

3) для того, чтобы различать операнды-значения-переменных и операнды-адреса-переменных (например, в ПОЛИЗе оператора присваивания), операнды-значения будем обозначать лексемами класса 4, а для операндов-адресов введем лексемы класса 5.

Будем считать, что генерируемая программа размещается в массиве P, переменная free - номер первого свободного элемента в этом массиве:

#define MAXLEN_P 10000

struct lex

{int class;

int value;}

struct lex P [ MAXLEN_P];

int free = 0;

Для записи очередного элемента в массив P будем использовать функцию put_lex:

void put_lex (struct lex l)

{P[ free++] = l;}

Кроме того, введем модификацию этой функции - функцию put_lex5, которая записывает лексему в ПОЛИЗ, изменяя ее класс с 4-го на 5-й (с сохранением значения поля value):

void put_lex5 (struct lex l)

{ l.class = 5; P[ free++] = l;}

Пусть есть функция

struct lex make_op(char *op),

которая по символьному изображению операции op находит в таблице ограничителей соответствующую строку и формирует лексему вида ( 2, i ), где i - номер найденной строки.

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

Кроме того, можно дополнить функции семантического анализа действиями по генерации:

void checkop_p (void)

{char *op; char *t1; char *t2; char *res;

t2 = spop(); op = spop(); t1 = spop();

res = gettype (op,t1,t2);

if (strcmp (res, "no"))

{spush (res);

put_lex (make_op (op));} /* дополнение! - операция

op заносится в ПОЛИЗ */

else ERROR();

}

Тогда грамматика, содержащая действия по контролю контекстных условий и переводу выражений модельного языка в ПОЛИЗ, будет такой:

E ® E1 | E1 [ = | > | < ] <spush (TD [curr_lex.value] ) > E1<checkop_p() >

E1 ® T { [ + | - | or] <spush (TD [curr_lex.value] ) >T <checkop_p() >}

T ® F { [ * | / | and] <spush (TD [curr_lex.value] ) >F <checkop_p() >}

F ® I <checkid(); put_lex ( curr_lex ) > | N <spush("int"); put_lex (curr_lex) > |

[ true | false ] <spush ("bool"); put_lex (curr_lex) > |

not F <checknot(); put_lex (make_op ("not")) > | (E)

Действия, которыми нужно дополнить правило вывода оператора присваивания, также достаточно очевидны:

S ® I <checkid(); put_lex5 (curr_lex) > :=

E <eqtype(); put_lex (make_op (":=")) >

При генерации ПОЛИЗа выражений и оператора присваивания элементы массива P заполнялись последовательно. Семантика условного оператора if E then S1 else S2 такова, что значения операндов для операций безусловного перехода и перехода "по лжи" в момент генерации операций еще неизвестны:

if (!E) goto l2; S1; goto l3; l2: S2; l3:...

Поэтому придется запоминать номера элементов в массиве P, соответствующих этим операндам, а затем, когда станут известны их значения, заполнять пропущенное.

Пусть есть функция

struct lex make_labl (int k),

которая формирует лексему-метку ПОЛИЗа вида (0,k).

Тогда грамматика, содержащая действия по контролю контекстных условий и переводу условного оператора модельного языка в ПОЛИЗ, будет такой:

S ® if E <eqbool(); pl2 = free++; put_lex (make_op ("!F")) >

then S <pl3 = free++; put_lex (make_op ("!")); P[pl2] = make_labl (free) >

else S < P[pl3] = make_lable (free) >

Замечание: переменные pl2 и pl3 должны быть локализованы в процедуре S, иначе возникнет ошибка при обработке вложенных условных операторов.

Аналогично можно описать способ генерации ПОЛИЗа других операторов модельного языка.

21.ПОЛИЗ (польская инверсионная запись)

Польская инверсная запись — это постфиксная запись операций. Она была пред­ложена польским математиком Я. Лукашевичем, откуда и происходит ее название.

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

Она чрезвычайно эффективна в тех случаях, когда для вычислений использует­ся стек. Ниже будет рассмотрен алгоритм вычисления выражений в форме об­ратной польской записи с использованием стека.

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

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

Перевод в ПОЛИЗ выражений.

ПримерДля выражения в обычной (инфиксной записи) a*(b+c)-(d-e)/f ПОЛИЗ будет иметь вид: abc+*de-f/-.

Справедливы следующие формальные определения.

ОпределениеЕсли Е является единственным операндом, то ПОЛИЗ выражения Е – это этот операнд.

ОпределениеПОЛИЗ выражения Е₁ q Е₂, где q - знак бинарной операции, Е₁ и Е₂ – операнды для q, является запись , где - ПОЛИЗ выражений Е₁ и Е₂ соответственно.

ОпределениеПОЛИЗ выражения qЕ, где q - знак унарной операции, а Е – операнд q, есть запись , где - ПОЛИЗ выражения Е.

ОпределениеПОЛИЗ выражения (Е) есть ПОЛИЗ выражения Е.

Перевод в ПОЛИЗ операторов.

Каждый оператор языка программирования может быть представлен как n-местная операция с семантикой, соответствующей семантике оператора.

Оператор присваивания I:=E в ПОЛИЗе записывается:

IE:=,

где «:=» - двуместная операция,

I, E – операнды операции присваивания;

I – означает, что операндом операции «:=» является адрес переменной I, а не ее значение.

ПримерОператор x:=x+9 в ПОЛИЗе имеет вид: x x 9 + :=.

Оператор переходав терминах ПОЛИЗа означает, что процесс интерпретации необходимо продолжить с того элемента ПОЛИЗа, который указан как операнд операции перехода. Чтобы можно было ссылаться на элементы ПОЛИЗа, будем считать, что все они пронумерованы, начиная с единицы (например, последовательные элементы одномерного массива). Пусть ПОЛИЗ оператора, помеченного меткой L, начинается с номера p, тогда оператору безусловного перехода goto L в ПОЛИЗе будет соответствовать:

p!, где ! – операция выбора элемента ПОЛИЗа, номер которого равен p.

Условный оператор.Введем вспомогательную операцию – условный переход «по лжи» с семантикой if (not B) then goto L. Это двуместная операция с операндами B и L. Обозначим ее !F, тогда в ПОЛИЗе она будет записываться:

B p !F, где p – номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой L.

С использованием введенной операции условный оператор if B then S₁ else S₂ в ПОЛИЗе будет записываться:

B p₁ !F S₁p₂ ! S₂, где p₁ – номер элемента, с которого начинается ПОЛИЗ оператора S₂, а p₁ – оператора, следующего за условным оператором.

ПримерПОЛИЗ оператора if x>0 then x:=x+8 else x:=x-3 представлен в таблице 4.3

Таблица 4.3 – ПОЛИЗ оператора if

Оператор цикла.С учетом введенных операций оператор цикла while B do S в ПОЛИЗе будет записываться:

B p₁ !F S p_o !, где p_o – номер элемента, с которого начинается ПОЛИЗ выражения B, а p₁ – оператора, следующего за данным оператором цикла.

Операторы ввода и выводаязыка М одноместные. Пусть R – обозначение операции ввода, а W – обозначение операции вывода, тогда оператор read(I) в ПОЛИЗе запишется как I R, а оператор write(E) – E W.