Szintaktikai elemzők tervezése

Gyakori programozói feladat, hogy egy szabályos szöveget fel kell dolgozni. Ez azt jelenti, hogy az abban lévő információt:

1. felismerjük és értelmezzük,
2. betöltjük valamilyen adatszerkezetbe,
3. az adatok alapján valamilyen műveletsort (algoritmust) végrehajtunk.

A szabályos szöveg azt jelenti, hogy abban az információ egy adott szabályrendszernek megfelelő formában van leírva. Ezt úgy is mondhatjuk, hogy a szöveg egy adott nyelven van írva és az író betartotta a nyelv nyelvtanát.

Ha tehát adott egy nyelvtan, akkor a fenti felsorolásban szereplő 1. feladat tulajdonképpen azt jelenti, hogy ellenőriznünk kell, hogy az elemzendő szövegünk megfelel-e annak a nyelvtannak. Ha igen, akkor rögtön tudjuk értelmezni is, hisz akkor a szöveg egyes elemeit (szavait) hozzá tudjuk rendelni nyelvtani fogalmakhoz, szerepkörökhöz (pl. alany, állítmány, jelző) és így értelmet nyer előttünk a szavak között lévő összefüggésrendszer.

Pontosan ez az, amit a fordítóprogram is tesz, amikor odaadunk neki egy C nyelvű programot. Megpróbálja a szövegünket a C nyelv szabályai szerint értelmezni és ha ez sikerül neki, akkor pontosan meg tudja mondani, hogy egy adott kódrészlet egy függvényt definiál, vagy egy ciklust ír le, stb.

Amikor egy elemzőprogramot szeretnénk írni, felmerül a kérdés, hogy hogyan írjuk le a nyelvtant oly módon, hogy abból könnyen elő tudjuk állítani az algoritmust, ami ténylegesen el is végzi az elemzést.

Az idegennyelvek tanulásakor megismert nyelvtankönyvek bár első ránézésre meglehetősen formálisnak és sokszor nagyon száraznak tűnnek, számunkra azonban mégis túlságosan szabadnyelvi és kötetlen módon fogalmazzák meg a szabályokat. Nekünk egy teljesen matematikai tisztaságú formalizmusra lenne szükségünk, amiből akár teljesen mechanikusan elő lehetne állítani az elemző kódját. Tulajdonképpen valami olyasmi ábrázolás-módszer párost keresünk, mint ami az állapotgépes problémák megoldására ismert: ha fel tudjuk írni egy probléma megoldásának állapottáblás alakját, akkor az alapján a programkód tulajdonképpen annyira automatikusan előállítható, hogy azt akár egy robotnak is könnyedén meg lehetne tanítani (tehát könnyű lenne írni egy programot, ami a táblát programkóddá alakítja). Mi most így ilyen módszert fogunk megismerni elemzők írására, és az ehhez használt leíró formalizmus az EBNF lesz.

Az EBNF-fel már a félév elején találkoztunk, amikor a pont a C nyelvvel való ismerkedés során egy-két szintaktikai fordulatot így adtunk meg. Az alapötlete az, hogy olyan szabályok sorozatát adjuk meg, amelyek egyéb szabályok és szövegrészletek (ún. terminálisok) alkotta kifejezésekből állnak.

Nézzünk meg egy, a listás előadáson látott mondatgeneráló program nyelvtanához hasonló példát:

mondat = tőmondat | összetett_mondat | szólás;

tőmondat = névelő alany állítmány;
összetett_mondat = névelő jelző alany határozó állítmány;
szólás = jelző alany határozó állítmány;

névelő = "a" | "az";
jelző = "piros" | "lassú" | "álmos" | "vidám" | "hasznos";
alany = "macska" | "tanár" | "kutya" | "hallgató";
határozó = "gyorsan" | "lassan" | "boldogan";
állítmány = "alszik" | "iszik" | "tanul";

A nyelvtan egyszerű magyar mondatok szerkezetét írja le és kilenc szabályból áll: mondat, tőmondat, összetett_mondat, szólás, névelő, jelző, alany, határozó és állítmány.

Az első szabály, a mondat kitüntetett szereppel bír: ő a legmagasabb szintű szabály, aki megmondja, hogy a nyelvünk milyen jellegű mondatokból építkezhet. Úgy is hívják az ilyen szabályokat, hogy kezdő szabály, hiszen az elemzést mindig vele kell kezdeni: azt a kérdést kell feltennünk, hogy az elemzendő szövegünk a nyelvünk egy mondata-e. A mondat szabály erre a kérdésre azt feleli, hogy a szöveg egy helyes mondat, ha az tőmondat, összetett mondat vagy szólás.

Ezek még absztrakt kategóriák, nem tudjuk ránézésre megmondani egy mondatról, hogy az például tőmondat-e, ezért tovább kell haladnunk a nyelvtanban. A tőmondat szabály azt mondja, hogy egy tőmondat egy névelőből, egy alanyból és egy állítmányból áll.

A névelő, alany és állítmány még mindig szabályok és nem a szövegünk elemei (amik a szavak), ezért még tovább haladunk és nagy örömünkre ezekben már konkrét szavakat találunk: például a névelő az az "a" vagy az "az" szavakat jelenti.

Ez egy nagyon fontos állomása az elemzésnek, mert elérkeztünk egy olyan pontra, ahol a szövegünk egy darabjáról eldönthetjük, hogy ténylegesen megfelel-e a nyelvtannak. Ha "a"-val, vagy "az"-zal kezdődik, akkor az elején egy névelő áll, tehát a mondat lehet egy tőmondat, vagy egy összetett mondat. Ahhoz, hogy ezt eldöntsük, tovább kell mennünk és meg kell néznünk, hogy a második eleme egy alany-e. Az alany szabályban szintén szvaakat találunk, tehát itt is közvetlenül tudunk hasonlítani és ez alapján értelmezhetjük a szöveget.

Észrevehetjük, hogy a szabályaink kétféle elemekből alkotott kifejezésekből állnak. Vannak olyanok, amelyek karaktersorozatok, tehát az elemzendő szövegünkkel közvetlenül képesek vagyunk összehasonlítást végezni. Ezeket hívjuk terminálisoknak. A szabályaink többi elemei egyéb szabályok, amelyeket még tovább kell értelmeznünk ahhoz, hogy a szövegünkkel való hasonlításig eljussunk. Ezeket nem-terminálisoknak hívják.

Minden nyelvtannak olyan szabálysorozatnak kell lennie, ahol a szabályok elemzése során mindenképpen végül terminálisokig jutunk el, hiszen különben nem tudnánk egy adott szöveg egyes részleteit beazonosítani tehát az elemzést elvégezni.

Az EBNF leírás eredetileg pontosan a példánkhoz hasonlóan, természetes (emberi) nyelvek elemzésére találták ki, ám végül leginkább a programnyelvek és egyéb szabályos, szöveges formátumok feldolgozásában kapott szerepet.

Az elemzés és értelmezés most bemutatott módszere pontosan követi felülről-lefelé (top-down) tervezés metodikáját. Minden szabálynak egy függvényt feleltetünk meg méghozzá úgy, hogy a kezdőszabály függvényét hívjuk meg legelőbb és ő épít az alacsonyabb szintű szabályokra, amelyek szintén meghívják a náluk alacsonyabb szinten lévő szabályok függvényeit egészen addig amíg el nem jutunk a szöveg és terminális szimbólumok hasonlításáig.

Egy szabályt leíró függvény a következő dolgokat teszi: megpróbálja a szabályt alkalmazni a szövegre. Ha sikerült, akkor a felismert szakasz után lépteti a szöveget (így haladunk előre az elemzésben), és logikai IGAZ értékkel tér vissza, különben nem léptet és HAMIS-at ad vissza.

Így a kezdőszabályunk hívása a következőképp fog kinézni:

if (!mondat(&szoveg)) {
    printf("Nem értem.\n");
}

Az elemzendő szöveg címét adjuk át a függvénynek, hogy szükség esetén képes legyen léptetni azt. A visszatérési érték pedig megmondja, hogy sikeres volt-e a elemzés – a mondat megfelel-e a nyelvtanunknak. Mivel itt most a feladatunk csupán annyi, hogy egy mondatot értelmezzünk, ezért amennyiben a kezdőszabály HAMIS értékkel tér vissza, akkor az azt jelenti, hogy a megadott mondat hibás, tehát kiírunk egy hibaüzenet, amely jelzi, hogy az értelmezés sikertelenül zárult.

A mondat függvény belseje nagyon hasonlít magához a szabályhoz: egyszerűen képzi három szabály VAGY-kapcsolatát:

bool mondat(SzoLista **aktualis) {
    return tomondat(aktualis) || osszetett_mondat(aktualis) || szolas(aktualis);
}

Az elemzett szöveget egy láncolt listában tároljuk, amelynek elemei a SzoLista struktúra példányai:

typedef struct SzoLista {
    char *szo;
    struct SzoLista *kov;
} SzoLista;

A függvény nem a struktúrában eltárolt adatokat szeretné megváltoztatni, hanem mindig a soronkövetkező, elemzésre váró szót tároló elem címét adja vissza. A visszatérési értéket azonban nem használhatjuk a cím szolgáltatására, mert ott a sikerességet jelző logikai értéknek kell szerepelni. Ezért van szükség a kettős indirekcióra: annak a mutatónak a címét vesszük át, ami az aktuális elemet megmutatja, így ezt képesek vagyunk átállítani egy másikra.

A mondat függvény a soronkövetkező szabályokra hárítja tovább az elemzést, hiszen azt mondja, hogy egy szöveg helyes mondat, ha az egy tőmondat (tomondat()) VAGY egy összetett mondat (osszetett_mondat()) VAGY egy szólás (szolas()).

A soronkövetkező szabályok a nyelvtanunkban még mindig csupa nem-terminálist tartalmaztak, így a nekik megfelelő függvények is további függvényekre bízzák az elemzés folytatását. Itt azonban annyiból eltértünk az EBNF leírásunktól,hogy egységesítettük a mondatrész-meghatározás feladatát. A nyelvtanunkban minden mondatrésznek egy külön szabály felelt meg, a mi kódunkban ezt az adott_mondatresz() függvény végzi, amely egy felsorolt típus (enum mondatresz) segítségével kapja meg azt az információt, hogy milyen mondatrészt keresünk.

bool tomondat(SzoLista **aktualis) {
    char *a_nevelo, *az_alany, *az_allitmany;
    SzoLista *eredeti = *aktualis;

    if (   adott_mondatresz(aktualis, nevelo, &a_nevelo)
        && adott_mondatresz(aktualis, alany, &az_alany)
        && adott_mondatresz(aktualis, allitmany, &az_allitmany)
    ) {
        printf("Tőmondat\n\tAlany: %s\n\tÁllítmány: %s\n", az_alany, az_allitmany);
        return true;
    }
    else {
        *aktualis = eredeti;
        return false;
    }
}

A fenti különbségtől eltekintve, az adott_mondatresz() függvény teljes mértékben megfelel a nyelvtani szabályokat leíró függvényeinknek: cím szerint átveszi az aktuális szó címét tároló pointert, siker esetén lépteti azt, és visszaadja logikai értékként, hogy sikeres volt-e az elemzés. Mivel ezen a ponton az adott mondat teljes elemzése elkészült, ráadásul még ki is írja ennek eredményét: megmondja, hogy az adott mondat egy tőmondat volt és kiírja annak névelőjét, alanyát és állítmányát.

Figyeljük meg, hogy ebben a szabályban egymásra következést kellett kifejezni: egy tőmandat egy névelővel kezdődik, amelyet az alany követ, majd ezután található az állítmány. A programkódban ez a három szabálynak megfelelő függvényhívások ÉS-kapcsolataként jelent meg.

Az első hívás (adott_mondatresz(aktualis, nevelo, &a_nevelo)) megnézi, hogy az első szó egy névelő-e. Ha igen, akkor az aktualis pointert átállítja a következő szóra és IGAZ-zal tér vissza. A logikai rövidzár miatt a második hívás (adott_mondatresz(aktualis, alany, &az_alany)) csak akkor fog kiértékelődni, ha az első IGAZ értékkel tért vissza, különben leáll az elemzés és a tomondat függvény HAMIS visszatérési értéket ad.

Ha tehát a névelőt megtaláltuk, akkor keressük az alanyt. Ha a második szó egy alany, akkor megint továbbléptetjük a pointert és IGAZ-at adunk vissza, tehát megy tovább az elemzés. Ha az állítmány is megvan, akkor végül a pointer a mondat végére mutat és a hármas ÉS-kapcsolatunk értéke logikai IGAZ lett. Ekkor tudjuk, hogy a mondatunk egy tőmondat, tehát befejeztük az elemzést és kiírhatjuk a mondatrészeinket.

Előfordulhat, hogy az elemzés során megtaláljuk a névelőt, de az alanyt nem ismerjük fel (például azért, mert ott egy jelző található és a szövegünk egy összetett mondat lesz). Ilyenkor az ÉS-kapcsolatunk értéke HAMIS és ezzel az értékkel is kell visszatérnie a tőmondat függvénynek. A gond az, hogy most a pointer a szöveg második szavára mutat (hiszen a névelőt sikeresen felismertük és ennek megfelelően továbbállítottuk a mutatót). Ha így visszatérünk, akkor mondat függvény a következő lépésben megpróbálja a mondatunkat összetett mondatként értelmezni (a VAGY-kapcsolat második eleme), de az sikertelen lesz, mert a szó eleji névelőt már nem fogja látni az osszetett_mondat() függvény.

A megoldás az, hogy minden szabályt leíró függvénynek el kell mentenie a pointer kezdeti értékét. Ha az elemzés bármely ponton sikertelen, akkor a pointert az eredeti értékére vissza kell állítani, hiszen csak így biztosítható, hogy egy másik szabály a szövegnek nekiveselkedve sikeresen tudja értelmezni azt. Ez történik a tomondat() függvény else ágának első sorában.

Az osszetett_mondat() és szolas() függvények szerkezete már nem különbözik érdemben a tomondat()-étól így tulajdonképpen áttekintettük az elemzési módszert, amellyel tetszőleges EBNF-nyelvtan tulajdonképpen gépiesen C-nyelvű kóddá alakítható. Ezt a módszert rekurzív alászálló módszernek hívják. A félév végén egy összetett példában találkozunk még vele. Ott zárójeles matematikai képletek értelmezését fogjuk elvégezni a segítségével. Az a példa azt is megmutatja, hogy miért szerepel a "rekurzív" szó a módszer nevében.

A bemutatott módszer teljesen mechanikusan alakítja a nem-terminálisok kifejezéseiből álló szabályokat függvényekké. Azon a ponton azonban, ahol eljutunk a terminálisokig, el kell kezdeni ténylegesen összehasonlítani a szövegünket a nyelvtanban szerepelő karaktersorozatokkal. Általában ezen a ponton a hatékony sztringkezelés érdekében beveztünk általános függvényeket és speciális adatszerkezeteket.

Ezt tettük jelen esetben is. A nyelvtanhoz tartozó "szótárat" nyelvtani kategóriáknak megfelelő tömbökben helyeztük el:

char *melleknevek[] = {"piros", "lassú", "álmos", "vidám", "hasznos", NULL};
char *fonevek[] = {"macska", "tanár", "kutya", "hallgató", NULL};
char *hatarozok[] = {"gyorsan", "lassan", "boldogan", NULL};
char *igek[] = {"alszik", "iszik", "tanul", NULL};
char *nevelok[] = {"a", "az", NULL};

A fenti tömbök címeit pedig eltároltuk egy újabb tömbben annak érdekében, hogy egységesen tudjuk majd kezelni az egyes csoportokat:

char **szotar[] = {fonevek, igek, melleknevek, hatarozok, nevelok};

Annak meghatározása, hogy az elemzett szöveg egy adott szava az aktuális szabály által elvárt soronkövetkező nyelvtani kategóriába tartozik-e, mindössze annyit jelent, hogy a szotar megfelelő indexű helyén található sztringtömbön végig kell haladni és minden szóval össze kell hasonlítani a kérdéses szót. Ezt végzi a benne_van() függvény:

bool benne_van(char *szo, char **szavak, char **talalat) {
    for (int i = 0; szavak[i] != NULL; ++i) {
        if (strcmp(szo, szavak[i]) == 0) {
            *talalat = szavak[i];
            return true;
        }
    }

    return false;
}

Ha a szavak tömbben megtaláljuk szo-t, akkor logikai IGAZ értékkel térünk vissza és a talalat mutatót ráállítjuk a megtalált szó kezdőcímére. Ezutóbbira azért van szükség, hogy az elemzés befejeztekor rendelkezésre álljanak a mondat egyes elemei.

A mondatrészek keresését még azzal tettük jobban átláthatóvá, hogy elkészítettük az adott_mondatresz() függvényt, amelynek a már említett felsorolt típus (enum mondatresz) segítségével tudjuk megadni, hogy az aktuális szót milyen mondatrésznek megfelelő szólistában keresse:

bool adott_mondatresz(SzoLista **aktualis, mondatresz a_mondatresz, char **szo) {
    char *talalat;

    if (*aktualis == NULL) return false;

    if (benne_van((*aktualis)->szo, szotar[a_mondatresz], &talalat)) {
        *aktualis = (*aktualis)->kov;
        *szo = talalat;
        return true;
    }

    return false;
}

A teljes programkód letölthető innen.