Генератор внутреннего представления программы на М-языке

Синтаксически управляемый перевод

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

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

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

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

Пусть есть грамматика, описывающая простейшее арифметическое выражение:

E ® T {+T}

T ® F {*F}

F ® a | b | (E)

Тогда грамматика с действиями по переводу этого выражения в ПОЛИЗ будет такой:

E ® T {+T < putchar('+') > }

T ® F {*F < putchar('*') > }

F ® a < putchar('a') > | b < putchar('b') > | (E)

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

Например, с помощью грамматики с действиями выполним перевод цепочек языка

L₁ = {0ⁿ1^m | n,m>0}

в соответствующие цепочки языка

L₂ = {a^mbⁿ | n,m>0}:

Язык L₁ можно описать грамматикой

S ® 0S | 1A

A ® 1A |e

Вставим действия по переводу цепочек вида 0ⁿ1^m в соответствующие цепочки вида a^mbⁿ:

S ® 0S < putchar('b') > | 1 < putchar('a') > A

A ® 1 < putchar('a') > A |e

Теперь при анализе цепочек языка L₁ с помощью действий будут порождаться соответствующие цепочки языка L₂.

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

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, иначе возникнет ошибка при обработке вложенных условных операторов.

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

Дата добавления: 2015-06-27