Hľadáte lex a yacc pre Java? Jacka nepoznáš

Spoločnosť Sun vydala Jack, nový nástroj napísaný v jazyku Java, ktorý automaticky generuje analyzátory zostavením vysokej gramatickej špecifikácie uloženej v textovom súbore. Tento článok bude slúžiť ako úvod do tohto nového nástroja. Prvá časť článku obsahuje krátky úvod do automatického generovania syntaktického analyzátora a moje prvé skúsenosti s nimi. Potom sa článok zameria na Jacka a na to, ako ho môžete použiť na generovanie syntaktických analyzátorov a aplikácií vytvorených s týmito syntaktickými analyzátormi na základe vašej gramatiky na vysokej úrovni.

Automatické generovanie syntaktického analyzátora kompilátora

Analyzátor je jednou z najbežnejších súčastí počítačovej aplikácie. Konvertuje text, ktorý môžu ľudia prečítať, na dátové štruktúry známe ako syntaktické stromy, ktorým počítač rozumie. Výrazne si pamätám môj úvod do automatického generovania syntaktického analyzátora: Na vysokej škole som absolvoval hodinu o konštrukcii kompilátora. S pomocou svojej manželky som napísal jednoduchý kompilátor, ktorý dokázal z programov napísaných v jazyku, ktorý je určený pre celú triedu, urobiť spustiteľné programy. Pamätám si, že som sa v tom okamihu cítil veľmi úspešne.

Vo svojej prvej „skutočnej“ práci po vysokej škole som dostal úlohu vytvoriť nový jazyk pre grafické spracovanie, ktorý by sa dal kompilovať do príkazov pre grafický koprocesor. Začal som s čerstvo zostavenou gramatikou a pripravil som sa na spustenie viactýždňového projektu zostavenia kompilátora. Potom mi priateľ ukázal nástroje Unixu lex a yacc. Lex - zostavil lexikálne analyzátory z regulárnych výrazov a - yacc zmenšil gramatickú špecifikáciu na tabuľkový kompilátor, ktorý dokázal produkovať kód, keď úspešne analyzoval produkcie z tejto gramatiky. použil som lex a yacc, a za necelý týždeň bol môj kompilátor funkčný! Neskôr GNU projekt Free Software Foundation vytvoril „vylepšené“ verzie servera lex a yacc - menovaný flex a bizón - na použitie na platformách, na ktorých nebol spustený derivát operačného systému Unix.

Svet automatického generovania syntaktického analyzátora opäť pokročil, keď Terrence Parr, ktorý bol študentom univerzity Purdue, vytvoril Purdue Compiler Construction Tool Set alebo PCCTS. Dve zložky PCCTS - DFA a ANTLR - poskytovať rovnaké funkcie ako lex a yacc; avšak gramatiky, ktoré ANTLR akceptuje gramatiky LL (k) oproti gramatikám LALR, ktoré používa yacc. Okrem toho je kód, ktorý generuje PCCTS, oveľa čitateľnejší ako kód vygenerovaný yacc. Generovaním kódu, ktorý je ľahšie čitateľný, PCCTS uľahčuje ľudskému čítaniu kódu pochopiť, čo jednotlivé kúsky robia. Toto pochopenie môže byť nevyhnutné pri pokuse o diagnostiku chýb v gramatickej špecifikácii. PCCTS rýchlo vyvinul sled ľudí, ktorým sa jeho súbory zdali ľahšie použiteľné ako yacc.

Sila automatického generovania syntaktického analyzátora spočíva v tom, že umožňuje používateľom sústrediť sa na gramatiku a obávať sa správnosti implementácie. Môže to byť obrovská úspora času pri jednoduchých aj zložitých projektoch.

Jack vykročí k tanieru

Nástroje hodnotím podľa všeobecnosti problému, ktorý riešia. Pretože sa požiadavka na analyzovanie zadávania textu objavuje znovu a znovu, v mojom paneli nástrojov je automatické generovanie syntaktického analyzátora veľmi vysoké. V kombinácii s rýchlym vývojovým cyklom Java poskytuje automatické generovanie syntaktického analyzátora nástroj na návrh kompilátora, ktorý je ťažké poraziť.

Jack (rýmuje sa na yacc) je generátor syntaktického analyzátora v duchu PCCTS, ktorý spoločnosť Sun bezplatne vydala pre programátorskú komunitu Java. Jack je mimoriadne ľahko opísateľný nástroj: Jednoducho povedané, dáte mu sadu kombinovaných gramatických a lexingových pravidiel vo forme súboru .jack a nástroj spustíte. Vráti vám triedu Java, ktorá túto gramatiku analyzuje. Čo môže byť jednoduchšie?

Získať Jacka je tiež celkom ľahké. Najskôr si stiahnete kópiu z domovskej stránky spoločnosti Jack. To k vám prichádza v podobe samostatne rozbaľovacej triedy Java s názvom Inštalácia. Ak chcete nainštalovať Jack, musíte to vyvolať Inštalácia triedy, ktorá sa na počítači so systémom Windows 95 vykonáva pomocou príkazu: C:> inštalácia Java.

Vyššie uvedený príkaz predpokladá, že java príkaz je vo vašej ceste príkazu a že cesta triedy bola nastavená správne. Ak vyššie uvedený príkaz nefungoval alebo ak si nie ste istí, či máte alebo nemáte veci správne nastavené, otvorte okno MS-DOS prechodom cez položky ponuky Štart -> Programy - MS-DOS. Ak máte nainštalovaný Sun JDK, môžete napísať tieto príkazy:

C:> cesta C: \ java \ bin;% cesta% C:> nastaviť CLASSPATH = .; c: \ java \ lib \ classes.zip 

Ak je nainštalovaná Symantec Cafe verzia 1.2 alebo novšia, môžete zadať tieto príkazy:

C:> cesta C: \ cafe \ java \ bin;% cesta% 

Cesta k triede by už mala byť nastavená v súbore s názvom sc.ini v priečinku bin kaviarne.

Ďalej zadajte znak inštalácia Java príkaz zhora. Inštalačný program sa vás spýta, do ktorého adresára chcete inštalovať, a pod ním sa vytvorí podadresár Jack.

Pomocou Jacka

Jack je celý napísaný v jazyku Java, takže mať triedy Jacka znamená, že tento nástroj je okamžite k dispozícii na každej platforme, ktorá podporuje virtuálny stroj Java. Znamená to však tiež, že v oknách systému Windows musíte Jacka spustiť z príkazového riadku. Povedzme, že ste si vybrali názov adresára JavaTools pri inštalácii Jacka do vášho systému. Aby ste mohli použiť Jacka, budete musieť na cestu triedy pridať Jackove triedy. Môžete to urobiť vo svojom autoexec.bat súboru alebo vo vašom .cshrc súbor, ak ste používateľom systému Unix. Kritický príkaz je niečo ako riadok zobrazený nižšie:

C:> nastaviť CLASSPATH = .; C: \ JavaTools \ Jack \ java; C: \ java \ lib \ classes.zip 

Upozorňujeme, že používatelia kaviarne Symantec Cafe môžu upravovať sc.ini súbor a zahrnúť tam Jackove triedy, alebo môžu nastaviť CLASSPATH výslovne, ako je uvedené vyššie.

Nastavením premennej prostredia, ako je uvedené vyššie, sa triedy Jack umiestnia do súboru CLASSPATH medzi „.“ (aktuálny adresár) a základné systémové triedy pre Javu. Hlavná trieda pre Jacka je COM.sun.labs.jack.Hlavná. Veľké písmená sú dôležité! Príkaz obsahuje presne štyri veľké písmená („C“, „O“, „M“ a ďalšie „M“). Ak chcete Jacka spustiť manuálne, zadajte príkaz:

C:> Java COM.sun.labs.jack.Main parser-input.jack

Ak na ceste k triede nemáte súbory Jack, môžete použiť tento príkaz:

C:> java -classpath.; C: \ JavaTools \ Jack \ java; c: \ java \ lib \ classes.zip COM.sun.labs.jack. Hlavný analyzátor-vstup.jack 

Ako vidíte, toto sa trochu predlžuje. Aby som minimalizoval písanie, dal som vyvolanie do a .bat súbor s názvom Jack.bat. V určitom okamihu v budúcnosti bude k dispozícii jednoduchý program C wrapper, možno aj keď si to prečítate. Dostupnosť tohto a ďalších programov nájdete na domovskej stránke spoločnosti Jack.

Keď je Jack spustený, vytvorí v aktuálnom adresári niekoľko súborov, ktoré neskôr skompilujete do svojho analyzátora. Väčšina z nich má predponu s menom vášho analyzátora alebo sú spoločné pre všetky analyzátory. Jeden z nich však ASCII_CharStream.java, sa môže zraziť s inými analyzátormi, takže je pravdepodobne dobrý nápad začať v adresári obsahujúcom iba súbor . Jack súbor, ktorý použijete na generovanie syntaktického analyzátora.

Ak raz spustíte Jacka, bude mať kopa ďalších, ak generácia prebehla hladko .java súbory v aktuálnom adresári s rôznymi zaujímavými názvami. Toto sú vaše analyzátory. Odporúčam vám otvoriť ich s editorom a prezrieť si ich. Keď ste pripravení, môžete ich zostaviť pomocou príkazu

C:> javac -d. ParserName.java

kde Názov analyzátora je meno, ktoré ste zadali svojmu analyzátoru vo vstupnom súbore. O tom trochu viac. Ak sa všetky súbory pre váš analyzátor nezkompilujú, môžete použiť metódu hrubej sily pri písaní:

C:> javac * .java 

Takto sa zostaví všetko v adresári. V tomto okamihu je váš nový analyzátor pripravený na použitie.

Popisy Jack Parseru

Príponu majú súbory popisu analyzátora Jack . Jack a sú rozdelené do troch základných častí: opcie a základná trieda; lexikálne žetóny; a terminály. Pozrime sa na jednoduchý popis syntaktického analyzátora (je obsiahnutý v príklady adresár, ktorý sa dodáva s Jackom).

možnosti {LOOKAHEAD = 1; } PARSER_BEGIN (Jednoduché1) verejná trieda Jednoduché1 {public static void main (String args []) hodí ParseError { Jednoduché1 analyzátor = nový Jednoduché1(System.in); parser.Input (); }} PARSER_END (Jednoduché1) 

Prvých pár riadkov vyššie popisuje možnosti pre syntaktický analyzátor; v tomto prípade POZERAŤ SA DOPREDU je nastavená na 1. Tu je možné nastaviť aj ďalšie možnosti, napríklad diagnostiku, spracovanie Java Unicode atď. Po týchto možnostiach nasleduje základná trieda syntaktického analyzátora. Tieto dve značky PARSER_BEGIN a PARSER_END zložiť triedu, ktorá sa stane základným kódom Java pre výsledný syntaktický analyzátor. Upozorňujeme, že názov triedy použitý v špecifikácii syntaktického analyzátora musieť rovnaké na začiatku, v strede aj na konci tejto časti. V príklade vyššie som uviedol názov triedy tučným písmom, aby bolo jasnejšie. Ako môžete vidieť v kóde vyššie, táto trieda definuje statiku hlavný metóda, aby mohla triedu vyvolať interpret Java v príkazovom riadku. The hlavný metóda jednoducho vytvorí inštanciu nového syntaktického analyzátora so vstupným tokom (v tomto prípade System.in) a potom vyvolá Vstup metóda. The Vstup metóda je v našej gramatike neterminálna a je definovaná vo forme prvku EBNF. EBNF je skratka pre Extended Backus-Naur Form. Forma Backus-Naur je metóda na určovanie bezkontextových gramatík. Špecifikácia pozostáva z a terminál na ľavej strane produkčný symbol, ktorý je zvyčajne „:: =“, a jeden alebo viac inscenácie na pravej strane. Použitý zápis je zvyčajne asi taký:

 Kľúčové slovo :: = "ak" | "potom" | "inak" 

Toto by sa čítalo ako: „The Kľúčové slovo terminal je jedným z reťazcových literálov „if“, „then“ alebo „else.“ „V Jackovi je tento formulár rozšírený tak, aby umožňoval reprezentáciu ľavej časti metódou a alternatívne rozšírenia môžu byť reprezentované regulárne výrazy alebo iné neterminály. Pokračovanie nášho jednoduchého príkladu obsahuje súbor nasledujúce definície:

void Input (): {} {MatchedBraces () "\ n"} void MatchedBraces (): {} {"{" [MatchedBraces ()] "}"} 

Tento jednoduchý syntaktický analyzátor analyzuje gramatiku uvedenú nižšie:

Kurzívou som označil neterminály na pravej strane produkcie a tučným písmom literály. Ako vidíte, gramatika jednoducho analyzuje zhodné sady zložených zátvorkách znakov „{“ a „}“. V súbore Jack existujú dve produkcie, ktoré popisujú túto gramatiku. Prvý terminál, Vstup, je touto definíciou definovaná ako tri položky v poradí: a Zhodné zátvorky terminál, znak nového riadku a token konca súboru. The Token definuje Jack, aby ste ho nemuseli špecifikovať pre svoju platformu.

Keď sa vygeneruje táto gramatika, ľavá strana inscenácie sa zmení na metódy vo vnútri Jednoduché1 trieda; po zostavení Jednoduché1 trieda číta znaky z Systém.v a overí, či obsahujú zodpovedajúcu sadu zložených zátvoriek. To sa dosiahne vyvolaním vygenerovanej metódy Vstup, ktorý sa generačným procesom transformuje na metódu, ktorá analyzuje an Vstup nekoncový. Ak syntaktická analýza zlyhá, metóda vyvolá výnimku ParseError, ktoré môže hlavná rutina zachytiť a potom sa sťažovať, ak sa tak rozhodne.

Samozrejme je toho viac. Blok vymedzený znakmi „{“ a „}“ za názvom terminálu - ktorý je v tomto príklade prázdny - môže obsahovať ľubovoľný kód Java, ktorý je vložený do prednej časti vygenerovanej metódy. Potom po každej expanzii existuje ďalší voliteľný blok, ktorý môže obsahovať ľubovoľný kód Java, ktorý sa má vykonať, keď syntaktický analyzátor úspešne zodpovedá tejto expanzii.

Zložitejší príklad

A čo tak príklad, ktorý je trochu komplikovanejší? Zvážte nasledujúcu gramatiku, opäť rozdelenú na kúsky. Táto gramatika slúži na interpretáciu matematických rovníc pomocou štyroch základných operátorov - sčítanie, násobenie, odčítanie a delenie. Zdroj nájdete tu:

možnosti {LOOKAHEAD = 1; } PARSER_BEGIN (Calc1) verejná trieda Calc1 {public static void main (String args []) hodí ParseError {Calc1 parser = nový Calc1 (System.in); while (true) {System.out.print ("Zadajte výraz:"); System.out.flush (); skus {switch (parser.one_line ()) {case -1: System.exit (0); predvolené: break; }} catch (ParseError x) {System.out.println ("Končí sa."); hodiť x; }}}} PARSER_END (Calc1) 

Prvá časť je takmer rovnaká ako Jednoduché1, až na to, že hlavná rutina teraz volá terminál jedna čiara opakovane, kým sa nepodarí analyzovať. Ďalej nasleduje nasledujúci kód:

IGNORE_IN_BNF: {} "" TOKEN: {} {} TOKEN: / * OPERATORS * / {} TOKEN: {} 

Tieto definície pokrývajú základné terminály, v ktorých je špecifikovaná gramatika. Prvý, menovaný IGNORE_IN_BNF, je špeciálny token. Akékoľvek tokeny načítané syntaktickým analyzátorom, ktoré sa zhodujú so znakmi definovanými v IGNORE_IN_BNF token sú ticho zahodené. Ako vidíte v našom príklade, toto spôsobí, že syntaktický analyzátor vo vstupe ignoruje znaky medzery, tabulátory a znaky návratu na koniec.