Informatika szigorlat 17-es t´etel: Fel¨ ulr˝ol lefel´e elemz´esek
1.
Lexik´ alis elemz´ es
A lexik´alis elemz˝o alapvet˝o feladata az, hogy a forr´asnyelv˝ u program lexik´alis egys´egeit felismerje, azaz meghat´arozza a forr´asnyelv˝ u k´odban a szimb´olumok sz¨oveg´et ´es t´ıpus´at. A szimb´olikus egys´egek prec´ız defin´ıci´oja regul´aris kifejez´esekkel adhat´o meg. Emiatt v´alik k¨ ul¨on a szintaktikus elemez˝ot˝ol, hiszen az nem adhat´o a Chomsky 3-as nyelvoszt´allyal. Ezek k¨onnyen val´os´ıthat´oak meg v´eges determinisztikus automat´akkal. Az elemz˝o l´etrehoz´as´anak menete: 1. Meg kell konstru´alni a szimb´olikus egys´egek grammatik´aj´aval ekvivalens v´eges determinisztikus automat´at. 2. Ezt kell implement´alni. Ez egyszer˝ uen megval´os´ıthat´o a case utas´ıt´as haszn´alat´aval. A lexik´alis elemz˝o egy szimb´olumot a lehet˝o leghosszabbnak tekint. Mindegyik alternat´ıv utas´ıt´as addig dolgozza fel a karaktereket, am´ıg azok az ´eppen ´ep´ıt´es alatt ´all´o szimb´olum r´eszek´ent ´ertelmezhet˝ok. A lexik´alis elemz˝o feladatai k¨oz´e tartozik a whitespace karakterek (a sz´ok¨oz ´es a tab, a sorv´ege jeleket m´ar source-handler kisz˝ urte) elt´avol´ıt´asa is. Itt a speci´alis probl´em´ak k¨oz´e sorolhat´o a kulcsszavak ´es a standard szavak felismer´ese. Leggyakoribb megold´as az, ha egy k¨ ul¨on t´abl´azatban t´aroljuk ezeket. Amikor lexik´alis elemz˝o egy szimb´olum beolvas´asa v´eg´ere ´er, ellen˝orzi, hogy ez benne van-e a t´abl´azatban, ´es ha igen, akkor felismeri ezt, ha nincs benne, akkor hat´arozza meg, hogy milyen lexik´alis egys´eg. Ha a lexik´alis elemz˝o egy karaktersorozatnak nem tud egy szimb´olumot sem megfeleltetni, akkor azt mondjuk, hogy lexik´alis hiba van a karakter´ sorozatban. Altal´ aban k´et hibaelfed˝o algoritmus egyik´et haszn´alj´ak: vagy nem foglalkoznak a m´ar beolvasott karakterekkel, az elemz´est a k¨ovetkez˝o, m´eg nem vizsg´alt karakterrel folytatj´ak vagy egyszer˝ uen kihagyj´ak vagy egy tetsz˝oleges karakterrel, ´altal´aban sz´ok¨ozzel helyettes´ıtik az illeg´alis karaktert. Lexik´alis elemz˝o gener´ator a lex nev˝ u program, ez a regul´aris kifejez´esekb˝ol elk´esz´ıti a lexik´alis elemz˝o programot.
1
2.
LL elemz´ esek
A fel¨ ulr˝ol lefel´e elemz´esek u ´gy m˝ uk¨odnek, hogy a nyelvtan kezd˝oszimb´olum´ab´ol kiindulva legbaloldalibb helyettes´ıt´eseket alkalmazva pr´ob´al eljutni az elemezend˝o sz¨oveghez. Az LL elemz´esek ezen bel¨ ul visszal´ep´es n´elk¨ ul oldja meg a feladatot. Az LL(k) elemz´esek, amiatt, hogy ne kelljen visszal´ep´est v´egrehajtania, k szimb´olumot kell hogy el˝oreolvasson. Def.: A G grammatik´at egyszer˝ u LL(1) grammatik´anak nevezz¨ uk, ha ε mentes, ´es ha minden A nemtermin´alis szimb´olumra a helyettes´ıt´esi szab´alyok k¨ ul¨onb¨oz˝o termin´alis szimb´olummal kezd˝odnek, azaz k ≥ 1 -re A → a1 α1 | a2 α2 | . . . | ak αk , ahol ai 6= aj , ha i 6= j. Az elemz´es ´allapotait az (x, β, y) h´armassal jel¨olj¨ uk, ahol x a m´eg nem elemzett sz¨oveg, β egy vermet, y pedig egy list´at jelent. Az elemezend˝o sz¨oveg v´eg´et # jellel megjel¨olj¨ uk, ´es a helyettes´ıt´esi szab´alyokat a felsorol´asuk sorrendj´eben megsz´amozzuk. Az elemz´eshez egy verem haszn´alhat´o. A verem alj´at is megjel¨olj¨ uk a # jellel. Ebben a veremben lesz az aktu´alis mondatforma, a kezdeti tartalma legyen S (a nyelvtan kezd˝oszimb´oluma). A verem tetej´en l´ev˝o szimb´olumot fogjuk ¨osszehasonl´ıtani az input sz¨oveg k¨ovetkez˝o, m´eg nem elemzett szimb´olum´aval. Az alkalmazott szab´alyok sorsz´am´at mindig feljegyezz¨ uk az y list´aba. Ezzel lehet majd az elemz´es v´eg´en a szintaxisf´at fel´ep´ıteni. Az elemz´est egy t´abl´azat seg´ıts´eg´evel fogjuk elv´egezni. A t´abla sorai a verem tetej´en l´ev˝o szimb´olumot, az oszlopai a k¨ovetkez˝o elemezend˝o szimb´olumot jel¨olik. A t´abla elemei: pop accept M (X, a) = (aα, i) error
ha X = a ha X = # ´es a = # ha X → aα az i-dik helyettes´ıt´esi szab´aly egy´ebk´ent
Az elemz´es ´allapot´atmenetei: a kezd˝o´allapot legyen (x#, S#, ε), ´es az elemz´es sikeresen fejez˝odik be, ha az elemz˝o az (#, #, y) ´allapotba ker¨ ul. Ha nem elemzett sz¨oveg az, ´es a verem tetej´en az X ´all, akkor az ´allapot´atmenetek a k¨ovetkez˝ok: (z, α, y) ha M (X, a) = pop OK ha M (X, a) = accept (az, Xα, y) → (az, βα, yi) ha M (X, a) = (β, i) error ha M (X, a) = error 2
B˝ovebb nyelvoszt´alyra alkalmazhat´o az elemz´es, ha nem tessz¨ uk azt a kik¨ot´est, hogy k¨ ul¨onb¨oz˝o termin´alis jellel kezd˝odjenek a szab´alyok. F IRST (α) := {a |α → aβ} ∗
Def.: A G ε-mentes grammatik´at ε-mentes LL(1) grammatik´anak nevezz¨ uk, ha minden A nemtermin´alis szimb´olumra ´es k > 1-re: A → α1 |α2 | . . . |αk eset´en F IRST (αi ) ∩ F IRST (αj ) = ∅ Az elemz´es ugyan´ ugy m˝ uk¨odik mint az el˝oz˝o esetben, az ´allapotmenetek is megegyeznek, csak kis v´altoz´as ´erinti a t´abl´azat meghat´aroz´ast: pop accept M (X, a) = (α, i) error
ha X = a ha X = # ´es a = # ha X → α az i-dik helyettes´ıt´esi szab´aly ´es a ∈ F IRST (α) egy´ebk´ent
F IRSTk (α) := {x |α → x, ha |x| < k, α → xβ, ha |x| = k} ∗
∗
Def.: A G grammatika LL(k) grammatika (k ≥ 0), ha: S → wAβ → wα1 β → wx ∗ ∗ S → wAβ → wα2 β → wy ∗
∗
´es F IRSTk (x) = F IRSTk (y) eset´en α1 = α2 . Def.: A G nyelvtant er˝os LL(k) (k ≥ 0) grammatik´anak nevezz¨ uk, ha S → wAβ → wα1 β → wx ∗ ∗ S → vAϑ → vα2 ϑ → vy ∗
∗
´es F IRSTk (x) = F IRSTk (y) eset´en α1 = α2 . Ezekben az esetekben a mindig legkisebb ilyen k ´ert´eket ´ertj¨ uk ez alatt. A k = 1 esetben a k´et nyelvoszt´aly megegyezik. Ezekhez a nyelvekhez – a fentiekhez hasonl´oan – l´etezik egy t´abl´azatot haszn´al´o m´odszer. Def : F OLLOWk (β) = {x|S → αβγ ´es x ∈ F IRSTk (γ)} ∗ k = 1 esetben a t´abl´azat elemei a k¨ovetkez˝o m´odon hat´arozhat´ok meg: pop accept (α, i) M (X, a) = (α, i) error
ha X = a ha X = # ´es a = # ha X → α az i-dik helyettes´ıt´esi szab´aly ´es a ∈ F IRST (α) ha X → α az i-dik helyettes´ıt´esi szab´aly ´es a ∈ F OLLOW1 (X) egy´ebk´ent
Az elemz´es fenti eml´ıtett m´odon v´egezhez˝o. A probl´em´at ekkor az jelenti, hogy meg kell hat´arozni a F IRST1 (α) ´es a F OLLOW1 (A) halmazokat. Erre k´et m´odszer lehets´eges: 3
Az LL(1) grammatika szab´alyaib´ol k¨ozvetlen¨ ul kaphatunk egy elemz˝o programot, ha a rekurz´ıv lesz´all´as m´odszer´et haszn´aljuk. Ennek a l´enyege az, hogy a nyelvtan nemtermin´alis szimb´olumaihoz elj´ar´asokat rendelnek, ´es az elemz´es k¨ozben a rekurz´ıv proced´ urah´ıv´asokon kereszt¨ ul a programnyelv implement´aci´oja val´os´ıtja meg a veremkezel´est. procedure accept(szimbolum); begin if aktualis-szimbolum=szimbolum then kovetkezo-szimbolum else error(...) end; A grammatika minden nemtermin´alis szimb´olum´ahoz rendelj¨ unk hozz´a egy proced´ ur´at. Az A szimb´olumhoz tartoz´o proced´ ura a k¨ovetkez˝o: procedure A; begin T(A) end; ahol T(A) az A-ra vonatkoz´o helyettes´ıt´esi szab´alyok hat´arozz´ak meg: 1. Az A → a szab´alyhoz rendelt program legyen az accept(a). 2. Az A → B szab´alyhoz rendelj¨ uk hozz´a a B proced´ urah´ıv´ast. 3. Az A → X1 X2 . . . Xn szab´alyhoz tartozzon a k¨ovetkez˝o blokk: begin T(X1); T(X2); ... T(Xn) end; 4. Ha az A → X1 |X2 | . . . |Xn szab´aly ε-mentes, akkor T(A) legyen case aktualis-szimbolum of first(X1): T(X1); first(X2): T(X2); ... first(Xn): T(Xn); end; 4
5. Ha az el˝oz˝oh¨oz hozz´avessz¨ uk az ε-szab´alyt is, akkor a fenti el´agaz´as v´eg´ere hozz´a kell ´ırni follow(A): -t is.
3.
Szemantikus elemz´ es
Szemantikus elemz´es alatt statikus szemantikus elemz´est ´ert¨ unk, azaz olyan tulajdon´agokat elemezzen a ford´ıt´o, mint p´eld´aul v´altoz´ok deklar´aci´oja, hat´ask¨ore, l´athat´os´aga, alprogramok form´alis ´es aktu´alis param´eterei k¨oz¨otti kompatibilit´as, stb.. Ezek a tulajdons´agok nem ´ırhat´oak le k¨ornyezetf¨ uggetlen nyelvtanokkal. Az elemz´esre az a m´odszer terjedt el, hogy az egyes szemantikus tulajdons´agok vizsg´alat´ara ¨on´all´o programokat ´ırnak. Ezekhez sokszor kell haszn´alni a szimb´olumt´abl´at. A legegyszer˝ ubb m´odszer az, ha a nyelvtan szab´alyait kieg´esz´ıtj¨ uk speci´alis jelekkel, akci´oszimb´ olumokkal, amik azt jelentik, hogy egy szemantikus rutint v´egre kell hajtani az elemz´eskor. Ha @s egy akci´oszimb´olumot jel¨ol, akkor az S → α@sβ → x levezet´esben ∗ ∗ a @s azt jelenti, hogy a @s sorraker¨ ul´ese eset´en az s szemantikus elemz˝o programelemet kell megh´ıvni, ´es az elemz´es csak ennek a programelemnek a lefut´asa ut´an folytat´odhat. P´eld´aul:
→ @CheckType. Term´eszetesen nem kell minden szab´alyt ´ılym´od´on b˝ov´ıteni, p´eld´aul: →. Ha a grammatika szab´alyait a szemantikus elemz´es c´elj´ab´ol akci´oszimb´olumokkal eg´esz´ıtj¨ uk ki, akkor a grammatik´at ford´ıt´asi grammatik´anak nevezz¨ uk. Az ilyen jelleg˝ u grammatik´akhoz a rekurz´ıv lesz´all´as m´odszer´et k¨onnyen lehet m´odos´ıtani. Ha a ford´ıt´asi grammatika egy szab´alya A → @a1 X1 @a2 X2 . . . Xn @an+1 ahol @ai egy akci´oszimb´olum vagy ε, akkor ehhez a szab´alyhoz tartoz´o program legyen a k¨ovetkez˝o: procedure A; begin [a1;] X1; [a2;] X2; ... Xn; [an+1] end; 5
A sz¨ogletes z´ar´ojel jelzi azt, hogy, ha@ai = ε, akkor az elj´ar´asnak nincs ilyen sora. Ezt a m´odszert h´ıvj´ak implicit szemantikus vermet kezel˝o szemantikus elemz´esnek. Az AT G = (T G, A, V, R, C) ¨ot¨ost attrib´ ut´ um ford´ıt´ asi grammatik´ anak nevezz¨ uk, ahol - T G egy ford´ıt´asi grammatika - A az attrib´ utumok v´eges halmaza - V az attrib´ utum´ert´ekek halmaza - R a szemantikus szab´alyok halmaza - C a logikai felt´etelek halmaza. Az X szimb´olum egy attrib´ utum´at szintetiz´altnak nevezz¨ uk, ha ´ert´ek´et egy szemantikus f¨ uggv´eny abban az esetben hat´arozza meg, amikor az X szimb´olum egy helyettes´ıt´esi szab´aly baloldal´an ´all, ha pedig a jobb oldalon ´all, akkor azt ¨ or¨ ok¨ olt attrib´ utumnak nevezz¨ uk. Teh´at az inform´aci´ot egy szintaxisf´aban a szintetiz´alt attrib´ utumok alulr´ol felfel´e, az ¨or¨ok¨oltek pedig fel¨ ulr˝ol lefel´e ´es szinten bel¨ ul tov´abb´ıtj´ak. Egy ATG-t L-attrib´ utum ford´ıt´ asi grammatik´ anak nevez¨ unk ´es L − AT Gvel jel¨ol¨ unk, ha minden A → X1 X2 . . . Xn helyettes´ıt´esi szab´alyra az attrib´ utumok kisz´am´ıt´asi sorrendje a k¨ovetkez˝o: J (A), J (X1 ), P(X1 ), J (x2 ), . . . , P(Xn ), P(A) , ahol J (Xi ): ¨or¨ok¨olt attrib´ utum ki´ert´ekel´es, ´es P(Xi ): szintetiz´alt attrib´ utum ki´ert´ekel´es. Ilyen t´ıpus´ u grammatik´aval el´erhet˝o, hogy a szemantikus elemz´est a szintaxisfa ´ep´ıt´es´evel p´arhuzamosan lehessen elv´egezni. Az L-ATG grammatik´ak j´ol haszn´alhat´ok a fel¨ ulr˝ol-lefel´e elemz´esekn´el, p´eld´aul az LL(1) elemz˝okben.
4.
K´ odgener´ al´ as
K´odgener´al´as alatt azt ´ertj¨ uk, hogy a m´ar elemzett magasszint˝ u programb´ol, hogyan lehet alacsonyszint˝ u assembly programot gener´alni.
5.
Szimb´ olumt´ abla- ´ es mem´ oriakezel´ es
A szimb´olumt´abla egy olyan t´abl´azatnak tekinthet˝o, amelyben egy sor egy szimb´olum programbeli jellemz˝oit tartalmazza. Ezek az attrib´ utumok els˝osorban a programnyelvt˝ol f¨ uggenek, de a leggyakrabban t´arolt attrib´ utumok a k¨ovetkez˝ok: 6
• a szimb´olum neve • a szimb´olum defin´ıci´oj´anak adatai • a szimb´olum t´ıpusdescriptora • a szimb´olum t´argyprogrambeli c´ıme • annak a forr´asnyelvi sornak a sorsz´ama, amelyben a szimb´olumot defini´alt´ak • azoknak a soroknak a sorsz´ama, amelyekben hivatkoz´as t¨ort´enik a szimb´olumra • a szimb´olum ´ab´ec´e-sorrendbeli l´ancol´asi c´ıme K´et alapvet˝o m˝ uvelete van a szimb´olumt´abl´anak: besz´ ur´as ´es keres´es. Blokkstrukt´ ur´aj´ u nyelvek eset´en sz¨ uks´eg van m´eg a set ´es a reset m˝ uveletre. A set egy blokkhoz tartoz´o alt´abl´at nyit meg, a reset pedig a blokk v´eg´en t¨orli ezt. Dinamikus mem´oriakezel´es eset´en a programelemek m´eret´et ´es az egyes p´eld´anyok darabsz´am´at csak v´egrehajt´asi id˝oben kell megismerni. Ezt ´altal´aban blokkstrukt´ ur´aj´ u programok v´egrehajt´asakor alkalmazzuk. Mivel minden blokkhoz egy ¨on´all´o adatmez˝o tartozik a run-time verem j´ol haszn´alhat´o az adatelemek elhelyez´es´ere, egy blokkba val´o bel´ep´eskor a blokk adatait a verembe tessz¨ uk, a blokkb´ol val´o kil´ep´eskor t¨or¨olj¨ uk. Az i-dik blokkhoz tartoz´o adatelemeket az ARi aktiv´aci´ os rekord tartalmazza, az aktiv´aci´os rekordban a blokk lok´alis v´altoz´oi, param´eterei ´es a blokkb´ol l´athat´o v´altoz´okra mutat´o pointerek vannak. Az aktiv´aci´os rekord h´arom r´eszb˝ol ´all, a lok´alis v´altoz´ok ter¨ ulet´eb˝ol, a display ter¨ uletb˝ol(statikus pointerek), ´es a param´eter ter¨ uletb˝ol. A blokk lok´alis v´altoz´oit a blokk szintsz´am´ab´ol ´es a blokkon bel¨ uli relat´ıv c´ımb˝ol ´all´o kett˝ossel ´abr´azolhatjuk. C´elszer˝ u a display ter¨ ulet b˝ov´ıt´esekor a megel˝oz˝o aktiv´aci´os rekordra mutat´o pointert haszn´alni.
7
