Постфіксне представлення арифметичних виразів

ГЛАВА 6. СИНТАКСИЧНО КЕРОВАНА ТРАНСЛЯЦІЯ

Для трансляції конструкцій мови програмування компілятору, крім генерації коду, може потрібно буде відслідкувати низку параметрів: тип граматичної конструкції, розташування першої інструкції в цільовому коді, кількість генерованих інструкцій і т.п. Тобто можна говорити про певні атрибути,що пов’язані з граматичними конструкціями вхідної мови. Звідси можна прийти до висновку, що можна цільову програму отримати як синтез таких атрибутів, які будемо називати семантичними правилами, в процесі синтаксичного аналізу, при якому розпізнаються граматичні конструкції. В цьому і полягає сутність синтаксично керованої компіляції (СКК).

Крім використання СКК на попередніх стадіях генерації коду в компіляторах універсальних мов програмування вона використовується для реалізації нескладних компіляторів. Нижче наводиться приклад побудови компілятора перетворення інфіксного запису арифметичних виразів в постфіксний.

Постфіксне представлення арифметичних виразів

В інфіксній формі запису оператор двохмісної операції стоїть між операндами, наприклад, сума двох змінних записується так: А+В. Це найбільш прийнята форма запису, яка застосовується при математичних записах у більшості мов програмування для представлення аріфметичних записів.

В префіксній формі запису оператор двохмісної операції стоїть перед операндами, наприклад, +АВ. Ця форма запису використовується для виклику функцій, наприклад, SUM(A,B).

У постфіксній формі запису оператор двохмісної операції стоіть після операндів, наприклад, АВ+. Постфіксна форма є цикавою тим, що вона дозволяє представити будь-який вираз без застосування дужок, при цьому для підрахунку значення виразу використовується стек. Тому в компіляторах мов програмування, які оперують з арифметичними виразами, спочатку здійснюється перетворення виразу із інфіксної форми в постфіксну форму, яка реалізується з використанням стеку, оскільки у складі машиних команд більшості процесорів є команди роботи зі стеком. Наведемо кілька простих прикладів перетворення виразів із інфіксної форми в постфіксну.

Приклад 6.1. A+B*C → A+(B*C) → A+(BC*) → A(BC*)+ → ABC*+

Приклад 6.2. (A+B)*C → (AB+)*C → (AB+)C* → AB+C*

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

В табл. 6.1 наведено інші приклади запису еквівалентних виразів в інфіксній та постфіксній формах, операнд “↑” відповідає операції „піднесення в степень”.

Талиця 6.1. Приклади запису в інфіксній та постфіксній формах

Алгоритм перетворення виразу із інфіксної форми в постфіксну в загальному вигляді виглядає так: спочатку здійснюється перетворення операції найвищого пріоритету (№1) одного рівня в операнди наступного рівня, потім – наступного рівня і т. д. до найнижчого рівня. Наприклад, у виразі A+B*C послідовність операцій <+,*>, а порядок їх виконання <*,+>, тобто при інфіксній формі матиме вираз ABC*+. А якщо для завдання пріоритетів використовуються дужки, спочатку за вище наведеним правилом виконуються перетворення на самому значущому вищому рівні пріоритету (самі внутрішні дужки) і вираз в дужках має бути перетворений в операнд, потом наступний і т. д. до самої зовнішньої пари дужок. Наприклад, у виразі (A+B)*C і послідовність операцій <+,*>, і порядок їх виконання такий же <+,*>, тобто при постфіксній формі матиме вираз AB+C*. Цей алгоритм легко реалізується стеком: якщо дужка відкрилася і її занесено в стек, то наступна аналогічна дужка теж заноситься в стек і т.д., поки не дійдемо до першої закриваючої дужки, що буде означати найвищий пріоритет в межах самих зовнішніх дужок. Після виконання операцій в цих дужках і вилучення зі стеку обох останніх дужок (закриваючої і відкриваючої) будемо йти до наступної закриваючої дужки і т.д. В алгоритмі треба також передбачити врахування пріоритетів арифметичних операцій.

Для демонстрації алгоритму використаємо таблицю (приклад 6.3), в якій в колонці „Symbol” будемо розміщувати поточне значення операнда або оператора при його скануванні; в колонці „Postf” – поточне значення виразу в постфіксній формі, при цьому до нього заносяться операнди при кожній появі в колонці „Symbol”, а оператори – при „розвантаженні” стеку (колонка Stack), куди вони заносяться в порядку появи при скануванні. Розвантажування стеку (перенесення символів операторів в кінець поточного значення колонки „Postf”) здійснюється за такими умовами:

1. Якщо черговий оператор, що прочитаний сканером, має пріоритет нижчій, чим самий верхній оператор, що знаходиться в стеку (в таблиці – самий правий). При цьому верхній оператор, що знаходиться в стеку, переноситься в кінець постфіксного запису, а прочитаний оператор заноситься в стек.

2. Якщо черговий оператор, що прочитаний сканером, і самий верхній оператор, що знаходиться в стеку, є оператором віднімання (символ “-“, то цей оператор дописується до постфіксного запису.

3. Якщо черговий оператор, що прочитаний сканером, і самий верхній оператор, що знаходиться в стеку, є оператором множення (символ “*”, то цей оператор дописується до постфіксного запису.

4. Якщо зустрілася закриваюча дужка “)”, то при цьому розвантажується вміст стеку тільки до першої відкриваючої дужки “(”. Самі дужки не переносяться, а відкриваюча дужка просто видаляється із стеку.

5. Якщо завершено сканування усього рядка, що представляє вираз в інфіксній формі, то розвантажується увесь вміст стеку при цьому оператори зі стеку покроково дописуються у кінець постфіксного запису.

Приклад 6.1. Вираз в інфіксній формі id1+id2*id3

Приклад 6. 2. Вираз в інфіксній формі id1*id2 +id3

Приклад 6.3. Вираз в інфіксній формі (id1+id2)*id3

Приклад 6. 4. Вираз в інфіксній формі id1-id2-id3