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

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

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

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

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

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

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

Постфиксная запись выражения Е может быть определена следующим образом.

1) Если Е является переменной или константой, то постфиксная запись Е представляет собой Е.

2) Если Е – выражение вида Е₁ op Е₂ , где op – произвольный бинарный оператор, то постфиксная запись Е представляет собой Е₁’ Е₂’ op, где Е₁’ и Е₂’ - постфиксные записи для Е₁ и Е₂ соответственно.

3) Если Е – выражение вида (Е₁), то постфиксная запись для Е₁ представляет собой также и постфиксную запись для Е.

4) Скобки в постфиксной записи не используются.

Например, постфиксная запись для выражения (8-3)+5 представляет 83-5+.

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

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

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

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

Дата добавления: 2014-12-27