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 до за i: = 1 до k, за да добавите ръб zci към b Топологична класификация D Разположение на върховете m 1 mk, такова, че има значение: Ако има ръб mimj, тогава го имам преди m j. Получаваме валиден ред за оценка на атрибута (ако D няма цикъл)
9 Методи за оценка на атрибутите 1 Методи за деривационно дърво Деривационното дърво се изгражда изрично, намира се графика на зависимост и се получава топологичен ред на реда за оценка на атрибутите по време на компилация. 2 Методи за анализ на правилата * Редът на оценяване се определя независимо от семантичната правила. Ако преводът се извършва по време на синтактичния анализ, редът се определя от метода на синтактичния анализ по време на изграждането на компилатора.
10 Синтактично дърво Опростено дърво на деривация Операторите и ключовите думи са вътрешни върхове. Клоновете, извлечени от правилата на веригата, се намаляват Използва се като временно представяне на компилирана програма или нейни части Синтаксисно управляваният превод може да се основава на деривационно дърво или синтаксисно дърво. към възлите на дървото и е анотирано Предимства на синтаксичното дърво Граматиката, подходяща за синтактичен анализ, не винаги представлява естествената йерархична структура на входния език за програмиране. Методът на парсинг ограничава реда на достъп до възлите на дървото на деривацията и този ред не е винаги подходящ за превод
11 Функции за изграждане на върхове: Синтаксисно дърво за изрази 1 mknode (op, ляво, дясно) 2 mkleaf (id, entry) Връща указател към 3 mkleaf (num, val) конструиран връх Vertexes за оператори се изпълняват като записи с няколко полета указател на оператор към операнд 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) Стойностите на атрибутите се съхраняват в специални полета в стека на анализатора и са свързани с граматични символи (или състояния). Ако символът няма атрибут, стойността е недефиниран стек с място за един атрибут: състояние ZYX val Zz Yy Xx отгоре Внедряване - двойка полета 1. състояние съдържа указатели (индекси) към LR (1) таблица за разбор - Граматичният символ е в състояние по подразбиране, не е необходимо да го запомним - За простота посочваме символа вместо съответното състояние 2. val съдържа стойности на атрибути - val [i] = стойност на атрибута за символа в състояние [i] Стойностите на синтезираните атрибути винаги се изчисляват преди намаляването от атрибутите, съхранявани в стека (= символни атрибути от дясната страна на правилото)
16 Определение на S-атрибут Изпълнение за парсиране отдолу нагоре (2) Пример: A XYZ, Aa = f (Xx, Yy, Zz) състояние val състояние val Z Zz отгоре Y Yy X Xx изчисление Aa намаление A -> XYZ A Aa отгоре - Zz: = val [отгоре] - Yy: = val [отгоре 1] - Xx: = val [отгоре 2] - отгоре: = отгоре 2 - val [отгоре]: = Aa
17 Граматично правило Дефиниция на S-атрибут Изпълнение за синтактичен анализ отдолу нагоре (3) LE кодов фрагмент n печат (val [отгоре]) EE 1 + T val [ntop]: = val [отгоре 2] + val [отгоре] 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) край; оценяване на синтезирани атрибути на връх n край Естествен начин за извеждане на дървото за деривация Прилагане на дефиниция на L-атрибут при синтактичен анализ 1 Анализ отгоре надолу Всички SRD на базата на LL (1) граматики 2 Синтактичен анализ отдолу нагоре Всички SRD на база LL (1) граматики, голяма част SRD въз основа на LR (1) граматики
20 Схеми за превод Друг начин за определяне на синтаксичен превод По-специфичен от SRD Също така указва реда, в който се оценяват атрибутите Семантичните действия се затварят в <> и се вмъкват между десните символи на правилата Схема за превод на правила, която превежда инфикса за добавяне и изваждане изрази към еквивалентни изрази на ETR addfix 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 има локална променлива за всеки атрибут на всеки символ, който се среща в правилото за А. 2 Кодът за нетерминал А решава кое правило да се приложи според текущия входен символ. 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 е извикване на функция за мрежата. Б. (iii) За действието копирайте кода директно в синтактичния анализатор, като замените всяка препратка към атрибут със свързана променлива.
26 Превод, управляван от синтаксис при синтактичен анализ Резюме 1 Внедряване на дефиниции на S-атрибут Имахме алгоритъм за синтактичен анализ отдолу нагоре. Те могат да бъдат внедрени и при синтактичен анализ отдолу - Премахване на лявата рекурсия от схемата за превод и изграждане на предсказващ компилатор 2 Внедряване на дефинициите на L-атрибут отгоре-надолу Алгоритъм за синтактичен анализ Може да се приложи и за парсиране отдолу-нагоре - Разширение на алгоритъма за обработка на дефиниции на S-атрибут И в двата случая наборът от CF граматики, на които се основава SRP, е ограничен - Отдолу-нагоре компилаторът е по-силен