Польская инверсная запись

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

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

Генерация.

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

Пусть транслируется условный оператор входного языка, имеющий вид:

IF (A - B) 10, 15, 20

Для данного входного языка определено, что

IF - служебное слово оператора условия.

A - B - арифметическое выражение.

10, 15, 20 - метки.

Работа оператора состоит в вычислении арифметического выражения

И сравнение полученного результата с нулем на больше, равно или меньше нуля.

В зависимости от трех возможных исходов сравнения осуществляется переход на соответствующую программную метку.

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

1

X > 0 10

1 "семантика"

X = 0 15 оператора IF.

1

X < 0 20

обработка ошибки

Тут как раз хороший повод вернуться к вопросу трансляции арифметических выражений. Часто для них (и не только) выполняют преобразование в польскую инверсную запись (ПОЛИЗ), что упрощает последующее выполнение-вычислеие.

Вообще есть три способа записи операций:

1. Инфиксный: a*b (например, а + b).

2. Префиксный: *ab (например, S(a,b)).

3.Постфиксный: ab* (например, а и b - просуммировать)

О третьем, постфиксном, способе и идет речь. Его еще называют

польской инверсной записью; в память о польском математике Яне Лукашевиче.

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

выход вход магазина (стека)

n верхушка магазина