Ez az írás eredetileg 1998-ban jelent meg, már annak idején is elmúlt időkön borongott. Szerencsére azonban van a cikknek egy nagy felismerése. A téma, amit ismertet (a szintaxisgráf néven ismert leíró-tervező eszköz), egykor divatosabb volt, később valóban kevésbé ismertté vált – de nagy túlélőt kell üdvözölni benne! A cikk először a jó emlékezetű (Új) Alaplap folyóiratban került publikálásra.(Új Alaplap 1998. évi 4. sz.) Most az eredeti szerző engedélyével (és apróbb kiigazításaival) közöljük újra.
Szintaxisgráfok
Van régi a Nap alatt…
Az Új Alaplapban nemrég fejeződött be egy elméleti és gyakorlati szempontból egyaránt sokat adó sorozat a gráfokról. Van-e még bőr ezen a rókán? Azt hisszük, igen. Erről jutott tudnillik eszünkbe egy valamikor sokat használt, manapság méltatlanul mellőzött tervezési eszköz: a szintaxisgráf. Tegyünk hozzá néhány meglepő dolgot ahhoz, amit tudni szoktunk róla.
A szintaxisgráfok úgy váltak közismertté, hogy Niklaus Wirth metanyelvként használta őket az általa megalkotott Pascal szemléletes leírására. (Napjainkban a Free Pascal is ezt a technikát használja — A szerk.). A nyelvvel együtt el is terjedtek. Különösen megkedvelték a vizuális ábrázoláshoz vonzódó mérnökök; egy időben divat volt például adatátviteli protokollokat ezek segítségével definiálni. Kevésbé szerették meg a szoftverek dokumentálói, mert egy többleteszközt igényelt: nem lehetett billentyűzeten megrajzolni a különben oly kifejező ábrákat. Más nyelvek leírására nem is vették át, és lassacskán kezd háttérbe szorulni. Pedig kár lenne idő előtt elbúcsúztatni, többet tud, mint gondolnánk! Erre mutatunk most példákat.
Képzeljünk el egy Basic-nyelvű rendszert! Azért éppen ilyet, mert ez maga is a számítástechnika közkincse, nem kell tehát sokat magyaráznunk róla. Viszont könnyű több alkalmazást is találni a szintaxisgráfok számára benne. (Hogy nincs semmi köze a Pascalhoz, külön előny. Legalább látjuk, hogy ábrázolásmódunk nem kötődik egyetlen nyelvhez.)
Valami újdonság…
Wirth kétféle módon cimkézi meg a gráf éleit: a terminális szimbólumok helyén körbe, ovális keretbe foglalt jellel, szóval szakítja meg az élt, a nemterminális szimbólumokat viszont téglalap alakú keretbe írt szó jelzi. (Emlékeztetésül: a terminálisoknak pontosan úgy kell szerepelniük egy szintaktikusan helyes programban, ahogy a gráfban a nevüket megadtuk. A nemterminálisok viszont a gráfkészletben más helyen előforduló szintaxisgráfok címét jelzik, tehát további kifejtést igényelnek.)
A mi újításunk az lesz, hogy egy harmadik fajta jelet is használunk. Ez egy szaggatott vonalas lekerekített keret lesz. Jelentése: a célprogram terminálisa, nevezzük el célterminálisnak. Ezeket a szimbólumokat nem a programozó írja a forrásprogramba, hanem a fordítás során keletkeznek. (Engedje el az olvasó annak pontos definiálását, hogy mikor és hogyan lehet használni ezt a háromféle cimkés módszert, hagyjuk meg a matematikusoknak.)
A szintaxisgráf, mint parser
Legyen az első példánk egy olyan elemző készítése, amely fordított lengyel formára (RPN) hozza a Basic program egy sorát. Valamiféle fordítóprogramra gondolunk tehát, de olyanra, ami nem közvetlenül végrehajtható gépi kódot állít elő, mint a compilerek, hanem egy gyorsan és kényelmesen értelmezhető belső formát. (Aki nem ismeri a fordított lengyel jelölést, annak most elegendő annyit megérteni, hogy alapötlete szerint a műveleti jel az őt megelőző operandusokra vonatkozik. Például A + B helyett az A B + sorrend használatos.)
A példa szintaxisdiagramjainak egy töredékét mutatjuk be illusztráció gyanánt (az értékadó utasítás egyszerűsített gráfjait). Az egyszerűsített gráfkészlet csak a négy alapműveletet tartalmazza – mint kétoperandusú műveleteket – és csak a minusz előjelet, mint egyoperandusút. (Mivel a forrásprogramban ezt is ugyanazzal a ‘–’ jellel írjuk, mint a képoperandusú minuszt, ezért az RPN-be ettől megkülönböztetett jelet fordítunk. Ezt itt a ‘~’ hullámvonal jelöli.)
Figyeljük meg, hogy a kifejezés elején szereplő másik előjelhez, a pluszhoz nem tartozik célterminális! Ez tudnillik redundáns előjel, + X pontosan annyit ér, mint X. A célprogramban tehát nem szükséges hozzá semmiféle tevékenység! Másik megjegyzésünk: a változó és szám formailag nemterminálisokok, de ismertnek tekintjük, ezért nem részletezzük őket tovább. A harmadik: meg kell különböztetni az értékadást jelző egyenlőségjel bal oldalán szereplő változót a jobb oldalon, a kifejezésben esetleg előfordulótól! (A C nyelv alkalmazóinak sokszor kell erre figyelni: „balérték”, vagy „jobbérték”, amit használnak.) De erre később még visszatérünk.
Hogyan lehet az elemzést végrehajtani? Az elv az, hogy párhuzamosan haladunk a beírt szövegen (a forráskifejezésen) és az értékadás szintaxisgráfján. Abba az irányba haladunk, amelyben azonos terminálisokat találunk, figyelembe véve a gráf éleinek – nyilakkal jelzett – irányítását. Ez közismert. Az újdonság: fordítsuk függőleges irányba a szintaxisgráfokat, és így, mint program folyamatábrát olvassuk! Az algoritmus:
- Ha van a gráfon olyan terminális, mint a forrásban, akkor a gráfon arra az ágra lépjünk, ahol ezt találtuk és mind a forrásban, mind a gráfon lépjünk át ezen a terminálison! (Felismerés.)
- Ha terminális nincs, de nemterminális van a gráfban, akkor haladjunk arra, és szubrutinként hívjuk meg a vele címzett gráfot. (Most feltesszük, hogy csak egy ilyen irány van.)
- Ha a két előző feltételnek megfelelő ág nincs a gráfban, akkor hibajelzést kell adni, a forrás szintaxisa rossz.
- Ha a gráfon célterminálist látunk, haladjunk át rajta és tegyük le az RPN-forma kódjába. (Végső soron ez akkor is megtörténik, amikor nemterminálisokon haladunk át, mert minden nemterminálist is valahol terminálisokra kell visszavezetni, és a hozzátartozó tevékenységet egy célterminális definiálja.)
Mi felel meg a gráf alakzatainak a belőle előállott elemző programban? Az egy pontból többfelé haladó élek esetében az ágakon szereplő terminálisokat lehet feltételes elágazással, például IF utasítás segítségével azonosítani. A hurkokban elöl-, vagy hátultesztelő ciklusokra ismerhetünk, attól függően, hogy hol szerepel bennük felismerhető terminális. A nemterminálisok téglalapjait, mint már erre céloztunk, szubrutinokkal valósíthatjuk meg.
Mit kaptunk? Egy RPN-compiler elemző részének (az ún. parsernek) a programját leíró folyamatábrát.
A szintaxisgráf, mint interpreter
Második példánkról csak néhány szóval tegyünk említést. A zsebszámológépek használatakor sokszor jó, ha matematikai felírásmódot lehet használni a műveletek sorrendjének előírására, zárójelekkel, precedencia-szabályokkal. Nem szükséges viszont tárolni a műveleteket, azonnal végrehajtható, amit bebillentyűztünk. Nyilván ráismerünk a körülírásból, hogy az értelmező programok működésére célzunk. A dologban az a fantasztikus, hogy ugyanaz a szintaxisdiagram, amit az előbb elemző előállítására használtunk, alkalmas értelmező leírására is. Csak annyi változtatásra van szükség, hogy az élek címkéihez rendelünk más tevékenységeket. (Igazából még ennyi sem szükséges: csak a célterminálisoknál kell eltérni az eddigiektől.) Most így kell tehát olvasnunk az algoritmust: „Ha a gráfon célterminálist látunk, haladjunk át rajta, és hajtsuk végre a hozzárendelt tevékenységet!”.
A tevékenységek: számnak, változónak tegyük az értékét egy verembe. A műveleti jelek által előírt számítást a veremben lévő utolsó egy vagy két értéken kell végrehajtani, és az eredményt visszatenni a verembe. És most térünk vissza a „balérték” fogalmára. Az egyenlőségjel bal oldalán szereplő változónak nem az értékére van szükség, hanem a címére. Értéke esetleg még nincs is. Az értékadó utasítás szerepe tehát: a jobb oldalon kapott értéket elhelyezi a baloldalra írt változóval meghatározott helyre.
Csinálhatjuk persze azt is, hogy inkább az RPN-formához készítünk értelmezőt (ahhoz sokkal könnyebb, éppen ezért találták ki az RPN-t). Ezért nem is lenne jó tovább cicomáznunk ezt az előbbiekben felvázolt, közvetlenül interpretáló módszert. Van ugyanis egy baja: csak menet közben derül ki, hogy a forrássor nem is volt szintaktikusan helyes. A zsebszámológép ilyenkor vagy hibát jelez, vagy ésszerű feltevésekkel korrigál.
A szintaxisgráf, mint inverz parser
Most valami egészen meglepőt csinálunk. Ha az első példánkban szereplő képzelt Basic-rendszer gyakorlati használatára gondolunk, felmerül egy kérdés: hogyan lehet a programunkat szerkeszteni, vagy kiíratni, ha csak a belső, RPN formát tároljuk, a forrásprogramot nem? Más megoldás híján, meg kell próbálnunk a belső formából visszanyerni a forrássorokat.
Hogyan lehetséges ez? Csodát fogunk tenni! Ugyanaz a szintaxisgráf, amelyről e cikk elején szóltunk, ezt a visszafordítást is képes leírni. Hogyan? Úgy, hogy a következő dolgokat csináljuk:
Először is az élekhez ismét más tevékenységet rendelünk, mint az elemző program esetében. (Ez már a harmadik fajta lesz a cikkben.) A célterminálisokat most felismerni kell; a nemterminálisoknál, itt is, egy-egy másik gráfot kell szubrutinszerűen helyettesíteni (csak most a visszafordítás gráfkészletéből, ami esetleg nem azonos az eredetivel); a terminálisokat az outputba kell írni (mert most ezeknek kell keletkezni).
A második, amit teszünk, az, hogy most az értékadás gráf végétől indulunk el, mindig az irányítással ellentétesen haladva, míg végül – hátulról-előre haladva – megérkezünk a gráf kezdetéhez. Közben előáll a forrássor, szintén először a vége, később az eleje. (Elképzelhetjük úgy is, hogy most ellenkező irányban fordítjuk függőlegesre a gráfokat, ez lesz a folyamatábránk.)
Az algoritmus a „terminális” és „célterminális” szavak cseréjével az előre haladó elemzésnél megadottal megegyezik:
Ha van a gráfon olyan célterminális, mint az RPN-formában, akkor a gráfon arra az ágra lépjünk, ahol ezt találtuk, és mind az RPN-ben, mind a gráfon lépjünk át ezen a célterminálison! (Felismerés)… És így tovább, nem is kell részletezni.
Inkább néhány gyakorlati szempontra térjünk ki!
1. Érezzük, hogy van valamiféle határozott izomorfia a forrás és az RPN-alak között. Vagyis az egyikben pontosan annyi információ van, mint a másikban. De van egy nagy különbség: az RPN-formában nem fordulhat elő szintaktikus hiba! (Akkor nem fogadtuk volna el lefordításra, amikor a forrásalakot először beírtuk.) A visszaalakítás során tehát nem kell arra felkészülni, hogy nem sikerül a továbbhaladás a gráf egyik élén sem. Ez nagy könnyebbség.
2. Ezzel a hibamentességgel tudatosan vissza is élhetünk. Nyugodtan össze lehet vonni olyan gráfokat és részgráfokat, amelyek valójában többet engednek meg, mint a nyelv, amit elemzünk. Nem a legügyesebb példa, de kéznél van: az értékadó utasítást kifejezés = kifejezés formában is felírhatjuk. Nem baj, hogy az egyenlőségjel bal oldalán nem fog előfordulni a kifejezés gráf bejárásainak túlnyomó többsége. Most csak az az érdekes, hogy a lehetőségek között szerepel az is, hogy itt egyetlen változó áll. Hiszen „véletlenül” a szintaktikusan helyes forrássorok esetében éppen ez szerepel majd. (A példa azért nem a legjobb, mert sokkal több összevonási lehetőség van, mint ebből gondolnánk. Meg aztán, emlékezzünk arra is, hogy az RPN-formában nem egyeznek meg egymással az egyenlőségjel bal és jobb oldalán előforduló változók. Mind a két formát meg kell engedni tehát a kifejezés összevont gráfjának megszerkesztésekor.)
Aki úgy érzi, hogy ez az összevonás lassítja a visszaalakító program működését, annak igaza van. De semmi baj! Gondoljunk arra, hogy egy kiviteli perifériát kell az eredménnyel (a forrássorokkal) kiszolgálni. Bőven lesz időnk…
3. Nos, könnyű azt mondani, hogy „olvassuk visszafelé”… – a gráfnak mindegy, de az RPN-nek nem! Feltehetőleg a tárolt, belső formájú információk jelentős része több bájtot foglal el. Például az első bájt jelzi azt, hogy a következő négyben egy valós számot helyeztünk el. Az ilyen adatokat csak úgy lehet kezelni, ha tudjuk, hol van az adatok első bájtja. Persze, ha már tudjuk, hogy van ilyen buktató, akkor csak csekély technikai nehézséget jelent a kezelése. (Hogy az eredményt is jobbról-balra állítja elő a módszer, legfeljebb kicsit furcsa és mulatságos, de nem okoz gondot.)
4. És, végül, még egy érdekesség! Mi történik a forrásalak redundáns műveleti jeleivel, zárójeleivel? Ezekhez nincs célterminális rendelve. A zárójelekhez azért nem, mert az RPN zárójelmentes forma, a műveleti sorrendet a műveleti jelek és az operandusok sorrendje írja elő. A redundáns műveleti jeleknél pedig mi magunk határoztuk el, hogy nem őrizzük meg ezeket. Hát bizony ezek a fordított lengyel alakra hozás során elvesznek, ennélfogva a visszafordítás során sem jönnek létre. Baj? Inkább azt mondanám, didaktikus előny. Ha sokat látjuk a bonyolultan beírt sorokat egyszerűbb alakban megjelenni, előbb-utóbb hozzá fogunk szokni ahhoz, hogy mit felesleges beírnunk. (Vagy ahhoz, hogy írjuk be nyugodtan a redundáns elemeket, ha nem tudjuk memorizálni a műveletek precedencia-szabályait. Majd a rendszer egységesíti, amit lehet.) Persze, ha szeretnénk valamit megőrizni a forrássor jellegzetességeiből, például a kis- és nagybetűket, egymásba ágyazott programrészletek behúzásait, felesleges pozitív előjeleket, hozzárendelhetünk ezekhez is megfelelő célterminálisokat.
Dicsérni kell, nem temetni…
Talán sikerült meggyőznünk az Olvasót, hogy a szintaxisgráfokat nem kell még elfelejteni. Nem pusztultak ki, legföljebb más szerepkört kapnak. Mert arra azért rá kell mutatni, hogy nem ok nélkül szundikálnak valahol a közfigyelemtől távolabb. Nem csak nehézkesen dokumentálható voltuk elgondolkoztató, mint jeleztük, hanem az is, hogy ez az eszközkészlet nem támogatja a gépi feldolgozhatóságot, amire pedig sok jó példa van (YACC…). És arról is mélyen hallgattunk, hogy strukturált programot kapunk-e egy gráf derékszögű elfordítása nyomán. (Ugyan miért kapnánk azt?…) Vagy legalább valami megnyugtatót a programhelyesség bizonyítására, nem mintha manapság ez nagy divat lenne.
Persze, jó programot egy ilyen szemléletes kiindulásból enélkül is könnyű írni. Mert, hogy ne fanyalogjunk tovább: a legnagyobb előny, ami megőrzi ezeket a rajzocskákat, éppen szemléletességük. Lám, nekünk is sikerült néhány gráf segítségével elvégeznünk a „Tanuljon könnyen, gyorsan compilert, interpretert, nyelvtranszformáló rendszerprogramokat írni!” gyorstalpaló tanfolyamot.
Sokoldalúságuk meggyőző. Vizualitásuk, gyorsan átlátható voltuk nyilvánvaló. Ahol biztos a fennmaradásuk, az az oktatás, a tervek töprengő fázisa, a konferenciákon az írásvetítőre vázolt illusztrációk. Ahol a kreativitás eszközéül szolgálnak.
Segesdy Gábor
Kapcsolódó cikkek: