Замечание
1. Для интерпретации, кроме ПОЛИЗа выражения, необходима дополнительная информация об операндах, хранящаяся в таблицах.
2. Может оказаться так, что знак бинарной операции по написанию совпадает со знаком унар- ной; например, знак «
» в большинстве языков программирования означает и бинарную операцию вычи- тания, и унарную операцию изменения знака. В этом случае во время интерпретации операции «
» воз- никнет неоднозначность: сколько операндов надо извлекать из стека и какую операцию выполнять.
Устранить неоднозначность можно, по крайней мере, двумя способами:
заменить унарную операцию бинарной, т. е. считать, что
а означает 0
а;
либо ввести специальный знак для обозначения унарной операции; например,
а заменить на
a. Важно отметить, что это изменение касается только внутреннего представления про- граммы и не требует изменения входного языка.
Элементы теории трансляции
/
Генерация внутреннего представления программ
84
Оператор присваивания I :
E в ПОЛИЗе будет записан как
I E :
где «:
» — это двухместная операция, а
I и
Е — ее операнды; подчеркнутое
I означает, что операндом операции «:
» является адрес переменной
I, а не ее значение.
Оператор перехода в терминах ПОЛИЗа означает, что процесс интерпретации надо продолжить с того элемента ПОЛИЗа, который указан как операнд операции перехода.
Чтобы можно было ссылаться на элементы ПОЛИЗа, будем считать, что все они пере- нумерованы, начиная с 1 (допустим, занесены в последовательные элементы одномерного массива).
Пусть
ПОЛИЗ оператора, помеченного меткой
L, начинается с номера
p, тогда опера- тор перехода
gotoL в ПОЛИЗе можно записать как
p! где «!» — операция выбора элемента ПОЛИЗа, номер которого равен
p.
Немного сложнее окажется запись в ПОЛИЗе
условных операторов и операторов цикла. Например, если рассматривать оператор
if B then S1
else S2
как обычную трехместную операцию с операндами
B,
S1
,
S2
, то ПОЛИЗ такого оператора должен выглядеть примерно так:
B′
S1
′
S2
′
if, где
B′ — ПОЛИЗ условия,
S1
′
S2
′ — ПОЛИЗ операторов
S1
,
S2,
if — обозначе- ние условной операции. Но тогда при интерпретации ПОЛИЗа обе ветви
S1
,
S2
заранее вы- числяются, независимо от условия
B, что
не соответствует семантике условного оператора.
Для корректной реализации в ПОЛИЗе управляющих конструкций
if,
while и т. п., их сначала заменяют эквивалентными фрагментами при помощи операторов перехода. Введем вспомо- гательную операцию — условный переход «по лжи» с семантикой
if (!
B)
goto L Это двухместная операция с операндами
B и
L. Обозначим ее !
F, тогда в ПОЛИЗе она будет записана как
B′
p !
F, где
p — номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой
L,
B′ — ПОЛИЗ логического выражения
В.
Семантика условного оператора
if Е then S1
else S2
с использованием введенной операции может быть описана так:
if (!
Е)
goto L2
;
S1
;
goto L3
;
L2
:
S2
;
L3
: ...
Тогда ПОЛИЗ условного оператора будет таким (порядок операндов — прежний!):
Е′
p2
!
F S1
′
p3
!
S2
′ ..., где
pi — номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой
Li,
i
2,3,
Е′ — ПОЛИЗ логического выражения
Е. Заметим, что расположение внутренних
Элементы теории трансляции
/
Генерация внутреннего представления программ
85 конструкций — условия Е и операторов S
1
, S
2
— относительно друг друга не изменилось.
Это обязательное требование к ПОЛИЗу управляющих конструкций.
Семантика оператора цикла whileЕ doSможет быть описана так:
L
0
: if (! Е) goto L
1
; S; goto L
0
; L
1
: ... .
Тогда ПОЛИЗ оператора цикла while будет таким (порядок операндов — прежний!):
Е′ p
1
!F S′ p
0
! ..., где p
i
— номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой L
i
,
i
0,1, Е′ — ПОЛИЗ логического выражения Е.
Операторы ввода и вывода М-языка являются одноместными операциями.
Оператор ввода read(I) в ПОЛИЗе будет записан как I read;
Оператор вывода write(E) в ПОЛИЗе будет записан как Е′ write, где Е′ — ПОЛИЗ выражения Е.
Постфиксная польская запись операторов обладает всеми свойствами, характерными для постфиксной польской записи выражений, поэтому алгоритм интерпретации выражений пригоден для интерпретации всей программы, записанной в ПОЛИЗе (нужно только расши- рить набор операций; кроме того, выполнение некоторых из них не будет давать результата, записываемого в стек).
Постфиксная польская запись может использоваться не только для интерпретации промежуточной программы, но и для генерации по ней объектной программы. Для этого в алгоритме интерпретации вместо выполнения операции нужно генерировать соответствую- щие команды объектной программы.
Синтаксически управляемый перевод
На практике синтаксический, семантический анализ и генерация внутреннего пред- ставления программы часто осуществляются одновременно.
Существует несколько способов построения промежуточной программы. Один из них, называемый синтаксически управляемым переводом, особенно прост и эффективен.
В основе синтаксически управляемого перевода лежит уже известная нам грамматика с действиями (см. раздел о контроле контекстных условий). Теперь, параллельно с анализом исходной цепочки лексем, будем выполнять действия по генерации внутреннего представле- ния программы. Для этого дополним грамматику вызовами соответствующих процедур гене- рации.
Содержательный пример — генерация внутреннего представления программы для М- языка — приведен ниже, а здесь в качестве иллюстрации рассмотрим более простой пример.
Пусть есть грамматика, описывающая простейшее арифметическое выражение.
G
expr
:
E → T {
T }
T → F {
F }
F →
a | b | (E)
Тогда грамматика с действиями по переводу этого выражения в ПОЛИЗ будет такой.
Элементы теории трансляции
/
Генерация внутреннего представления программ
86
G
expr_polish
:
E → T {
T
cout
'
';
}
T → F {
F
cout
'
';
}
F →
a
cout
'a';
| b
cout
'b';
| (E)
В процессе анализа методом рекурсивного спуска входной цепочки a
b
с по грам- матике G
expr_polish
в выходной поток будет выведена цепочка a b с
, являющаяся польской записью исходной цепочки. Таким образом, данная грамматика с действиями каждой цепоч- ке языка арифметических выражений ставит в соответствие подходящую цепочку языка польских записей арифметических выражений. Иными словами, такая грамматика задает
перевод из одного формального языка в другой.
Определение: Пусть T
1
и T
2
— алфавиты. Формальный перевод
— это подмноже- ство множества всевозможных пар цепочек в алфавитах T
1
и T
2
:
(T
1
*
T
2
*
).
Назовем входным языком перевода
язык L
вх
(
)
{
|
: (
,
)
}.
Назовем целевым (или выходным) языком перевода
язык L
ц
(
)
{
|
: (
,
)
}.
Перевод
неоднозначен, если для некоторых
T
1
*
,
,
T
2
*
,
, (
,
)
и
(
,
)
.
Рассмотренная выше грамматика G
expr_polish
задает однозначный перевод: каждому вы- ражению ставится в соответствие единственная польская запись. Неоднозначные переводы могут быть интересны при изучении моделей естественных языков; для трансляции языков программирования используются однозначные переводы.
Заметим, что для двух заданных языков L
1 и L
2 существует бесконечно много фор- мальных переводов
25)
. Чтобы задать перевод из L
1 в L
2
, важно точно указать закон соответ-
ствия между цепочками L
1 и L
2
Пример. Пусть L
1
{0
n
1
m
| n
0, m
0} — входной язык, L
2
{a
m
b
n
| n
0, m
0} — выходной язык и перевод
определяется так: для любых n
0, m
0 цепочке
0
n
1
m
L
1
соответствует цепочка a
m
b
n
L
2
. Можно записать
с помощью теоретико- множественной формулы:
{ (0
n
1
m
, a
m
b
n
) | n
0, m
0 }, L
вх
(
)
L
1
, L
ц
(
)
L
2
Задача.
Реализовать перевод
{ (0
n
1
m
, a
m
b
n
) | n
0, m
0}грамматикой с действиями.
Решение
Язык L
1
можно описать грамматикой:
S
→ 0S | 1A
A →
1A |
Вставим действия по переводу цепочек вида 0
n
1
m
в соответствующие цепочки вида
a
m
b
n
:
S
→ 0S
cout
'b';
| 1
cout
'a';
A
A →
1
cout
'a';
A |
25)
При условии, что хотя бы один из языков
L
1
, L
2
бесконечен. Действительно, пусть
L
1
{a
n
| n
0},
L
2
{b, c}
. Существует бесконечно много переводов
i
{(a
i
, b)}
{(a
n
, c) | n
i, i
0}, где
L
вх
(
i
)
L
1
, L
ц
(
i
)
L
2
Элементы теории трансляции
/
Генерация внутреннего представления программ
87
Теперь при анализе методом рекурсивного спуска цепочек языка L
1
с помощью дей- ствий будут порождаться соответствующие цепочки языка L
2
Генератор внутреннего представления программы на
М
- языке
Каждый элемент в ПОЛИЗе — это лексема, т. е. пара вида
тип_лексемы, значе-
ние_лексемы
. При генерации ПОЛИЗа будем использовать дополнительные типы лексем
(для внутреннего представления операторов):
POLIZ_GO — «!»;
POLIZ_FGO — «!F»;
POLIZ_LABEL — для ссылок на номера элементов ПОЛИЗа;
POLIZ_ADDRESS — для обозначения операндов-адресов (например, в ПОЛИЗе оператора присваивания).
Будем считать, что генерируемая программа размещается в объекте prog класса
Poliz, заданном описанием:
Poliz prog (1000); class Poliz
{ lex *p; int size; int free; public:
Poliz ( int max_size )
{ p
= new Lex [size = max_size]; free = 0;
};
Poliz() { delete []p; }; void put_lex(Lex l) { p[free]=l; ++free; }; void put_lex(Lex l, int place) { p[place]=l; }; void blank() { ++free; }; int get_free() { return free; }; lex& operator[] ( int index )
{ if (index > size) throw "POLIZ:out of array"; else if ( index > free ) throw "POLIZ:indefinite element of array"; else return p[index];
}; void print()
{ for ( int I = 0; i < free; ++i ) cout << p[i];
};
};
Элементы теории трансляции
/
Генерация внутреннего представления программ
88
Объект
prog для хранения внутреннего представления программы разместим в от- крытой части класса
Parser: class Parser
{
Lex curr_lex; public:
Poliz prog;
Parser (const char *program ) : scan (program),prog (1000) {} void analyze();
};
Генерация внутреннего представления программы будет проходить во время синтак- сического анализа параллельно с контролем контекстных условий, поэтому для генерации можно использовать информацию, собранную синтаксическим и семантическим анализато- рами; например, при генерации ПОЛИЗа выражений
можно воспользоваться содержимым стека, с которым работает семантический анализатор. Кроме того, можно дополнить функ- ции семантического анализа действиями по генерации.
Добавим в конец тела функции
check_op(
) оператор
prog.put_lex (
Lex (
op) ); запи- сывающий в ПОЛИЗ знак операции
op, а в конец функции
check_not(
) добавим оператор
prog.put_lex (
Lex (
LEX_NOT) ); записывающий лексему
not (во внутреннем представлении) в
ПОЛИЗ.
Тогда грамматика, содержащая действия по контролю контекстных условий и перево- ду выражений модельного языка в ПОЛИЗ, будет такой:
E → E1
|
E1
[
|
|
]
st_lex.push (
c_type )
E1
check_op (
)
E1
→
T { [
|
|
or ]
st_lex.push (
c_type )
T
check_op (
)
}
T → F { [
| / |
and ]
st_lex.push (
c_type )
F
check_op (
)
}
F → I
check_id (
);
prog.put_lex (
curr_lex );
|
N
st_lex.push (
LEX_INT);
prog.put_
lex (
curr_lex );
|
[
true |
false ]
st_lex.push (
LEX_BOOL);
prog.put_lex (
curr_lex );
|
not F
check_not(
);
| (
E)
Действия, которыми нужно дополнить правило вывода оператора присваивания, так- же достаточно очевидны:
S → I
check_id (
);
prog.put_lex (
Lex (
POLIZ_ADDRESS,
c_val ) );
:
E
eqtype (
);
prog.put_lex (
Lex (
LEX_ASSIGN ) );
При генерации ПОЛИЗа выражений и оператора присваивания элементы объекта
prog заполнялись последовательно.
Семантика условного оператора
if E thenS1
else S
2
такова, что значения операндов для операций безусловного перехода и пе- рехода «по лжи» в момент генерации операций еще неизвестны:
if (!
E)
goto l2
;
S1
;
goto l3
;
l2
:
S2
;
l3
:…
Элементы теории трансляции
/
Генерация внутреннего представления программ
89
Поэтому придется оставлять соответствующие этим операндам элементы объекта
prog незаполненными и запоминать их номера, а затем, когда станут известны их значения, заполнять пропущенное.
Тогда грамматика, содержащая действия по контролю контекстных условий и перево- ду условного оператора модельного языка в ПОЛИЗ, будет такой:
S → if E
eqbool(
);
pl2
prog.get_free(
);
prog.blank(
);
prog.put_lex (
Lex (
POLIZ_FGO ) );
then S1
pl3
prog.get_free(
);
prog.blank(
);
prog.put_lex (
Lex (
POLIZ_GO) );
prog.put_lex (
Lex (
POLIZ_LABEL,
prog.get_free(
) ),
pl2
);
else S2
prog.put_lex (
Lex (
POLIZ_LABEL,
prog.get_free(
) ),
pl3
);
Семантика оператора цикла
while E do Sописывается так:
L0
:
Скачать 2.2 Mb.