Szemantikus elemzés implementációja

Tananyag géptermi gyakorlathoz vagy önálló munkához

1. lépés

Ebben a tananyagban egy olyan nyelvet fogunk használni, amelynek alapelemei a nemnegatív egész számok, a logikai literálok és változók. A változókat a program elején kell deklarálni. A deklarációk után értékadások sorozata következik. Ezek bal oldalán egy változó, jobb oldalán egy változó vagy egy literál szerepel. Egy példaprogram:

natural n
natural m
boolean b
n := 0
b := true
m := n

  • Töltsd le a nyelv lexikális és szintaktikus elemzőjét valamint a tesztfájlokat!
  • Nézd át a flex forrást (assign.l) és a bisonc++ forrást (assign.y)!
  • A Parser.h és Parser.ih fejállományokat a bisonc++ generálta az első futtatásakor, de ezekbe beleírhatunk.
  • A Parser.h fejállományba felvettük a lexikális elemzőt adattagként, és hozzáadtunk egy konstruktort, ami inicializálja azt.
  • A Parser.ih implementációs fejállományban implementáltuk a lex függvényt, ami továbbítja lexikális elemző által felismert tokeneket a szintaktikus elemzőnek, és beállítja a szintaktikus elemző d_loc__ mezőjét arra pozícióra, ahol az elemzés éppen tart a forrásszövegben! Ugyanebben a forrásfájlban a hibakezelést végző error függvényt is módosítottuk.
  • Fordítsd le a projektet a make paranccsal (vagy "kézzel", a flex, bisonc++ és g++ segítségével)!
  • Futtasd a programot a helyes, a lexikális hibás és a szintaktikus hibás példákra!
  • Figyeld meg, hogy a program nem jelez hibát a szemantikus hibás példákra! Ennek a feladatsornak az a célja, hogy kiszűrjük ezeket a hibákat.

2. lépés

Szimbólumtáblát szeretnénk létrehozni. Az egyszerűség kedvéért ezt a C++ standard könyvtárának map adattípusával fogjuk megvalósítani. A map kulcsa a változó neve (string) lesz, a hozzárendelt érték pedig tartalmazni fogja a változó típusát és a deklarációjának sorát. A szükséges C++ kódot egy új fejállományba, a semantics.h fájlba írjuk.
  • A semantics.h fájlban include-old az iostream, string és map standard fejállományokat!
  • Hozz létre ugyanitt egy felsorolási típust a programnyelvben előforduló két típus reprezentálásához!
    enum type { natural, boolean };
  • Készíts egy var_data nevű rekord típust, amit az egyes változókhoz hozzárendelt adatok tárolására fogunk használni. Két mezője legyen:
    • decl_row azt fogja tárolni, hogy az adott változó a program hányadik sorában volt deklarálva.
    • var_type a változó típusát tárolja. Ez a mező az imént definiált type típusú legyen!
  • Írj a var_data rekordhoz egy két paraméteres konstruktort is, hogy könnyen lehessen inicializálni az ilyen típusú objektumokat létrehozásukkor. Legyen továbbá egy nulla paraméteres (üres törzsű) konstruktor is, mert erre majd szükség lesz akkor, amikor ilyen típusú elemeket akarunk egy map-ben tárolni!
  • A Parser.h fejállományban add hozzá a Parser osztály privát adattagjai közé a szimbólumtáblát:
    std::map<std::string,var_data> szimbolumtabla;
  • Az assign.y fájl elején cseréld le a %baseclass-preinclude direktívában az <iostream> fejállományt "semantics.h"-ra, hogy az imént készített fejállomány része legyen a projektnek!
  • Próbáld lefordítani a projektet, és javítsd az esetleges hibákat!

3. lépés

Az assign.y fájlban a deklarációk szintaxisát leíró szabályhoz szeretnénk majd egy olyan akciót írni, ami az adott változót beszúrja az adataival együtt a szimbólumtáblába. Ehhez a következőkre van szükség:
  • A deklaráció sorának száma: ez a d_loc__.first_line érték lesz, amit a lex függvény állít be. (Lásd az 1. lépést!)
  • A változó típusa: ez onnan derül ki, hogy éppen melyik szabály-alternatíva az aktív (NATURAL IDENT vagy BOOLEAN IDENT).
  • A változó neve: ezt csak a lexikális elemző tudja! El kell érnünk, hogy ez továbbításra kerüljön a szintaktikus elemzőhöz.
A bisonc++ megengedi, hogy tetszőleges (terminális vagy nemterminális) szimbólum mellé egy ún. szemantikus értéket (lásd az előadás anyagában: attribútum) rendeljünk. Mivel különböző szimbólumokhoz különböző típusú szemantikus érték rendelhető, ezért létre kell hoznunk egy unió típust ezekhez. Erre a bisonc++ külön szintaxist biztosít, amiből majd egy valódi C++ unió típust fog generálni. Ennek most egyetlen sora lesz, hiszen kezdetben csak a változókhoz szeretnénk szemantikus információként hozzárendelni a nevüket.
  • Az assign.y fájlhoz az első %token deklaráció elé add hozzá a következőt:
    %union
    {
      std::string *szoveg;
    }
  • Ennek az uniónak a mezőneveit használhatjuk arra, hogy meghatározzuk az egyes szimbólumokhoz rendelt szemantikus értékek típusát. Egészítsd ki az azonosító tokent így: %token <szoveg> IDENT;
  • Az azonosító tokeneknek most már lehet szemantikus értéke (string), de ezt be is kell állítanunk valahol. A terminálisok szemantikus értékét a lex függvény tudja beállítani. (Lásd az előadás anyagában: kitüntetett szintetizált attribútum.) Egészítsd ki a lex függvényt (még a return előtt) a következő sorokkal:
    if( ret == IDENT )
    {
      d_val__.szoveg = new std::string(lexer.YYText());
    }
    (Az YYText() függvénnyel lehet elkérni a flex-től a felismert token szövegét. Ebből létrehozunk egy string-et. A Parser osztály d_val__ adattagja olyan unió típusú, amit az imént az assign.y fájlba írtunk. Ennek a szoveg mezőjébe írhatjuk a szöveget.)
Most már elérjük az assign.y fájlban a szabályok mögé írható akciók belsejében az azonosítókhoz tartozó szövegeket. Az a: A B C szabály esetén az A szimbólum szemantikus értékére $1, a B szimbóluméra $2, a C szimbóluméra $3 hivatkozik. Ezek típusának megállapításához meg kell néznünk, hogy az unió típusnak melyik mezőjét rendeltük hozzá az adott szimbólumhoz. Ennek a mezőnek a típusa lesz a szemantikus érték típusa. (Esetünkben string*.)
  • A deklarációkra vonatkozó szabályalternatívákat egészítsd ki úgy, hogy kiírják a standard kimenetre az éppen deklarált változó nevét!
    NATURAL IDENT
    {
      std::cout << *$2 << std::endl;
    }
  • Futtasd a helyes példára a programot!

4. lépés

Ahelyett, hogy a standard kimenetre írnánk a deklarált változók nevét, most betesszük az adataikat a szimbólumtáblába. A map adattípusnak van [] operátora, ennek segítségével lehet beállítani és lekérdezni az adott kulcshoz tartozó értéket.
  • Írd át a deklarációkhoz tartozó szabályalternatívák programját úgy, hogy a változót és adatait szúrja be a szimbólumtáblába!

    NATURAL IDENT
    {
      szimbolumtabla[*$2] = var_data( d_loc__.first_line, natural );
    }

  • Ellenőrizzük le a beszúrás előtt, hogy nem volt-e már ugyanezzel a névvel korábban deklaráció! A map adattípus count függvénye megadja, hogy egy adott kulcshoz hány elem van a map-ben (0 vagy 1).

      if( szimbolumtabla.count(*$2) > 0 )
      {
        std::stringstream ss;
        ss << "Ujradeklaralt valtozo: " << *$2 << ".\n"
        << "Korabbi deklaracio sora: " << szimbolumtabla[*$2].decl_row << std::endl;
        error( ss.str().c_str() );
      }

    A hibaüzenet szövegének összegyűjtéséhez és a korábbi deklaráció sorának szöveggé konvertálásához a stringstream osztályt használtuk. Ehhez be kell include-olni a semantics.h fájlba a sstream standard fejállományt!
    A stringstream típusú ss-ből a str() tagfüggvénnyel lehet lekérni a benne összegyűlt string-et. Mivel az error függvény (lásd a Parser.ih-ban!) string helyett C stílusú karakterláncot vár paraméterként, ezért a c_str() függvény segítségével konvertálunk.
  • Töltsd ki hasonlóan a logikai változók deklarációjához tartozó szabályalternatívát is, de ott a szimbólumtáblába logikai változót szúrj be!
  • A programnak most már a 4.szemantikus-hibas fájlra hibát kell jeleznie.

5. lépés

Azt is szeretnénk ellenőrizni, hogy az értékadásokban használt változók deklarálva vannak-e.
  • Egészítsd ki az értékadásokat és a kifejezéseket leíró szabályoknak az IDENT-et tartalmazó alternatíváit úgy, hogy hibaüzenetet kapjunk nem deklarált változók esetén!
  • Ellenőrizd, hogy az 5. és 6. szemantikus hibás tesztfájlra valóban hibaüzenetet ad-e a fordító!
Az értékadások típushelyességének ellenőrzéséhez szükséges, hogy szemantikus értéket adjunk a kifejezésekhez. A konkrét esetben ez lehet a korábban definiált type felsorolási típusú érték. A kifejezéseket leíró szabályokban be fogjuk állítani a kifejezés szemantikus értékét (a kifejezés típusát) a szabály jobboldala alapján (lásd az előadás anyagában: szintetizált attribútum). A szabály baloldalának szemantikus értékére a $$ jelöléssel hivatkozhatunk az akciókban. Ha nemterminálisokhoz szeretnénk szemantikus értéket hozzárendelni, akkor ezt is fel kell tüntetni a fájl elején. Mivel ez már nem token, ezért a %type <unió_megfelelő_mezője> nemterminális_neve szintaxist kell használni.
  • Egészítsd ki az assign.y fájlban korábban definiált uniót egy type* típusú mezővel, és tüntesd fel az expr nemterminálishoz rendelt szemantikus érték típusát az unióban létrehozott új mezőnév segítségével!
  • Egészítsd ki a kifejezéseket leíró négy szabályalternatíva akcióit olyan utasításokkal, amelyek beállítják a szabály baloldalának szemantikus értékét (a kifejezés típusát)!
    Például az IDENT alternatíva esetén a szimbólumtáblából kérhetjük le az azonosító típusát:
    $$ = new type(szimbolumtabla[*$1].var_type);
    A TRUE alternatíva még egyszerűbb:
    $$ = new type(boolean);
  • Használd fel az expr nemterminálisokhoz most beállított szemantikus értékeket az értékadásra vonatkozó szabályban: ellenőrizd, hogy az értékadás két oldala azonos típusú-e!

    if( szimbolumtabla[*$1].var_type != *$3 )
    {
      error( "Tipushibas ertekadas.\n" );
    }

  • Most már valamennyi szemantikus hibás példára hibát kell jeleznie a programnak.
  • Az IDENT és expr szimbólumok szemantikus értékeit minden esetben (a lex függvényben és a szabályokhoz csatolt akciókban is) a new kulcsszó segítségével, dinamikus memóriafoglalással hoztuk létre. Azokban az akciókban, ahol ezek a szimbólumok a szabály jobb oldalán állnak, felhasználtuk az értékeket. A program memóriahatékonyságának érdekében azonban a felhasználás után fel kell szabadítani a lefoglalt memóriát, hogy elkerüljük a memóriaszivárgást. Nézd végig az összes szabályt, és ahol a jobb oldalon IDENT vagy expr áll, ott az akció végére írd be a következő utasítást: delete $i (ahol i az IDENT vagy expr sorszáma).