online kép - Fájl  tubefájl feltöltés file feltöltés - adja hozzá a fájlokat onlinefedezze fel a legújabb online dokumentumokKapcsolat
  
 

Letöltheto dokumentumok, programok, törvények, tervezetek, javaslatok, egyéb hasznos információk, receptek - Fájl kiterjesztések - fajltube.com

Online dokumentumok - kep
  
felso sarok kategória jobb felso sarok
 

Biológia állatok Fizikai Földrajz Kémia Matematika Növénytan Számítógépes
Filozófia
Gazdaság
Gyógyszer
Irodalom
Menedzsment
Receptek
Vegyes

 
bal also sarok   jobb also sarok
felso sarok   jobb felso sarok
 




































 
bal also sarok   jobb also sarok

Informatika II. gyakorlat Fordítók, fordítasi technikak

számítógépes





felso sarok

egyéb tételek

jobb felso sarok
 
Adatbazis létrehozasa - Access
FOLYAMATVIZUALIZÁLÓ ÉS SCADA PROGRAM-RENDSZEREK
Az operaciós rendszer
Adatok tömörített tarolasa - előnyök, hatranyok
Fajlrendszerek
AS/400 rendszerkoncepció
Szamrendszerek
Windows halózati jellemzői
A CD-n lévő szamokról, keletkezésükről
Processzorok
 
bal also sarok   jobb also sarok

Budapesti Müszaki és Gazdaságtudományi Egyetem

Villamosmérnöki és Informatikai Kar


Automatizálási és Alkalmazott Informatikai Tanszék

Alkalmazott Informatika Csoport

 
T i









Informatika II. gyakorlat



hallgatói segédlet




Fordítók, fordítási technikák















Bevezetés

A mérés célja az elöadás a fordítók, fordítási eljárásokkal kapcsolatban elhangzott információk gyakorlatban történö alkalmazása. Bár ez a segédlet is tartalmaz egy rövid, egyszerüsített összefoglalást erröl a témakörröl, a gyakorlat sikeres elvégzéséhez szükséges az elöadás anyagok ismerete is.

A fordítóprogramok általánosságban képesek egy megadott forrásnyelvek készített adatállományt egy célnyelvre lefordítani. A forrás és a célnyelv sokféle lehet, tipikus példa, hogy egy programozási nyelvröl (C++) gép kódú alkalmazást készítünk, de más lehetöségek is elképzelhetöek, mint ahogy ez a segédlet példáiban is 151g64b látható. A fordítókról rengeteg jó és kevésbé jó leírás van az Interneten[1], ill. nyomtatott könyv formájában.

A föbb fordítási lépések az 1. ábrán láthatóak[3]:


. ábra Fordítási lépések


A kiindulás a forrásnyelvü adatállomány, ami elsö lépésben kisebb blokkokra, tokenekre bontunk. Egy-egy token lehet pl. egy változó, egy szám, vagy karaktersorozat. Ebben a lépésben távolítjuk el a felesleges sortöréseket és szóközöket is. A tokenekböl a következö lépésben a forrásnyelv szabályai szerint szintaxis fát építünk. A szabályok megadása legtöbbször a formális nyelvekben megszokott jelleget követi. A harmadik lépés során a szintaxis fát ellenörizzük szemantikai szempontból, pl. itt végezhetö el a típusok ellenörzése is. A negyedik lépésben a szemantikailag ellenörzött szintaxis fából köztes kódot generálunk. Összetettebb feladatokban ezen a köztes kódon további ellenörzéséket (pl. adatfolyam ellenörzés) végezhetünk el, amivel csökkenthetjük a majdani futásidejü hibák esélyét. Az ötödik lépés során a köztes kódot optimalizáljuk, majd a hatodik lépésben legeneráljuk a célnyelvü adatállományt (pl. bináris kódot).  

A fordítási folyamat elsö két lépése nagyrészt automatizálható, ha a tokenek definícióját és a nyelvtani szabályokat megadjuk. A token-definíciók regurális kifejezések, vagy EBNF leírások segítségével adhatóak meg. A nyelvtani szabályok a formális nyelveknél tanult módon, a mondatszimbólum nemterminálisokra történö bontásával adhatóak meg. Természetesen a nemterminális szimbólumok további felbontását is meg kell adni egészen a terminális szimbólumokhoz vezetö szabályokig.

A mérés során, és a segédletben is az ANTLR[4] nevü programot fogjuk használni a szintaxis fa felépítéséhez. Az ANTLR egy nyelvi definíciós fájl alapján olyan osztályokat generál, amelyek képesek elvégezni a forrás elemzését, tokenekre bontását, valamint a szintaxis fa felépítését. A fa elkészítését követöen a programozó feladata, hogy további ellenörzéseket folytasson (a szemantikai elemzés keretein belül), amennyiben azokra szükség van, ill. kódot generáljon a szintaxis fa alapján.

Az ANTLR által használt definíciós fájlt általában ".g" kiterjesztéssel hozzuk létre. A fájl a következö elemekböl épül fel:

  1. Header fájlok inicializálása
  2. Nyelvi beállítások
  3. A Parser osztály definíciója (nyelvi szabályok)
  4. A Lexer osztály definíciója (tokenek)
  5. A TreeParser osztály definíciója (osztály a fa feldolgozásához)

Az 1. pontra akkor van szükség, ha saját faépítö algoritmust szeretnénk létrehozni (l. 3. feladat), különben ez a lépés kihagyható.

A 2. pont azt szabályozza, hogy a nyelvi definíciót milyen programozási nyelv (C++, C#, Java, .) szintaktikájával kell értelmezni, ill. milyen nyelvüek legyen a definíciós fájlból generált osztályok. Ez egy nagyon fontos lépés, ugyanis az ANTLR Java alapú program, alapbeállításként Java osztályokat generál, ami a jelen mérésben nem megfelelö, mivel a mérés a fordítók C++ alapú változatát írja elö.

A 3. pont a forrásnyelv definíciója EBNF[5] formában megadott szabályok formájában. Fontos megemlíteni, hogy az egyes szabályok elé és mögé saját kódrészleteket illeszthetünk be, amennyiben az szükséges. Ezek a kódrészletek képesek pl. az aktuális kifejezés értékét tárolni és változtatni a forrásban megadott müveleteknek megfelelöen.

A 4. pont a tokenek definícióját tartalmazza, egyszerü példák a tokenek megadására a z ANTLR honlapján[6] találhatóak.

Az 5. pont elhagyható, amennyiben saját fa reprezentációt alkalmazunk, vagy ha az elkészült szintaxis fán semmilyen müveletet sem szeretnénk elvégezni. A TreeParser-ek segítségével egyszerüen adhatunk meg a fa alapján elvégzendö müveleteket.


Az ANTLR által generált (C++) nyelvü fájlokat egy Visual Studio project fájlba kell foglalni, majd le kell fordítani, aminek eredményeképpen kapunk egy egyszerü, de hatékony nyelvtani elemzöt a kiválasztott forrásnyelvhez.

Az ANTLR telepítése

A https://www.imada.sdu.dk/~morling/issue1.htm honlap részletesen leírja, hogy hogyan lehet az ANTLR programot otthoni környezetben beüzemelni. Habár a leírás egy régebbi ANTLR verzióhoz készült, mint amit a mérésen használni fogunk, a föbb lépések mégis megtalálhatóak a leírásban:

  1. Le kell tölteni (és fel kell telepíteni) az ANTLR legújabb verzióját a https://www.antlr.org oldalról
  2. Le kell tölteni és fel kell telepíteni a Java Development Kit legújabb verzióját
  3. Hozzá kell adni a Path környezeti változóhoz a Java bin könyvtárát (ha az nem került oda magától)
  4. Meg kell adni egy ClassPath nevü környezeti változót, itt a honlapon szerelötöl eltéröen elegendö a C:\antlr277\lib\antlr.jar értéket megadni (természetesen az ANTLR telepítési könyvtárát átírva), majd újra kell indítani a gépet (!)
  5. Létre kell hozni Visual Studioban egy új, üres solution fájt[7], majd ehhez hozzáadni egy új C++ projectet.
  6. Meg kell adni a következöket a project beállításainál:
    1. AdditionalIncludeDirectories ="C:\antlr\277\include"
    2. AdditionalDependencies  ="C:\antlr\277\lib\antlr.lib"
    3. AdditionalLibraryDirectories ="C:\antlr\277\lib"
  7. A projecthez hozzá kell adni az egyes feladatok .g fájljából generált .cpp és .hpp fájlokot, majd le kell fordítani. A .g .cpp átalakítás parancssorból a java antlr.Tool mydeffile.g parancsot kell kiadni, ahol a mydeffile.g tartalmazza a forrás nyelvének definícióját.

A mérésre való felkészülést segítendö jelen segédlet mellé letölthetök a project fájlok is, amikben csak az ANTLR telepítési útvonalát kell átírni (amennyiben az szükséges).

I. Példa - Egyszerüsített számológép

Az elsö feladat egy, a standard inputon megadott müveletsor beolvasása és a müvelet eredményének kiírása. A müveletsor csak egész számokat ill. a "+" és a "*" müveletet tartalmazhatja.


A feladat megoldása a  .g fájl megadásával történik


//Meg kell adni, hogy C++ nyelvü osztályokat szeretnénk generálni

options


// A parser osztály tesreszabása

class CalcParser extends Parser;

options


// A nyelvtani szabályok, ahol expr a teljes kifejezés (a

// mondatszimbolum). Ez a szabaly azt irja le, hogy egy kifejezes

// az mexpr és a PLUS nevü szimbolumok sorozatából adódnak ki. A

// kifejezést pontosvesszovel zarjuk le.

expr  : mexpr (PLUS^ mexpr)* SEMI!

;


// Az mexpr szimbolum felbontasanak szabalya, ami

// kimondja, hogy az atom es a STAR szimbolumok sorozatara bonthato

mexpr : atom (STAR^ atom)*

;


// Az atom tovabb bonthato pontosan egy INT-re

atom: INT;


// A lexer (a tokeneket analizalo) osztaly definicioja



class CalcLexer extends Lexer;


// A "white space" karaktereket (pl. sor vege) ki kell hagyni, azok

// nem kepeznek kulon tokent

WS_   : (' ' | '\t' | '\n' | '\r')


;


// Az egyszeru tokenek definicioja

STAR: '*';

PLUS: '+';

SEMI: ';';


// Egy INT szam szamjegyek sorozatabol epul fel

protected

DIGIT: '0'..'9';

INT : (DIGIT)+;


// Az alapertelmezett fabejaro osztalyt szeretnenk hasznalni

class CalcTreeWalker extends TreeParser;


// szamitsuk ki a forras, azaz a bemeneti muveleti sor eredmenyet

expr returns [float r]


: #(PLUS a=expr b=expr)

| #(STAR a=expr b=expr)

| i:INT

;


A .g fájlból a korábban leírt módon generálhatjuk le a C++ osztályokat. Ezeket a fájlokat adjuk a projecthez.


A következö lépés a statikus Main függvény definiálása.


#include <iostream>

#include <sstream>

// Az ANTLR osztalyara is szukseg van a fa epitesehez

#include "antlr/AST.hpp"


// A generalt fajlok

#include "CalcLexer.hpp"

#include "CalcParser.hpp"

#include "CalcTreeWalker.hpp"


int main( int argc, char* argv[] )


input_string.str(expr.str());

input = &input_string;

filename = "<arguments>";

}


// A lexer inicializalasa

CalcLexer lexer(*input);

lexer.setFilename(filename);


// A parser inicializalasa (szuksege van a lexerre!)

CalcParser parser(lexer);

parser.setFilename(filename);


//A faepito rutinok inicializalasa

ASTFactory ast_factory;

parser.initializeASTFactory(ast_factory);

parser.setASTFactory(&ast_factory);


//A forra tenyleges feldolgozasanak megkezdese

parser.expr();


// A szintaxis fa kinyerese a parser-tol

RefAST t = parser.getAST();


// Sikerult a fa felepitese?

if( t )


else


}

catch(ANTLRException& e)


catch(exception& e)


return 0;



A project fájlt (megtalálható mellékletként) ezek után már csak fordítani és futtatni kell. A program a standard inputról olvassa be a kifejezést, amit ki kell számolnia.

II. Példa - Számológép vektormüveletekhez

A második feladat egy, a standard inputon megadott müveletsor beolvasása és a müvelet eredményének kiírása. A müveletsor vektorokat, összeadást ("+"), szorzást ("*") ill. zárójeleket tartalmazhat.


Ez a feladat annyival bonyolultabb az elözönél, hogy itt a skalárok helyett vektorokkal végezzük el a müveleteket. Ez az egyszerünek tünö változtatás jelentösebb módosításokat igényel:


Az elsö feladatban az ANTLR által felkínált fa szerkezetet használtuk fel, ami egyrészröl kényelmes volt, hiszen a fa csomópontjainak építése nagyrészt automatizálható volt, másrészröl viszont ez az ábrázolás tartalmaz néhány megkötést, ami megnehezítheti a fa feldolgozását. Ennélfogva a példában egy új fa típust fogunk használni. Ez a fa a Tree osztályban található meg, ami tartalmazza az alapvetö faépítö és kiírató függvényeket, valamint a fa csomópontjainak (vektorok és müveleti jelek) kezelését. A Tree osztályban az egyes csomópont típusokhoz egy-egy egész számot rendelünk, ami a csomópont típusának a kódját reprezentálja. Ezeknek a kódoknak a feloldása a NodeTypes.hpp fájlban találhatóak meg.

A vektorok kezeléséröl, a vektorok összeadásának és szorzásának elvégzéséröl szintén gondoskodni kell. Erre szolgál a Vector template osztály, ahol a template típusának jelen esetben "int"-et használunk majd. Ez az osztály nem függ a fordítótól, a fa felépítésétöl, hanem valóban csupán az alapvetö vektormüveleteket tartalmazza.

Mivel a feladat megoldásához szükséges kiegészítö osztályok megvannak[8] így a következö lépés a nyelvi definíciós fájl megváltoztatása:

Meg kell adni, hogy nem a beépített fa építö algoritmust szeretnénk használni:


header "post_include_hpp"



class CalcParser extends Parser;


options



A nyelvtan szabályai is más felépítésüek lesznek, pl.




expr returns [Tree* pt1]


: pl1=mexpr

(PLUS^ pr1=mexpr )*

else



;


Ez a szabály egyrészt kifejezi azt, hogy az expr tovább bontható egy mexpr szimbólumra és egy pluszjel - mexpr párosból adódott sorozatra. Másrészt viszont a szabály tartalmaz kódrészleteket is, amik a fa építését végzö müveletek hívásáról gondoskodnak. A nyelvtani szabályok így bonyolultabb felépítésüek lesznek, de a bövítés révén a müveletek szélesebb skáláját lehet rajtuk elvégezni.

A zárójelek ill. a vektorok feldolgozásához új szabályokra (nyelvi is token-jellegü) is szükség van. Ezek a szabályok a korábbiakhoz hasonlóan a formális nyelveknél megszokott módon adhatóak meg.


mexpr returns [Tree* pt2]


: pl2=element

(STAR^ pr2=element )*

else



;


element returns [Tree* pt3]


: pm3=vector

| LPAREN! pm3=expr RPAREN!


;


vector returns [Tree* pt4]


: LBRACKET! pl4=atom

(SEMI pr4=atom )* RBRACKET!

;


LPAREN: '(';

RPAREN: ')';

LBRACKET: '[';

RBRACKET: ']';

COMMA:  ',';


A vektorok összeadása és szorzása csak akkor értelmezhetö, ha a vektorok nagysága megegyezik. Ezt az információt a szemantikus elemzés során ellenörizhetjük. A szemantikus elemzés ebben az esetben végignézi a korábban elkészített szintaxis fát és megnézi, hogy a müveletekben rész vevö vektorok mérete megfelelö-e. Ez a logika a SemanticAnalyser.cpp fájlban található. A pluszjel esetében pl. kiolvassuk az aktuális csomópont két gyermek elemét (a müvelet két operandusát), a fa csomópontokból rekurzív módon vektorokat készítünk, majd összehasonlítjuk azok sorainak számát. A szorzásnál hasonló módszerrel ellenörizzük, hogy az adatok szemantikai szempontból megfelelöek-e.

Az utolsó teendönk a Main függvény átírása, ami viszonylag egyszerüen elvégezhetö:

.

CalcParser parser(lexer);

parser.setFilename(filename);


Tree* pt = parser.sentence();

if( pt )


catch (char* s)


}


III. Példa - Számológép HTML kimenettel

A harmadik példafeladat a korábbiakban elkészült vektorokat kezelö számológép kiegészítése olyan módon, hogy az képes legyen az eredményt és az operandusokat HTML formátumban megjeleníteni.


A harmadik példa a korábban elkészített számológép kibövítése, hogy az HTML kimenetet adjon, azaz mintegy kódot generálunk a forrás adatállományból. A feladathoz nagy segítséget nyújt a HtmlGenerator osztály, ami a szemantikus analízishez hasonlóan képes a szintaxis fán rekurzívan navigálva az egyes csomópontokhoz HTML nyelvü kódot generálni. Az osztály felépítése meglehetösen egyszerü, általánosnak mondható. A GetHTML függvény legenerálja a HTML vázát, míg a GetHTMLRecursive függvény elvégzi a paraméterként megkapott szintaxis fához (vagy fa részlethez) tartozó kód generálását. Az egyes müveletekböl egymásba ágyazott táblázatokat készít. A vektor osztály képes önmagát HTML formátumban megjeleníteni a toHtml függvény segítségével.

A példa az elsö két példához képest egyszerü ugyan, de leegyszerüsített formában megmutatja a kódgenerálás egyik lehetséges módszerét.







https://hu.wikipedia.org/wiki/Ford%C3%ADt%C3%B3program,

https://en.wikipedia.org/wiki/Compiler

Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Compilers Principles, Techniques, and Tools, Addison - Wesley, 1988

A lépések adott esetben eltérhetnek az ábrán szereplöktöl, amennyiben a forrásnyelv egyszerü, avagy nagyon bonyolult.

https://www.antlr.org

https://www.cee.hw.ac.uk/~rjp/Coursewww/Cwww/EBNF.html

Innentöl kicsit eltér a honlapon szereplö leírástól

Az osztályok implementációján a példa során nem változtatunk.


: 2742







Felhasználási feltételek