CF parsing: top-down, LL(k), recursive descent, predictive

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.

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 ')'

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). 

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