Delphi World - Лекції з конструювання компіляторів - Частина 12

8.8. Виділення загальних подвиражений

Виділення загальних подвиражений проводиться на лінійній ділянці та ґрунтується на двох положеннях.

1. Оскільки на лінійній ділянці змінної може бути кілька присвоювань, то при виділенні загальних виразів необхідно розрізняти входження змінних до і після присвоювання. Для цього кожна змінна має номер. Спочатку номери всіх змінних встановлюються рівними 0. При кожному надання змінної її номер збільшується на 1.

2. Виділення загальних виразів здійснюється при обході дерева виразу знизу вгору зліва направо. При досягненні чергової вершини (нехай операція, застосована в цій вершині, є бінарна 'op'; у разі унарної операції міркування ті самі) переглядаємо загальні вирази, пов'язані з op. Якщо є вираз, пов'язаний з op і таке, що його лівий операнд є загальним виразом з лівим операндом нового виразу, а правий операнд - загальний вираз з правим операндом нового виразу, то оголошуємо новий вираз загальним зі знайденим і в новому виразі запам'ятовуємо покажчик на знайдене загальний вираз. Базисом побудови служить змінна: якщо операндами обох виразів є однакові змінні з однаковими номерами, вони є загальними подвыражениями. Якщо вираз не виділений як загальний, він заноситься до списку операцій, пов'язаних з op (рис. 8.27).

Розглянемо тепер реалізацію алгоритму виділення загальних виразів. Підтримуються такі глобальні змінні: Table – таблиця змінних; для кожної змінної зберігається її номер (Count) та покажчик на вершину дерева виразів, у якій змінна зустрілася в останній раз у лівій частині (Last); OpTable - таблиця списків загальних виразів, пов'язаних із кожною операцією (Addr -покажчик на вершину дерева, List – продовження списку);

З кожною вершиною дерева виразу пов'язана запис:

Всі загальні вирази зібрані в список (з типом елемента LisType), що починається з OpTable [Op], як це зображено на рис. 8.28.

Виділення загальних виразів та побудова дерева здійснюються наведеними нижче правилами. Атрибут Entry нетерміналу Variable дає покажчик на змінну таблиці. Атрибут Val символу Op надає код операції. Атрибут Node символів IntExpr та Assignment дає покажчик на запис типу NodeType відповідного нетерміналу.

Розглянемо тепер деякі прості правила розподілу регістрів за наявності загальних виразів. Якщо кількість регістрів обмежена, можна вибрати один із двох варіантів.

2. Вводимо ще один прохід. На першому проході розподіляємо регістри. Якщо деякій вершині виявляється, що її поддерево загальне з вже обчисленим раніше, але значення регістру втрачено, то такій вершині другою проході необхідно згенерувати команду скидання регістру в робочу пам'ять. Виграш у коді буде, якщо вартість команди скидання регістру + доступ до пам'яті у повторному використанні цієї пам'яті не перевищує вартості піддерева, що замінюється. Оскільки вартість команди MOVE відома, можна порівняти вартості та прийняти оптимальне рішення: чи мітити попередню вершину для скидання, чи обчислювати повністю піддерево.

8.9. Генерація оптимального коду методами синтаксичного аналізу

8.9.1. Зіставлення зразків

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

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

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

Як правило, ті самі конструкції вихідної (або проміжної) програми можна реалізувати різними послідовностями машинних команд. Це відповідає тому, що є різні покриття проміжного уявлення. Завдання вибору команд у тому, щоб вибрати найкращий спосіб реалізації тієї чи іншої дії чи послідовності дій, т. е. вибрати певному сенсі оптимальне покриття. Для вибору оптимального покриття було запропоновано кілька цікавих алгоритмів, зокрема, що використовують динамічне програмування [10,11]. Ми тут розглянемо алгоритм [12], що комбінує можливості синтаксичного аналізу та динамічного програмування, в основу якого покладено синтаксичний аналіз неоднозначнихграматик (модифікований алгоритм Кока, Янгера та Касамі [13,14]) ефективніший у реальних додатках. Цей метод може бути застосований і тоді, коли в якості проміжного уявлення використовується дерево.

8.9.2. Синтаксичний аналіз для T-граматик

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

Для T-граматик всі ланцюжки, які виводяться з будь-якого нетерміналу A, є префіксними виразами з фіксованою арністю операцій. Довжини всіх виразів із вхідного ланцюжка a1. an можна попередньо обчислити. Тому можна перевірити, чи можна порівняти правило з підчіпкою ai. ak вхідний ланцюжок a1. an, проходячи ліворуч-направо ai. ak. У процесі проходу ланцюжком попередньо обчислені довжини префіксних виразів використовуються для того, щоб перейти від одного терміналу до наступного терміналу, пропускаючи підчіпки, що відповідають нетерміналам правої частини правила.

Ланцюгові правила не залежать від операцій, отже їх необхідно перевіряти окремо. Використання одного ланцюгового правила може залежати від застосування іншого ланцюгового правила. Отже, застосування ланцюгових правил необхідно перевіряти циклічно доти, доки не можна застосувати жодне з ланцюгових правил. Ми припускаємо, що вграматиці немає циклів у застосуванні ланцюгових правил. Тип Titem в алгоритмі 8.1 нижче служить для опису ситуацій (тобто правил виведення та позиції всередині правила). Тип Tterminal - це тип термінального символу граматики, тип Tproduction - тип правила виведення.

Робота алгоритму ілюструється на рис. 8.32. Багато r[i] мають розмір O(P). Очевидно, що алгоритм має тимчасову та ємнісну складність O(n).

Розглянемо знову приклад рис. 8.29. У префіксному записі наведений фрагмент програми записується так:

На рис. 8.33 наведено результат роботи алгоритму. Правила обчислення вартості наведені у розділі 8.9.3.

Нехай G – це T-граматика. Для кожного ланцюжка z із L(G) можна побудувати дерево виразу. Ми можемо переписати алгоритм так, щоб він працював з деревами виразів, а не з префіксними виразами. Цей варіант алгоритму наведено нижче. У цьому алгоритмі дерево виразу обходиться зверху вниз і в ньому шукаються піддерева, порівняні з правими частинами правил G. Обхід дерева здійснюється процедурою PARSE. Після обходу піддерева даної вершини в ній застосовується процедура MATCHED, яка намагається знайти всі зразки, які можна порівняти з піддеревою даної вершини. Для цього кожне правило-зразок розбивається на компоненти відповідно до зустрічаються в ньому операціями. Дерево обходиться праворуч наліво лише для того, щоб мати відповідність до порядку обчислення в алгоритмі 8.1. Очевидно, що можна обходити дерево виводу та зліва направо. Структура даних, що представляє вершину дерева, має таку форму:

Виходом алгоритму є дерево виразу для z, вершинам якого зіставлені застосовні правила. Якщо T-граматика неоднозначна, можна побудувати кілька різних висновків для заданої вхідний ланцюжка.

Алгоритми 8.1 та 8.2 "універсальні" в тому сенсі, що конкретні граматики виразів та зразків є, по суті, параметрами цих алгоритмів. Для кожної конкретної граматики можна написати власний алгоритм пошуку зразків. Наприклад, у разі нашої граматики виразів та наведених на рис. 8.30 зразків алгоритм 8.2 може бути представлений атрибутною граматикою, наведеною нижче. Для кожного правила є два типи зразків: "внутрішні", що відповідають правилам-зразкам, і "зовнішні", що надходять зверху через атрибут Match предка. Атрибут Match представлений як вектор зразків виду. Кожен із зразків має вигляд або , де op - оперція в цій вершині, а op-list - список її операндів, або зразок - це нетермінал N. У першому випадку op-list "розподіляється" за нащадками вершини для подальшого зіставлення, у другому зіставлення вважається успішним, якщо є правило N-g, де w - складається з зразків, успішно зіставлених нащадкам цієї вершини. Крім атрибута Match, зразки можуть задаватися і відповідно до правил, можливо застосовних у цій вершині. Ці дві множини зразків можуть перетинатися. Синтезований атрибут Pattern (також вектор) дає результат зіставлення за вектором-зразком Match.

Цьому правилу відповідає один зразок 2. Тому як зразки нащадків через їх атрибути Match передаються, відповідно, і .

Зразки, що відповідають цьому правилу, такі:

Атрибути Match другого і третього символів як зразки при зіставленні можуть бути передані вектори і, відповідно. З аналізу інших правил можна зробити висновок, що при зіставленні зразків предків лівої частини даного правила атрибуту Match символу лівої частини може бути переданий зразок (із зразків 2,3,6) або зразок Reg.

Іншим значенням Pattern присвоїти false.

Зразки, що відповідають цьому правилу, такі:

Відповідно, атрибуту Match другого символу як зразки при зіставленні можуть бути передані (зразок 3) або (зразок 7). З аналізу інших правил можна зробити висновок, що при зіставленні зразків предків лівої частини даного правила атрибуту Match можуть бути передані зразки (зі зразка 6) і Reg.

Для дерева мал. 8.29 отримаємо значення атрибутів, наведені на рис. 8.34. Тут M позначає Match, P – Pattern, C – Const, R – Reg.

8.9.3. Вибір дерева виведення найменшої вартості

T-граматики, що описують системи комад, зазвичай є неоднозначними. Щоб створити код для деякого вхідного ланцюжка, необхідно вибрати одне з можливих дерев виведення. Це дерево повинне представляти бажану якість коду, наприклад, розмір коду та/або час виконання. Для вибору дерева з безлічі всіх побудованих дерев виведення можна використовувати атрибути вартості, атрибутні формули, що обчислюють їх значення, та критерії вартості, які залишають для кожного нетерміналу єдине застосовне правило. Атрибути вартості порівнюються всім нетерміналам, атрибутні формули - всім правилам T-граматики.

що обчислює для правила p значення атрибуту a нетерміналу A у вершині n. Для всіх застосованих правил шукається таке, що дає мінімальне значення вартості. Відсутність застосованих правил позначається через undefined, значення якого належить більшим за будь-яке певне значення. Додамо в алгоритм 8.2 реалізацію атрибутів вартості, формул їх обчислення та критеріїв відбору. З алгоритму можна виключити пошук підвисновків, які відповідають правилам, котрим значення атрибута вартості не визначено. Структура данихщо представляє вершину дерева, набуває наступного вигляду:

Тіло процедури PARSE набуває вигляду

Коли вибрано дерево виведення найменшої вартості, обчислюються значення атрибутів, зіставлених вершинам дерева виводу, і генеруються відповідні машинні команди. Обчислення значень атрибутів, генерація коду здійснюються в процесі обходу вибраного виведення дерева зверху вниз, зліва направо. Обхід вибраного дерева виведення виконується процедурою обчислювача атрибутів, на вхід якої надходять корінь виразу дерева і аксіома граматики. Процедура використовує правило p:A::=z0 X0 z1. Xk zk, пов'язане із зазначеною вершиною n, та заданий нетермінал A, щоб визначити відповідні їм вершини n1. nk та нетермінали X1. Xk. Потім обчислювач рекурсивно оминає кожну вершину ni, маючи на вході нетермінал Xi.

---