Formális nyelvek és az ANTLR
2009. március 29., vasárnap by Zoltan Tanczos
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:
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:
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:
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:
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:
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)
