v0.4 2003.11.10.
FORDÍTÓPROGRAMOK I. Előadás Műszaki informatika szakos hallgatók számára Veszprémi Egyetem Számítástudomány Alkalmazása Tanszék 2002.
v0.4 2003.11.10.
Ajánlott irodalom: Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman Compilers (Principles, Techniques, Rules) Addison – Wesley, 1988
2
v0.4 2003.11.10.
Fordítóprogram Forrásnyelv SOURCE LANGUAGE
A
fordító
FORDÍTÓ
Célnyelv TARGET LANGUAGE
Hibaüzenet ERROR MESSAGE
egy forrásnyelvről egy célnyelvre fordít közölve az esetleges hibákat
Az
informatikában gyakran programozási nyelvekre gondolunk
Forrásnyelvű program ( pl.: C ) Cél nyelvű program ( pl.: assembly, gépikód ) 3
v0.4 2003.11.10.
Azonban tetszőleges program be és kimenete is valamely nyelven meghatározott BEMENET
PROGRAM
KIMENET
Egy program bemeneteit jól, lehetőleg formálisan definiálni kell. Egy program kimenetének értelmezhetőnek kell lennie egy másik program, vagy egy felhasználó számára. A program műveleteket adatokon végez A bemenetek és az adatszerkezetek, illetve az adatszerkezetek és a kimenet közti leképezést a fordító végzi.
Tehát bárkinek, akinek nem csak egy modult, hanem teljes szoftvert kell készítenie, annak tudnia kell: a be- és kimenetet formálisan definiálni és a definiált nyelvhez fordítóprogramot készíteni.
4
v0.4 2003.11.10.
A
tárgy célja megmutatni:
hogyan lehet nyelveket definiálni, hogyan lehet nyelveket algoritmikusan „értelmezni”, mely nyelveket lehet könnyen értelmezni.
Példa:
Egy matematikai megoldó bemenete: Aritmetikai kifejezés: 2+1*6 Szöveges feladat: A csiga egy métert tesz meg óránkén egy függőleges falon felfelé. Két méterről indulva, milyen magasan lesz hat óra múlva?
Megjegyzés:
A nyelvek lehetnek:
Szövegesek (Pl.: XML)
Grafikusak (Pl.: UML)
Ebben a félévben szöveges nyelvekkel foglalkozunk, de a grafikus nyelveknek is van szöveges megfelelője. (Pl.: UML tárolása XML nyelven)
5
v0.4
2003.11.10.
Fordítóprogram felépítése FORRÁSNYELV
1. LEXIKAI ELEMZO
2. SZINTAKTIKAI ELEMZO
3. SZEMANTIKAI ELEMZO
SZIMÓLUMTÁBLA KEZELO
HIBAKEZELO 4. KÖZBÜLSO KÓD GENERÁLÓ
5. KÓD OPTIMALIZÁLÓ
6. KÓD GENERÁLÓ
CÉLNYELV
Megjegyzés:
Az 1-4 lépéseket vizsgáljuk szoftverfejlesztésben betöltött kiemelt szerepe alapján.
6
v0.4 2003.11.10.
1. Lexikai Elemzés A forrásnyelvű szöveget elejétől a végéig karakterenként beolvassuk, és olyan szakaszokra bontjuk (ún.: tokenekre), melyekben szereplő karaktereknek együtt van értelme. Példa: position := initial + rate * 60 Tokenekre bontva: 1. „position” azonosító 2. „ := ” értékadás szimbólum 3. „initial” azonosító 4. „ + ” összeadás jel 5. „rate” azonosító 6. „ * ” szorzás jel 7. „60” szám
Megjegyzés:
Lexikai elemzés során, a tokenek közötti elválasztó karaktereket elhagyjuk.
Természetes nyelvi analógia: a szöveget szavakra bontjuk.
7
v0.4 2003.11.10.
2. Szintaktikai Elemzés
Más néven hierarchikus elemzésnek vagy (parsing) parzolásnak nevezzük. Tokeneket szervez hierarchiába nyelvtani szabályok alapján. Példa: 1. 2. 3. 4.
Minden „azonosító” egy „kifejezés” Minden „szám” is egy „kifejezés” Ha exp1 és exp2 kifejezések, akkor exp1*exp2 is kifejezés Ha id „azonosító” és exp egy „kifejezés”, akkor id := exp egy „utasítás”
A szintaktikai elemzés eredménye a tokenek kapcsolatát leíró fa: szintaxis fa
8
v0.4 2003.11.10.
Szintaxis
fa: Utasítás ÁLLÍTÁS
Azonosító
position
:=
Kifejezés
Kifejezés
+
Kifejezés
Azonosító
Kifejezés
*
initial
Azonosító
rate
Kifejezés
Szám
60
Természetes
nyelvi analógia: a nyelvtani mondatrészek 9
v0.4 2003.11.10.
3. Szemantikai Elemzés
Ellenőrzi, hogy a formailag helyes szövegrészeknek van e értelme. Tipikus feladat a típusegyeztetés
4. Közbülső kód generálás
Olyan reprezentációját képezi a nyelvnek, amely könnyen felépíthető és belőle a kimenet könnyen generálható. Példa: egy dinamikusan tárolt fa :=
Id 1
+
*
Id 2
Id 3
Az 5. és 6. lépéseket nem tárgyaljuk
N U LL
60
10
v0.4 2003.11.10.
Szimbólumtábla kezelő
Egy
szöveg tartalmazhat azonosítókat
Például: egy azonosító hivatkozhat:
konstansra változóra függvényre
Egy
fordító alapvető feladata, hogy rögzítse a szövegben lévő azonosítókat, a hozzájuk tartozó adatokkal együtt.
Például: mi egy azonosító:
neve típusa érvényessége (a szövegen belül) hivatkozott információ helye a memóriában 11
v0.4 2003.11.10.
Megjegyzés
Ezen
adatokat a szimbólumtábla tárolja
A szemantikai elemzés során a szimbólumtáblából olvassuk az azonosítók típusát. Id
Név
1
position
2
initial
3
rate
Típus
Hibakezelő
A
fordítás minden lépése okozhat hibákat
Olyan fordító, amely megáll az első hibánál, kevésbé hasznos (minél több hibát írjon ki) 12
v0.4 2003.11.10.
FORDÍTÓPROGRAMOK II. Előadás Műszaki informatika szakos hallgatók számára Veszprémi Egyetem Számítástudomány Alkalmazása Tanszék 2002. 13
v0.4 2003.11.10.
Egyszerű egy lépésben fordító
Bevezető
gondolatok
Egy nyelvet az határoz meg, hogy:
hogyan néz ki : szintaxis
mi a jelentése : szemantikája A szintaxis meghatározásához bevezetjük a széles körben használt környezetfüggetlen nyelvtanokat. Egy nyelv jelentésének meghatározásához nem formalizált információkat is használnunk kell.
Például: nekünk kell eldöntenünk, hogy két szöveg ugyanazt jelenti-e. A környezetfüggetlen nyelvtanok segítenek a nyelv értelmezésében is. A nyelvtanorientált fordítási technikát szintaxis vezérelt ( syntax directed) fordításnak nevezzük. 14
v0.4 2003.11.10.
Példaként
felépítünk egy fordítót, ami infix formáról postfix formába alakít.
infix: operátorok az operanduszok között
Pl.: 9 - 5 + 2 postfix: operátorok az operanduszok után
Pl.: 9 5 - 2 +
Postfix
kiértékelés
berakjuk a verembe az operanduszokat ha egy operátor következik, akkor kivesszük a veremből az operanduszait, elvégezzük a műveletet és visszatesszük a verembe az eredményt. ha a postfix formában írt kifejezés végére értünk, akkor a veremben a végeredmény található.
Pl.:
5 9
„-” 4
2 4
„+” 6 15
v0.4 2003.11.10.
Első
lépésként olyan fordítót építünk, mely „+” és „-” jelekkel elválasztott számjegyekből álló kifejezést fordít, majd ezt bővítjük tovább.
Szintaxis vezérelt fordítás esetén a szintaktikai, szemantikai elemzés és a közbülső kód generálás egy lépésben történik. KARAKTER SOROZAT
LEXIKAI ELEMZŐ
TOKENEK
SZINTAXIS
SOROZAT
VEZÉRELT ÉRTELMEZÉS
KÖZBÜLSŐ REPREZENTÁCIÓ
16
v0.4 2003.11.10.
Szintaxis meghatározása
A környezetfüggetlen nyelvtan elemei: 1. A tokeneket tekintjük terminális szimbólumoknak (halmaz) 2. Nemterminális szimbólumok (halmaz) 3. Levezetési szabályaink (halmaz)
Egy szabály: nemterminális → terminálisok és nemterminálisok sorozata 4. Kiindulási szimbólum (ahonnan elkezdjük a levezetést)
Példa: + és – jelekből, illetve számjegyekből álló kifejezés: mint 9 - 5 + 2, 3 - 1, 7 1) List → List + digit 2) List → List – digit 3) List → digit 4) digit → 0|1|2|…|9 17
v0.4 2003.11.10.
Ha
szabályokkal definiálunk egy nyelvtant, akkor a kezdő vagy kiindulási szimbólumra vonatkozó szabályokat írjuk le először. (Az előző példában List a kezdő szimbólum)
A tokenek sorozata (string) nulla, vagy több tokent tartalmaz. Ha nullát, akkor üres sorozatnak nevezzük és „e”-vel jelöljük.
Egy nyelvtanból tokenek sorozatához juthatunk:
kezdőszimbólumból indulva a nemterminalisokat helyettesítve a nekik megfelelő szabályok jobb oldalain álló sorozatokkal míg csak terminálisokból, tehát tokenekből álló sorozathoz nem jutunk.
18
v0.4 2003.11.10.
Példa
A 3-mas szabály alapján 9 egy lista (list) mivel számjegy (digit) b) A 2-es szabály alapján 9 – 5 egy lista (list), mivel 9 egy lista és 5 egy számjegy c) Az 1-es szabály alapján 9 – 5 + 2 egy lista, mivel 9 – 5 egy lista és 2 egy számjegy
Ezt a levezetést a következő fa szemlélteti, melynek minden csúcspontjában a nyelv egy szimbóluma szerepel. Az ilyen fát, levezetési fának (parse tree) nevezzük. a)
list → list + digit list → list - digit
list
list → digit
digit
list
list
digit
list → digit
digit → 2
digit digit → 9
9
-
5
+
2
19
v0.4 2003.11.10.
Levezetési fák
Egy adott kornyezetfuggetlen nyelvtan eseten a levezetesi fakra a kovetkezo tulajdonsagok teljesulnek: 1. 2. 3. 4.
A gyökér címkéje a kiindulási szimbólum Egy levél címkéje egy token, vagy e Közbülső csúcs címkéje egy nemterminális Ha A egy közbülső csúcs címkéje, aminek n gyermeke van és X1,…Xn a gyermekeinek cimkje: A → X1X2…Xn egy levezetési szabály A → e esetén az A címkéjű csúcsnak csak egy gyereke van
Ha a leveleket balról jobbra összeolvassuk, megkapjuk a levezetett szót. Az az eljárás, mely során egy token sorozathoz meghatározzuk a levezetési fát az az elemzés vagy parzolás (parsing). 20
v0.4 2003.11.10.
Egyértelműség
Ha egy nyelvtan olyan, hogy valamely sorozat többféleképpen is levezethető, akkor a nyelvtan nem egyértelmű.
Más szavakkal, egy nyelvtan nem egyértelmű, ha van olyan sorozat, melynek több levezetési fája is van. Példa: S→S+S|S–S|0|1|2|…|9 S S S
S S
9
S
S
S
-
5
S
+
2
9
-
5
S +
2 21
v0.4 2003.11.10.
Nyelvtanok egyértelművé télele: Asszociativitás (9 - 5) + 2 ugyanaz-e mint 9 - (5 + 2) vagy 9 - 5 + 2 ? Mi a kiértékelés sorrendje? ⇒ Ilyenkor kell plusz információ, amit beviszünk a nyelvtanba.
Hagyományosan a „+” és a „-” műveletek illetve a „*” és „/” műveleteket balról jobbra végezzük, tehát bal asszociatívnak nevezzük őket, így a 9 - 5 + 2 azonos a (9 - 5) + 2 –vel.
Hagyományosan a programozási nyelvekben az értékadást jobbról balra hajtjuk végre, tehát jobb asszociatív. a = b = c azonos a = (b = c)
Példa:
left → digit | left + digit | left – digit right → letter | letter = right right
left left left - digit digit 9
5
letter
+
digit 2
a
=
right
letter = b
right letter c
22
v0.4 2003.11.10.
Nyelvtanok egyértelművé télele: Operátorok kiértékelési sorrendje (precedencia) 9 + 5 * 2 lehetséges kiértékelési sorrendjei: (9 + 5) * 2 illetve 9 + (5 * 2) Mivel mind a + és mind a * balasszociatív, ez a kérdés a külön-külön kiértékelési sorrendjük alapján nem oldható fel. Több operátor esetén a relatív precedenciákat is meg kell határozni. A különböző precedencia szintekhez külön nemterminálisokat vezetünk be.
Példa: expr → expr + term | expr – term | term term → term * factor | term / factor | factor factor → digit | (expr) 23
v0.4 2003.11.10.
Szintaxis vezérelt fordítás
Példa: infix → postfix átalakítás Egy E infix kifejezés postfix formára hozása Ha E egy változó vagy konstans, E postfix formája önmaga. Ha E egy E1 op E2 alakú kifejezés, ahol op egy tetszőleges operátor, akkor E postfix alakja E1’ E2’ op ahol E1’ és E2’ rendre E1 és E2 postfix alakja. Ha E egy (E1) alakú kifejezés, akkor E postfix alakja E1 postfix alakja. (tehát nincs szükség zárójelezésre) Példa: (9 – 5) + 2 postfix alakja 95 – 2 +
9 – (5 + 2) postfix alakja 952 + -
24
v0.4 2003.11.10.
Szintaxis vezérelt fordításhoz szintaxis vezérelt definíciókat használunk. Szintaxis vezérelt definíció esetén A bemenet szintaktikai szerkezetét egy környezetfüggetlen nyelvtan határozza meg. A szimbólumokhoz attribútumokat vagy tulajdonságokat rendelünk. A levezetési szabályokhoz szemantikai szabályokat rendelünk, amelyek megadják egy nyelvtani szabályban szereplő nemterminális szimbólumok attribútumának számítási módját.
Szintetizált attribútumról beszélünk, ha értékét a kiértékelési fában hozzá tartozó csúcs gyermekeinek attribútumából számítjuk. 25
v0.4 2003.11.10.
Példa:
infix → postfix átalakítás
levezetési szabályok
|
szemantikai szabályok konkatenáció
expr → expr1 + term
expr.t := expr1.t || term.t || ‘+’
expr → expr1 – term . . expr → term term → 0 term → 1 . . . term → 9
expr.t := expr1.t || term.t || ‘-’ attribútum
expr.t := term.t term.t := ‘0’ term.t := ‘1’ . . . term.t := ‘9’
26
v0.4 2003.11.10.
Szintetizált attribútumok kiszámítása levezetési fa alapján: 9–5+2 ez a kimenet
expr.t := ’95-2+’
term.t := ’2'
expr.t := ’95-’
term.t := ’5'
expr.t := ’9’
term.t := ’9’
-
5
+
2
Végeredményül a győkér szintetizált attribútumában megkapjuk a postfix formát. 27
v0.4 2003.11.10.
FORDÍTÓPROGRAMOK III. Előadás Műszaki informatika szakos hallgatók számára Veszprémi Egyetem Számítástudomány Alkalmazása Tanszék 2002. 28
v0.4 2003.11.10.
Szintetizált attribútumok kiértékelése A
levezetési fa minden olyan bejárása célravezető, ahol egy csúcs gyermekeit előbb értékeljük ki mint magát a csúcsot.
Ennek
egy könnyen megvalósítható módja a mélységi bejárás rekurzív eljárással, preorder bejárási sorrendben.
procedure visit (n : node) begin for each child m of n, from left to right do visit ( m ); evaluate semantic rules at node n end end 29
v0.4 2003.11.10.
Fordítási sémák A
továbbiakban eljárásszerűen adjuk meg a fordítás módját.
A
fordítási séma egy olyan környezetfüggetlen nyelvtan, ahol a szabályok jobb oldalába programrészleteket, úgynevezett szemantikai akciókat (semantic action) ágyazunk.
A
fordítási séma abban különbözik a szintaxis vezérelt definíciótól, hogy a szemantikai szabályok kiértékelési sorrendje egyértelműen meghatározott. 30
v0.4 2003.11.10.
A szemantikai akciókat a szabályon belül kapcsos zárójelbe tesszük. Pl.:
expr → expr + term expr → expr term expr → term term → 0 term → 1 . . . term → 9
{ print(‘+’) } { print(‘-’) } { print(‘0’) } { print(‘1’) } . . . { print(‘9’) }
A szintaxis vezérelt definíció alkalmazásával ellentétben nincs mindig szükség átmeneti tárolásra. 31
v0.4 2003.11.10.
Ha egy szabályban szemantikai akció szerepel, akkor a levezetési fában a szabály bal oldalán szereplő csúcshoz egy plusz gyermeket veszünk fel, szaggatott vonallal csatolva és a szemantikai akcióval címkézve.
Pl.: 9 – 5 + 2 → 95 – 2 + expr print (’+’) expr
term print (’-’)
expr
-
term
term 9 print (’9’)
5
print (’5’)
A bejárási sorrend kötött.
2
print (’2’) 32
v0.4 2003.11.10.
Levezetés (parzolás) Azt
az eljárást, amely során megadjuk, hogy egy kifejezés (tokenek sorozata) hogyan vezethető le nyelvtani szabályokkal, elemzésnek vagy parzolásnak hívjuk.
A
elemzés egyben a levezetési fa felépítését is jelenti.
Ezen
eljárások többsége két csoportra osztható:
top – down: gyökértő a levelek felé bottom – up: levelektől a gyökér felé
A
top – down módszerek általában könnyebben végrehajthatók.
A
bottom – up módszerek a nyelvek bővebb osztályának kezelésére alkalmasak. 33
v0.4
Top – Down elemzés
2003.11.10.
Visszalépéses algoritmussal (back - tracking) 1. Tekintsük a token sorozat bal oldalán álló első tokent és a nyelvtan kiindulási szimbólumára vonatkozó szabályokat. 2. Vegyünk egy olyan levezetési szabályt, mely jobb oldalának bal oldalán ez a token áll. 3. A kiválasztott szabályok alapján próbáljuk levezetni a következő tokent a) a terminálisokat egyeztetjük b) a nem terminálisokból levezetjük (2. lépés rekurzív hívása) 34
v0.4 2003.11.10.
Példa:
Pascal –hoz hasonló típusokat megadó nyelvtan type → simple | ↑ id | array [ simple ] of type simple → integer | char | num dotdot num
array [ num dotdot num ] of integer elemzése
35
v0.4 2003.11.10.
LÉPÉS 1,
ELEMZÉS
BEMENET
type
array [ num dotdot num] of integer
type
2.
array
[ simple ]
of
integer array [ num dotdot num] of integer
of
integer array [ num dotdot num] of integer
type
3.
array
[ simple ] type
3.1
array
[ simple ]
of
integer
array [ num dotdot num] of integer 36
v0.4 2003.11.10.
LÉPÉS
LEVEZETÉS
3.2 rekurzió: → 2. lépés
BEMENET
type array
[ simple ]
of
type
array [ num dotdot num] of integer
num dotdot num
type
3.1 array
[ simple ]
array [ num dotdot num] of integer of
type
num dotdot num
37
v0.4 2003.11.10.
LÉPÉS
LEVEZETÉS
BEMENET
visszalépés a rekurzióban
type
3.1 array
[ simple ]
array [ num dotdot num] of integer of
type
num dotdot num type
3.2 array
[ simple ]
array [ num dotdot num] of integer of
type
num dotdot num 38
v0.4 2003.11.10.
LÉPÉS
LEVEZETÉS
rekurzió → 2. lépés
BEMENET
type
array
[ simple ]
of
num dotdot num
type
array [ num dotdot num] of integer
simple
type
3.2
array
[ simple ]
of
num dotdot num
type
array [ num dotdot num] of integer
simple integer
39
v0.4 2003.11.10.
Ha a 3.1 vagy 3.2 nem sikerül, akkor visszatérünk a 2. lépéshez és újabb szabályt választunk, ha ilyen nincs, akkor visszalépünk a rekurzióban. Azt a speciális esetet, amikor nincs szükség visszalépésre, előrejelző elemzésnek (predictive parsing) hívjuk.
40
v0.4 2003.11.10.
Előrejelző levezetés (predictiv parsing)
rekurzív
eljárások egy halmaza dolgozza fel
a nyelvtan minden nemterminálisához egy-egy rekurzív eljárás tartozik Előrejelző levezetés esetén a következő illesztendő token (look ahead) alapján egyértelműen eldönthető, hogy mely szabályt kell alkalmazni, illetve mely eljárást kell meghívni. procedure match (t : token) begin if lookahead = t then lookahead := next token else error end 41
v0.4 2003.11.10.
procedure type begin if lookahead is in { integer, char, num } then simple else if lookahead = ‘’ then begin match (‘’); match (‘id’) end else if lookahead = array then begin match (‘array’) match (‘[’) simple match (‘]’) match (‘of’); type end else error end 42
v0.4 2003.11.10.
procedure simple begin if lookahead = ‘integer’ then match (‘integer’) else if lookahead = ‘char’ then match (‘char’) end else if lookahead = ‘num’ then begin match (‘num’) match (‘dotdot’) match (‘num’) end else error end
43
v0.4 2003.11.10.
Az előrejelző elemzés csak akkor műkodik, ha egyértelműen eldönthető, hogy a következő token mely szabály jobb oldalából vezethető le, másképp, mi lehet az első token ami egy szabály alkalmazása során generálódik. Egy α sorozatból levezethető első tokenek halmazát FIRST(α) jelöli. Pl.: type –ból levezethető szabályokról kell döntenünk type → simple
First ( simple ) = { integer, char, num }
| ↑id
First ( ↑id ) = { ↑ }
| array [simple] of type
First ( array…) = { array}
Visszalépés nélküli elemzés lehetséges, ha minden A nemterminalis és bármely két A → α és A → β szabály esetén FIRST(α) ∩ FIRST(β) = ∅ (diszjunkt) 44
v0.4 2003.11.10.
„e” szabályok kezelése
A nemterminális → e szabályokat akkor alkalmazzuk, ha a nemterminálisra a többi szabály nem alkalmazható (nem kell hibát jelezni, error helyett ezt alkalmazzuk)
A First halmazok meghatározása
Abban az esetben, ha a nyelvtan nem tartalmaz nemterminális → e alakú szabályokat, akkor egy A nemterminálishoz tartozó First(A) halmaz tartalma a az A bal oldalú szabályok jobb oldalának első helyén álló terminálisok halmaza, és az A bal oldalú szabályok jobb oldalának első helyén álló nemterminálisok FIRST halmazámak uniója.
Példa: A → B… A → C… A → a… A → b…
FIRST(A) = {a,b} ∪ FIRST(B) ∪ FIRST(C)
45
v0.4 2003.11.10.
Bal rekurzió mentesítés A → Aα | β… A → βR R → αR | c
átalakítható: (R egy új nemterminális)
ez azért fontos, mert: Bal
rekurzív nyelvtanok esetén a Top - Down elemzés végtelen ciklusba eshet, mert úgy alkalmazunk szabályokat, hogy az elemzendő sorozat nem fogy.
Az
elemző levezető algoritmus végességét garantálja, ha a véges bemenetről a terminálisok fogynak egy szabály alkalmazásával. 46
v0.4 2003.11.10.
FORDÍTÓPROGRAMOK IV. Előadás Műszaki informatika szakos hallgatók számára Veszprémi Egyetem Számítástudomány Alkalmazása Tanszék 2002. 47
v0.4 2003.11.10.
Példa:
Fordítási séma római → arab
N → A1B0C0D0 | B1C0D0 | C1D0 | D1 A1 → M A1 → MM A1 → MMM B1 → C B1 → CC … B1 → CM B0 → B1 B0 → e
{ print (‘1’) } { print (‘2’) } { print (‘3’) } { print (‘1’) } { print (‘2’) }
D1 → I D1 → I … D1 → IX B0 → B1 D0 → e
{ print (‘1’) } { print (‘2’) }
{ print (‘9’) }
C1 → X C1 → XX … C1 → XC C0 → C1 C0 → e
{ print (‘1’) } { print (‘2’) } { print (‘9’) } { print (‘0’) }
{ print (‘0’) }
{ print (‘9’) } { print (‘0’) } 48
v0.4 2003.11.10.
Példa:
Fordítási séma arab → római
N → A1B0C0D0 | B1C0D0 | C1D0 | D1 A1 → 1 A1 → 2 A1 → 3 B1 → 1 B1 → 2 … B1 → 9 B0 → B1 B0 → 0
{ print (‘M’) } { print (‘MM’) } { print (‘MMM’) } { print (‘C’) } { print (‘CC’) } { print (‘CM’) }
C1 → 1 { print (‘X’) } C1 → 2 { print (‘XX’) } … C1 → 9 { print (‘XC’) } C0 → C 1 C0 → 0 D1 → 1 { print (‘I’) } D1 → 2 { print (‘II’) } … D1 → 9 { print (‘IX’) } D0 → D1 D0 → 0
49
v0.4 2003.11.10.
Példa: szintaxis vezérelt definíció (arab számok) expr expr term1
→ term1 → expr1 term0 →1 →2
expr.t = term1.t expr.t = expr1.t * 10 + term0.t term1.t = 1 =2
→9 → term1 →0
=9 term0.t = term1.t term0.t = 0
... term0 term0
levezetés 360-ra:
expr = 36 * 10 + 0 = 360 expr.t=3*10+6 expr.t = 3
term0.t = 6
term1.t = 3
term1.t = 6
3
6
term0.t = 0 0
50
v0.4
Emlékezető A lexikai elemző feladata karakterek sorozatából tokenek sorozatát létrehozni.
A szintaktikai elemző tőle kéri a tokeneket
2003.11.10.
TOKEN FORRÁS SZÖVEG
LEXIKAI ELEMZŐ
SZINTAKTIKAI ELEMZŐ ÚJABB TOKEN SZIMBÓLUM TÁBLA
A lexikai elemző tokeneket minták alapján azonosít. 51
v0.4
2003.11.10.
Alapfogalmak
Token: szintaktikai és szemantikai szempontból azonosan kezelt fogalom, amit a nyelvtanban egy szimbólum jelöl.
Egy tokenhez tartozó mintázat: olyan karaktersorozatok, amik egyazon tokent eredményeznek.
Lexéma: egy minta konkrét előfordulása a szövegben
Például:
TOKEN OPERÁTOR
MINTÁZAT
LEXÉMA
+
3 + 2
-
Ha egy tokenhez több minta is tartozik, akkor a tokenhez attribútumokat rendelünk. 52
v0.4
2003.11.10.
Például: E = M (adott kifejezés) token attribútumai
EZEK ÉPÍTIK FEL A KIFEJEZÉST
Minták
Formális definíciója: Pl.: reguláris kifejezésekkel
Felismerése
Pl.: véges autómatával 53
v0.4 2003.11.10.
Előfeldolgozás
Ismeretlen
karaktersorozatról az feltételezzük, hogy új
azonosító.
Ha
a feldolgozás további része ezen feltételezés alapján nem lehetséges, akkor visszalépünk és próbáljuk a hibát megkeresni.
Egy karaktert törlünk Egy karaktert beszúrunk Két szomszédos karaktert felcserélünk Egy karaktert kicserélünk
Alapelv:
Azt a megoldást keressük, ami a legkevesebb módosítással vezet értelmezhető sorozathoz. Ekkor ezen módosítások száma a hibák száma 54
v0.4 2003.11.10.
Pufferelés (Buffering) Ha több karakternyi előre és visszalépésre van szükség, akkor annak érdekében, hogy a karaktereket ne kelljen odavissza mozgatni, puffereljük és indexeljük őket.
KARAKTEREK
LEXÉMA ELEJE
ÉPPEN VIZSGÁLT KARAKTER
55
v0.4 2003.11.10.
Minták megadása
Alapfogalmak
ábécé: szimbólumok (karakterek) véges halmaza
Karaktersorozat, vagy sztring (szó): szimbólumok véges sorozata az ábécéből
Konkatenáció: két szó W1 és W2 konkatenáltja W=W1W2 a két szó egymás után írva mint sorozat
Van olyan szó, ami egyetlen karaktert sem tartalmaz, ez az üres szó, amit e –vel jelölünk.
A nyelv szavak, vagy karaktersorozatok halmaza 56
v0.4 2003.11.10.
Műveletek nyelveken
Unió:
w ∈ L=L1∪ L2 pontosan akkor, ha w ∈ L1 vagy w ∈ L2
Konkatenáció:
w ∈ L1L2 pontosan akkor, ha w =w1w2 ahol w1 ∈ L1 és w2 ∈ L2
Kleene
lezárt: w ∈ L = L1* pontosan akkor, ha w = w1w2w3…wn, ahol wi ∈ Li és n ∈ N ( n = 0 értelmezése: e ∈ L1*) 57
v0.4 2003.11.10.
Reguláris kifejezés
Egy
ábécé minden eleme és „e” reguláris kifejezés. A kifejezés által definiált nyelvek: L(δ) = {δ} bármely δ ∈ ∑ ∪ {e}
Ha
r és s reguláris kifejezés, akkor r | s reguláris kifejezés és L(r | s) = L(r) ∪ L(s) r s reguláris kifejezés és L(r s) = L(r)L(s) r* reguláris kifejezés és L(r*) = L(r)* L((r)) = L(r) (extra zárójelezés megengedett) 58
v0.4
Reguláris definíció:
2003.11.10.
azon1 → reguláris kifejezés az ábécé felett azon2 → ... azonk → reguláris kifejezés az ábécé elemei és azon1, azon2, … azonk-1 azonosítók felett.
További jelölések:
Előfordulások számára (r)? L(r) ∪ {e} (r)+ L(r)L(r)*
Karakter osztályok [abc] L([abc]) = {a} ∪ {b} ∪ {c} ( [abc] = a | b | c ) [A-Z] L([A-Z]) = {A} ∪ {B} ∪ {C} ∪ … ∪ {Z} ( [A-Z] = A | B | C | … | Z )
59
v0.4 2003.11.10.
FORDÍTÓPROGRAMOK V. Előadás Műszaki informatika szakos hallgatók számára Veszprémi Egyetem Számítástudomány Alkalmazása Tanszék 2002. 60
v0.4 2003.11.10.
Szintaktikai elemző
A
szintaktikai elemző helye a fordítás folyamatában TOKENEK
FORRÀS SZÖVEG
SZINTAKTIKAI ELEMZÕ
LEXIKAI ELEMZÕ
LEVEZETÈSI FA
TOKEN KERESÈS
Nyelvek
Church tétel: általános nyelvtan által adott nyelvek és a Turing gép által elfogadott nyelvek ekvivalenciája. Cocke-Younger-Kamasi algoritmus általános nyelvtanok alapján képes nyelveket levezetni Minél szűkebb a nyelvi osztály annál hatékonyabb levezető algoritmusok tartoznak hozzá
61
v0.4 2003.11.10.
Hibakezelés
Alapvelvek:
A hiba mibenlétét tisztán és pontosan meg kell tudnunk fogalmazni
Gyorsan vissza kell tudni állítani a hibákat, hogy további hibákat detektálhassunk
A hiba kezelő ( és detektáló ) nem lassíthatja le túlságosan a hibátlan nyelvek fordítását Hiba visszaállítási stratégiák ( error recovery )
pánikszerű (panic mode) egy blokkot hagy figyelmen kívül pl.: egy sort, egy begin-end pár közötti részt a hiba környezetében
kifejezés szintű visszaállítás ( phrase level ) lokális javítások, ahol a levezető elakad pl.: vessző , pontosvessző csere, pontosvessző hozzáadása, pontosvessző figyelmen kívül hagyása 62
v0.4 2003.11.10.
hiba előrevetítés ( error production ) tipikus hibák ismeretében olyan nyelvtan készítése, ami hibás kifejezéseket is eredményez, és ilyet levezetve pontos hibaüzenetet ad
globális javítás ( global correction ) teljes szöveg legkevesebb javításával azt értelmessé tenni. Nagyon hasznos, de borzasztó költséges.
CFG
( ismétlés )
levezetés levezetési fa egyértelműség nyelvek maghatározása Kérdés: reguláris kifejezésből, hogy kapok CFG-t ? Válasz: reguláris kifej. → NFA → CFG ( reguláris nyelvtan ) Egy CFG reguláris pontosan akkor ha R ⊆ ( V \ ∑ ) x ∑* x ( ( V \ ∑ ) ∪ e ) 63
v0.4 2003.11.10.
Példa: ab (a ∪ b ) a*
a ab S
a Q
T b
Q → aT | bT T → aT | e S → abQ Balrekurzió eltüntetése: A → Aα1 | Aα2 | Aα3 | ... | Aαm | β1 | β2 | ... | βn helyett: A → β1A’| β2A’| ... | βnA’ A’ → α1A’| α2A’| ... | αmA’| e Balfaktorizálás: azonos előtagok eltüntetése A → αβ1 | αβ2 | ... | αβ1n | γ helyett A → αA’ | γ A’ → β1 | β2 | ... | βn 64
v0.4 2003.11.10.
Felülről
lefelé levezetés ( top-down derivation )
Mélységi bejárással megtehető ( rekurzívan ) Előrejelző levezetés
Balrekurzió eltüntetés
Balfaktorizálás szükséges hozzá
Egyértelműség Átvitel diagramok: minden nemterminálishoz
kezdő és végállapot
szabályok a kezdőből végállapotba elvezető utak éleken egy-egy szimbólummal
ha az élen terminális áll, akkor beolvassuk, ha nemterminális, akkor átugrunk annak kezdő állapotába
65
v0.4 2003.11.10.
Például:
E → T E’ E’ → +T E’ | e T
E:
E’
T
E’:
+
T
e
E’
+
E’: e
66
v0.4 2003.11.10.
Előrejelző levezetés feltétele: átviteli diagramok determinisztikus volta, azaz ne létezzen több átvitel egy állapotból ugyanarra a bemenetre
egyértelmű nyelvtant próbáljunk meghatározni
ha a nemdeterminizmus nem tüntethető el, akkor előrejelző levezetés nem Megvalósítás: verem automatával
Emlékeztető generál
elfogad
példa
reguláris nyelvek
reg. exp. reg. gram.
véges aut.
a*b*
CF nyelvek
CFG
verem aut.
anbn
Turing gép
anbmcndm
ált. nyelvtan általános nyelvek R ⊆ V*(V\∑)V*xV*
67
CFG → veremautomata
↓E
a↑a b↑b +↑+ ↑E↓T ↑E↓T+ ↑T↓a ↑T↓b
v0.4 2003.11.10.
Általában a verem automata nem determinisztikus így nem megvalósítható
Determinisztikus esetben rekurzió nélkül is megvalósítható: A levezetési táblázat megadja a bemenet alapján, hogy mely szabályt kell alkalmazni.
BEMENET VEREM
ELÕREJELZÕ LEVEZETÕ
KIMENET
LEVEZETÈSI TÀBLÀZAT 68
v0.4 2003.11.10.
Példa: E → TE’ E’ → +TE’ | e
T’ → FT’ F → id | ( E )
T’ → *FT’ | e
A levezetési táblázat: Bemeneti szimbólumok
Nem terminális
id
E
E → TE’
E’ T
*
(
T → FT’
$
E’ → e
E’ → e
T’ → e
T’ → e
T → FT’ T→e
F → id
)
E → TE’ E’ → TE’
T’ F
+
T’ → *FT’ F→(E)
69
v0.4 2003.11.10.
Ez alapján az id + id * id levezetése: verem
bemenet
kimenet
$E
id+id*id$
$E’T
id+id*id$
E → TE’
$E’T’E
id+id*id$
T → FT’
$E’T’id
id+id*id$
F→e
$E’T’
+id*id$
$E’
+id*id$
T’ → e
$E’T+
+id*id$
E’ → +TE’
$E’T
id*id$
…
…
…
70
v0.4 2003.11.10.
FORDÍTÓPROGRAMOK VI. Előadás Műszaki informatika szakos hallgatók számára Veszprémi Egyetem Számítástudomány Alkalmazása Tanszék 2002. 71
v0.4 2003.11.10.
A levezetési táblázat elkészítése
FIRST és FOLLOW segédfüggvények
FIRST 1. Ha x egy terminális, akkor FIRST (x) = {x} 2. Ha van x → e szabály, akkor e ∈ FIRST (x) 3. Ha x egy nemterminális és x → y1y2...yk egy szabály, akkor: a. Minden j ≤ k-ra, ha e ∈ FIRST (yi) minden i= 1, 2, ...j-1-re akkor FIRST (yj) \ {e} ⊆ FIRST (x) b. ha e ∈ FIRST (yi) minden i= 1, 2, ... k-ra akkor e ∈ FIRST (x) FOLLOW 1. Legyen $ ∈ FOLLOW (S), ahol S a kezdőszimbólum és $ a bemenetet lezáró szimbólum 72
v0.4 2003.11.10.
2. Ha létezik A → αBβ szabály, akkor legyen FIRST (β) \ {e} ⊆ FOLLOW (B) 3. Ha létezik A → αB vagy A → αBβ ahol e ∈ FIRST (β) akkor FOLLOW (A) ⊆ FOLLOW (B)
Algoritmus 1. A nyelvtan minden A → α szabályára hajtsuk végre 2-t és 3-at 2. Minden a ∈ FIRST (α) terminálisra, legyen (A → α) ∈ M (A, a) 3. Ha e ∈ FIRST (α) , akkor legyen (A → α) ∈ M (A, b) minden b ∈ FOLLOW (A) terminálisra vagy $-ra 4. Minden nem definiált mezőjébe M-nek írjunk hibajelzést
73
v0.4 2003.11.10.
LL (1) nyelvek
Ha
a nyelvtan nem egyértelmű vagy balrekurzív, akkor biztosan lesz legalább egy cellája a levezetési táblázatnak, ami egynél több szabályt tartalmaz.
Előrejelző levezetés csak akkor alkalmazható, ha minden cella legfeljebb egy szabályt tartalmaz.
Azokat a nyelveket, melyekre a levezetési táblázat minden cellája legfeljebb egy szabályt tartalmaz, LL (1) nyelveknek hívjuk.
L → balról olvasva L → a legbaloldalibb nem terminálist tekintve 1 → egy karakter előreolvasás alapján eldönthető egyértelműen, hogy melyik szabályt kell alkalmazni
74
v0.4 2003.11.10.
LL (1) nyelvek megkülönböztető tulajdonságai Ha A → α | β része a nyelvnek, akkor 1. α-ból és β-ból nem vezethető le ugyanolyan terminálissal kezdődő szó 2. α és β közül legfeljebb az egyikből vezethető le e 3. Ha β ⇒* e, akkor α-ból nem vezethető le olyan a terminálissal kezdődő szó, melyre a ∈ FOLLOW (A)
Bemutatott eszközök alkalmazása hiba visszaállításban
Pánikszerű:
„A” kifejtésénél olyan karakterre jutunk, amire nincs szabály a táblázatban, akkor a bemeneten az első a ∈ FOLLOW (A) karakterig olvasunk
ha a bemeneten lévő karakter b ∈ FIRST (B), akkor átugrunk a B nemterminálisra
75
v0.4 2003.11.10.
Kifejezés szintű hibakezelés:
A levezetési táblázat nemdefiniált celláiba a hibakezelő függvények címeit írjuk, amik elvégzik a karakterek lokális beillesztését vagy törlését
Feladat:
Készítsünk előrejelző levezetőt („parser”-t vagy más néven szintaktikai elemzőt ) a következő nyelvtanhoz bexpr → bexpr or bterm | bterm bterm → bterm and bfactor | bfactor bfactor → not bfactor | (bexpr) | true | false Mivel balrekurziót tartalmaz ezért előtte balrekurzió mentesíteni kell: bexpr → bterm bexpr’ bexpr’ → or bterm bexpr’ | e bterm → bfactor bterm’ bterm’ → and bfactor bterm’ | e bfactor → not bfactor | (bexpr) | true | false 76
v0.4 2003.11.10.
A FIRST halmazok
FIRST (bfactor) = { n, ( , t, f } FIRST (bterm’) = { e, a } FIRST (bterm) = FIRST (bfactor) = { n, ( , t, f } FIRST (bexpr’) = { o, e ) FIRST (bexpr) = FIRST (bterm) = { n, (, t, f }
A FOLLOW halmazok 1. { $ } ⊆ FOLLOW (bexpr) 2. ( ahol nem terminális van a szabály belsejében) FIRST ( ) ) = { ) } ⊆ FOLLOW (bexpr) FIRST (bterm’) \ { e } ⊆ FOLLOW (bfactor) FIRST (bexpr’) \ { e } ⊆ FOLLOW (bterm)
77
v0.4 2003.11.10.
3. e ∈ FIRST (bterm’) ebből következik, hogy FOLLOW (bterm’) ⊆ FOLLOW (bfactor) FOLLOW (bterm) ⊆ FOLLOW (bterm’) továbbá e ∈ FIRST (bterm’) miatt FOLLOW (bterm) ⊆ FOLLOW (bfactor) e ∈ FIRST (bexpr’) ⇒ FOLLOW (bexpr’) ⊆ FOLLOW (bterm) FOLLOW (bexpr) ⊆ FOLLOW (bexpr’) továbbá e ∈ FIRST (bexpr’) miatt FOLLOW (bexpr) ⊆ FOLLOW (bterm)
{$}
A fentiek alapján az alábbi gráf írható fel: FOLLOW(bexpr)
{)} {a}
FOLLOW(bfactor)
{ο}
FOLLOW(bterm)
FOLLOW(bexpr’) FOLLOW(bterm’)
78
v0.4 2003.11.10.
A
FOLLOW halmazok a gráfról leolvashatóak
A
FOLLOW (bexpr) = { ), $ } FOLLOW (bexpr’) = { ), $ } FOLLOW (bterm) = { ), $, o } FOLLOW (bterm’) = { ), $, o } FOLLOW (bfactor) = { ), $, o, a }
levezetési táblázat n
bexpr
(
t
f
)
$
bexpr’→e bterm→bfactor bterm’
bterm’ bfactor
o
bexpr→bterm bexpr’
bexpr’ bterm
a
expr’ → or bterm bexpr’
bterm’ → and bfactor bterm’
bterm’→e → not
→ (bex)
→ true
→ false
79
v0.4 2003.11.10.
A levezetési fa
bexpr bexpr'
bterm bfactor true
bterm' e
or bterm bexpr' bfactor bterm' e
( bexpr ) bterm
bexpr' e
bfactor bterm' true
e 80
v0.4 2003.11.10.
FORDÍTÓPROGRAMOK VII. Előadás Műszaki informatika szakos hallgatók számára Veszprémi Egyetem Számítástudomány Alkalmazása Tanszék 2002. 81
v0.4 2003.11.10.
Alulról felfelé parzolás (Bottom-up)
más
néven: eltol-redukál (shift reduce)
levezetők
építés a levéltől kezdve szabályokat visszafelé alkalmazva: szövegrész cseréje nem-terminálisra = redukció mígnem a kezdő szimbólumhoz jutunk
Példa
S → aABf A → Abc | b B→d Nyelvtan esetén:
abbcdf
aAbcdf
aAdf
aABf
S 82
v0.4 2003.11.10.
Handle
(fogódzó, kapaszkodó): az a mintázat amire visszafelé alkalmazunk egy szabályt
Példa
E→E+E E→E*E E→(E) E → id Nyelvtan esetén: Handle
Redukáló szabály
id1 + id2 * id3
id1
E → id
E + id2 * id3
id2
E → id
E + E * id3
id3
E → id
E+E*E
E*E
E→E*E
E+E
E+E
E→E+E
E
83
v0.4 2003.11.10.
Megvalósítás veremmel
Akciók 1. 2. 3. 4.
a bemenetet pakoljuk a verembe, amíg nem redukálható CFG: ha egy szó levezethető, akkor mindig a leginkább jobbra levő nemterminálist kifejtve is levezethető ( rightmost derivation ), így a handle mindig a verem tetején lesz eltolás (bemenet → verem) (shift) redukálás (szabály alkalmazása visszafelé) (reduce) elfogad (accept) hiba (error)
Dilemmák
eltol / redukál dilemma: eltol vagy redukál ? redukál / redukál dilemma: mely szabályt alkalmazzuk ?
84
v0.4 2003.11.10.
Példa
(megvalósítás veremmel) Verem
Bemenet
Akció
$
id1+ id2* id3 $
eltolás
$id1
+ id2* id3 $
redukálás E→id
$E
+ id2* id3 $
eltolás
$E+
id2* id3 $
eltolás
$E+id2
* id3 $
redukálás E→id
$E+E
* id3 $
eltolás
$E+E*
id3 $
eltolás
$E+E*id3
$
redukálás E→id
$E+E*E
$
redukálás E→E*E
$E+E
$
redukálás E→E+E
$E
$
elfogad
85
v0.4 2003.11.10.
A LR(k) nyelvi osztály L balról jobbra olvassuk a bemenetet R legjobboldalabbi nemterminális cseréjét (rightmost derivation) feltételezve k „k” karakter hosszúságban látjuk előre a bemenetet
LR
(0): semmit nem látunk csak shift-tel behozunk valamit a verembe a a … a $ BEMENET
LR levezető 1
2
n
VEREM sm xm sm1
s0
Kezelő program
akció
lépés
KIMENET
86
v0.4 2003.11.10.
A veremben Si egy állapot, ami korábban a verembe pakoltakról hordoz információt, meghatározása DFAval:
Konfiguráció: (s0 x1 s1 ... xm sm, ai ai+1 ... an $) („verem tartalma”, „be nem olvasott bemenet”) akciók: az LR levezetési táblázat alapján 1. Ha az akció [sm, ai] = eltol s, akkor a következő konfiguráció: (s0 x1 s1 ... xm sm ai s, ai+1 ai+2 ... an $) 2. Ha [sm, ai] = redukál A → B, |B| = r és s = lépés[sm-r, A] akkor a következő konfiguráció: (s0 x1 s1 ... xm-r sm-r A s, ai ai+1 ...an $) 3. Ha [sm, ai] = elfogad, akkor elfogad 4. Ha [sm, ai] = hiba, akkor hiba-visszaállító eljárás
87
v0.4 2003.11.10.
Levezető algoritmus
Bemenet:
Kimenet:
Módszer:
a bemeneti szimbólumsorozat = w LR levezetési táblázat (akciók + lépések) ha w ∈ L(G), akkor levezetési fa, különben hibakezelés - Egy s0 kezdő állapot van a verem alján és w$ a bemeneten induláskor - A levezető programot futtatjuk míg „elfogad” vagy „hiba” üzenetet nem ad.
Példa
1. 2. 3. 4. 5. 6.
A következő nyelvtanra: E → E +T E→T T→T*F T→F F → (E) F → id 88
v0.4 2003.11.10.
Állapot
táblázat
állapot 0
akciók id
+
*
s5
(
lépések )
$
s4
1
s6
2
r2
s7
r2
r2
3
r4
r4
r4
r4
4
s4 r6
T
F
1
2
3
8
2
3
9
3
elf.
s5
5
E
r6
r6
6
s5
s4
7
s5
s4
r6 10
8
s6
s11
9
r1
s7
r1
r1
10
r3
r3
r3
r3
11
r5
r5
r5
r5 89
v0.4 2003.11.10.
1. 2. 3. 4.
si eltolás és „i” állapot a verembe rj eltolás és „j”-edik szabály alkalmazásával elfogad ⇒ elfogad üres mező ⇒ hiba
SLR levezetési táblázat készítése SLR = ( Simple LR )
LR(0) tételek: szabályok és a jobb oldalon egy pont
A → • XYZ A → X • YZ A → XY • Z A → XYZ • Ha a pont előtti részből levezethető szimbólum sorozat van a veremben, akkor arra számítunk, hogy a pont utáni részből levezethető szimbólum sorozat van a bemeneten
90
v0.4 2003.11.10.
Lezárt (closure): Legyen I egy tételhalmaz: 1. Kezdetben I ⊆ lezárt (I) 2. Ha A → α • Bβ ∈ lezárt (I) és B → σ egy szabály, akkor B → •σ ∈ lezárt (I) 2-t addig alkalmazzuk, míg új tétel kerül a lezárt (I)-be
Példa
E’ → E E→E+T|T T→T*F|F F → (E) | id nyelvtanra nézve: Legyen I = {E’ → • E}, ekkor (closure) lezárt (I) = { E’ → • E, E → • E+T, E → • T, T → • T*F, T → • F, F → • (E), F → • id }
91
v0.4 2003.11.10.
Lépés
(goto):
lépés ( I, X ) olyan A → α X • β tételeket tartalmazó halmaz lezártja amelyekre A → α • X β ∈ I
LR(0)
tételek kanonikus kollekciója
procedure → procedure items( ‘G’ ) begin C:={ closure ( { s’→ • s } ) }; repeat for each set of items I in C and each grammar symbol X such that goto ( I, X ) is not empty and not in C do add goto ( I, X ) to C until no more items can be added to C end
92
v0.4 2003.11.10.
Példa
Nyelvtan: E’ → E E →E+T|T ... T →T*F|F F → (E) | id
I0: E’ → • E E →•E+T E →•T T →•F F → • (E) F → • id T → • T*F
I1: E’ → E • E→E•+T I2: E→T• T→T•*F
93
v0.4 2003.11.10.
I3: T→F•
I4: F→(•E) E→•E+T E→•T
I7: T → T* • F F→•(E) F → • id I8: F→(E•)
I5: F → id •
I9: E→E+T•
I6: E→E+•T T→•T*F T→•F
I10: T→T*F• I11: F→(E)•
94
v0.4 2003.11.10.
FORDÍTÓPROGRAMOK VIII. Előadás Műszaki informatika szakos hallgatók számára Veszprémi Egyetem Számítástudomány Alkalmazása Tanszék 2002. 95
v0.4 2003.11.10.
Tekintsük
a következő véges automatát:
állapotai a tételek (mely szabály alkalmazásában hányadik szimbólumnál tartunk) állapotátmenetek egy szimbólum olvasásával az állapot nem egyértelmű már kezdetben sem item 1 e
item 2
a a
e
...
analógiák: NFA → DFA átalakítás A DFA állapotai az NFA állapotainak halmazai
Az állapotok a tételek halmazai I0, I1
S’’ = E ( S’ )
I0 = closure({ S’→S })
δ(A,σ) = U E(p) minden (q,σ,p) ∈ ∆, q ∈ A esetén
I1 = goto( I1,σ )
96
v0.4 2003.11.10.
Példa:
(az előző példa folytatása)
I0 = closure ( { E’ → E } ) = { E’ → • E, E → • E + T, E → • T, T → • T * F, F → • ( E ), F → • id } ) goto ( I0 , E ) = closure ( { E’ → E •, E → E • + T } ) = { E’ → E •, E → E • + T } = I1 goto ( I0 , T ) = closure ( { E → T • , T → T • * F } ) = { E → T • , T → T • * F } = I2 goto ( I0 , F ) = closure ( { T → F • } ) = { T → F • } = I3 goto ( I0 , ( ) = closure ( { F → ( • E ) } ) = {F → ( • E ), E → • E + T, E → • T, T → • T * F, T → • F, F → • ( E ), F → • id } = I4 goto ( I0 , id ) = closure ( { T → id • } ) = { T → id • } = I5 goto ( I1 , + ) = closure ( { E → E + • T } ) = { E → E + • T, T → • T * F, T → • F, F → • ( E ), F → • id } = I6 goto ( I2 , * ) = closure ( {T → T * • F } ) = {T → T * • F , F → • ( E ), F → • id } = I7 97
v0.4 2003.11.10.
goto ( I4 , E ) = closure ( { F → ( E • ), E → E • + T } ) = { F → ( E • ), E → E • + T } = I8 +
I1
T
I6 + F
E I2
T
I0
I10
I7 (
T
F
*
(
*
I9
I3
(
F
( I4 id
id
E
I8
(
I11
+
I5 98
v0.4 2003.11.10.
SLR levezetési táblázat generálása 1. Legyen C = { I0, I1, … , In } LR(0) tételek halmazának kollekciója 2. Az i. állapot megfelel a Ii halmaznak. Az i. állapothoz tartozó levezetési akciók: a. Ha A → α • a β ∈ Ii és goto (Ii , a ) = Ij akkor akció [ i, a ] = ˝ eltol j ˝ b. Ha A → α • ∈ Ii , akkor akció [ i, a ] = ˝ redukál A → α ˝ minden a ∈ follow ( A ) esetén. ( A nem lehet s’ ) c. Ha s’ → s • ∈ Ii , akkor az akció [ i, $ ] = ˝ elfogad ˝ Megjegyzés: Ha az akció mátrix valamely mezőjére több szabályunk is van, akkor a nyelv nem SLR-beli.
3. Minden A nem terminálisra, ha goto ( Ii , A ) = Ij , akkor akció [ i, a ] = j 4. Azokhoz a mezőkhöz amiket az 1, 2, 3 lépések nem definiáltak hibaüzenetet rendelünk 5. A kezdő állapot az, amelyekhez tartozó halmaz a s’ → • s –et tartalmazza 99
v0.4 2003.11.10.
Példa
nyelvtan: E’ → E E→E+T|T T→T*F|F F → ( F ) | id first halmazok: first ( + ) = { + } first ( * ) = { * } first ( ( ) = { ( } first ( ) ) = { ) } first ( E’ ) = first ( E ) first ( E’ ) = first ( T ) first ( T ) = first ( F ) first ( F ) = { (, id }
(1) (2,3) (4,5) (6,7)
Megjegyzés: csak az érdekel, hogy az „e” ne legyen eleme egyetlen first halmaznak sem, tehát egyik nem terminális sem 100 eltüntethető.
v0.4 2003.11.10.
follow
halmazok:
$ ∈ follow ( E ) follow ( E’ ) ⊆ follow ( E ) + ∈ follow ( E ) follow ( E ) ⊆ follow ( T ) * ∈ follow ( E ) follow ( T ) ⊆ follow ( F ) ) ∈ follow ( E ) Ebből következik, hogy: follow ( E’ ) = { $ } follow ( E ) = { +, ), $ } follow ( T ) = { +, *, ), $ } follow ( F ) = { +, ), $ }
(1) (2) (2,3) (4) (4,5) (6)
101
v0.4 2003.11.10.
Akciók
és eltolások:
Például: I0 = { E’ → • E, E → • E + T, E → • T, T → • T * F, F → • ( E ), F → • id } ( 2.a lépés ) akció [ 0 , ( ] = eltol 4 akció [ 0 , id ] = eltol 5 Például: I1 = { E’ → E •, E → E • + T } ( 2.a lépés ) akció [ 1, + ] = eltol 6 ( 2.c lépés ) akció [ 1 , $ ] = elfogad
102
v0.4 2003.11.10.
Például: I2 = { E → T • , T → T • * F } ( 2.b lépés ) mivel follow ( E ) = { +, ), $ } ezért akció [ 2, $ ] = akció [ 2, + ] = akció [ 2, ) ] = = redukál E → T
103
v0.4 2003.11.10.
FORDÍTÓPROGRAMOK IX. Előadás Műszaki informatika szakos hallgatók számára Veszprémi Egyetem Számítástudomány Alkalmazása Tanszék 2002. 104
v0.4 2003.11.10.
Nem SLR nyelvek
Tekintsük
a következő nyelvtant
( L left value, R right value, *R value of R ) S→L=R S→R L → *R L → id R → id
Kanonikus
LR(0) tételek erre a nyelvtanra:
I0 = { S’ → • S, S → • R, L → • * R, L → • id, R → • id, S→•L=R} I1 = { S → S • } I2 = { S → L • = R, R → L • }
105
v0.4 2003.11.10.
Tekintsük
az I2 halmazt
S → L • = R ═► akció [ 2, = ] = eltol 6 mivel = ∈ follow ( R ) R → L • ═► akció [ 2, = ] = redukál R → L tehát egy s / r ( eltol / redukál ) konfliktus keletkezett, mivel a levezetési táblázat egyazon cellájába két értéket akartunk beírni. Mivel a nyelvtan egyértelmű, így arra következtetünk, hogy nem SLR-beli.
Kanonikus
LR levezetési táblázatok
SLR esetén A → α redukáló lépést alkalmazunk, ha i állapotban [ A → α • ] ∈ Ii és a ∈ follow ( A ) Előfordulhat, hogy i állapotban βα van a verem tetején úgy, hogy βA után nem következhet ‘a’ a szóban. Megoldás: további információt viszünk az állapotba: egyenként pontosan megadjuk, hogy mely bemeneti karakter esetén redukálható α az A-ra. 106
v0.4 2003.11.10.
LR(1) tételek
[ A → α • β, a ] ahol A → α β egy szabály és ‘a’ pedig egy terminális vagy $ Megjegyzés:
Az előreolvasás a [ A → α • β, a ] tételeket nem befolyásolja ha β ≠ e de Egy [ A → α • β, a ] LR(1) tétel egy γ előtagra érvényes ha R∗
S ⇒ δAw ⇒ σαβw G
ahol: 1. γ = δ α 2. ‘a’ az w első szimbóluma ( terminális ), vagy w = e és a = $
A lezárt újrafogalmazása: Ha egy [ A → α • Bβ, a ] tétel érvényes egy γ előtagra , akkor R∗
R
G
G
S ⇒ δAax ⇒ σαBβ ax ahol γ = δ α 107
v0.4 R∗
Tegyük fel hogy, a esetén
R∗
2003.11.10.
βax ⇒ by , ekkor minden B → η szabály G
S ⇒ σBby ⇒ σηby G
Tehát [ B → • η, b ] érvényes a δ előtagra. ‘b’ lehet az első terminális ami β-ból került levezetésre, vagy β-ból levezethető ea
R∗
βax ⇒ by levezetése során, ekkor b = a, másképpen b G
egy tetszőleges terminális a First ( βax )-ből. Mivel a terminális így First ( βax ) = First ( βa ). Az LR(1) tételek algoritmikus leszámolása: function closure ( I ) begin repeat for each item [ A → α • Bβ, a ] ∈ I each production β→ δ in G and each terminal b ∈ first ( βa ) 108
v0.4 2003.11.10.
such that [ B → • η, b ] ∉ I do add [ B → • σ, b ] to I until no more items can be added to I return I end function goto ( I, X ) begin Let J be the set of items [ A → αX • β, a ] such that [ A → αX • β, a ] ∈ I return closure ( J ) end procedure items ( G ) begin C:= { closure ( { [ s’→ • S, $ ] } ) } repeat for each set of items I in C and each granted symbol X
109
v0.4 2003.11.10.
such that goto ( X , I ) is not empty in C do add goto ( X, I ) to C until no more set of items can be added to C end
Példák
Tekintsük a { [ S’→ • S, $ ] } halmazt Kérdés: [ S’→ • S, $ ] hogyan írható [ A → α • Bβ, a ] alakba Válasz: A = S’ B=S a=$ α=e β=e A closure eljárás szerint [ B → • δ, b ] alakú tételeket generálunk minden B → δ szabályra és b ∈ first ( βa ) terminálisra Legyen a vizsgált nyelvtan: S’ → S S → CC C → cC | d ekkor [ S’→ • CC, $ ] kerül a lezártba
110
v0.4 2003.11.10.
Tekintsük a [ S’→ • CC, $ ] tételt: [ A → α • Bβ, a ] alakba írható, ha A = S , α = e, β = C, B = C, a = $ ekkor: first ( βa ) = first ( β$ ) = first ( C ) = { c, d } tehát: [ C → • cC, c ], [ C → • cC, d ], [ C → • d, c ], [ C → • d, d ] →s-el átmenve I1: I0: S’ → • S, $ S’ → S •, $ S → • CC, $ →c-vel átmenve I2: C → • CC, c / d S → C • C, $ C → • d, c / d C → • CC, $ C → • d, $ és így tovább…
111
v0.4 2003.11.10.
Kanonikus LR levezetési táblázat generálása 1. Készítsük el a G’ nyelvre az LR(1) tételek halmazainak kollekcióját 2. Az i állapota a Ii halmazt reprezentálja A levezetési akciókat a következő féle képen határozzuk meg: a. Ha [ A → α • aβ, b ] ∈ Ii és goto (Ii , a ) = Ij akkor akció [ i,a ] = eltol j ahol ‘a’ egy terminális b. Ha [ A → α •, a ] ∈ Ii , A ≠ S’ akkor az akció [ i,a ] = redukál A → α c. Ha [ S’→ S •, $ ] ∈ Ij akkor akció [ i,$ ] = elfogad
3. Ha goto ( Ii ,A ) = Ij akkor goto [ i, A ] = j 4. Minden nem definiált cellába írjunk hibaüzenetet 5. Kezdő állapot az, melyhez tartozó Ii halmaz elem az [ S’→ • S, $ ] tétel
112
v0.4 2003.11.10.
FORDÍTÓPROGRAMOK X. Előadás Műszaki informatika szakos hallgatók számára Veszprémi Egyetem Számítástudomány Alkalmazása Tanszék 2002. 113
v0.4 2003.11.10.
Szintaxisvezérelt fordítás
Emlékezető: 1. Lexikai elemzés: szimbólumok azonosítása 2. Szintaktikai elemzés ( levezetés ): nyelvi szimbólumok szimbólumok nyelvtani kapcsolata 3. Szemantikai elemzés: szimbólumok kapcsolatainak jelentése
Szemantikai szabályok leírására
Szintaxis vezérelt definíciók Fordítási séma
Szintaxis vezérelt definíció A nyelvi szimbólumokhoz attribútumokat rendeltünk a. Szintetizált attribútumok • A levezetési fában a gyermekekhez rendelt attribútumokból számoljuk a szülő attribútumait • Szabályban: a bal oldalon álló szimbólum attribútuma a jobb oldalon álló szimbólumok attribútumainak függvénye
114
v0.4 2003.11.10.
b. Származtatott vagy örökölt attribútum • A fában egy csúcshoz tartozó szimbólum attribútumait a szülők és testvérek attribútumaiból számoljuk • Szabályban: a jobb oldalon álló szimbólumok attribútumait a bal és a jobb oldalon álló szimbólumok attribútumaiból számoljuk Szintetizált attribútum
Példa: Nyelvi szabályok
Szemantikai szabályok
L→En
print ( E.val )
E → E1 + T
E.val := E1.val + T.val
E→T
E.val := T.val
T → T1 * F
T.val := T1.val * F.val
T→F
T.val := F.val
F→(E)
F.val := E.val
F → digit
F.val := digit.lexval 115
v0.4 2003.11.10.
Ekkor a 3*5+4n levezetése
L print(19) E.val=15+4=19 E.val=15 +
T.val=4
T.val=3*5=15
F.val=4
T.val=3 * F.val=3
n
F.val=5 digit .lexval=4 digit .lexval=5
digit.lexval=3
Bejárási sorrend: alulról-felfelé 116
v0.4 2003.11.10.
Származtatott attribútumok
Gyakran átírható szintetizált attribútumokra, de néha származtatottal könnyebb megfogalmazni
Példa: ( típusdefiníció ) Nyelvi szabályok
Szemantikai szabályok
D→TL
L.in := T.type
T → int
T.type := integer
T → real
T.type := real
L → L1, id
L1.in := L.in addtype ( id.entry, L.in )
L → id
addtype ( id.entry, L.in )
117
v0.4 2003.11.10.
Példa: levezetés típusdefiníció alapján: real(id1,id2,id3)
D L.in=real
T. type=real real
L.in=real L.in=real
,
,
id3
id2
id2
Függőségi
gráf
Csúcsok: attribútumok Élek: ha ‘a’ értékéből kiszámoljuk ‘b’-t, akkor ‘b’ függ ‘a’-tól, attribútumok amit a → b jelöl. ettol függ
ez
118
v0.4 2003.11.10.
Topológiai rendezésnek nevezzük a csúcsok egy V1, V2, …, Vn sorrendjét, ha minden Vi → Vj élre i < j a rendezés szerint A topológikus rendezés ad egy megfelelő sorrendet az attribútumok kiértékelésére Példa: szintetizált attribútumok 1
3
2
4
5
6
7
8
Lehetséges kiértékelési sorrendek: 4, 5, 6, 2, 7, 8, 3, 1 4, 7, 6, 8, 3, 5, 2, 1 119
v0.4 2003.11.10.
Szintaxisvezérelt
definíciók alkalmazása:
szintaxisfa készítése A szintaxisfa egy dinamikus adatszerkezet, ami leírja a levezetés eredményét ( a levezetési fa tömörített formája ) Például: 3*5+4
A szintaxisfa felépítéséhez használt szintaxis vezérelt definíciók Például: Nyelvi szabályok
Szemantikai szabályok
E → E1 + T
E.nptr := mknode (‘+’, E1.nptr, T.nptr)
E → E1 - T
E.nptr := mknode (‘-’, E1.nptr, T.nptr)
E→T
E.nptr := T.nptr
T→(E)
T.nptr := E.nptr
T → id
T.nptr := mkleaf (id, id.entry)
T → num
T.nptr := mkleaf (num, num.val)
120
v0.4 2003.11.10.
Példa: „ a-4+c ”-hez tartozó szintaxisfa: +
-
id
id
num
C címére mutató mutató
to entry for a
A szintetizált attribútumok kiszámítása a levezető ( parser ) vermének alkalmazásával
Mivel a szintetizált attribútumokat alulról-felfelé számoljuk így alulról-felfelé ( bottom-up ) levezető kell Például: LR levezető
Amikor szabályt alkalmazunk visszafelé, akkor a szintetizált attribútumokat is kiszámoljuk 121
v0.4 2003.11.10.
Például: Nyelvi szabályok
Szemantikai szabályok
L→En
print ( val[ top ] )
L → E1 + T
val[ ntop ] := val[ top-2 ] + val[ top ]
E→T T → T1 * F
val[ ntop ] := val[ top-2 ] * val[ top ]
T→F F→(E)
val[ ntop ] := val[ top-1 ]
F → digit
Ha egy olyan szabályt redukálunk amelynek jobb oldalán r szimbólum van akkor: ntop := top – r +1
122
v0.4 2003.11.10.
L-attribútumú definíció Ha egy A → X1X2…Xn esetén az Xj attribútuma ( 1 ≤ j ≤ n ) csak a következőktől függ:
Az X1X2…Xj-1 szimbólumok attribútumaitól és
„A”-nak a származtatott attribútomaitól
LL levezetőkkel ( pl: perdiktív parser ) és a levezetési fa mélységi bejárásával számolható
Fordítási
sémák ( emlékeztető )
A szabályok jobb oldalába { } közzé tett szemantikai akciókat ágyazunk A szemantikai akciók végrehajtása a levezetési fa bejárásának megfelelően Példa: infix → postfix átalakítás E→E+T E→E-T E→T E→0 : E→9
{ print ( ‘+’ ) } { print ( ‘-’ ) } { print ( ‘0’ ) } : { print ( ‘9’ ) } 123
v0.4 2003.11.10.
E
A „ 9-5+2 ” levezetési fája
{print (’9’)}
E
E -
Felülről
T 5
T 9
+
{print (’+’)}
T 2
{print (’2’)}
{print (’5’)}
{print (’9’)}
lefelé fordítás ( top-down translation ) A.a=g(g(f( X.x ), Y1.y ), Y2.y ) A.a=g(f(X.x),Y1.y)
A.a=f(X.x) X
Y2
Y1 124
v0.4 2003.11.10.
Balrekurzív nyelvtanunk van Attribútumokat alulról-felfelé számoljuk
Ezzel szemben: Előrejelző levezetőt szeretnénk használni a.
Jobb rekurzív nyelvtant használunk
Az attribútumokat felülről lefelé számoljuk A
X
R.i = f(X.x) Y1
R.i = g(f(X.x), Y1.y) Y2
R.i = g(g(f(X.x), Y1.y, Y2.y) e 125
v0.4 2003.11.10.
szintaxis fa elkészítése
a. E → E1 + T { E.nptr := mknode ( ‘+’, E1.nptr, T.nptr ) } E → E1 – T { E.nptr := mknode ( ‘–’, E1.nptr, T.nptr ) } E → T { E.nptr := T.nptr } b. Balrekurzió mentesítés után: E → T { R.i := T.nptr } R { E.nptr := R.s } R → + T { R1.i := mknode ( ‘+’, R.i , T.nptr ) } R1 { R.s := R1.s } R → - T { R1.i := mknode ( ‘-’, R.i , T.nptr ) } R1 { R.s := R1.s } R→e T → ( E ) { T.nptr := E.nptr } T → id { T.nptr := mkleaf ( id, id.entry ) } T → num { T.nptr := mkleaf (num, num.val) }
126
v0.4 2003.11.10.
E T.nptr id
R.i -
R.i
T.nptr +
id
num
num
-
T.nptr
R.s
+
id
e
id
c
Előretekintő levezetővel megvalósítható Felépítjük a szintaxisfát ═► rögtön ki tudjuk értékelni 127
v0.4 2003.11.10.
Rekurzív
kiértékelés
Amikor az attribútumok nem értékelhetőek ki a levezetéssel párhuzamosan Függvényekkel járjuk be a levezetési fát egy csúcs gyermekeit nem feltétlenül balról-jobbra olvasva
128
v0.4 2003.11.10.
FORDÍTÓPROGRAMOK XI. Előadás Műszaki informatika szakos hallgatók számára Veszprémi Egyetem Számítástudomány Alkalmazása Tanszék 2002. 129
v0.4 2003.11.10.
Megjegyzés
( szóhasználat )
Azokat a szintaxis vezérelt definíciókat, melyek csak szintetizált attribútumokat tartalmaznak S attribútumú definícióknak nevezzük
Örökölt
( származtatott ) attribútumok kiértékelése alulról-felfelé
Emlékeztető: Az LR levezetők a nyelvek bővebb osztályát fogadják el, mint az LL levezetők A bemutatásra kerülő eljárás L-attribútumú definíciók kiértékelésére képes Mivel LR esetén csak a szabálynak megfelelő minta végére érve tudjuk pontosan mely szabályt kell levezetni visszafelé, így a szemantikai akcióknak a szabály végén kell lennie A beágyazott akciók eltüntethetőek, új nem terminális szimbólumok úgynevezett jelzők ( markerek ) bevezetésével
130
v0.4 2003.11.10.
Például: E → TR R → + T { print ( ‘ + ‘ ) } R | -T { print ( ‘ - ‘ ) } R | e T → num { print ( num.val( ) )} Átalakítható: E → TR R → + TMR | - TMR | e T → num { print ( num.val( ) ) } M → e { print ( ‘ + ‘ ) } M → e { print ( ‘ - ‘ ) } Származtatott attribútumok a veremben
Fordítási séma P → TL { L.in := T.type } T → int { T.type := integer } T → real {T.type := real } L → L1 id { L1.in := L.in; addtype ( id entry, L.in ) } L → id { addtype ( id entry, L.in ) } 131
v0.4 2003.11.10.
„ real p,q,r ” levezetése
D L.in
T.type real L.in L.in p
,
, q
r
Bemenet
Verem
real p,q,r
-
p,q,r
real
p,q,r
←T
,q,r
←Tp
,q,r
←TL
q,r
←TL,q
,r
←TL
,r
←TL,
r
←TL,r
Levezetési szabály T → real
L ← id
←TL
L ← L,id
←D
D → TL 132
v0.4 2003.11.10.
Amikor L-re redukálunk egy szabály jobb oldalát, akkor mindig T van a veremben alatta, így annak típusához közvetlenül hozzáférünk Szabály
Kódrészlet
D → TL’
T → int
val[ ntop ] := integer
T → real
val[ ntop ] := real
L → L, id
addtype ( val[ top ], val[ top – 3 ])
L → id
addtype ( val[ top ], val[ top – 1 ])
Ha a származtatott attribútumok forrása nem mindig ugyan olyan távolságra van, akkor segéd szimbólumokat vezetünk be
133
v0.4 2003.11.10.
Példa: Nyelvi szabályok
S→aAC
C.i := A.s
S→bABC
C.i := A.s
C→c
C.s := g( C.i )
Átalakítható a következő formában Nyelvi szabályok
Szemantikai szabályok
Szemantikai szabályok
S→aAC
C.i := A.s
S→bABMC
M.i := A.s; C.i := M.s
C→c
C.s := g( C.i )
M→e
M.s := M.i
Így a C.i számításához szükséges attribútum mindig ugyan olyan messze van a verem tetejétől 134
v0.4 2003.11.10.
Ugyanezt a technikát használjuk, ha a számításhoz szükséges érték nincs mindig a veremben Például: ha a következő szabályt hozzátesszük az előzőekhez: Nyelvi szabályok S→aAC
Szemantikai szabályok C.i := f ( A.s )
átalakítható: Nyelvi szabályok
Szemantikai szabályok
S→aANC
N.i := A.s; C.i := N.s
N→e
N.s := f ( N.i )
így közvetlenül c elé kerül A atribútuma
135
v0.4 2003.11.10.
Típus ellenőrzés ( Type checking )
Egyszerű:
Olyan nyelvekre használható, ahol az azonosítókat előre kell definiálni ( előbb definiálni mint használni )
Például: ( D deklaráció, E kifejezés, T típus, ↑ pointer )
D→D;E D → D ; D | id : T T → char | integer | array[ num ] of T | ↑ T E → literal | num | id | E mod E | E [ E ] | E ↑
Megjegyzés
array[256] of char, egy 256 hosszú tömb 1-től 256-ig indexelve ↑ integer, egészre mutató pointer
136
v0.4 2003.11.10.
Ilyen
nyelvekre a típus ellenőrzés fordítási sémával megadható
type attribútumot rendelünk a nem terminálisokhoz melynek lehetséges értékei típusok vagy type error Alapvető típusok Például: D → id : T
{ addtype ( id.entry, T.type ) }
T → char
{ F.type := char }
T → integer
{ T.type := integer }
T→↑T
{ T.type := pointer ( T1.type ) }
T → array[ num ] of T1
{ T.type := array ( 1…num.val,F1.type ) }
137
v0.4 2003.11.10.
Kifejezések
típusellenőrzése
E → literal
{ E.type := char }
T → num
{ E.type := integer }
E → id
{ E.type := lookup ( id.entry ) }
E → E1 mod E2
{ E.type := if ( E1.type = integer ) and ( E2.type = integer ) then integer else type error }
E → E1 [ E2 ]
{ E.type := if ( E2.type = integer ) and ( E1.type = array ( s,t ) ) then t else type error }
E → E1 ↑
{ E.type := if ( E1.type = pointer ( t ) ) then t else type error }
Lookup: szimbólumtáblában való keresés 138
v0.4 2003.11.10.
FORDÍTÓPROGRAMOK XII. Előadás Műszaki informatika szakos hallgatók számára Veszprémi Egyetem Számítástudomány Alkalmazása Tanszék 2002. 139
v0.4 2003.11.10.
Állítások
típus ellenőrzése
csak típus ellenőrzés az érték
vagy void = valós
vagy type_error = hibás például:
értékadás: S → id := E
{ S.type := if id.type = E.type then void else type_error }
feltételes kifejezés
S → if E then S1
{ S.type := if E.type = boolean then S1.type else type_error }
A szintetizált attribútumokban kiterjesztjük a hibajelzést a kezdő szimbólumig 140
v0.4 2003.11.10.
Megjegyzés: id.type-ot a szimbólum táblából kereshetjük ki: pontosabban lookup ( id.entry )
Ciklus
S → while E do S1
Szekvencia S → S1 ; S2
{ S.type := if E.type = boolean then S1.type else type_error } { S.type := if S1.type = void and S1.type = void then void else type_error }
Böhm – Jaccobini tétel: bármely algoritmus megvalósítható 3 vezérlés szerkezettel Szekvencia Szelekció Iteráció 141
v0.4 2003.11.10.
Függvények
típus ellenőrzése
E→E(E)
függvény
argumentum
típusa: S → t, ha S az argumentum típus t a visszatérési érték típusa
E → E1 ( E2 )
{ E.type := if E2.type = S and E2.type = S → t then t else type_error }
142
v0.4 2003.11.10.
Például: függvény:
valósból → egészbe leképző függvény Trunc.type = real → int idR.type = real idK.type = char
esetén: E → fv Trun ( idR )
{ E.type := int }
E → fv Trun ( idK )
{ E.type := type_error }
143
