Page 51 - 4761

Обчислення виразу, записаного у формі тріад, відбувається послідовно: операція,
задана тріадою, виконується над операндами, а якщо в якості одного з операндів (або
обох) виступає посилання на другу тріаду, то береться результат обчислення тої тетради.

Приклад 4.2. Вираз A:=B*C+D-B*10, запишемо у вигляді тетрад.
1. *(B, C)
2. +(C^1, D)
3. *(B, 10)
4. –(^2, ^3)
5. :=(A,^4), де ^ – посилання тріади на результат другої
Це машино-незалежна форма ВПП. Вимагає менше пам’яті для свого
представлення і відображають взаємозв’язок операцій між собою. Вони ближчі до
двоадресних машинних команд.

Зворотній польський запис. В цьому запису знаки операцій записуються
безпосередньо за операндами. Порівняно зі звичайним записом операцій в польському
записі операнди розміщуються в тому ж порядку, а знаки операцій – строго в порядку їх
виконання. Той факт, що в цій формі запису всі операції виконуються в тому порядку, в
якому вони записані, робить її дуже зручною для обчислення виразів на комп’ютері.
Польський запис не потребує враховувати пріоритет операцій, в ній не використовуються
дужки, і в цьому його основна перевага.
Він дуже ефективний, коли для обчислення використовується стек.
Головний недолік зворотного польського запису виходить з методу обчислення
виразів в ньому: оскільки використовується стек, то для роботи з ним завжди доступна
тільки верхівка стеку, а це викликає додаткові труднощі при оптимізації виразів в формі
зворотного польського запису. Практично вони не піддаються оптимізації.
Але там, де оптимізація виразів не потрібна або не має великого значення,
зворотній польський запис є дуже зручним методом внутрішнього представлення
програми.
Зворотній польський запис був запропонований спершу для обчислення
арифметичних виразів. Але цим його застосування не обмежується. В компіляторі можна
породжувати код в формі зворотного польського запису для обчислення практично любих
виразів. Для цього достатньо ввести знаки для, які передбачають обчислення відповідних
операцій. В тому числі можна ввести операції умовного та безумовного переходу, які
передбачають зміну послідовності ходу обчислень і переміщення вперед або назад на
деяку кількість кроків в залежності від результату на верхівці стеку.
Польський зворотній запис широко використовується для обчислення виразів в
інтерпретаторах, де оптимізація обчислень або відсутня зовсім або не має суттєвого
значення.
Обчислення виразів в зворотному польському записі іде елементарно просто за
допомогою стеку. Для цього вираз переглядається а порядку зліва направо і елементи, які
зустрічаються в ньому, обробляються за наступними правилами:
1. Якщо зустрічається операнд то він поміщується в стек (попадає у верхівку
стеку).
2. Якщо зустрічається знак упорної операції (операції, яка потребує одного
операнда), то операнд вибирається з верхівки стеку, операція виконується і результат
поміщається в стек (попадає у верхівку стеку).
3. Якщо зустрічається знак бінарної операції, то два операнда вибираються з
верхівки стеку, операція виконується і результат поміщається в стек (верхівку стеку).
Обчислення виразу закінчується, коли досягається кінець запису виразу. Результат
обчислення при цьому завжди знаходиться у верхівці стеку.

49