Leder du efter lex og yacc til Java? Du kender ikke Jack

Sun har frigivet Jack, et nyt værktøj skrevet i Java, der automatisk genererer parsere ved at kompilere en grammatikspecifikation på højt niveau, der er gemt i en tekstfil. Denne artikel vil tjene som en introduktion til dette nye værktøj. Den første del af artiklen dækker en kort introduktion til automatisk parsergenerering og mine første erfaringer med dem. Derefter vil artiklen fokusere på Jack, og hvordan du kan bruge den til at generere parsere og applikationer, der er bygget med disse parsers, baseret på din grammatik på højt niveau.

Automatisk generering af compiler-parser

En parser er en af ​​de mest almindelige komponenter i et computerprogram. Den konverterer tekst, der kan læses af mennesker til datastrukturer kendt som parsetræer, som computeren forstår. Jeg husker tydeligt min introduktion til automatisk parsergenerering: På college havde jeg gennemført en klasse om kompilerkonstruktion. Med hjælp fra min kone til at være, havde jeg skrevet en simpel kompilator, der kunne omdanne programmer skrevet på et sprog, der er lavet til klassen, til eksekverbare programmer. Jeg kan huske, at jeg følte mig meget færdig på det tidspunkt.

I mit første "rigtige" job efter college fik jeg et forsøg på at oprette et nyt sprog til grafikbehandling til at kompilere i kommandoer til en grafisk coprocessor. Jeg startede med en nykomponeret grammatik og var parat til at starte i multiweekeprojektet om at sammensætte en kompilator. Så viste en ven mig Unix-værktøjerne lex og yacc. Lex bygget leksikale analysatorer fra regulære udtryk, og yacc reduceret en grammatikspecifikation til en tabeldrevet kompilator, der kunne producere kode, når den med succes havde analyseret produktioner fra den grammatik. jeg brugte lex og yacc, og på mindre end en uge var min kompilator i gang! Senere producerede Free Software Foundation's GNU-projekt "forbedrede" versioner af lex og yacc -- som hedder flex og bison - til brug på platforme, der ikke kørte et derivat af Unix-operativsystemet.

Verden af ​​automatisk parsergenerering avancerede igen, da Terrence Parr, dengang studerende ved Purdue University, oprettede Purdue Compiler Construction Tool Set eller PCCTS. To komponenter i PCCTS - DFA og ANTLR - giver de samme funktioner som lex og yacc; dog de grammatikker, der ANTLR accepterer er LL (k) -grammatik i modsætning til de LALR-grammatikker, der bruges af yacc. Desuden er den kode, som PCCTS genererer, meget mere læsbar end den kode, der genereres af yacc. Ved at generere kode, der er lettere at læse, gør PCCTS det lettere for et menneske, der læser koden, at forstå, hvad de forskellige stykker laver. Denne forståelse kan være afgørende, når man prøver at diagnosticere fejl i grammatikspecifikationen. PCCTS udviklede hurtigt et tilhænger af folk, der fandt dets filer lettere at bruge end yacc.

Kraften ved automatisk parsergenerering er, at det giver brugerne mulighed for at koncentrere sig om grammatikken og ikke bekymre sig om rigtigheden af ​​implementeringen. Dette kan være en enorm tidsbesparelse i både enkle og komplekse projekter.

Jack træder op til pladen

Jeg vurderer værktøjer ud fra det generelle problem, de løser. Da kravet om at analysere tekstindtastning kommer op igen og igen, satser automatisk parsergenerering ret højt i min værktøjskasse. Kombineret med Java's hurtige udviklingscyklus giver automatisk parsergenerering et værktøj til kompilerdesign, der er svært at slå.

Jack (rimer med yacc) er en parsergenerator, i ånden af ​​PCCTS, som Sun har frigivet gratis til Java-programmeringssamfundet. Jack er et usædvanligt let værktøj at beskrive: Kort sagt giver du det et sæt kombinerede grammatiske og lexing regler i form af en .jack-fil og kører værktøjet, og det giver dig tilbage en Java-klasse, der vil analysere grammatikken. Hvad kan være lettere?

At få fat i Jack er også ret let. Først downloader du en kopi fra Jacks startside. Dette kommer til dig i form af en selvudpakning af Java-klasse kaldet installere. For at installere Jack skal du påberåbe dette installere klasse, som på en Windows 95-maskine udføres ved hjælp af kommandoen: C:> Java-installation.

Kommandoen vist ovenfor antager, at java kommandoen er i din kommandosti, og at klassestien er konfigureret korrekt. Hvis ovenstående kommando ikke fungerede, eller hvis du ikke er sikker på, om du har tingene konfigureret korrekt, skal du åbne et MS-DOS-vindue ved at krydse menupunkterne Start-> Programmer-> MS-DOS-prompt. Hvis du har installeret Sun JDK, kan du skrive disse kommandoer:

C:> sti C: \ java \ bin;% sti% C:> indstil CLASSPATH = .; c: \ java \ lib \ classes.zip 

Hvis Symantec Cafe version 1.2 eller nyere er installeret, kan du skrive disse kommandoer:

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

Klassestien skal allerede være opsat i en fil, der kaldes sc.ini i papirkurven på Cafe.

Skriv derefter java installation kommando ovenfra. Installationsprogrammet spørger dig, hvilket bibliotek du vil installere i, og Jack-underkatalogen oprettes under det.

Brug af Jack

Jack er skrevet udelukkende på Java, så det at have Jack-klasser betyder, at dette værktøj øjeblikkeligt er tilgængeligt på enhver platform, der understøtter den virtuelle Java-maskine. Det betyder dog også, at du i Windows-bokse skal køre Jack fra kommandolinjen. Lad os sige, at du valgte katalognavnet JavaTools, da du installerede Jack på dit system. For at bruge Jack skal du tilføje Jacks klasser til din klassesti. Du kan gøre dette i din autoexec.bat fil eller i din .cshrc fil, hvis du er en Unix-bruger. Den kritiske kommando er noget som linjen vist nedenfor:

C:> sæt CLASSPATH = .; C: \ JavaTools \ Jack \ java; C: \ java \ lib \ classes.zip 

Bemærk, at Symantec Cafe-brugere kan redigere sc.ini fil og inkludere Jack-klasser der, eller de kan indstille CLASSPATH eksplicit som vist ovenfor.

Indstilling af miljøvariablen som vist ovenfor placerer Jack-klasser i CLASSPATH mellem "." (det aktuelle bibliotek) og basesystemklasserne til Java. Hovedklassen for Jack er COM.sun.labs.jack.Main. Store bogstaver er vigtige! Der er nøjagtigt fire store bogstaver i kommandoen ('C', 'O', 'M' og en anden 'M'). For at køre Jack manuelt skal du skrive kommandoen:

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

Hvis du ikke har Jack-filerne i din klassesti, kan du bruge denne kommando:

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

Som du kan se, bliver dette lidt langt. For at minimere indtastning sætter jeg påkaldelsen i en .flagermus fil navngivet Jack.bat. På et eller andet tidspunkt i fremtiden vil et simpelt C wrapper-program blive tilgængeligt, måske endda når du læser dette. Tjek Jack-hjemmesiden for tilgængeligheden af ​​dette og andre programmer.

Når Jack køres, opretter den flere filer i den aktuelle mappe, som du senere vil kompilere i din parser. De fleste er enten forud for navnet på din parser eller er fælles for alle parsers. En af disse dog ASCII_CharStream.java, kan kollidere med andre parsere, så det er sandsynligvis en god ide at starte i en mappe, der kun indeholder .jack fil, du vil bruge til at generere parseren.

Når generationen er gået glat, når du kører Jack, har du en masse .java filer i det aktuelle bibliotek med forskellige interessante navne. Dette er dine analysatorer. Jeg opfordrer dig til at åbne dem for en redaktør og se dem over. Når du er klar, kan du kompilere dem med kommandoen

C:> javac -d. Parsernavn.java

hvor Parsernavn er det navn, du gav din parser i inputfilen. Mere om det lidt. Hvis alle filerne til din parser ikke kompileres, kan du bruge brute force-metoden til at skrive:

C:> javac * .java 

Dette vil samle alt i kataloget. På dette tidspunkt er din nye parser klar til brug.

Jack parser beskrivelser

Jack parser-beskrivelsesfiler har udvidelsen .jack og er opdelt i tre grundlæggende dele: optioner og basisklasse; leksikale tokens og ikke-terminaler. Lad os se på en simpel parserbeskrivelse (dette er inkluderet i eksempler katalog, der følger med Jack).

valgmuligheder {LOOKAHEAD = 1; } PARSER_BEGIN (Simpel1) offentlig klasse Simpel1 {public static void main (String args []) kaster ParseError { Simpel1 parser = ny Simpel1(System.in); parser.Input (); }} PARSER_END (Simpel1) 

De første par linjer ovenfor beskriver mulighederne for parseren; I dette tilfælde SE FREMAD er indstillet til 1. Der er andre muligheder, såsom diagnostik, Java Unicode-håndtering osv., der også kan indstilles her. Efter indstillingerne kommer parserens basisklasse. De to tags PARSER_BEGIN og PARSER_END parentes klassen, der bliver den grundlæggende Java-kode for den resulterende parser. Bemærk, at det klassenavn, der bruges i parserspecifikationen skal være den samme i begyndelsen, midten og slutningen af ​​denne sektion. I eksemplet ovenfor har jeg sat klassenavnet med fed skrift for at gøre det klart. Som du kan se i koden ovenfor definerer denne klasse en statisk vigtigste metode, så klassen kan påberåbes af Java-tolk på kommandolinjen. Det vigtigste Metode instantierer simpelthen en ny parser med en inputstrøm (i dette tilfælde System.in) og påberåber sig derefter Indgang metode. Det Indgang metoden er en ikke-terminal i vores grammatik, og den er defineret i form af et EBNF-element. EBNF står for Extended Backus-Naur Form. Backus-Naur-formularen er en metode til at specificere kontekstfrie grammatikker. Specifikationen består af en terminal på venstre side, et produktionssymbol, der typisk er ":: =", og et eller flere produktioner på højre side. Den anvendte betegnelse er typisk sådan:

 Søgeord :: = "hvis" | "derefter" | "andet" 

Dette læses som: "The Nøgleord terminal er en af ​​strenglitteralerne 'hvis', 'derefter' eller 'ellers. "" I Jack udvides denne form, så den venstre del kan repræsenteres ved en metode, og de alternative udvidelser kan repræsenteres ved regulære udtryk eller andre ikke-terminaler. Fortsat med vores enkle eksempel indeholder filen følgende definitioner:

ugyldigt input (): {} {MatchedBraces () "\ n"} ugyldigt MatchedBraces (): {} {"{" [MatchedBraces ()] "}"} 

Denne enkle parser analyserer grammatikken vist nedenfor:

Jeg har brugt kursiv til at vise ikke-terminalerne på højre side af produktionen og fed skrift til at vise bogstaver. Som du kan se, analyserer grammatikken simpelthen matchende sæt bøjle "{" og "}" tegn. Der er to produktioner i Jack-filen til beskrivelse af denne grammatik. Den første terminal, Indgang, er ved denne definition defineret til at være tre elementer i rækkefølge: a MatchedBraces terminal, en newline-karakter og et slut-til-fil-token. Det token defineres af Jack, så du ikke behøver at specificere det til din platform.

Når denne grammatik genereres, omdannes de venstre sider af produktionen til metoder inde i Simpel1 klasse; når kompileret, Simpel1 klasse læser tegn fra System.i og kontrollerer, at de indeholder et matchende sæt seler. Dette opnås ved at påkalde den genererede metode Indgang, som transformeres af genereringsprocessen til en metode, der analyserer en Indgang ikke-terminal. Hvis analysen mislykkes, kaster metoden undtagelsen ParseError, som hovedrutinen kan fange og derefter klage over, hvis den vælger det.

Selvfølgelig er der mere. Blokken afgrænset af "{" og "}" efter terminalnavnet - som er tom i dette eksempel - kan indeholde vilkårlig Java-kode, der indsættes foran den genererede metode. Derefter er der efter hver udvidelse en anden valgfri blok, der kan indeholde vilkårlig Java-kode, der skal udføres, når parseren matcher denne udvidelse.

Et mere kompliceret eksempel

Så hvad med et eksempel, der er lidt mere kompliceret? Overvej følgende grammatik, igen opdelt i stykker. Denne grammatik er designet til at fortolke matematiske ligninger ved hjælp af de fire grundlæggende operatorer - addition, multiplikation, subtraktion og division. Kilden kan findes her:

valgmuligheder {LOOKAHEAD = 1; } PARSER_BEGIN (Calc1) offentlig klasse Calc1 {offentlig statisk ugyldig main (String args []) kaster ParseError {Calc1 parser = ny Calc1 (System.in); while (true) {System.out.print ("Indtast udtryk:"); System.out.flush (); prøv {switch (parser.one_line ()) {case -1: System.exit (0); standard: pause; }} fange (ParseError x) {System.out.println ("Afslut."); smide x; }}}} PARSER_END (Calc1) 

Den første del er næsten den samme som Simpel1, bortset fra at hovedrutinen nu kalder terminalen one_line gentagne gange, indtil den ikke kan parse. Dernæst kommer følgende kode:

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

Disse definitioner dækker de grundlæggende terminaler, hvor grammatikken er specificeret. Den første, der hedder IGNORE_IN_BNF, er et specielt symbol. Ethvert tokens læst af parseren, der matcher de tegn, der er defineret i en IGNORE_IN_BNF token kasseres lydløst. Som du kan se i vores eksempel, får dette parseren til at ignorere mellemrumstegn, faner og vognreturtegn i input.