1 ÖSSZEÁLLÍTÓK: Szintaxis által vezérelt fordítás: Jana Dvořáková
2 Mi a szintaxis-vezérelt fordítás? A teljes fordítót az elemzési folyamat vezérli. Szintaxis-vezérelt fordítás = az elemzés összekapcsolása a következő fordítási fázisokkal A következő szakasz szintaxis-vezérelt szintaxis-vezérelt fordítása A műveletek nyelvtani szabályokhoz vannak hozzárendelve -vezérelt definíció Absztrakt jelölés 2 Fordítási séma Hasonló a szintaxis-vezérelt definíciókhoz, de több megvalósítási részlet (műveletek sorrendje)
3 Műveletek végrehajtása 1 Egy elemzés során, egy átmenet, amelyet fordítókban használnak, a derivációs fa kifejezett felépítése nélkül Lehetséges speciális szintaxis-vezérelt definíciók esetében - pl. Az L-attribútum definíciók gyakorlatilag az összes szintaxis által vezérelt definíciót tartalmazzák, amelyek a származtatási fa kifejezett felépítése nélkül is megvalósíthatók.2 A explicit módon felépített derivációs fa bemeneti karakterláncának levezetési fától függőségi gráf művelet-értékelési sorrendjének bejárásával.
4 Szintaxis-vezérelt meghatározás (SRD) A szintaxis-vezérelt fordítás elvont specifikációja A bemeneti nyelv CF nyelvtanának kiterjesztésével jön létre 1 attribútum A nyelvtani szimbólumokhoz rendelt attribútumok Xx = az X szimbólum x attribútuma Nem adnak további információkat a adott szimbólum helyet a memóriában. 2 Szemantikai szabályok A nyelvtani szabályokhoz rendelt Bb: = f (C 1.c 1. C kc k) Egy nyelvtani szabályon belüli szimbólumattribútumok kiszámítására szolgálhat mellékhatású függvényekkel (pl. Kimeneti érték, globális változó értéke) SRD mellékhatásfüggvények nélkül = attribútum nyelvtan
5 Csúcs a levezetési fában = rekord mezőkkel nyelvtani szimbólum attribútum 1 attribútum 2 attribútumok A nyelvtani szimbólum a rekord első mezejében található, és egy zászló az attribútumban Az attribútumok más mezőkben vannak tárolva Attribútumtípusok 1 Szintetizált attribútumok Az értékek kiszámított használt 2 Örökölt attribútumok Az értékeket a szülők és testvérek attribútumainak értékei alapján számítják ki. Alkalmas a struktúrák függőségének kifejezésére attól a helyzettől, amelyben találhatók Ha Bb: = f (C 1.c 1. C kc k) azt mondjuk, hogy Bb C 1.c 1. függ. C kc k A kiszámított attribútumértékű derivációs fát annotált derivációs fának hívjuk, a termináloknak csak szintetizált attribútumai vannak, és nem. a nyelvtani szimbólumnak csak örökletes tulajdonságai vannak
6 Szintaxis-vezérelt meghatározás 1. példa - számológép Nyelvtani szabály Szemantikai szabály LE n nyomtatási (e.val) függvény mellékhatással 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 digit F.val: = digit.lexval attribútum értéke elküldött lexikális elemző Az X.val az X szintetizált attribútuma, egész SRD értékkel, csak a szintetizált attribútumokkal, S-attribútum definíciónak hívják, és mindig értékelhető a derivációs fán alulról felfelé történő áttéréssel
7 Szintaxis-vezérelt meghatározás 2. példa - deklarációk Nyelvtani szabály D T L; T int T valós LL 1, id L id Szemantikus szabály L.in: = T.type T.type: = egész T.type: = valós L 1.in: = L.in addtype (id.entry, L.in ) addtype (id.entry, L.in) Az L.in egy öröklődő tulajdonság. A T.type egy szintetizált attribútum Nem értékelhető egyszerűen S-attribútum definícióként
8 Megjeleníti az attribútumok közötti függőségeket Függőségi gráf Orientált grafikon D = (V, E) V - csúcsok halmaza, nyelvtani szimbólumok attribútumai E - élek halmaza, Xx Yy E, ha Yy X-től függ minden levezetési fa n csúcsánál minden egyes attribútumhoz és szimbólumhoz a vn nyelvtanhoz hozzon létre egy csúcsot a; a levezetési fa minden csúcsához minden egyes szemantikai szabályhoz: b: = f (c 1. ck), amely a vn és az i szabályhoz társul: = 1-től k-ig zci él hozzáadásához b topológiai osztályozás D Csúcsok elrendezése m 1 . mk, amelyik érvényes: Ha van él mimj, akkor m j előtt megvan. Megkapjuk az attribútumértékelés érvényes sorrendjét (ha D-nek nincs ciklusa)
9 Tulajdonság-kiértékelési módszerek 1 Levezetési fa-módszerek A levezetési fát kifejezetten felépítjük, egy függőségi gráfot találunk, és az összeállítási időpontban megkapjuk az attribútum-értékelési sorrend topológiai sorrendjét. építési idő 3 "Hanyag" módszer * Az értékelés sorrendjét a szemantikai szabályoktól függetlenül határozzuk meg. Ha a fordítást az elemzés során hajtják végre, akkor a sorrendet az elemző módszer határozza meg a fordító összeállításakor.
10 Szintaktikus fa Egyszerűsített levezetési fa Az operátorok és a kulcsszavak belső csúcsok A láncszabályok által származtatott ágak lecsökkennek. Fordított program vagy annak részei ideiglenes ábrázolásaként használhatók. A szintaxis-vezérelt fordítás származási fán vagy szintaxisfán alapulhat. a fa csomópontjaihoz, és ez megjegyzéssel van ellátva. A szintaxisfa előnyei Az elemzésre alkalmas nyelvtan nem mindig jelenti az input programozási nyelv természetes hierarchikus felépítését. Az elemzési módszer korlátozza a levezetési fa csomópontjaihoz való hozzáférés sorrendjét, és
11 Funkciók a csúcsépítéshez: Szintaxisfa a kifejezésekhez 1 mknode (op, bal, jobb) 2 mkleaf (id, entry) Visszaad egy mutatót egy 3 mkleaf (num, val) felépített csúcsra. Az operátorok csúcspontjai több mezővel rendelkező rekordként kerülnek megvalósításra operátormutató operandusra 1 mutató operandóra 2 Pontok az azonosítókhoz és numerikus állandókhoz Az operátor csúcscímke Fordításkor még több mező van a rekordban az azonosítók száma 4 mutató attribútumának szimbólumtáblájához
12 Szintaxisfa a kifejezésekhez Szintaxis-vezérelt meghatározás Nyelvtanszabály EE 1 + TEE 1 TETTT 1 FT (E) T id T szám Szemantikai szabály 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) Az X.nptr az X szintetizált attribútuma, és mutatót tartalmaz a megfelelő csúcsra
13 Szintaktikus fa vs. DAG A közös részkifejezéseket csak egy részfa képviseli. Új csúcs hozzáadásakor ellenőrizzük, hogy nem létezik-e már azonos csúcs. Kifejezés: a + a (bc) + (bc) d * + * a * - d * da - bca - bcbc
14 SRD megvalósítása elemzéshez Nehéz lehet egy automatikus fordító elkészítése bármely SRD-hez Nagy osztályaink egyszerűek 1 S-attribútum definíciók Csak szintetizált attribútumokat tartalmaznak 2 L-attribútum definíciók Szintetizált és öröklött attribútumokat egyaránt tartalmaznak Bizonyos korlátok az öröklött attribútumok kiszámításához Magában foglalja az összes SRD-t, amelyeket explicit levezetési fa konstrukció nélkül hajtanak végre. S-attribútum definíciók L-attribútum definíciók. Mindkét osztály felülről lefelé és alulról felfelé értelmezhető Korlátozások a használt nyelvtanra
15 S-attribútum definíció Végrehajtás alulról felfelé történő elemzéshez (1) Az attribútumértékeket a parser verem speciális mezőiben tárolják, és nyelvtani szimbólumokkal (vagy állapotokkal) társítják. undefined Verem egy attribútum szóközével: állapot ZYX val Zz Yy Xx top Megvalósítás - mezőpár 1. Az állapot mutatókat (indexeket) tartalmaz az LR (1) elemző táblához - A nyelvtani szimbólum alapértelmezés szerint állapotban van, nem szükséges emlékezni rá - Az egyszerűség kedvéért a megfelelő állapot helyett a szimbólumot adjuk meg. a val attribútumértékeket tartalmaz - val [i] = a szimbólum attribútumértéke az [i] állapotban. A szintetizált attribútumok értékeit mindig kiszámoljuk a veremben tárolt attribútumok redukciója előtt (= szimbólumattribútumok a szabály jobb oldalán)
16 S-attribútum definíció Megvalósítás alulról felfelé történő elemzéshez (2) Példa: A XYZ, Aa = f (Xx, Yy, Zz) állapot val állapot val Z Zz top Yyy X Xx számítás Aa redukció A -> XYZ A Aa top - Zz: = val [top] - Yy: = val [top 1] - Xx: = val [top 2] - top: = top 2 - val [top]: = Aa
17 Nyelvtani szabály S-attribútum definíció Megvalósítás alulról felfelé történő elemzéshez (3) LE kódrészlet n nyomtatás (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 számjegy A kódtöredékek az LR elemző redukcióival társulnak. A szemantikai szabályoktól kapjuk őket helyettesítéssel attribútumok a mező mezőben lévő pozíciókkal Csak a redukció előtt hajtják végre. A top és ntop top változók a verem aktuális teteje, ntop a verem új teteje Redukciós eljárás az A β szabály szerint, ahol β = r 1 ntop van fent r A kódrészletet végrehajtják, és a 3-as felső csökkentés ntop-ra áll
18 L-attribútum definíció A szintaxis által vezérelt definíció akkor L-attribútum, ha bármely AX 1, X 2 szabály esetében X n úgy véli, hogy az X j jobb oldalán lévő szimbólum minden öröklött attribútuma csak a szimbólumok 1 attribútumától függ. X 1, X 2. X j 1, amelyek az A. szimbólum X és 2 örökletes attribútumaitól balra található szabályban vannak. SRD, amely nem L-attribútum Nyelvtani szabály: A LM A QR Szemantikai szabály: Li: = l (ai) Mi: = m (ls) As: = f (Ms) Ri: = r (ai) Qi: = q (rs) As: = f (Qs) Megjegyzés: Minden S-attribútum definíció egy L-attribútum nem felel meg a definíciónak
19 L-attribútum definíció Az attribútumok kiértékelése Az attribútumokat úgy lehet értékelni, hogy a fán mélységesen átmennek (első-első rendű) eljárás dfvisit (n: csomópont); minden étrendnél el kell kezdeni egy m csúcsot n zl ava, hogy elkezdje értékelni az m csúcs öröklött tulajdonságait; dfvisit (m) vége; az n csúcs szintetizált attribútumainak értékelése A levezetési fa természetes útja, nagy része SRD az LR (1) nyelvtanok alapján
20 Fordítási sémák A szintaxis-alapú fordítás megadásának egy másik módja Specifikusabb, mint az SRD Megadja az attribútumok kiértékelésének sorrendjét is. A szemantikai műveletek <> -be vannak foglalva, és beszúrva a szabályok jobb oldali szimbólumai közé. kifejezések egyenértékű ETR addfix kifejezésekhez TR 1 ε T num addop.lexeme lehet + vagy - Nyelvtan létrehozható a bal rekurzió eltávolításával a híres nyelvtanból kifejezésekhez
21 Megkötések a fordítási sémákhoz A művelet nem hivatkozhat nem kiszámolt attribútumra. S-attribútum-definíciók fordítási sémái Egyszerű megoldás - a műveletek a szabályok végén helyezkednek el. L-attribútum-definíciók fordítási sémái 1 A szimbólum öröklött attribútuma a jobb oldalon egy szabályt a bal oldali műveletben kell kiszámítani. 2 A művelet nem hivatkozhat a jobb oldali szimbólum szintetizált attribútumára. 3 A szabály bal oldalán található szintetizált nonterminális attribútum csak akkor számítható ki, ha az összes olyan attribútumot kiszámították, amelytől függ. A megfelelő művelet a kiszámításához általában a szabály jobb oldalán található. Példa "rossz" fordítási séma S A 1 A 2 A a
22 L-attribútum definíció Megvalósítás prediktív elemzésben A megvalósítás csak az L-1 (1) nyelvtanokon alapuló L-attribútum-definíciók (fordítási sémák *) esetében lehetséges, amelyek többek között nem tartalmazhatnak bal rekurziót Van egy módszer a bal rekurzió közvetlen eltávolítására a fordítási sémákból Az algoritmus kiterjesztése a bal rekurzió eltávolítására a CF nyelvtanból Alkalmazható szintetizált attribútumokkal rendelkező fordítási sémákra Ha már van LL (1) nyelvtanon alapuló fordítási séma, akkor van egy algoritmus egy prediktív szintaxis által vezérelt szerkesztésre fordítóprogram
23 A bal rekurzió eltávolítása a fordításból. bemeneti fordítási séma: A A 1 Y A X Miután eltávolítottuk a bal rekurziót a CF nyelvtanból, új nyelvtant kapunk: A X R R Y R ε A szemantikai műveletek átírása után megkapjuk a kapott fordítást. séma: A X R R Y R 1 R ε
25 Prediktív fordítói tervezés Bemenet. A prediktív elemzésre alkalmas nyelvtanon alapuló szintaxis-vezérelt fordítási séma. Kimenet. Kód a prediktív szintaxis-vezérelt fordítóhoz. 1 Minden nem terminális A számára hozzon létre egy olyan függvényt, amelynek formális paramétere van minden egyes örökölt A attribútumhoz, és visszaadja a szintetizált nem terminálok A értékeit. Az A függvénynek van egy helyi változója a szabályban előforduló minden szimbólum minden attribútumához esetén A. 2 A nem terminális A kódja dönti el, hogy melyik szabályt alkalmazza az aktuális bemeneti szimbólumnak megfelelően. 3 Az egyes szabályokhoz tartozó kód a következő műveleteket hajtja végre. (i) Az X szintetizált attribútummal rendelkező X token esetében tárolja az x értékét az X.x számára deklarált változóban. Ezután hívja meg a match (x) eljárást, és görgessen a bemenethez. (ii) Nem terminális B esetén hozzon létre egy c formájú hozzárendelést: = B (b 1, b 2. bk), ahol b 1, b 2. bk a nem terminális B, c öröklött attribútumai változói a szintetizált net attribútum változója. B és B a net függvényhívása. B. (iii) A művelethez másolja a kódot közvetlenül az elemzőbe, minden attribútum hivatkozást helyettesítve egy társított változóval.
26 Szintaxisvezérelt fordítás az elemzésben Összefoglalás 1 Az S-attribútum definíciók megvalósítása Alulról felfelé irányuló elemzési algoritmussal rendelkezünk. Felülről lefelé történő elemzésben is megvalósíthatók - Bal oldali rekurzió eltávolítása a fordítási sémából és egy prediktív fordító szerkesztése 2 Megvalósítás az L-attribútum definíciók felülről lefelé irányuló elemzési algoritmusa megvalósítható alulról felfelé történő elemzéshez - Algoritmus kiterjesztés az S-attribútum definíciók feldolgozásához Mindkét esetben korlátozott az SRP alapjául szolgáló CF nyelvtanok halmaza - Az alulról felfelé a fordító erősebb