Mondom a szitut. Megkapod melóban a taskot, hogy kéne írni mondjuk Java-hoz egy interface extractort, ami egy Java forrásfile-hoz elkészít az abban levő osztályhoz egy interface-et, ha az osztály neve ClassName, akkor az interface neve legyen IClassName, az összes metódust, amit az osztályban deklaráltunk, kapja meg az interface (konstruktort ofc nem), ha ClassName implementál valami interface-et, akkor azt extendelje IClassName,
ezt reflectionnel meg lehet csinálni
a metódus argumentumok neve legyen az interface-ben ugyanaz, mint az osztályban volt,
wat.. ok, akkor javac -parameters, aztán reflection
és a metódus deklarációjában levő kommentek is maradjanak.
hell no
Tehát ha van egy input file, hogy
class Schanyi<T> implements ITuroRudiListener<T> {
Schanyi( String paramparam ){...}
int getTomegAram( String kiszerint /* sokan kerdezik */ ) {
return 42;
}
void setTomegAram( String ki /* ohaten */, int newValue ){
/* TODO do something, srsly */
}
}
akkor ebből legyen az az output, hogy
interface ISchanyi<T> extends ITuroRudiListener<T> {
int getTomegAram( String kiszerint /* sokan kerdezik */ );
void setTomegAram( String ki /* ohaten */, int newValue );
}
ok, challenge accepted.
A persze az lenne, ha minél több részt garantáltan működő 3rdparty toolok csinálnának és csak keveset kéne kódolni hozzá. A Java nyelv is szintaktikailag egy CF nyelvtannal leírható (azon a szinten, ahogy most szükség van erre), és ha építenénk egy parse treet a forráskódhoz, akkor abban már "csak" DOM-barangolással ki tudunk szedni minden információt. Ezúttal nem a bottom-up JFlex+CUP megoldásunkat fogjuk használni, hanem a top-down ANTLR-t izzítjuk be, hogy lássunk ilyet is.
Egy egész kis elmélet: a top-down azt jelenti, hogy a parser kiindul a nyelvtan kezdőszimbólumából, aztán minden egyes lépésben alkalmaz egy szabályt, és ezzel direktben megpróbálja levezetni a stringet, közben ha olyan, akkor backtrackelhet is. Megint megkülönböztetünk olyan parsereket, amik az input soron következő $k$ tokenjét előrenézve hoznak döntést (ahogy az LR($k$) parserek előrenéztek $k$ karaktert és ebből, meg a parser állapotából döntöttek, hogy shift legyen vagy reduce; ott a gyakorlatban $k=1$ szokott lenni), és ennek, meg az aktuális átírandó nemterminálisnak (baloldali levezetést csinálunk, vagyis mindig az első nemterminálist írjuk át - az LR($k$) parserek egyébként egy jobboldali levezetést csinálnak meg visszafele) meg esetleg a belső állapotuknak függvényében döntik el, hogy melyik szabályt hajtsák végre. Ha ezt determinisztikusan tudják csinálni, és nem kell backtrack, akkor LL($k$) parsernek hívjuk.
Nézzünk egy példát: a "végezzünk bitműveleteket" történet,
A $\to$ Conj | Conj 'V' A
Conj $\to$ Neg | Neg '&' Conj
Neg $\to$ Atom | '-' Atom
Atom $\to$ '0' | '1' | (A)
hát még erre sincs LL($k$) parser. Miért? Mert mondjuk rögzítsünk egy $k$-t. Akkor az is egy valid kifejezés ebben a nyelvtanban, hogy ((..(0)..), meg az is, hogy ((..(0)..)V1, ahol $k$ darab nyitócsukójel van. A parser első körben azt látja mindkét esetben, hogy jön $k$ darab nyitójel, ő valami kezdőállapotban van, és az A nemterminálisból kéne elindulni, de nyilván nem tudja ebből kitalálni, hogy az A $\to$ Conj (első esetben) vagy az A $\to$ Conj 'V' A (másodikban) szabályt aktiválja.
Persze egy LR($1$) parser simán megeszi ezt, láttuk, hogy az egész shunting yardolható operátor precedencia nyelvtanos történetek mind shift-reduce parsolhatóak. Redukálni kell, ha a parse tree stack tetején '0', '1', (A), Atom, '-' Atom, Neg '&' Conj vagy Conj 'V' A áll, meg akkor, ha Neg és a következő token nem egy '&', meg akkor is, ha Conj és a következő token nem egy 'V'. Egyébként meg shiftelni, clear.
Persze egy LR($1$) parser simán megeszi ezt, láttuk, hogy az egész shunting yardolható operátor precedencia nyelvtanos történetek mind shift-reduce parsolhatóak. Redukálni kell, ha a parse tree stack tetején '0', '1', (A), Atom, '-' Atom, Neg '&' Conj vagy Conj 'V' A áll, meg akkor, ha Neg és a következő token nem egy '&', meg akkor is, ha Conj és a következő token nem egy 'V'. Egyébként meg shiftelni, clear.
Ha még egy kicsit tudni akarunk az LL($k$) és az LR parsolható nyelvekről, hát, az összes LL($k$) parsolható nyelv LR($1$) (bár magát a nyelvtant lehet, hogy fésülni kell hozzá egy kicsit). Tehát egy determinisztikus, konstans sok szimbólumot előrenéző top-down parsolható nyelv mindig parsolható bottom-up, egy szimbólum előrenézésével.
Persze felmerül a kérdés, hogy akkor minek foglalkozik bárki top-down parserekkel? Nos, a top-down nem szinonimája az LL($k$)-nak. A fenti nyelvre egy teljesen jó leszálló parser az, hogy
parseA(){
ret = parseConj();
if( peek() == 'V' ) { getch(); return A( ret, parseA() ); }
return A( ret );
}
parseConj(){
ret = parseNeg();
if( peek() == '&' ) { getch(); return Conj(ret, parseConj() ); }
return Conj( ret );
}
parseNeg(){
if( peek() == '-' ) { getch(); return Neg('-', parseAtom() ); }
return parseAtom();
}
parseAtom(){
c = getch();
switch( c ){
case '0':
case '1': return Atom( c );
case '(': ret = parseA();
if( peek() == ')' ) {
getch();
return Atom( '(', ret, ')' );
}
default: throw "helpful message: undefined is not a function"
}
}
és ha megnézzük, ez a parser egyrészt determinisztikus, másrészt csak egy karaktert néz mindig előre az inputban. Az igaz, hogy a szabály illesztésének az elején még nem tudja, hogy mit kellene tegyen az alternatívák közül, de közben eldől. És ami pozitívum: mindenképp sokkal olvashatóbb ennek a parsernek a kódja, és világosabb, hogy mi miért történik (debugkor etc), mint a fentebbi shift-reduce algoritmusnál.
Tippre ez a kód a következő, ekvivalens nyelvtannak megfelelően parsol:
A $\to$ Conj ConjTail
ConjTail $\to\ \varepsilon$ | 'V' A
Conj $\to$ Neg NegTail
NegTail $\to\ \varepsilon$ | '&' Conj
Neg $\to$ '-' Atom | Atom
Atom $\to$ '0' | '1' | '(' A ')'
Tippre ez a kód a következő, ekvivalens nyelvtannak megfelelően parsol:
A $\to$ Conj ConjTail
ConjTail $\to\ \varepsilon$ | 'V' A
Conj $\to$ Neg NegTail
NegTail $\to\ \varepsilon$ | '&' Conj
Neg $\to$ '-' Atom | Atom
Atom $\to$ '0' | '1' | '(' A ')'
ami viszont már egyébként LL($1$)-nek is látszik.
A fenti parser kódot, amikor is minden nemterminálisnak kb megfelel egy metódus, ami belül eldönti, hogy melyik szabályt alkalmazzuk, és ezen metódusok a szabályoknak megfelelően kölcsönösen rekurzívan hívják egymást, recursive descent parsernek hívják. Ha ezt még ráadásul úgy is teszi, hogy backtrackre nincs szükség (mint fent), akkor pedig predictive parsernek.
Ökölszabály, hogy ha a nyelvtanunkban van $A\to A\alpha$ ún. balrekurzív szabály (vagy nemterminális), akkor azt nem lehet top-down parsolni (mert akkor a metódus olvasás nélkül végtelen ciklusban hívná magát).
Ökölszabály, hogy ha a nyelvtanunkban van $A\to A\alpha$ ún. balrekurzív szabály (vagy nemterminális), akkor azt nem lehet top-down parsolni (mert akkor a metódus olvasás nélkül végtelen ciklusban hívná magát).
Ez OK, így van, viszont van balrekurzió-mentesítés, ami ekvivalens, balrekurzió-mentes nyelvtant ad, amire még talán lehet is top-down parsert írni. Írnék én a balrekurzió-mentesítésről is szívesen, DE most nem fogok!
Mert van az ANTLR nevű parser generátor, ami az input nyelvtanunkhoz készít egy recursive descent (egyébként egész olvasható) parsert, a legújabb változatába bele van égetve már a közvetlen balrekurzió-mentesítés is (azért az $A\to B\alpha$, $B\to A\beta$ szabályok kifognak rajta :P ), és megpróbál prediktív parsert építeni, de ha nem sikerül, akkor backtrackelő recursive descent lesz belőle.
A következő postban ANTLR-rel fogjuk megoldani a post elején feldobott kérdést és írunk egy java forrásból interface extractor kódot, amiből tényleges kódot írnunk csak pár tucat sort kell, tops. Jó lesz.
folytköv
