ГЛАВА 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. Приклади запису в інфіксній та постфіксній формах
Інфіксна форма | Постфіксна форма |
A+B | AB+ |
A+B-C | AB+C- |
(A+B)*(C-D) | AB+CD-* |
A↑B*C-D+E/F/(G+H) | AB↑C*D-EF/GH+/+ |
(A+B)*C-(D-E)↑(F+G) | AB+C*DE-FG+↑- |
A-B/(C*D↑E) | ABCDE↑*/- |
Алгоритм перетворення виразу із інфіксної форми в постфіксну в загальному вигляді виглядає так: спочатку здійснюється перетворення операції найвищого пріоритету (№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
№ | Symbol | Postf | Stack | Comments |
1 | id1 | id1 | $ | |
2 | + | id1 | $+ | |
3 | id2 | id1 id2 | $+ | |
4 | * | id1 id2 | $+* | |
5 | id3 | id1 id2 id3 | $+* | Прочитано останній символ, треба розвантажувати стек |
6 | id1 id2 id3 * | $+ | Зчитано та додано до „Postf” верхній елемент стеку | |
7 | id1 id2 id3 * + | $ | Зчитано та додано до „Postf” наступний (він і останній) елемент стеку |
Приклад 6. 2. Вираз в інфіксній формі id1*id2 +id3
№ | Symbol | Postf | Stack | Comments |
1 | id1 | id1 | $ | |
2 | * | id1 | $* | |
3 | id1 id2 | $* | ||
4 | + | id1 id2 | $* | Операція “+” має менший пріоритет у порівнянні з операцією “*”, тому |
5 | id1 id2 * | $+ | розвантажуємо стек – символ операції “*” переноситься до „Postf”, а символ “+” заносимо до стеку | |
6 | id3 | id1 id2 * id3 | $+ | Прочитано останній символ, треба розвантажувати стек |
7 | id1 id2 * id3 + | $ | Зчитано зі стеку та додано до „Postf” вміст стеку |
Приклад 6.3. Вираз в інфіксній формі (id1+id2)*id3
№ | Symbol | Postf | Stack | Comments |
1 | ( | $( | ||
2 | id1 | id1 | $( | |
3 | + | id1 | $(+ | |
4 | id2 | id1 id2 | $(+ | |
5 | ) | id1 id2 | $(+ | зустрілася закриваюча дужка “)”, |
6 | id1 id2 + | $ | тому розвантажуємо стек – символ операції “+” переноситься до „Postf”, а дужки видаляються | |
7 | * | id1 id2 + | $* | |
id3 | id1 id2 * id3 | $* | Прочитано останній символ, треба розвантажувати стек | |
9 | id1 id2 + id3 * | $ | Зчитано зі стеку та додано до „Postf” вміст стеку |
Приклад 6. 4. Вираз в інфіксній формі id1-id2-id3
№ | Symbol | Postf | Stack | Comments |
1 | id1 | id1 | $ | |
2 | - | id1 | $- | |
3 | id2 | id1 id2 | $- | |
4 | - | id1 id2 | $- | Оскільки операція “-” не комутативна, тому |
5 | id1 id2 - | $- | символ операції “-” переноситься до „Postf | |
6 | id3 | id1 id2 - id3 | $- | Прочитано останній символ, треба розвантажувати стек |
7 | id1 id2 - id3 - | $ | Зчитано зі стеку та додано до „Postf” вміст стеку |