Sun har gitt ut Jack, et nytt verktøy skrevet i Java som automatisk genererer parsers ved å kompilere en grammatikkspesifikasjon på høyt nivå som er lagret i en tekstfil. Denne artikkelen vil tjene som en introduksjon til dette nye verktøyet. Den første delen av artikkelen dekker en kort introduksjon til automatisk generering av parser, og mine første erfaringer med dem. Deretter vil artikkelen fokusere på Jack og hvordan du kan bruke den til å generere parsers og applikasjoner bygget med disse parsers, basert på grammatikken på høyt nivå.
Automatisk generering av kompilatorparser
En parser er en av de vanligste komponentene i et dataprogram. Den konverterer tekst som kan leses av mennesker til datastrukturer kjent som parse trær, som forstås av datamaskinen. Jeg husker tydelig introduksjonen min til automatisk parsergenerering: På college hadde jeg fullført en klasse om kompilatorkonstruksjon. Ved hjelp av min kone å være, hadde jeg skrevet en enkel kompilator som kunne gjøre programmer skrevet på et språk som er laget for klassen, til kjørbare programmer. Jeg husker at jeg følte meg veldig dyktig på det tidspunktet.
I min første "ekte" jobb etter college, fikk jeg et oppdrag for å lage et nytt grafikkbehandlingsspråk for å kompilere til kommandoer for en grafikkprosessor. Jeg startet med en nykomponert grammatikk og forberedte meg på å starte i flerukeprosjektet med å sette sammen en kompilator. Så viste en venn meg Unix-verktøyene lex og yacc. Lex bygget leksikale analysatorer fra regulære uttrykk, og yacc reduserte en grammatikkspesifikasjon til en tabelldrevet kompilator som kunne produsere kode når den med hell hadde analysert produksjoner fra den grammatikken. jeg brukte lex og yacc, og på mindre enn en uke var kompilatoren min i gang! Senere produserte Free Software Foundation GNU-prosjekt "forbedrede" versjoner av lex og yacc - navngitt flex og bison - for bruk på plattformer som ikke kjørte et derivat av Unix-operativsystemet.
Verden av automatisk parseregenerering avanserte igjen da Terrence Parr, den gang student ved Purdue University, opprettet Purdue Compiler Construction Tool Set eller PCCTS. To komponenter av PCCTS - DFA og ANTLR - gir de samme funksjonene som lex og yacc; men grammatikkene som ANTLR aksepterer er LL (k) grammatikk i motsetning til LALR grammatikk som brukes av yacc. Videre er koden som PCCTS genererer mye mer lesbar enn koden generert av yacc. Ved å generere kode som er lettere å lese, gjør PCCTS det lettere for et menneske som leser koden å forstå hva de forskjellige delene gjør. Denne forståelsen kan være viktig når du prøver å diagnostisere feil i grammatikk-spesifikasjonen. PCCTS utviklet raskt en følge av folk som fant filene lettere å bruke enn yacc.
Kraften til automatisk parsergenerering er at den lar brukerne konsentrere seg om grammatikken og ikke bekymre seg for riktig implementering. Dette kan være en enorm tidsbesparende i både enkle og komplekse prosjekter.
Jack går opp til tallerkenen
Jeg vurderer verktøy etter allmennheten i problemet de løser. Siden kravet om å analysere tekstinngang kommer opp igjen og igjen, vurderer automatisk parsergenerering ganske høyt i verktøykassen min. Kombinert med den raske utviklingssyklusen til Java, gir automatisk parsergenerering et verktøy for kompilerdesign som er vanskelig å slå.
Jack (rimer med yacc) er en parsergenerator, i ånden til PCCTS, som Sun har gitt ut gratis til Java-programmeringssamfunnet. Jack er et usedvanlig enkelt verktøy å beskrive: Enkelt sagt, du gir det et sett med kombinerte grammatiske og lekserende regler i form av en .jack-fil og kjører verktøyet, og det gir deg tilbake en Java-klasse som vil analysere den grammatikken. Hva kan være enklere?
Å få tak i Jack er også ganske enkelt. Først laster du ned en kopi fra Jacks hjemmeside. Dette kommer til deg i form av en selvutpakking av Java-klassen installere. For å installere Jack må du påkalle dette installere klasse, som på en Windows 95-maskin gjøres ved hjelp av kommandoen: C:> java install.
Kommandoen vist ovenfor forutsetter at java kommandoen er i kommandostien din og at klassestien er satt opp riktig. Hvis kommandoen ovenfor ikke fungerte, eller hvis du ikke er sikker på om du har ting konfigurert riktig, åpner du et MS-DOS-vindu ved å krysse menyelementene Start-> Programmer-> MS-DOS Prompt. Hvis du har installert Sun JDK, kan du skrive disse kommandoene:
C:> bane C: \ java \ bin;% bane% C:> sett CLASSPATH = .; c: \ java \ lib \ classes.zip
Hvis Symantec Cafe versjon 1.2 eller nyere er installert, kan du skrive disse kommandoene:
C:> bane C: \ cafe \ java \ bin;% bane%
Klassestien skal allerede være satt opp i en fil som heter sc.ini i papirkurven til Cafe.
Skriv deretter inn java installere kommando ovenfra. Installasjonsprogrammet vil spørre deg hvilken katalog du vil installere i, og underkatalogen Jack vil bli opprettet under det.
Bruker Jack
Jack er skrevet helt på Java, så å ha Jack-klassene betyr at dette verktøyet umiddelbart er tilgjengelig på alle plattformer som støtter den virtuelle Java-maskinen. Det betyr imidlertid også at du i Windows-bokser må kjøre Jack fra kommandolinjen. La oss si at du valgte katalognavnet JavaTools da du installerte Jack på systemet ditt. For å bruke Jack må du legge til Jacks klasser i klassestien din. Du kan gjøre dette i din autoexec.bat filen eller i din .cshrc filen hvis du er Unix-bruker. Den kritiske kommandoen er omtrent som linjen vist nedenfor:
C:> sett CLASSPATH = .; C: \ JavaTools \ Jack \ java; C: \ java \ lib \ classes.zip
Merk at Symantec Cafe-brukere kan redigere sc.ini filen og inkluder Jack-klassene der, eller de kan sette CLASSPATH eksplisitt som vist ovenfor.
Ved å sette miljøvariabelen som vist ovenfor, settes Jack-klassene i CLASSPATH mellom "." (den gjeldende katalogen) og basesystemklassene for Java. Hovedklassen for Jack er COM.sun.labs.jack.Main. Store bokstaver er viktig! Det er nøyaktig fire store bokstaver i kommandoen ('C', 'O', 'M' og en annen 'M'). For å kjøre Jack manuelt, skriv inn kommandoen:
C:> java COM.sun.labs.jack.Main parser-input.jack
Hvis du ikke har Jack-filene i klassebanen din, kan du bruke denne kommandoen:
C:> java -classpath.; C: \ JavaTools \ Jack \ java; c: \ java \ lib \ classes.zip COM.sun.labs.jack.Main parser-input.jack
Som du ser blir dette litt langt. For å minimere skrive setter jeg innkallingen til en .flaggermus filen heter Jack.bat. På et tidspunkt i fremtiden vil et enkelt C wrapper-program bli tilgjengelig, kanskje til og med når du leser dette. Sjekk ut hjemmesiden til Jack for tilgjengeligheten av dette og andre programmer.
Når Jack kjøres, oppretter den flere filer i den nåværende katalogen som du senere vil kompilere til parseren din. De fleste er enten foran navnet på parseren din eller er felles for alle parsers. En av disse, ASCII_CharStream.java, kan kollidere med andre parsere, så det er sannsynligvis en god ide å starte i en katalog som bare inneholder .jack filen du skal bruke til å generere parseren.
Når du har kjørt Jack, hvis generasjonen har gått greit, vil du ha en haug med .java filer i den nåværende katalogen med forskjellige interessante navn. Dette er analysatorene dine. Jeg oppfordrer deg til å åpne dem for en redaktør og se dem over. Når du er klar kan du kompilere dem med kommandoen
C:> javac -d. ParserName.java
hvor Parsernavn er navnet du ga parseren din i inndatafilen. Mer om det litt. Hvis alle filene for parseren din ikke kompileres, kan du bruke brute force-metoden for å skrive:
C:> javac * .java
Dette vil samle alt i katalogen. På dette tidspunktet er den nye parseren klar til bruk.
Jack parser beskrivelser
Jack parser-beskrivelsesfiler har utvidelsen .jack og er delt inn i tre grunnleggende deler: opsjoner og basisklasse; leksikale tokens; og ikke-terminaler. La oss se på en enkel parserbeskrivelse (dette er inkludert i eksempler katalog som følger med Jack).
alternativer {LOOKAHEAD = 1; } PARSER_BEGIN (Enkelt1) offentlig klasse Enkelt1 {public static void main (String args []) kaster ParseError { Enkelt1 parser = ny Enkelt1(System.in); parser.Input (); }} PARSER_END (Enkelt1) De første linjene ovenfor beskriver alternativer for parseren; i dette tilfellet SE FREMOVER er satt til 1. Det er andre alternativer, for eksempel diagnostikk, Java Unicode-håndtering og så videre, som også kan angis her. Etter alternativene kommer baseklassen til parseren. De to kodene PARSER_BEGIN og PARSER_END braketter klassen som blir den grunnleggende Java-koden for den resulterende parseren. Merk at kursnavnet som brukes i parserspesifikasjonen må være den samme i begynnelsen, midten og slutten av denne delen. I eksemplet ovenfor har jeg satt kursnavnet med fet skrift for å gjøre dette klart. Som du kan se i koden ovenfor, definerer denne klassen en statisk hoved- metode slik at klassen kan påberopes av Java-tolk på kommandolinjen. De hoved- metoden starter bare en ny parser med en inngangsstrøm (i dette tilfellet System.in) og deretter påkaller Inngang metode. De Inngang metoden er en ikke-terminal i vår grammatikk, og den er definert i form av et EBNF-element. EBNF står for Extended Backus-Naur Form. Backus-Naur-skjemaet er en metode for å spesifisere kontekstfrie grammatikker. Spesifikasjonen består av en terminal på venstre side, et produksjonssymbol, som vanligvis er ":: =", og ett eller flere produksjoner på høyre side. Notasjonen som brukes er vanligvis noe sånt:
Søkeord :: = "hvis" | "deretter" | "ellers"
Dette vil bli lest som: "The Nøkkelord terminal er en av strenglitteralene 'hvis', 'da' eller 'annet.' "I Jack utvides dette skjemaet slik at venstre del kan representeres av en metode, og de alternative utvidelsene kan være representert av regulære uttrykk eller andre ikke-terminaler. Fortsett med vårt enkle eksempel, inneholder filen følgende definisjoner:
ugyldig Input (): {} {MatchedBraces () "\ n"} void MatchedBraces (): {} {"{" [MatchedBraces ()] "}"} Denne enkle parseren analyserer grammatikken vist nedenfor:
| Inngang | ::= | MatchedBraces "\ n" |
| MatchedBraces | ::= | "{" [ MatchedBraces ] "}" |
Jeg har brukt kursiv for å vise ikke-terminalene på høyre side av produksjonene og fet skrift for å vise bokstaver. Som du ser, analyserer grammatikken bare sett med avstivende "{" og "}" -tegn. Det er to produksjoner i Jack-filen for å beskrive denne grammatikken. Den første terminalen, Inngang, er definert av denne definisjonen til å være tre elementer i rekkefølge: a MatchedBraces terminal, en ny linjetegn og et token til slutten av filen. De token er definert av Jack slik at du ikke trenger å spesifisere det for plattformen din.
Når denne grammatikken genereres, blir venstresidene av produksjonene omgjort til metoder inne i Enkelt1 klasse; når kompilert, Enkelt1 klasse leser tegn fra System.i og verifiserer at de inneholder et matchende sett med seler. Dette oppnås ved å påkalle den genererte metoden Inngang, som transformeres av generasjonsprosessen til en metode som analyserer en Inngang ikke-terminal. Hvis analysen mislykkes, kaster metoden unntaket ParseError, som hovedrutinen kan fange og deretter klage på hvis den velger det.
Selvfølgelig er det mer. Blokken avgrenset av "{" og "}" etter terminalnavnet - som er tom i dette eksemplet - kan inneholde vilkårlig Java-kode som settes inn foran på den genererte metoden. Så, etter hver utvidelse, er det en annen valgfri blokk som kan inneholde vilkårlig Java-kode som skal utføres når parseren samsvarer med utvidelsen.
Et mer komplisert eksempel
Så hva med et eksempel som er litt mer komplisert? Tenk på følgende grammatikk, igjen delt opp i biter. Denne grammatikken er designet for å tolke matematiske ligninger ved hjelp av de fire grunnleggende operatorene - addisjon, multiplikasjon, subtraksjon og divisjon. Kilden finner du her:
alternativer {LOOKAHEAD = 1; } PARSER_BEGIN (Calc1) offentlig klasse Calc1 {public static void main (String args []) kaster ParseError {Calc1 parser = new Calc1 (System.in); while (true) {System.out.print ("Enter Expression:"); System.out.flush (); prøv {switch (parser.one_line ()) {case -1: System.exit (0); standard: pause; }} fange (ParseError x) {System.out.println ("Avslutter."); kaste x; }}}} PARSER_END (Calc1) Den første delen er nesten den samme som Enkelt1, bortsett fra at hovedrutinen nå kaller terminalen en linje gjentatte ganger til den ikke kan analyseres. Deretter kommer følgende kode:
IGNORE_IN_BNF: {} "" TOKEN: {} {} TOKEN: / * OPERATORS * / {} TOKEN: {} Disse definisjonene dekker de grunnleggende terminalene der grammatikken er spesifisert. Den første, kalt IGNORE_IN_BNF, er et spesielt symbol. Eventuelle tokens som leses av parseren som samsvarer med tegnene som er definert i en IGNORE_IN_BNF token blir stille forkastet. Som du kan se i vårt eksempel, fører dette til at parseren ignorerer mellomromstegn, faner og vognretur i inngangen.
