Fordítóprogramok. (Fordítóprogramok felépítése, az egyes komponensek feladata. A lexikáliselemző működése, implementációja. Szintaktikus elemző algoritmusok csoportosítása, összehasonlítása; létrehozásuk és működésük vázlatos ismertetése. Az ATG-k szerepe és alapfogalmai. Kódgenerálás assemblyben alapvető imperatív vezérlési szerkezetekehez.) Csörnyei Z. könyve alapján
Fordítóprogramok felépítése, az egyes programok feladata A következő jelölésmódot használjuk: program(bemenet)(kimenet) A fordítóprogram struktúrája: compiler(forrásnyelvű program)(tárgyprogram, lista) • input-handler(forrásnyelvű program)(karaktersorozat) : első lépés egy olyan program végrehajtása, amelyik a forrásnyelvű programot a fordítás számára könnyen hozzáférhető karaktersorozattá alakítja. • output-handler(forrásnyelvű program, hibák)(lista) : forrásnyelvű sorokból egy listát készít, melyet a háttértárolón, egy fájlban, az oprendszertől függő formátumban helyezi el. • source-handler(forrásnyelvű program, hibák)(karaktersorozat, lista): mivel az input- és az output-handlernek is a bemenete a forrásnyelvű program, ezért ezt célszerű egy programba összefoglalni. • code-handler(tárgykód)(tárgyprogram) : a compiler által készített tárgykódot is háttértárolón, egy fájlban (pl.: relokálható bináris formátumban) kell elhelyezni. A code-handler ezt a műveletet végzi. Tehát a következő lesz a fordítóprogram struktúrája összefoglalva: source-handler(forrásnyelvű program, hibák)(karaktersorozat, lista) compiler(karaktersorozat)(tárgykód, hibák) code-handler(tárgykód)(tárgyprogram)
forrásnyelvű program
source-handler
lista
compiler
code-handler
tárgynyelvű program
A compiler felépítése A felbontás nem szekvenciát jelöl, hanem a fordítóprogramot 3 egymástól jól elkülöníthető funkcionális, működési egységre bontottuk fel.
A source-handler és a code-handler végzi el az összes perifériafüggő és az oprendszertől függő műveleteket, a compiler most már ténylegesen csak a fordítással foglalkozik. Az compilernek két nagy feladatot kell megoldania: 1. analizálni a bemeneten kapott karaktersorozatot : a forrásnyelvű program karaktersorozatát részekre bontja és ezt vizsgálja 2. szintetizálnia a tárgykódot : az egyes részeknek megfelelő tárgykódokból építi fel a program teljes tárgykódját Analízis feladatai: 1. lexikális elemző(karaktersorozat)(szimbólumsorozat, lexikális hibák) ◦ A karaktersorozatban meghatározza az egyes szimbolikus egységeket, a konstansokat, változókat, kulcsszavakat, operátorokat. ◦ Kiszűri a szóköz karaktereket, a forrásnyelvű programba írt kommenteket (ezekből tárgykód nem származik). ◦ Több sorba írt utasítás összeállítása (magasszintű nyelveknél) 2. szintaktikus elemző(szimbólumsorozat)(szintaktikusan elemzett program, szintaktikus hibák) ◦ program struktúrájának felismerése és ellenőrzése ◦ a szimbólimsorozatban az egyes szimbólumok a megfelelő helyen vannak-e, ◦ sorrendjük megfelel-e a prognyelv szabályainak, ◦ nem hiányzik-e vhonnan egy szimbólum 3. szemantikus elemző(szintaktikusan elemzett program)(analizált program, szemantikus hibák) ◦ pl.: megvizsgálja hogy egy adott műveletben megadott szimbóum deklarálva van-e, konstansnak van-e értéke, típusok azonosak-e. Szintézis feladatai: 1. kódgenerátor(analizált program)(tárgykód) ◦ Legtöbb fordítóprogram tárgykódként az adott szgép assembly nyelvű vagy gépi kódú programját állítja elő 2. kódoptimalizáló(tárgykód)(tárgykód) ◦ Egyszerű esetben: a tárgykódban lévő azonos programrészek felfedezése és egy alprogramba való helyezése, vagy hurkok ciklusváltozótól független részeinek megkeresését és hurkon kívül való elhelyezését jelenti. ◦ Bonyolultabb: gépfüggő kódoptimalizáló programok, amleyek pl.: optimális regiszterhasználatot biztosítanak. ANALÍZIS lexikális elemző
szintaktikus elemző
szemantikus elemző
SZINTÉZIS kódgeneráló
kódoptimalizáló
A lexikális elemző működése, implementációja A szimbolikus egységek precíz defje reguláris grammatikával, más néven Chomsky 3-as típusú grammatikával, reguláris kifejezésekkel vagy determinisztkus automatával adható meg. Lexikális elemző létrehozásának menete: 1. A szimbolikus egységek leírását a reguláris kifejezések nyelvén adjuk meg, és megkonstruáljuk az ekvivalens determinisztikus véges automatát, 2. elkészítjük a determinisztikus véges automata implementációját (könnyen implementálható a case utasítás használatával) Működésének alapelve, hogy egy szimbólumot mindig a lehető leghosszab karaktersorozatból kell felépíteni. Inputjában benne van az összes benne van az összes szóköz és tabulátor jel (korábban csak a kocsivissza, és soremelés karaktereket hagyta el a source-handler) → (tab|space)* kiszűrése, nem adja ezeket tovább. Egy szimbólumhoz egy előre megadott kódot rendel, és ez a kód kerül majd bele a lex. elemző outputjába. Tartalmazhat kiegészítő információkat is, pl.: konstans szimbólum típusa, értéke (erre az infokra pl. a szemantikus elemzőnek lesz szüksége). Az információk tárolására az elemzők egy szimbólumtáblát használnak, és a szimbólum kódja után egy pointert helyeznek el, ami a szimbólumhoz tartozó szimbólumtábla bejegyzésre mutat. Működése során fellépő speciális problémák: • Kulcsszavak: programozási nyelvben olyan azonosítók, melyeknek speciális célra fenntartott nevük, előre definiált jelentésük van. Eredeti jelentésüktől eltérő módon nem használhatóak. • Standard szavak: az előzőek ezekre is fennállnak, azzal a kivétellel hogy jelentésük a programban megváltoztathatóak. ◦ Felismerésük egyszerű, ha ezeket speciális karakterekkel írják, vagy speciális elő-és utókarakterekkel jelölik meg. ◦ Kezelésükre két módszer van: ▪ külön táblázatban tároljuk a kulcsszavakat ▪ minden kulcsszót reguláris kifejezéssel írunk le, és megadjuk reguláris kifejezésekhez tartozó automata implementációját • Az előreolvasás: ◦ a leghosszabb karaktersorozatból álló szimbólum felismerésére törekszik, a szimbólum jobb oldali végpontjának meghatározására gyakran egy vagy több karaktert előre kell olvasnia. Ezért a reguláris kifejezések leírásában bevezetnek a szimbólum jobb oldali végpontjának bevezetésére egy / jelet, melyet előreolvasási operátornak neveznek. pl.: DO / (betű|szjegy)* = (betű|szjegy)* • Direktívák ◦ a forrásnyelvekben a direktívák a fordítóprogram működésének vezérlésére szolgál ◦ a direktívákat és a a direktívák operandusaiban szereplő szimbólumokat is a lex. elemzőnek kell meghatároznia. ◦ A lex. elemzőnek már szintaktikus és szemantikus ellenőrzéseket is kell végeznie, és kódjellegű információt előállítania. pl.: ha a direktíva a feltételes fordítás if direktívája, fel kell ismernie a direktíva összes szimbólumát, majd kiértékelnie az elágazás feltételét, amely
•
ha false akkor nem szabad a sorokban szereplő szimbólumokat elemeznie addig, amíg egy endif vagy egy else direktívát nem talál. Hibakezelés ◦ Ha a lexikális elemző egy karaktersorozatnak nem tud egy szimbólumot sem megfeleltetni, akkor azt mondjuk, hogy a karaktersorozatban lexikális hiba van ◦ Leggyakoribb okai: ▪ illegális karakterek ▪ karakterek felcserélődése ▪ karakterek hiánya ◦ Nem célszerű hiba esetén az elemzést megszakítani, így vmilyen hibaelfedő algoritmusra van ilyenkor szükség, amely lehetőséget biztosít arra hogy az elemzés a lehető legkevesebb karakter kihagyásával folytatódjon ◦ Leggyakrabban előforduló hibák és lehetséges hibaelfedő módszereik ▪ Nem megengedett (illegális) karakter a karaktersorozatban: 2 megoldás lehetséges 1. nem foglalkoznak a beolvasott karakterrel, az elemzést a következő, még nem vizsgált karakterrel folytatják 2. tetszőleges karakterrel (ált. space) karakterrel helyettesítik ▪ Kulcsszavak írása történhet speciális karaktertípussal vagy speciális zárójelezéssel. Ekkor a kulcsszavak elemzésénél az illegális karakter miatti hibák kiküszöbölhetők. ▪ Hiányzó karaktereknek gyakran az a hatásuk, hogy a lexikális elemző nem tudja a szimbólumokat elkülöníteni egymástól. ▪ Számok formátumhibája ▪ Karakterstringek és kommentek terminátorainak hiányai vagy hibái. Ezek kezelésére különösen nagy gondot kell fordítani.
Szintaktikus elemző algoritmusok csoportosítása, összehasonlítása; létrehozásuk és működésük vázlatos ismertetése
Felülről-lefelé elemzések Def.: Ha A→α∈P, akkor az xAβ mondatforma legbaloldalibb helyettesítése xαβ, azaz xAβ ⇒ xαβ legbal
* levezetésben minden helyettesítés legbaloldalibb helyettesítés, akkor ezt a levezetést Def.: Ha az S⇒x legbalodalibb levezetésnek nevezzük. Teljes visszalépéses elemzés algoritmusa: c1,c2,...,cn az elemzendő szimbólumsorozat. Az elemzés állapotait az (s,i,α,β) négyesekkel írjuk le, ahol • s az állapot típusa ◦ q = normálállapot ◦ b = visszalépés ◦ t = az elemzés vége
• i az input szövegre mutató pointer • α – a vizsgált mondatforma elemzésének történetét tartalmazó verem tartalma • β – a vizsgált mondatformát tartalmazó verem tartalma Kezdőállapot: (q, 1, ε, S#) Állapotátmenetek: • szintaxisfa építése az első szabállyal: ha A1→γ1, akkor (q, i, α,Αβ)→(q, i, αA1, γ1b) • input szimbólum olvasása: ◦ ci = a akkor (q, i, α,aβ)→(q,i+1,αa,β) ◦ ci ≠ a akkor (q, i, α,aβ)→(b,i,α,aβ) • visszalépés az input szövegben: (b,i,αa,β)→(b,i-1,α,aβ) • következő alternatív helyettesítési szabály keresése: (b,i,αAj, γjb)→ ◦ ha i=1, A=S és az S-nek csak j helyettesítési szabálya van, akkor az algoritmus szintaktikus hiba detektálásával befejeződik: (b,1,αSj,γjβ)→(t,1,αSj,γjβ) ◦ ha van Aj+1→γj+1 szabály, akkor (b,i,αAj, γjβ)→(q,i,αAj+1,γj+1β) ◦ egyébként, azaz már felhasználtuk az A minden alternatíváját, (b,i,αAj, γjβ)→(b,i, α, Αβ) • sikeres befejezés (q,n+1,α,#)(t,n+1, α, ε) Korlátozott visszalépéses elemzés: * A teljes visszalépéses elemzés olyan módosítással, hogyha eljutottunk egy S⇒xAβ levezetéshez, és A→αk helyettesítés következik, amiből visszajutunk oda, ahol ezt a szabályt alkalmaztuk, akkor a teljes visszalépéses elemzés A→αk helyett a következő A→αk+1 szabályt alkalmazza, és az elemzés folyatódhat tovább. A korlátozott visszalépéses elemzés azonban ezt a A→αk+1-re való áttérést már nem hajtja végre, az elemzést szintaktikus hiba találásával befejezi. Az egyszerű LL(1) grammatika Def.: A G grammatikát egyszerű LL(1) grammatikának nevezzük, ha • ε-mentes • minden helyettesítési szabály jobb oldala terminális szimbólummal kezdődik, • alternatívák esetén a jopbb oldalak kezdő terminálisai páronként különbözőek, azaz A→a1α1 | a1α1 | … | akαk, ahol ai ≠ aj, ha i ≠ j Az elemző táblázat kitöltése: (bβ,i), ha X →β az i-edik helyettesítési szabály pop, ha X = b M[X,b] = accept, ha X = # és b=# error egyébként. Az elemzés állapotai (ay#, Ya#, v): (még nem elemzett szöveg, az elemzés mondatformájának még nem elemzett része, szabályok sorszáma) Kezdőállapot: (x#, S#, ε)
Az ε-mentes LL(1) grammatika Def.: A G ε-mentes grammatikát ε-mentes LL(1) grammatikának nevezzük, ha minden A nemterminális szimbólumra és k>1-re A→α1 |α2 | … | αk esetén FIRST(αi)∩FIRST(αj) = 0, ha 1≤ i < j ≤k * (FIRST(α) = { α |α ⇒aβ}) Az elemző táblázat kitöltése (hasonló az egyszerű LL(1)-hez): (β,i), ha X→β az i-edik helyettesítési szabály és b∈FIRST(β) pop, ha X = b M[X,b] = accept, ha X = # és b=# error egyébként. LL(k) grammatikák Def.: Legyen a FIRSTk(α) (k≥0) az α-ból levezethető szimbólumsorozatok k hosszúságú kezdő terminális sorozatainak halmaza, azaz * * és |x|
LL(1) elemzés táblázattal (β,i), M[X,b] =
pop, accept, error
ha X→β az i-edik helyettesítési szabály és b∈FIRST1(β) vagy (ε∈FIRST1(β) és b FOLLOW1(X)) ha X = b ha X = # és b=# egyébként.
A rekurzív leszállás módszere • accept: terminális szimbólumok vizsgálatára procedure accept(szimbólum) begin if aktuális_szimbólum = szimbólum then következő_szimbólum else error(...) end;
• A szimbólumhoz tartozó eljárás procedure A begin T(A) end;
T(A)-t az A-ra vonatkozó helyettesítési szabályok jobb oldalán álló szibólumok határozzák meg: A →a szabályhoz rendelt program legyen az accept(a) A →B szabályhoz rendeljük hozzá a B eljáráshívást A →X1X2...Xn tartozzon a következő blokk:
begin T(X_1) T(X_2) … T(X_n) end; • A→α1 |α2 | … | αk case aktuális_szimbólum of FIRST_1(alpha_1): T(alpha_1) FIRST_1(alpha_2): T(alpha_2) … FIRST_1(alpha_n): T(alpha_n) end; ha van e akkor az a sor FOLLOW_1(A) : skip
