Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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

Читайте также:
  1. Алгоритм перевода выражений в польскую запись
  2. Аналогична математическая запись ограничения по расходу В
  3. Арест денежных средств на банковском счете. Приостановление операций по счету
  4. Аудит валютных операций коммерческого банка
  5. Аудит депозитных операций кредитной организации.
  6. Аудит кассовых операций
  7. Аудит кассовых операций банка.
  8. Аудит кредитных операций банка
  9. Аудит операций с производственными запасами и товарами
  10. АУТОГЕННАЯ ТРЕНИРОВКА И БИОЛОГИЧЕСКАЯ ОБРАТНАЯ СВЯЗЬ
  11. БУХГАЛТЕРСКИЙ УЧЕТ ЛИЗИНГОВЫХ ОПЕРАЦИЙ
  12. В одной из работ было показано, что новорожденные младенцы успокаиваются, если им дать прослушать запись ударов человеческого сердца.



В, 10 )

П, D )

В, С )

4. - Г2. Л3 )

5. := ( А, А4 )

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


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

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

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

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

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

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

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

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

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

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




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

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

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

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

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

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

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

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

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

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

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

1 Язык программирования 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; Просмотров: 616; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 54.224.197.251
Генерация страницы за: 0.009 сек.