На практике синтаксический, семантический анализ и генерация внутреннего представления программы часто осуществляются одновременно.
Существует несколько способов построения промежуточной программы. Один из них, называемый синтаксически управляемым переводом, особенно прост и эффективен.
В основе синтаксически управляемого перевода лежит уже известная нам грамматика с действиями (см. §4.6 - контроль контекстных условий). Теперь, параллельно с анализом исходной цепочки лексем, будем выполнять действия по генерации внутреннего представления программы. Для этого дополним грамматику вызовами соответствующих процедур генерации.
Пусть есть грамматика, описывающая простейшее арифметическое выражение:
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)
Этот метод можно использовать для перевода цепочек одного языка в цепочки другого языка (что, собственно, мы и делали, занимаясь переводами в ПОЛИЗ цепочек лексем).
Например, с помощью грамматики с действиями выполним перевод цепочек языка
L1 = {0n1m | n,m>0}
в соответствующие цепочки языка
L2 = {ambn | n,m>0}:
Язык L1 можно описать грамматикой
S ® 0S | 1A
A ® 1A |e
Вставим действия по переводу цепочек вида 0n1m в соответствующие цепочки вида ambn :
S ® 0S <putchar('b')> | 1 <putchar('a')> A
A ® 1 <putchar('a')> A |e
Теперь при анализе цепочек языка L1 с помощью действий будут порождаться соответствующие цепочки языка L2.
Каждый элемент в ПОЛИЗе - это лексема, то есть пара вида
(номер_класса, номер_в_классе).
Нам придется расширить набор лексем:
- будем считать, что новые операции (!, !F, R, W) относятся к классу ограничителей, как и все другие операции модельного языка;
- для ссылок на номера элементов ПОЛИЗа введем лексемы класса 0, то есть (0, p) - лексема, обозначающая p-ый элемент в ПОЛИЗе;
- для того чтобы различать операнды-значения-переменных и операнды-адреса-переменных (например, в ПОЛИЗе оператора присваивания), операнды-значения будем обозначать лексемами класса 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
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, иначе возникнет ошибка при обработке вложенных условных операторов.
Аналогично можно описать способ генерации ПОЛИЗа других операторов модельного языка.
