Tražite lex i yacc za Javu? Ne poznaješ Jacka

Sun je objavio Jack, novi alat napisan na Javi koji automatski generira parsere sastavljanjem gramatičke specifikacije visoke razine pohranjene u tekstualnoj datoteci. Ovaj će članak poslužiti kao uvod u ovaj novi alat. Prvi dio članka obuhvaća kratki uvod u automatsko generiranje parsera i moja prva iskustva s njima. Tada će se članak usredotočiti na Jacka i kako ga možete koristiti za generiranje parsera i aplikacija izgrađenih s tim parserima, na temelju vaše gramatike na visokoj razini.

Automatsko generiranje parsera kompajlera

Analizator je jedna od najčešćih komponenti računalne aplikacije. Pretvara tekst koji ljudi mogu pročitati u podatkovne strukture poznate kao raščlanjivanje stabala, koje računalo razumije. Izrazito se sjećam svog uvoda u automatsko generiranje parsera: Na fakultetu sam završio tečaj o konstrukciji kompajlera. Uz pomoć svoje supruge, napisao sam jednostavan kompajler koji je programe koji su napisani na jeziku stvorenom za klasu mogao pretvoriti u izvršne programe. Sjećam se da sam se u tom trenutku osjećao vrlo postignuto.

U svom prvom "pravom" poslu nakon fakulteta dobio sam zadatak za stvaranje novog jezika za obradu grafike koji će se kompilirati u naredbe za grafički koprocesor. Počeo sam sa svježe komponiranom gramatikom i pripremio se za pokretanje višetjednog projekta sastavljanja kompajlera. Tada mi je prijatelj pokazao Unix uslužne programe lex i yacc . Lex je leksičke analizatore izgradio od regularnih izraza, a yacc je smanjio gramatičku specifikaciju u tablični pokretač koji je mogao proizvoditi kôd kada je uspješno raščlanio produkcije iz te gramatike. Koristio sam lex i yacc, i za manje od tjedan dana moj kompajler je bio pokrenut! Kasnije je GNU projekt Zaklade za slobodni softver proizveo "poboljšane" verzije lex-a i yacc-a - nazvane flex i bison - za upotrebu na platformama koje nisu izvodile derivat operativnog sustava Unix.

Svijet automatske generacije parsera ponovo je napredovao kada je Terrence Parr, tada student na Sveučilištu Purdue, stvorio Purdue Compiler Construction Tool Tool ili PCCTS. Dvije komponente PCCTS-a - DFA i ANTLR - pružaju iste funkcije kao lex i yacc ; međutim gramatike koje ANTLR prihvaća su LL (k) gramatike za razliku od LALR gramatika koje koristi yacc . Nadalje, kôd koji generira PCCTS mnogo je čitljiviji od koda koji generira yacc. Generiranjem koda koji je lakši za čitanje, PCCTS olakšava čovjeku koji čita kôd da razumije što rade različiti dijelovi. Ovo razumijevanje može biti ključno pri pokušaju dijagnosticiranja pogrešaka u gramatičkoj specifikaciji. PCCTS je brzo razvio sljedeće ljude kojima je bilo lakše koristiti njegove datoteke od yacc-a.

Moć automatskog generiranja parsera je u tome što omogućuje korisnicima da se koncentriraju na gramatiku i ne brinu o ispravnosti implementacije. Ovo može izuzetno uštedjeti vrijeme i kod jednostavnih i kod složenih projekata.

Jack priđe tanjuru

Alate ocjenjujem prema općenitosti problema koji rješavaju. Kako se zahtjev za raščlanjivanjem unosa teksta pojavljuje uvijek iznova, automatsko generiranje raščlanjivača prilično je visoko u mom alatu. U kombinaciji s brzim razvojnim ciklusom Jave, automatsko generiranje parsera pruža alat za dizajn kompajlera koji je teško nadmašiti.

Jack (rima se s yacc) generator je parsera, u duhu PCCTS-a, koji je Sun besplatno objavio za programsku zajednicu Java. Jack je izuzetno jednostavan alat za opisivanje: Jednostavno rečeno, dajete mu skup kombiniranih gramatičkih i leksičkih pravila u obliku .jack datoteke i pokrećete alat, a vraća vam Java klasu koja će raščlaniti tu gramatiku. Što može biti lakše?

Dohvatiti Jacka također je prilično lako. Prvo preuzmite kopiju s Jackove početne stranice. To vam dolazi u obliku Java-pakete Java klase pod nazivom install. Za instaliranje Jack morate prizvati tu installklasu, koja, na Windows 95 stroj je učinjeno pomoću naredbe: C:>java install.

Gore prikazana naredba pretpostavlja da je javanaredba u vašem naredbenom putu i da je put klase postavljen na odgovarajući način. Ako gornja naredba nije uspjela ili ako niste sigurni jeste li neke stvari pravilno postavili ili ne, otvorite prozor MS-DOS-a prelazeći stavke izbornika Start-> Programi-> MS-DOS Prompt. Ako imate instaliran Sun JDK, možete upisati ove naredbe:

C:> put C: \ java \ bin;% put% C:> postavi CLASSPATH = .; c: \ java \ lib \ classes.zip 

Ako je instalirana Symantec Cafe verzija 1.2 ili novija, možete upisati ove naredbe:

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

Put predavanja već bi trebao biti postavljen u datoteci koja se naziva sc.ini u bin direktoriju Cafea.

Zatim upišite java installnaredbu odozgo. Instalacijski program pitati će vas u koji direktorij želite instalirati, a ispod toga će se stvoriti poddirektorij Jack.

Koristeći Jacka

Jack je u cijelosti napisan na Javi, pa posjedovanje Jack tečajeva znači da je ovaj alat odmah dostupan na svakoj platformi koja podržava Java virtualni stroj. Međutim, to također znači da na Windows kutijama morate pokrenuti Jack iz naredbenog retka. Recimo da ste odabrali naziv direktorija JavaTools kada ste instalirali Jack na svoj sustav. Da biste koristili Jacka, trebat ćete dodati Jackove razrede u svoj put predavanja. To možete učiniti u datoteci autoexec.bat ili u datoteci .cshrc ako ste korisnik Unixa. Kritična naredba je nešto poput retka prikazanog dolje:

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

Imajte na umu da korisnici Symantec Cafea mogu uređivati datoteku sc.ini i tamo uključiti Jack tečajeve ili ih mogu CLASSPATHizričito postaviti kako je gore prikazano.

Postavljanje varijable okoline, kao što je prikazano gore, stavlja Jack klase CLASSPATHizmeđu "." (trenutni direktorij) i osnovne sistemske klase za Javu. Glavna klasa za Jacka je COM.sun.labs.jack.Main. Pisanje velikih slova je važno! U naredbi su točno četiri velika slova ('C', 'O', 'M' i još jedno 'M'). Da biste Jack pokrenuli ručno, upišite naredbu:

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

Ako nemate Jack datoteka na putu do predavanja, možete upotrijebiti ovu naredbu:

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

Kao što vidite, ovo postaje pomalo dugo. Kako bih minimizirao tipkanje, stavio sam poziv u .bat datoteku pod nazivom Jack.bat . U nekom trenutku u budućnosti postat će dostupan jednostavan program za omotavanje C, možda čak i dok ovo čitate. Dostupnost ovog i drugih programa potražite na početnoj stranici Jacka.

Kada se Jack pokrene, on stvara nekoliko datoteka u trenutnom direktoriju koje ćete kasnije prevesti u svoj parser. Većina je ili s prefiksom imena vašeg parsera ili su zajedničke svim parserima. Međutim, jedan od njih ASCII_CharStream.javamože se sudariti s drugim raščlanjivačima, pa je vjerojatno dobro započeti u direktoriju koji sadrži samo datoteku .jack koju ćete koristiti za generiranje raščlanjivača.

Jednom kad pokrenete Jack, ako je generacija prošla bez problema, imat ćete hrpu .javadatoteka u trenutnom direktoriju s raznim zanimljivim imenima. Ovo su vaši parseri. Potičem vas da ih otvorite s urednikom i pregledate ih. Kad budete spremni, možete ih sastaviti naredbom

C:> javac -d. ParserName.java

gdje ParserNameje ime koje ste dali vašem parseru u ulaznoj datoteci. O tome malo više. Ako se sve datoteke za vaš parser ne kompajliraju, možete upotrijebiti grubu silu metodom tipkanja:

C:> javac * .java 

Ovo će kompajlirati sve u direktoriju. U ovom je trenutku vaš novi parser spreman za upotrebu.

Jack parser opisi

Jack parser description files have the extension .jack and are divided into three basic parts: options and base class; lexical tokens; and non-terminals. Let's look at a simple parser description (this is included in the examples directory that comes with Jack).

options { LOOKAHEAD = 1; } PARSER_BEGIN(Simple1) public class Simple1 { public static void main(String args[]) throws ParseError { Simple1 parser = new Simple1(System.in); parser.Input(); } } PARSER_END(Simple1) 

The first few lines above describe options for the parser; in this case LOOKAHEAD is set to 1. There are other options, such as diagnostics, Java Unicode handling, and so on, that also can be set here. Following the options comes the base class of the parser. The two tags PARSER_BEGIN and PARSER_END bracket the class that becomes the base Java code for the resulting parser. Note that the class name used in the parser specification must be the same in the beginning, middle, and ending part of this section. In the example above, I've put the class name in bold face to make this clear. As you can see in the code above, this class defines a static main method so that the class can be invoked by the Java interpreter on the command line. The main method simply instantiates a new parser with an input stream (in this case System.in) and then invokes the Input method. The Input method is a non-terminal in our grammar, and it is defined in the form of an EBNF element. EBNF stands for Extended Backus-Naur Form. The Backus-Naur form is a method for specifying context-free grammars. The specification consists of a terminal on the left-hand side, a production symbol, which is typically "::=", and one or more productions on the right-hand side. The notation used is typically something like this:

 Keyword ::= "if" | "then" | "else" 

This would be read as, "The Keyword terminal is one of the string literals 'if', 'then', or 'else.'" In Jack, this form is extended to allow the left-hand part to be represented by a method, and the alternate expansions may be represented by regular expressions or other non-terminals. Continuing with our simple example, the file contains the following definitions:

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

This simple parser parses the grammar shown below:

Input ::= MatchedBraces "\n"
MatchedBraces ::= "{" [ MatchedBraces ] "}"

I've used italics to show the non-terminals on the right side of the productions and boldface to show literals. As you can see, the grammar simply parses matched sets of brace "{" and "}" characters. There are two productions in the Jack file to describe this grammar. The first terminal, Input, is defined by this definition to be three items in sequence: a MatchedBraces terminal, a newline character, and an end-of-file token. The token is defined by Jack so that you don't have to specify it for your platform.

When this grammar is generated, the left-hand sides of the productions are turned into methods inside the Simple1 class; when compiled, the Simple1 class reads characters from System.in and verifies that they contain a matching set of braces. This is accomplished by invoking the generated method Input, which is transformed by the generation process into a method that parses an Input non-terminal. If the parse fails, the method throws the exception ParseError, which the main routine can catch and then complain about if it so chooses.

Of course there's more. The block delineated by "{" and "}" after the terminal name -- which is empty in this example -- can contain arbitrary Java code that is inserted at the front of the generated method. Then, after each expansion, there is another optional block that can contain arbitrary Java code to be executed when the parser successfully matches that expansion.

A more complicated example

So how about an example that's a bit more complicated? Consider the following grammar, again broken down into pieces. This grammar is designed to interpret mathematical equations using the four basic operators -- addition, multiplication, subtraction, and division. The source can be found here:

options { LOOKAHEAD=1; } PARSER_BEGIN(Calc1) public class Calc1 { public static void main(String args[]) throws ParseError { Calc1 parser = new Calc1(System.in); while (true) { System.out.print("Enter Expression: "); System.out.flush(); try { switch (parser.one_line()) { case -1: System.exit(0); default: break; } } catch (ParseError x) { System.out.println("Exiting."); throw x; } } } } PARSER_END(Calc1) 

The first part is nearly the same as Simple1, except that the main routine now calls the terminal one_line repeatedly until it fails to parse. Next comes the following code:

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

Te definicije pokrivaju osnovne terminale u kojima je gramatika navedena. Prvi, nazvan IGNORE_IN_BNF , poseban je žeton. Svi tokeni koje pročita parser koji se podudaraju sa znakovima definiranim u IGNORE_IN_BNF tokenu se tiho odbacuju. Kao što možete vidjeti u našem primjeru, to uzrokuje da parser ignorira razmake, kartice i znakove za vraćanje zaprege u unosu.