Oracle Business Intelligence

Ma megvolt a diploma védése, melynek során mérnökké nyilvánítottak. Juppi!

Diplomamunkám ezen a címen érhető el, a bizottság ötösre értékelte az elvégzett munkám, és így végeredményben a diplomám minősítése négyes lett. A védésen tartott prezentációm diái itt vannak.

Rövid bejegyzés lesz, mostanában picit kevés a szabadidőm (diplomamunka, záróvizsgák):


A fenti linken pár screenshot látható a diplomamunka keretében implementált T-SQL - PL/SQL fordítóról. Amolyan proof-of-concept munka, ANTLR+StringTemplate segítségével. Ha leadtam a leadni valókat és befejeztem a befejezni valókat, majd írok egy összefoglalást, hogy mennyire fényjézus ez az ANTLR.

A nyelv formális definíciója

Jelölje ∑ a nyelv karakterkészletének véges halmazát. Ezt a halmazt nevezzük a nyelv alfabetájának.

Legyen ∑* a ∑ alfabetából alkotott véges, de nem korlátos hosszúságú jelsorozatok halmaza. Nem üres ∑ halmaz esetén ∑* halmaz megszámlálhatóan végtelen számosságú.

Egy adott alfabetából képezhető összes lehetséges jelsorozatba beletartozik az üres jelsorozat, az ε is.

Valamely - egy adott ∑ alfabeta felett értelmezett - L nyelv a ∑* halmaz egy tetszőleges részhalmaza.

Fordítók

Egy fordító általánosságban nem más, mint egy olyan program, ami valamilyen bemeneti jelsorozatra valamilyen kimeneti jelsorozattal válaszol. Bemeneti jelsorozat alatt nem akármilyen karaktereket, hanem a nyelv karakterkészletébe, alfabetájába tartozó karaktereket értünk. A bemeneti jelsorozatokat szokás még mondatoknak nevezni. Tehát a fordító egy L nyelvbe tartozó s mondatot valamilyen t mondatra képez le.

A nyelveket formálisan nyelvtanok segítségével írhatjuk le. Nyelvtanok segítségével a nyelv mondatai levezethetőek, generálhatóak. A gyakorlatban a nyelvtanokat mégis arra használjuk, hogy eldöntsük, egy mondat eleme-e az adott nyelvnek.

A nyelvtanokat egy négyes határozza meg:

G = (N, ∑, P, S)

ahol N a nyelvtani szimbólumok véges halmaza, ∑ a nyelv alfabetája, P a levezetési, vagy másnéven helyettesítési szabályok összessége, S pedig a mondatszimbólum.

Chomsky-féle nyelvosztályok

A nyelvtanokat meghatározó helyettesítési szabályok (vagy másnéven levezetési szabályok) bonyolultsága alapján Chomsky a nyelveket osztályokba sorolta.

3-as nyelvosztály

A 3-as nyelvosztály nyelvtanaiban csak kétféle levezetési szabálytípus engedélyezett:

A → a illetve A → aB

ahol a nemterminális szimbólumokat nagy, a terminális szimbólumokat kis betűvel jelöljük.

Az ilyen alakú nyelvtanokat reguláris (jobbreguláris) nyelvtanoknak nevezzük. Ezek a nyelvtanok generálják a reguláris nyelveket.

2-es nyelvosztály

A 2-es nyelvosztály helyettesítési szabályainak alakja:

A → α

ahol α tetszőleges terminális és nemterminális szimbólumokat tartalmazható jelsorozat. Az ilyen alakú szabályokat úgy lehet értelmezni, hogy az A nemterminális szimbólum a környezetétől függetlenül bármikor helyettesíthető az α jelsorozattal. Ezért ezen nyelvosztály nyelveit környezetfüggetlen, Context Free (CF) nyelveknek nevezik.

1-es nyelvosztály

Az 1-es nyelvosztály helyettesítési szabályainak alakja:

βAγ → βαγ

azaz a A → α szabály csakis a β-γ környezetben alkalmazható. Ezért ezeket a nyelveket környezetfüggő, Context Sensitive (CS) nyelveknek nevezik.

0-ás nyelvosztály

A 0-ás nyelvosztályban alkalmazható szabályokra nézve nincsen korlátozás.

ANTLR nyelvtanok

Az ANTLR számára megadhatunk nyelvtanokat, amik nem mások, mint szabályok halmazai. Ezekből a szabályokból az ANTLR egy rekurzív-leszálló (recursive-descent) elemzőt készít, ami az adott nyelv mondatait ismeri fel, azaz eldönti, hogy az adott mondat eleme-e a nyelvnek, a mondat követi-e a nyelvnek a nyelvtanban leírt szabályait.

Például, az ANTLR jelölésrendszerét használva (ami nem más, mint az EBNF (Extended Backus-Naur Form) jelölésrendszer) egy C-szerű nyelv változódeklarációit leíró nyelvtan egy részlete így nézhet ki:

variableDef
 : declaration SEMICOLON
 | declaration EQUALS expr SEMICOLON
 ;

ahol a ':' előtt álló rész egy nemterminális szimbólum, az utáni rész pedig nemterminális (kis kezdőbetűvel kezdődő) és terminális (nagy kezdőbetűvel kezdődő) szimbólumok halmaza. Ez a levezetési szabály két alternatívát tartalmaz: egy sima változó deklaráció, vagy deklaráció inicializációval. Az alternatívákat a '|' szimbólum választja el.

Használva az előzőleg bevezetett formális jelölést, a fenti nyelvtan így néz ki:

• N: variableDef, declaration, expr
• ∑: SEMICOLON (';'), EQUALS ('='), illetve egyéb, a fenti szabályban fel nem sorolt karakterek
• P: a szabályok halmaza
• S: a mondatszimbólum, ahonnan indul a levezetés. ANTLR-ben bármelyik nemterminális szimbólum lehet mondatszimbólum.

Az EBNF jelölésrendszer CF nyelvtanok leírását teszi lehetővé. Sajnos több nyelv nem illeszkedik a CF nyelvosztályba, egy adott kifejezés szintaktikai értelmezéséhez szükséges a kontextus ismerete. Például, C++ nyelvben a T(i) kifejezés kétféleképpen is értelmezhető: lehet függvényhívás, vagy típuskonverzió is, attól függően, hogy T függvény-e, vagy egy típus.

Az ANTLR az ehhez hasonló problémákat úgynevezett predikátumok használatával oldja meg: szemantikus és szintaktikus predikátumokkal.

A szemantikus predikátumok szemantikus megszorításokat fejeznek ki. Három esetet különböztethetünk meg. Az első az ellenőrző (validating) szemantikus predikátumok esete, melyek logikai kifejezések, amik kiértékelése futásidőben történik. Ha a kifejezés hamis, akkor az adott szabály használata meghiúsul (az elemző kivételt dob). A szintaxis a következő: {*kifejezés*}?

Például, ha maximum 4 számból álló sorozatot akarunk értelmezni, használhatjuk az alábbi szabályt:

data: ( b+=BYTE )+ {$b.size()<=4}? 
 ; 

ahol egy $b nevű listát építünk a BYTE terminális szimbólumokból, egészen addig, amíg a lista mérete kisebb vagy egyenlő mint 4.

A második eset a "kapcsoló" (gated) szemantikus predikátumok használata, amik egy szabályon belül egy alternatíva használatát kapcsolják ki-be. Ezek szintén logikai kifejezések, melyek kiértékelése futásidőben történik. Ha a kifejezés hamis, akkor az adott alternatíva az elemző számára láthatatlan. Ennek használatára remek példa lehet az SQL nyelv, ahol különböző utasításokkal lehet ki vagy bekapcsolni a nyelv egy adott kiegészítését. Ennek szintaxisa {*kifejezés*}?=>

A "maximum 4 elem illesztése" megszorítást kapcsoló predikátumokkal is megoldhatjuk:

data
@init {int n=1;}
 : ( {n<=4}?=> BYTE {n++;} )+
 ;

ahol az @init részben deklarálunk egy n nevű lokális változót deklarálunk. A BYTE alternatíva csak akkor látszódik, ha a kifejezés (n<=4) értéke igaz.

Az utolsó pedig a többértelműséget feloldó szemantikus predikátumok esete. A szintaxis megegyezik az ellenőrző predikátumok szintaxisával. A működésük is igen hasonló. A különbség mindösszesen annyi, hogy a többértelműséget feloldó predikátumok csak akkor jutnak szerephez, ha a szintaxis maga nem egyértelmű.

Az ANTLR által generált LL(*) elemző (az LL(k) elemzők kiegészítése tetszőleges k értékkel) az alternatívák között egy véges automata (DFA) segítségével dönt. A többértelműséget feloldó predikátumok segítik a véges automatát a helyes döntés meghozatalában.


Felhasznált irodalom:

• Bach Iván: Formális nyelvek (Typotex Kiadó, 2001)
• Terence Parr: The Definitive ANTLR Reference: Building Domain-Specific Languages (Pragmatic Bookshelf, 2007)

A hétvégén tovább folytattam az ANTLR-el való ismerkedést. Az ANTLR egy parser-generátor, ami egy nyelvtan alapján generál egy rekurzív leszálló (recursive descent) szintaktikai elemzőt.

Egy elemző alapesetben nem csinál mást, minthogy eldönti, hogy egy adott mondat része-e a nyelvnek, szintaktikailag értelmes-e. Az ANTLR segítségével viszont könnyedén készíthetünk olyan nyelvtanokat, amikből a generált parser egy bemenő mondatból kimenetként egy absztrakt szintaxis fát (AST) állít elő. Ezt a fát bejárva akár kiértékelhetjük a bemenetet (utasításokat), akár transzformációkat végezve átfordíthatjuk egy másik nyelvre.

Terence Parr a könyvében azt javasolja, hogy AST-k bejárásához is használjunk nyelvtanokat, pontosabban egy nyelvtan leírásából generált parsert, aminek a bemeneti mondatai az AST-k, kimenete meg mondjuk egy StringTemplate sablon megfelelő kitöltése.

Ezt a folyamatot szemlélteti - szintén Parr könyvéből származó - ábra:

A Code Generation honlapján 2005-ben megjelent egy cikk, "Language Translation Using ANTLR and StringTemplate" címmel, amiben Terence Parr bemutatja, hogyan lehet egy fordítót készíteni, ami egy C-szerű nyelvből Java, Python, vagy Java bytecode kódot állít elő. A példa nyelvtanok sajnos még az ANTLR 2-es verziójával készültek, amit azóta több szempontból is felülmúlt a legújabb, 3-as verzió. A hétvégén ezt alakítottam át, hogy működjön a 3-as verzióval, és először egy AST-t generáljon, majd az AST-t bejárva töltse ki a sablonokat.

A nyelvtanok itt találhatóak:

A tesztelést megvalósító Java kód:

Működése pedig:

A teszt bemenet legyen a honlapon is fentlevő kódrészlet:

 char c;
 int x;
 int foo(int y, char d) {
   int i;
   for (i=0; i<3; i=i+1) {
     x=3;
     y=5;
   }
 }

Ezt Python-ra fordítva az alábbi kimenetet kapjuk:

kelda@psycho:~/ANTLR/cminus$ cat input.txt | java Test
(GLOBALS (VAR char c)) (GLOBALS (VAR int x)) (FUNCTIONS
(FUNCTION int foo (PARAMS (PARAM int y) (PARAM char d))
(BLOCK (LOCALS (VAR int i)) (STATEMENTS (FOR (INIT (= i
0)) (COND (< i 3)) (STMT (= i (+ i 1))) (BLOCK LOCALS
(STATEMENTS (= x 3) (= y 5))))))))

def foo(y, d):
  i = 0
  while ( i < 3 ):
      x = 3
      y = 5
      i = i + 1

Az elején az AST látható (gyökér levél1 levél2 ... levéln) formában, utána pedig a kimenet.

Ez a bejegyzés igazából nem akart másról szólni, minthogy illusztrálja az ANTLR és a StringTemplate erejét, a részletek bemutatása nélkül. Később részletesen is bemutatom majd a működését, a nyelvtanok felépítését, és hogy az egész hogyan is illeszkedik a blogomba :)

Egy kis segítségként annyit elárulhatok, hogy az SQL Developer egyik könyvtárában van egy oracle.sqldeveloper.migration.translation.sqlserver.jar file, aminek a belsejében található egy generic.stg és egy tsql.stg StringTemplate sablon. Azaz az SQL Developer Migration Workbench is az ANTLR és a StringTemplate segítségével végzi a nyelvi fordítást.