Iščete lex in yacc za Javo? Jacka ne poznaš

Sun je izdal Jack, novo orodje, napisano v Javi, ki samodejno generira razčlenjevalnike s sestavljanjem slovnične specifikacije na visoki ravni, shranjene v besedilni datoteki. Ta članek bo uvod v to novo orodje. Prvi del članka zajema kratek uvod v samodejno generiranje razčlenjevalnikov in moje prve izkušnje z njimi. Nato se bo članek osredotočil na Jacka in kako ga lahko uporabite za ustvarjanje razčlenjevalnikov in aplikacij, zgrajenih s temi razčlenjevalniki, na podlagi vaše slovnice na visoki ravni.

Samodejno generiranje razčlenjevalnika prevajalnika

Razčlenjevalnik je ena najpogostejših komponent računalniške aplikacije. Besedilo, ki ga lahko preberejo ljudje, pretvori v podatkovne strukture, znane kot razčlenjevalna drevesa, ki jih računalnik razume. Jasno se spominjam svojega uvajanja v samodejno generiranje razčlenjevalnikov: na fakulteti sem zaključil predavanje o konstrukciji prevajalnikov. S pomočjo svoje žene sem napisal preprost prevajalnik, ki je lahko programe, napisane v jeziku, pripravljenem za ta razred, spremenil v izvedljive programe. Spomnim se, da sem se takrat počutil zelo uspešno.

V svojem prvem "resničnem" delu po fakulteti sem dobil nalogo za ustvarjanje novega jezika za obdelavo grafike, ki bi ga zbral v ukaze za grafični koprocesor. Začel sem s sveže sestavljeno slovnico in se pripravljal na začetek večtedenskega projekta sestavljanja prevajalnika. Potem mi je prijatelj pokazal pripomočke Unix lex in yacc. Lex - zgradil leksikalne analizatorje iz regularnih izrazov in yacc znižal specifikacijo slovnice v prevajalnik, ki ga poganja tabela in lahko proizvaja kodo, ko je uspešno razčlenil produkcije iz te slovnice. uporabil sem lex in yacc, in čez manj kot teden dni je bil moj prevajalnik zagnan! Kasneje je projekt GNU Free Software Foundation ustvaril "izboljšane" različice lex in yacc - imenovan fleks in bizon - za uporabo na platformah, ki niso imele izpeljanke operacijskega sistema Unix.

Svet avtomatske generacije razčlenjevalnikov je spet napredoval, ko je Terrence Parr, takrat študent na univerzi Purdue, ustvaril komplet orodij za izdelavo prevajalnikov Purdue ali PCCTS. Dve komponenti PCCTS - DFA in ANTLR - zagotavljajo enake funkcije kot lex in yacc; vendar slovnice to ANTLR sprejema slovnice LL (k) v nasprotju s slovnicami LALR, ki jih uporablja yacc. Poleg tega je koda, ki jo ustvari PCCTS, veliko bolj berljiva kot koda, ki jo ustvari yacc. Z ustvarjanjem kode, ki je lažje berljiva, PCCTS olajša človeku, ki bere kodo, razumeti, kaj delajo različni deli. To razumevanje je lahko bistvenega pomena pri poskusu diagnosticiranja napak v slovnični specifikaciji. PCCTS je hitro razvil naslednje ljudi, ki se jim zdijo datoteke lažje uporabljati kot yacc.

Moč samodejnega ustvarjanja razčlenjevalnika je v tem, da uporabnikom omogoča, da se osredotočijo na slovnico in ne skrbijo za pravilnost izvedbe. To lahko izjemno prihrani čas tako pri preprostih kot pri zapletenih projektih.

Jack stopi do krožnika

Orodja ocenjujem po splošnosti problema, ki ga rešujejo. Ko se vedno znova pojavlja zahteva po razčlenjevanju vnosa besedila, samodejno ustvarjanje razčlenjevalnika v moji orodjarni dosega precej visoko stopnjo. V kombinaciji s hitrim razvojnim ciklom Jave samodejno ustvarjanje razčlenjevalnikov ponuja orodje za oblikovanje prevajalnikov, ki ga je težko premagati.

Jack (rima z yacc) je generator razčlenjevalnika, v duhu PCCTS, ki ga je Sun brezplačno izdal programski skupnosti Java. Jack je izjemno enostavno orodje za opis: preprosto povedano, daste mu nabor kombiniranih slovničnih pravil in pravil leksiranja v obliki datoteke .jack in zaženete orodje, nato pa dobite nazaj razred Java, ki bo razčlenil to slovnico. Kaj bi lahko bilo lažje?

Doseči Jacka je prav tako enostavno. Najprej prenesete kopijo z domače strani Jacka. To pride do vas v obliki samopakiranega razreda Java, imenovanega namestite. Če želite namestiti Jack, morate to priklicati namestite razreda, ki se v računalniku z operacijskim sistemom Windows 95 izvede z ukazom: C:> namestitev jave.

Zgoraj prikazani ukaz predpostavlja, da java ukaz je v vaši ukazni poti in da je pot razreda nastavljena ustrezno. Če zgornji ukaz ni deloval ali če niste prepričani, ali so stvari nastavljene pravilno, odprite okno MS-DOS tako, da prehodite elemente menija Start-> Programs-> MS-DOS Prompt. Če imate nameščen Sun JDK, lahko vnesete te ukaze:

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

Če je nameščena različica Symantec Cafe različice 1.2 ali novejša, lahko vnesete te ukaze:

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

Pot razreda mora biti že nastavljena v datoteki z imenom sc.ini v bin imeniku Cafe.

Nato vnesite namestite java ukaz od zgoraj. Namestitveni program vas bo vprašal, v kateri imenik želite namestiti, pod tem pa bo ustvarjen podimenik Jack.

Uporaba Jacka

Jack je v celoti napisan na Javi, zato je z razredi Jack to orodje takoj na voljo na vseh platformah, ki podpirajo navidezni stroj Java. Vendar pa to tudi pomeni, da morate v oknih s sistemom Windows zagnati Jack iz ukazne vrstice. Recimo, da ste izbrali ime imenika JavaTools, ko ste Jack namestili v sistem. Če želite uporabljati Jacka, boste morali svoji poti predavanja dodati Jackove razrede. To lahko storite v svojem autoexec.bat datoteko ali v vašem .cshrc datoteko, če ste uporabnik Unixa. Kritični ukaz je podoben spodnji vrstici:

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

Uporabniki kavarne Symantec Cafe lahko urejajo datoteko sc.ini datoteko in tam vključite razrede Jack, ali pa jih lahko nastavijo ZAPRTI kot je prikazano zgoraj.

Nastavitev spremenljivke okolja, kot je prikazano zgoraj, postavlja razrede Jack v ZAPRTI med "." (trenutni imenik) in osnovni sistemski razredi za Javo. Glavni razred za Jacka je COM.sun.labs.jack.Main. Kapitalizacija je pomembna! V ukazu so natanko štiri velike črke ('C', 'O', 'M' in druga 'M'). Če želite Jack zagnati ročno, vnesite ukaz:

C:> java COM.sun.labs.jack.Main razčlenjevalnik-input.jack

Če v poti predavanja nimate datotek Jack, lahko uporabite ta ukaz:

C:> java -classpath.; C: \ JavaTools \ Jack \ java; c: \ java \ lib \ classes.zip COM.sun.labs.jack.Main parser-input.jack 

Kot lahko vidite, je to nekoliko dolgo. Da bi čim manj zmanjšal tipkanje, sem klic postavil v .netopir datoteka z imenom Jack.bat. Nekoč v prihodnosti bo na voljo preprost program za zavijanje C, morda tudi ko to preberete. Oglejte si Jackovo domačo stran, da najdete ta in druge programe.

Ko zaženete Jack, v trenutnem imeniku ustvari več datotek, ki jih boste pozneje zbrali v svoj razčlenjevalnik. Večina ima predpono z imenom vašega razčlenjevalnika ali pa je skupna vsem razčlenjevalnikom. Eden od teh pa je ASCII_CharStream.java, lahko trči z drugimi razčlenjevalniki, zato je verjetno dobro začeti v imeniku, ki vsebuje samo .jack datoteko, ki jo boste uporabili za ustvarjanje razčlenjevalnika.

Ko zaženete Jacka, jih boste imeli, če je generacija šla brez težav .java datoteke v trenutnem imeniku z različnimi zanimivimi imeni. To so vaši razčlenjevalniki. Priporočam vam, da jih odprete z urejevalnikom in si jih ogledate. Ko ste pripravljeni, jih lahko sestavite z ukazom

C:> javac -d. ParserName.java

kje ParserName je ime, ki ste ga v vhodni datoteki dali svojemu razčlenjevalniku. Več o tem čez nekaj. Če se vse datoteke za vaš razčlenjevalnik ne prevedejo, lahko uporabite tip brute force:

C:> javac * .java 

Tako boste zbrali vse v imeniku. Na tej točki je vaš novi razčlenjevalnik pripravljen za uporabo.

Jack parser opisi

Datoteke opisov Jack parser imajo pripono .jack in so razdeljeni na tri osnovne dele: možnosti in osnovni razred; leksikalni žetoni; in ne-terminali. Oglejmo si preprost opis razčlenjevalnika (ta je vključen v primeri imenik, ki je priložen Jacku).

možnosti {LOOKAHEAD = 1; } PARSER_BEGIN (Preprosto1) javni razred Preprosto1 {public static void main (String args []) vrže ParseError { Preprosto1 razčlenjevalnik = nov Preprosto1(System.in); razčlenjevalnik.Input (); }} PARSER_END (Preprosto1) 

Prvih nekaj vrstic zgoraj opisuje možnosti za razčlenjevalnik; v tem primeru GLEJ NAPREJ je nastavljena na 1. Tu lahko nastavite tudi druge možnosti, kot so diagnostika, obdelava Java Unicode itd. Po možnosti sledi osnovni razred razčlenjevalnika. Obe oznaki PARSER_BEGIN in PARSER_END oklepaj razred, ki postane osnovna koda Java za nastali razčlenjevalnik. Upoštevajte, da je ime razreda, uporabljeno v specifikaciji razčlenjevalnika mora biti enaka v začetku, sredini in koncu tega dela. V zgornjem primeru sem ime razreda dal v krepkem tisku, da je to jasno. Kot lahko vidite v zgornji kodi, ta razred definira statiko glavni , tako da lahko razlagalnik Java v ukazni vrstici prikliče razred. The glavni metoda preprosto ustvari nov razčlenjevalnik z vhodnim tokom (v tem primeru System.in) in nato prikliče Vhod metoda. The Vhod metoda v naši slovnici ni terminalska in je definirana v obliki elementa EBNF. EBNF je kratica za razširjeno obliko Backus-Naur. Obrazec Backus-Naur je metoda za določanje slovnic brez konteksta. Specifikacija je sestavljena iz a terminala na levi strani proizvodni simbol, ki je običajno ":: =", in en ali več produkcije na desni strani. Uporabljeni zapis je običajno približno tak:

 Ključna beseda :: = "če" | "potem" | "drugače" 

To bi se glasilo kot " Ključna beseda terminal je eden od nizovnih dobesednih črk "if", "then" ali "else." "V Jacku je ta obrazec razširjen, tako da levi del predstavlja metoda, nadomestne razširitve pa lahko predstavlja regularni izrazi ali drugi ne-terminali. V nadaljevanju našega preprostega primera datoteka vsebuje naslednje definicije:

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

Ta preprost razčlenjevalnik razčleni sliko, prikazano spodaj:

Kurzivo sem uporabil za prikaz ne-terminalov na desni strani produkcije in krepko pisavo za prikaz dobesednih besed. Kot lahko vidite, slovnica preprosto razčleni ujemajoče se sklope oklepajev "{" in "}". V datoteki Jack sta dve produkciji, ki opisujeta to slovnico. Prvi terminal, Vhod, je v tej definiciji opredeljena kot tri zaporedne postavke: a MatchedBraces terminal, znak nove vrstice in žeton konca datoteke. The žeton definira Jack, tako da vam ga ni treba določiti za svojo platformo.

Ko se ta slovnica ustvari, se leve strani produkcije spremenijo v metode znotraj Preprosto1 razred; ko je sestavljen, Preprosto1 razred bere znake iz Sistem.v in preveri, ali vsebujejo ustrezen nabor oklepajev. To dosežemo s klicem generirane metode Vhod, ki se s postopkom generiranja pretvori v metodo, ki razčleni Vhod ne terminal. Če razčlenitev ne uspe, metoda vrže izjemo Napaka razčlenitve, ki ga lahko glavna rutina ujame in se nato pritoži, če se tako odloči.

Seveda je še več. Blok, označen z "{" in "}" za imenom terminala, ki je v tem primeru prazen, lahko vsebuje poljubno kodo Java, ki je vstavljena na sprednji strani ustvarjene metode. Potem je po vsaki razširitvi še en izbirni blok, ki lahko vsebuje poljubno kodo Java, ki se izvede, ko se razčlenjevalnik uspešno ujema s to razširitvijo.

Bolj zapleten primer

Kaj pa primer, ki je nekoliko bolj zapleten? Razmislite o naslednji slovnici, spet razdeljeni na koščke. Ta slovnica je namenjena interpretaciji matematičnih enačb s pomočjo štirih osnovnih operatorjev - seštevanje, množenje, odštevanje in deljenje. Vir najdete tukaj:

možnosti {LOOKAHEAD = 1; } PARSER_BEGIN (Calc1) javni razred Calc1 {public static void main (String args []) vrže ParseError {Calc1 parser = new Calc1 (System.in); while (true) {System.out.print ("Enter Expression:"); System.out.flush (); poskusite {switch (parser.one_line ()) {case -1: System.exit (0); privzeto: odmor; }} catch (ParseError x) {System.out.println ("Exiting."); vrzi x; }}}} PARSER_END (Calc1) 

Prvi del je skoraj enak kot Preprosto1, le da glavna rutina zdaj pokliče terminal ena_vrstica večkrat, dokler ne uspe razčleniti. Sledi naslednja koda:

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

Te opredelitve zajemajo osnovne terminale, v katerih je navedena slovnica. Prva, imenovana IGNORE_IN_BNF, je poseben žeton. Vsi žetoni, ki jih je razčlenil razčlenjevalnik in se ujemajo z znaki, definiranimi v IGNORE_IN_BNF žeton se tiho zavrže. Kot lahko vidite v našem primeru, to povzroča, da razčlenjevalnik v vnosu prezre znake presledka, zavihke in vrnitve znakov.