1 КОМПІЛЯТОРИ: Синтаксичний переклад Яни Дворжакової
2 Що таке синтаксичний переклад? Весь компілятор контролюється процесом розбору Синтаксичний переклад = зв’язування синтаксичного аналізу з наступними фазами компіляції синтаксичний синтаксичний переклад наступної фази Дії призначаються правилам граматики Генерування коду Збереження інформації в таблиці символів Створення повідомлень про помилки Перевірка узгодженості типу .докладніше Позначення 1 Синтаксичне визначення Анотація нотації 2 Схема перекладу Подібно до синтаксичних визначень, але більше деталей реалізації (порядок дій)
3 Виконання дій 1 Під час синтаксичного аналізу Один перехід, що використовується у компіляторах Без явної побудови дерева деривації Можливе для спеціальних типів визначень, керованих синтаксисом - Напр. Визначення L-атрибутів включають практично всі дефініції, керовані синтаксисом, які можуть бути реалізовані без явної побудови дерева виведення.2 Шляхом обходу явно побудованого дерева деривації вхідний рядок Графік залежності дерева деривації Графік дії
4 Синтаксичне визначення (SRD) Абстрактна специфікація керованого синтаксисом перекладу Створюється шляхом розширення граматики CF мови вводу на 1 атрибути, присвоєні символам граматики Xx = атрибут x символу X Вони не надають додаткової інформації про заданий символ - значення атрибута: рядок, число, тип, місце в пам'яті. 2 Семантичні правила, присвоєні граматичним правилам Bb: = f (C 1.c 1. C kc k) Використовується для обчислення атрибутів символів в межах одного граматичного правила Може містити функції з побічним ефектом (наприклад, вихідне значення, зміна значення глобальної змінної) SRD без функцій побічних ефектів = граматика атрибутів
5 Вгорі дерева виведення = запис із полями граматичний символ атрибут 1 атрибут 2 Атрибути Символ граматики знаходиться в першому полі запису і є прапором в атрибуті Атрибути зберігаються в інших полях Типи атрибутів 1 Синтезовані атрибути Значення розраховується відповідно до використаних значень дочірніх атрибутів. 2 Спадкові атрибути. Значення обчислюються відповідно до значень атрибутів батьків та братів/сестер. Підходить для вираження залежності структур від контексту, в якому вони знаходяться. Якщо Bb: = f (C 1 .c 1. C kc k) ми говоримо, що Bb залежить від C 1.c 1. C kc k Дерево виведення з обчисленими значеннями атрибутів називається анотованим деревом виведення. Термінали мають лише синтезовані атрибути, а немає. граматичний символ має лише спадкові ознаки
6 Визначення на основі синтаксису Приклад 1 - калькулятор Правило граматики Семантичне правило LE n функція друку (e.val) з побічним ефектом EE 1 + T E.val: = E 1.val + T.val ET E.val: = T. val TT 1 F T.val: = T 1.val F.val TF T.val: = F.val F (E) F.val: = E.val F цифра F.val: = digit.lexval значення атрибута надісланий лексичний аналізатор X.val - це синтезований атрибут для X із цілочисельним значенням SRD, лише із синтезованими атрибутами називається визначенням S-атрибута і завжди може бути оцінений на дереві виведення шляхом переходу знизу вгору
7 Визначення, кероване синтаксисом Приклад 2 - оголошення Граматичне правило D T L; T int T реальний LL 1, id L id Семантичне правило L.in: = T.type T.type: = integer T.type: = real L 1.in: = L.in addtype (id.entry, L.in ) addtype (id.entry, L.in) L.in - це успадкований атрибут T.type - синтезований атрибут Не може бути оцінений просто як визначення S-атрибута
8 Показує залежності між атрибутами Графік залежності Орієнтований графік D = (V, E) V - набір вершин, атрибути граматичних символів E - набір ребер, Xx Yy E, якщо Yy залежить від Xx для кожної вершини n у дереві виведення до для кожного атрибуту та граматики символів vn створити вершину для a; для кожної вершини в дереві виведення до для кожного семантичного правила b: = f (c 1. ck), пов'язаного з правилом vn to для i: = 1 до k, щоб додати ребро zci до b Топологічна класифікація D Розстановка вершин m 1 . mk, таке, що має місце: якщо є ребро mimj, то я маю його перед m j. Отримуємо дійсний порядок оцінки атрибутів (якщо D не має циклу)
9 Методи оцінки атрибутів 1 Методи дерева виведення Дерево деривації побудовано явно, знайдено графік залежності та отримано топологічний порядок порядку оцінки атрибутів під час компіляції 2 Методи аналізу правил Порядок оцінки визначається статичним семантичним аналізом правил у компіляторі час побудови 3 "Недбалі" методи * Порядок оцінки визначається незалежно від семантичних правил.Якщо переклад виконується під час синтаксичного аналізу, порядок визначається методом синтаксичного аналізу під час побудови компілятора.
10 Синтаксичне дерево Спрощене дерево деривації Оператори та ключові слова - це внутрішні вершини Зменшуються гілки, виведені за правилами ланцюга. Використовується як тимчасове представлення скомпільованої програми або її частин. Синтаксичний переклад може базуватися на дереві деривації або дереві синтаксису. до вузлів дерева і коментується Переваги дерева синтаксису Граматика, придатна для синтаксичного аналізу, не завжди представляє природну ієрархічну структуру вхідної мови програмування Метод синтаксичного аналізу обмежує порядок доступу до вузлів дерева виведення, і цей порядок не завжди підходить для перекладу
11 Функції побудови вершин: Дерево синтаксису для виразів 1 mknode (op, зліва, справа) 2 mkleaf (id, entry) Повертає вказівник на побудовану вершину 3 mkleaf (num, val) Вершини для операторів реалізовані як записи з декількома полями вказівник на оператор на операнд 1 вказівник на операнд 2 Вершини для ідентифікаторів та числових констант Оператор є міткою вершини Під час перекладу в записі для атрибутів ідентифікатор id 4 вказує ще більше полів на таблицю символів
12 Дерево синтаксису для виразів Синтаксичне визначення Визначення Граматичне правило EE 1 + TEE 1 TETTT 1 FT (E) T id T num Семантичне правило E.nptr: = mknode (+, E 1.nptr, T.nptr) E.nptr: = mknode (, E 1.nptr, T.nptr) E.nptr: = T.nptr T.nptr: = mknode (, T 1.nptr, F.nptr) T.nptr: = E.nptr T.nptr: = mkleaf (id, id.entry) T.nptr: = mkleaf (num, num.val) X.nptr - це синтезований атрибут для X і містить вказівник на відповідну вершину
13 Синтаксичне дерево vs. DAG Загальні підвирази представлені лише одним піддеревом. При додаванні нової вершини перевіряється, чи більше не існує однакової вершини Вираз: a + a (bc) + (bc) d * + * a * - d * da - bca - bcbc
14 Впровадження SRD для синтаксичного аналізу Може бути важко створити автоматичний компілятор для будь-якого SRD У нас є великі класи, для яких це просто 1 Визначення S-атрибутів Містять лише синтезовані атрибути 2 Визначення L-атрибутів Містять як синтезовані, так і успадковані атрибути Певні обмеження для обчислення успадковані атрибути Включає всі SRD, які реалізовані без явної конструкції дерева деривації Визначення S-атрибутів L-атрибути Визначення Обидва класи можуть бути реалізовані при розборі зверху вниз та знизу вгору Обмеження на використовувану граматику
15 Визначення S-атрибута Реалізація для синтаксичного аналізу знизу вгору (1) Значення атрибутів зберігаються в спеціальних полях у стеку синтаксичного аналізатора та пов'язані з граматичними символами (або станами). Якщо символ не має атрибута, значення undefined Стек з місцем для одного атрибута: стан ZYX val Zz Yy Xx top Реалізація - пара полів 1. стан містить покажчики (індекси) на таблицю синтаксичного аналізу LR (1) - Символ граматики неявно знаходиться у стані, не потрібно запам'ятайте це - для простоти ми вказуємо символ замість відповідного стану 2. val містить значення атрибутів - val [i] = значення атрибута для символу в стані [i] Значення синтезованих атрибутів завжди обчислюються перед скорочення від атрибутів, що зберігаються в стеку (= атрибути символів у правій частині правила)
16 Визначення S-атрибута Реалізація для синтаксичного аналізу знизу вгору (2) Приклад: A XYZ, Aa = f (Xx, Yy, Zz) стан val стан val Z Zz top Y Yy X Xx розрахунок Aa зменшення A -> XYZ A Aa top - Zz: = val [вгорі] - Yy: = val [вгорі 1] - Xx: = val [вгорі 2] - зверху: = зверху 2 - val [вгорі]: = Aa
17 Правило граматики Визначення S-атрибута Впровадження для синтаксичного розбору знизу вгору (3) Фрагмент коду LE n print (val [top]) EE 1 + T val [ntop]: = val [top 2] + val [top] ETTT 1 F val [ntop]: = val [top 2] val [top] TFF (E) val [ntop]: = val [top 1] F-цифра Фрагменти коду пов'язані зі скороченнями в парсері LR. Ми отримуємо їх із семантичних правил, замінюючи атрибути з позиціями в полі val Виконується безпосередньо перед зменшенням Змінні top і ntop top - поточна вершина стека, ntop - нова вершина процедури зменшення стека згідно з правилом A β, де β = r 1 ntop встановлено вгорі r Виконується фрагмент коду, а зменшення 3 top встановлюється на ntop
18 Визначення L-атрибута Визначення, кероване синтаксисом, є L-атрибутом, якщо для будь-якого правила AX 1, X 2. X n вважає, що кожен успадкований атрибут символу в правій частині X j залежить лише від 1 атрибута символів X 1, X 2. X j 1, які знаходяться в правилі ліворуч від X ja 2 спадковими атрибутами символу A. SRD, що не є L-атрибутом Граматичне правило: A LM A QR Семантичне правило: Li: = l (ai) Mi: = m (ls) As: = f (Ms) Ri: = r (ai) Qi: = q (rs) As: = f (Qs) Примітка: Кожне визначення S-атрибута також є L-атрибут Не відповідає визначенню
19 Визначення L-атрибута Оцінка атрибутів Атрибути можуть бути оцінені шляхом обходу дерева у глибині (перший-перший порядок) процедури dfvisit (n: вузол); почати для кожної дієти a m вершини n zl ava право розпочати оцінювати успадковані атрибути вершини m; dfvisit (m) end; оцінити синтезовані атрибути вершини n end Природний спосіб обходу дерева виведення Впровадження визначення L-атрибутів при синтаксичному аналізі 1 Синтаксичний розбір зверху вниз Всі SRD на основі граматик LL (1) 2 Синтаксичний аналіз знизу вгору Усі SRD на основі граматик LL (1), велика частина SRD на основі граматик LR (1)
20 Схеми перекладу Інший спосіб вказати переклад, керований синтаксисом Більш конкретний, ніж SRD. Також визначає порядок, в якому обчислюються атрибути. Семантичні дії укладаються в <> і вставляються між правими символами правила. ETR-еквівалент надбудови постфікса TR 1 ε T num addop.lexeme може бути + або - Граматика створена шляхом видалення лівої рекурсії з відомої граматики для виразів
21 Обмеження для схем перекладу Дія не повинна посилатися на нерахуваний атрибут Схеми перекладу для визначень S-атрибутів Просте рішення - дії розміщуються в кінці правил Схеми перекладу для визначень L-атрибутів 1 Спадковий атрибут символу з правого боку правила його. 2 Дія не повинна посилатися на синтезований атрибут символу праворуч. 3 Синтезований нетермінальний атрибут у лівій частині правила можна обчислити лише після того, як були обчислені всі атрибути, від яких воно залежить. Відповідна дія для його обчислення зазвичай знаходиться в кінці правої частини правила Приклад "поганої" схеми перекладу S A 1 A 2 A a
22 Визначення L-атрибута Реалізація в інтелектуальному аналізі Реалізація можлива лише для визначень L-атрибутів (схеми перекладу *) на основі граматик LL (1), які, крім усього іншого, не можуть містити ліву рекурсію. Існує метод безпосереднього видалення лівої рекурсії зі схем перекладу Розширення алгоритму видалення лівої рекурсії з граматики CF Може застосовуватися до схем перекладу із синтезованими атрибутами Якщо у нас вже є схема перекладу, заснована на граматиці LL (1), існує алгоритм побудови прогнозованого синтаксису компілятор
23 Видалення лівої рекурсії з перекладу. схема вхідного перекладу: A A 1 Y A X Після видалення лівої рекурсії з граматики CF ми отримуємо нову граматику: A X R R Y R ε Після переписування семантичних дій отримуємо результуючий трансл. схема: A X R R Y R 1 R ε
25 Вхід для проектування передбачуваного компілятора. Схема перекладу на основі синтаксису, заснована на граматиці, придатній для інтелектуального синтаксичного аналізу. Вихідні дані. Код для інтелектуального компілятора, керованого синтаксисом. 1 Для кожного нетермінала A створіть функцію, яка має формальний параметр для кожного успадкованого атрибута A і повертає значення синтезованих нетерміналів A. Функція A має локальну змінну для кожного атрибута кожного символу, що зустрічається в правилі для A. 2 Код нетерміналу A вирішує, яке правило застосовувати відповідно до поточного вхідного символу. 3 Код, пов'язаний з кожним правилом, виконує такі дії. (i) Для маркера X із синтезованим атрибутом x зберігаємо значення x у змінній, оголошеній для X.x. Потім викликайте процедуру збігу (x) і перейдіть до введення. (ii) Для нетермінального B генерують присвоєння виду c: = B (b 1, b 2. bk), де b 1, b 2. bk - змінні для успадкованих атрибутів нетерміналу B, c є змінною для синтезованого атрибуту мережі. B і B - це виклик функції мережі. B. (iii) Для дії скопіюйте код безпосередньо в синтаксичний аналізатор, замінюючи посилання на кожен атрибут на пов'язану змінну.
26 Синтаксичний переклад під час синтаксичного аналізу Резюме 1 Впровадження визначень атрибутів S Ми мали алгоритм синтаксичного розбору знизу вгору. Вони також можуть бути реалізовані при синтаксичному аналізі зверху вниз - Видалення лівої рекурсії зі схеми перекладу та побудова прогностичного компілятора 2 Реалізація визначень L-атрибутів алгоритм розбору зверху вниз Також може бути реалізований для розбору знизу вгору - Розширення алгоритму для обробки визначень S-атрибутів В обох випадках набір граматик CF, на яких базується SRP, обмежений - Знизу вгору компілятор сильніший