Oracle Business Intelligence

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.

Ebben a félévben főleg a diplomatervem elkészítésével fogok foglalkozni, melynek címe:

azaz az előző féléves önálló labor témámat folytatom. A diplomaterv kiírásom pontjai:

Az első pont egy kicsit trükkös, ugyanis eddig igen kevés releváns szakirodalmat sikerült találnom. Amit találtam, azok is főleg az adatok migrációjával foglalkozik. Ezek közül kiemelendő Erik Peter Bansleben diplomamunkája az esettanulmány hasonlósága miatt:

The source systems consisted of a combination of Microsoft SQL Server and Access databases, while the target platform was an Oracle 9i server which was to serve as the backend database for the new system.

Ha esetleg tud valaki a témába vágó irodalomról, megköszönném, ha jelezné akár hozzászólásban, akár e-mailben: orveny kukac gmail pont com. Nagy segítség lenne :)

Az előző félévben gyakorlatilag a második ponttal foglalkoztam, így úgy érzem, ez nem fog különösebb kihívást jelenteni.

Ami érdekesebb, az a 3. és 4. pont: gyakorlatilag egy Transact-SQL -> PL/SQL fordítót kell készítenem. Szerencsére rátaláltam az ANTLR framework-re, aminek segítségével egy nyelvtanból viszonylag könnyedén lehet szintaktikus elemzőket, fordítókat készíteni.

A honlapján megtalálható Dermott O'Neill-től, az SQL Developer egyik fejlesztőjétől egy idézet:

The decision to use Antlr and StringTemplate for Oracles next generation Migration and SQL Developer features was easy due to the fantastic support on the forums, extensive documentation and great tools. In particular, the ability to parse trees and define target languages using StringTemplate, provided the end to end language translation technology we required. Other parser generators left us high and dry with only half the solution.

Egyelőre még csak az irodalom feldolgozás fázisában tartok, de mindenesetre igen bíztató, hogy egy olyan eszköz használatát tanulom, amivel az SQL Developer Migration Workbench is működik :)