Обратная польская запись операций

В, 10)

П, D)

В, С)

4. - Г2. ^Л3)

5.:= (А, ^А4)

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

Обратная польская запись операций

Обратная (постфиксная) польская запись — очень удобная для вычисления вы­ражений форма записи операций и операндов. Эта форма предусматривает, что знаки операций записываются после операндов.

Более подробно обратная польская запись рассмотрена далее.

Ассемблерный код и машинные команды

Машинные команды удобны тем, что при их использовании внутреннее пред­ставление программы полностью соответствует объектному коду и сложные пре­образования не требуются. Команды ассемблера представляют собой лишь форму записи машинных команд (см. раздел «Трансляторы, компиляторы и интерпре­таторы — общая схема работы», глава 13), а потому в качестве формы внутренне­го представления программы практически ничем не отличаются от них.

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

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

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

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

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

I лава 14. I енерацин и оптимизация кода

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

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

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

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

Обратная польская запись была предложена первоначально для записи арифме­тических выражений. Однако этим ее применение не ограничивается. В компи­ляторе можно порождать код в форме обратной польской записи для вычисления практически любых выражений¹. Для этого достаточно ввести знаки, предусмат­ривающие вычисление соответствующих операций. В том числе, возможно ввести операции условного и безусловного перехода, предполагающие изменение после­довательности хода вычислений и перемещение вперед или назад на некоторое количество шагов в зависимости от результата на верхушке стека [6, т. 2, 74, 82]. Такой подход позволяет очень широко применять форму обратной польской за­писи.

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

Вычисление выражений с помощью обратной польской записи

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

1. Если встречается операнд, то он помещается в стек (попадает на верхушку
стека).

2. Если встречается знак унарной операции (операции, требующей одного опе­
ранда), то операнд выбирается с верхушки стека, операция выполняется
и результат помещается в стек (попадает на верхушку стека).

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

кода, методы генерации mjm<»

3. Если встречается знак бинарной операции (операции, требующей двух опе­рандов), то два операнда выбираются с верхушки стека, операция выполняет­ся и результат помещается в стек (попадает на верхушку стека).

Вычисление выражения заканчивается, когда достигается конец записи выраже­ния. Результат вычисления при этом всегда находится на верхушке стека.

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

На рис. 14.4 рассмотрены примеры вычисления выражений в обратной польской записи.

6 7 10 4 + +

Вычисление выражения 6+7* (10+4) = 104

/

+

*

+

Вычисление выражения 6+(7+10) * 4=74 6 7 + 10 4

Вычисление выражения 6+7+10 * 4 = 53

Рис. 14.4. Вычисление выражений в обратной польской записи с использованием стека

Схема СУ-компиляции для перевода выражений в обратную польскую запись

Существует множество алгоритмов, которые позволяют преобразовывать выра­жения из обычной (инфиксной) формы записи в обратную польскую запись.

Далее рассмотрен алгоритм, построенный на основе схемы СУ-компиляции для языка арифметических выражений с операциями +, -, * и /. В качестве основы алгоритма выбрана грамматика арифметических выражений, которая уже много­кратно рассматривалась ранее в качестве примера.

Эта грамматика приведена далее.

622 Глава 14. Генерация и оптимизация кода

G({+,-./.*.a.b}. {S.T.E}. P, S): Р:

s _> s+т | s-т | т

Т -* Т*Е | Т/Е | Е Е -> (S) | a | b

Схему СУ-компиляции будем строить с таким расчетом, что имеется выходная цепочка символов R и известно текущее положение указателя в этой цепочке р. Распознаватель, выполняя свертку или подбор альтернативы по правилу грам­матики, может записывать символы в выходную цепочку и менять текущее по­ложение указателя в ней.

Построенная таким образом схема СУ-компиляции для преобразования арифме­тических выражений в форму обратной польской записи оказывается исключи­тельно простой [6, т. 2]. Она приведена ниже. В ней с каждым правилом грамма­тики связаны некоторые действия, которые записаны через; (точку с запятой) сразу за правой частью каждого правила. Если никаких действий выполнять не нужно, в записи следует пустая цепочка (X).

S -> S+T; R(p) = '+"	• P=P+1
S -> S-T: R(p) = "-"	■ P=P+1
S -» T; X
T -> T*E; R(p) - "*"	, p=p+l
T -* T/E; R(p) - "/"	, p=p+l
T -> E: X
E -> (S): X
E -» a: R(p) = "a".	p=p+l
E -» b: R(D) = "b".	D=D+1

Эту схему СУ-компиляции можно использовать для любого распознавателя без возвратов, допускающего разбор входных цепочек на основе правил данной грамматики (например, для распознавателя на основе грамматики операторного предшествования, рассмотренного в разделе «Восходящие распознаватели КС-языков без возвратов», глава 12). Тогда, в соответствии с принципом СУ-перево-да, каждый раз выполняя свертку на основе некоторого правила, распознаватель будет выполнять также и действия, связанные с этим правилом. В результате его работы будет построена цепочка R, содержащая представление исходного выра­жения в форме обратной польской записи (строго говоря, в данном случае авто­мат будет представлять собой уже не только распознаватель, но и преобразова­тель цепочек [6, 42]).

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

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