Стр. 67 - Информационные структуры и их преобразование

Содержание 65
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
исходной программы, а все последующие просмотры компилятора могут
быть реализованы в виде самостоятельных обходов этого дерева. Кроме того,
некоторые просмотры, такие как оптимизация программы, удобнее всего
выполнять именно над деревьями разбора.
Польская запись
Польская запись была предложена польским логиком Лукасевичем. В
этой форме записи все операторы непосредственно предшествуют
операндам. Так, обычное выражение (a+b)*(c-d) в польской записи может
быть представлено как *+ab-cd.
Такую форму записи называют также префиксной. Аналогичным
образом вводится обратная, или постфиксная, польская запись, в которой все
операторы выписываются после операндов. Скажем, пример, приведенный
выше, в обратной польской записи будет записан следующим образом:
ab+cd-*. Для представления унарных операций в польской записи можно
воспользоваться эквивалентными выражениями, использующими бинарные
операции, как в следующем примере: -b -> 0 - b, а можно ввести новый знак
операции, скажем, @b . Польская запись может быть распространена не
только на арифметические выражения, но и на прочие конструкции языка.
Например, оператор a := a + b может быть записан в польской записи как
:=a+ab, а условный оператор if <expr> then <instr1> else <instr2> может быть
записан как следующая последовательность операторов:
<expr> <c1> BZ <instr1> <c2> BR <instr2>,
где c1 указывает на первую инструкцию <instr2>, а c2 - на первую
инструкцию, следующую за <instr2>, BR - безусловный переход на адрес
<c2>, а BZ - переход на <c1> при условии равенства нулю выражения
<expr1>.
Пользуясь такой терминологией, мы можем называть традиционную
форму записи выражений инфиксной, так как в ней знаки операций
расположены между операндами. Понятно, что любое выражение может
быть переведено из инфиксной формы в польскую запись и наоборот.
Польская запись замечательна тем, что при ее использовании исчезает
потребность в приоритетах операций - каждая операция выполняется в
порядке появления в исходной цепочке (хотя очевидно, что приоритет
операций необходимо учитывать при преобразованиях из инфиксной
формы).
Польская запись (особенно обратная) очень хорошо накладывается на
стековую модель: каждый встреченный операнд загружается в стек, а
операции производятся только на вершине стека: каждая операция снимает