Byg dine egne sprog med JavaCC

Har du nogensinde spekuleret på, hvordan Java-kompilatoren fungerer? Har du brug for at skrive parsere til markupdokumenter, der ikke abonnerer på standardformater såsom HTML eller XML? Eller ønsker du at implementere dit eget lille programmeringssprog bare for det hele? JavaCC giver dig mulighed for at gøre alt dette i Java. Så hvad enten du bare er interesseret i at lære mere om, hvordan kompilatorer og tolke fungerer, eller hvis du har konkrete ambitioner om at skabe efterfølgeren til Java-programmeringssproget, så vær med mig på denne måneds søgen efter at udforske JavaCC, fremhævet ved opførelsen af en praktisk lille kommandolinjelommeregner.

Grundlæggende kompilerkonstruktion

Programmeringssprog er ofte opdelt, noget kunstigt, i kompilerede og fortolkede sprog, selvom grænserne er blevet slørede. Som sådan skal du ikke bekymre dig om det. De begreber, der diskuteres her, gælder lige så godt for såvel kompilerede som fortolkede sprog. Vi bruger ordet kompilator nedenfor, men for anvendelsesområdet for denne artikel skal det omfatte betydningen af tolk.

Kompilatorer skal udføre tre hovedopgaver, når de præsenteres med en programtekst (kildekode):

Lexikal analyse
Syntaktisk analyse
Kodegenerering eller -udførelse

Hovedparten af kompilatorens arbejde er centreret omkring trin 1 og 2, som involverer at forstå programmets kildekode og sikre dens syntaktiske korrekthed. Vi kalder den proces parsing, som er parser 's ansvar.

Lexikalisk analyse (lexing)

Lexikalisk analyse tager et kortvarigt kig på programkildekoden og deler den i korrekt tokens. Et token er et væsentligt stykke af et programs kildekode. Tokeneksempler inkluderer nøgleord, tegnsætning, bogstaver som tal og strenge. Ikke-tokener inkluderer hvidt rum, som ofte ignoreres, men bruges til at adskille tokens og kommentarer.

Syntaktisk analyse (parsing)

Under syntaktisk analyse udtrækker en parser mening fra programmets kildekode ved at sikre programmets syntaktiske korrekthed og ved at opbygge en intern repræsentation af programmet.

Computersprogsteori taler om programmer,grammatik, og Sprog. I den forstand er et program en sekvens af tokens. En bogstavelig er et grundlæggende computersprogselement, der ikke kan reduceres yderligere. En grammatik definerer regler til opbygning af syntaktisk korrekte programmer. Kun programmer, der spiller efter de regler, der er defineret i grammatikken, er korrekte. Sproget er simpelthen det sæt af alle programmer, der opfylder alle dine grammatikregler.

Under syntaktisk analyse undersøger en kompilator programkildekoden med hensyn til de regler, der er defineret i sprogets grammatik. Hvis nogen grammatikregel overtrædes, viser compileren en fejlmeddelelse. Undervejs skaber kompilatoren en let bearbejdet intern repræsentation af computerprogrammet, mens programmet undersøges.

Et computersprogs grammatikregler kan specificeres entydigt og i sin helhed med noteringen EBNF (Extended Backus-Naur-Form) (for mere om EBNF, se Ressourcer). EBNF definerer grammatikker i form af produktionsregler. En produktionsregel siger, at et grammatikelement - enten bogstaveligt eller sammensatte elementer - kan bestå af andre grammatikelementer. Litteraturer, som er irreducerbare, er nøgleord eller fragmenter af statisk programtekst, såsom tegnsætningssymboler. Komponerede elementer er afledt ved anvendelse af produktionsregler. Produktionsregler har følgende generelle format:

GRAMMAR_ELEMENT: = liste over grammatikelementer | alternativ liste over grammatikelementer

Lad os som et eksempel se på grammatikreglerne for et lille sprog, der beskriver grundlæggende aritmetiske udtryk:

expr: = antal | udtryk '+' udtryk | expr '-' expr | expr '*' expr | expr '/' expr | '(' expr ')' | - expr nummer: = ciffer + ('.' ciffer +)? ciffer: = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

Tre produktionsregler definerer grammatiske elementer:

ekspr
nummer
ciffer

Det sprog, der er defineret ved denne grammatik, giver os mulighed for at specificere aritmetiske udtryk. En ekspr er enten et nummer eller en af de fire infix-operatorer, der er anvendt på to eksprs, en ekspr i parentes eller en negativ ekspr. EN nummer er et flydende tal med valgfri decimalbrøk. Vi definerer en ciffer at være et af de velkendte decimalcifre.

Kodegenerering eller -udførelse

Når parseren med succes parser programmet uden fejl, findes det i en intern repræsentation, der er let at behandle af compileren. Det er nu relativt let at generere maskinkode (eller Java-bytecode for den sags skyld) fra den interne repræsentation eller at udføre den interne repræsentation direkte. Hvis vi gør det førstnævnte, kompilerer vi; i sidstnævnte tilfælde taler vi om tolkning.

JavaCC

JavaCC, tilgængelig gratis, er en parsergenerator. Det giver en Java-sprogudvidelse til angivelse af et programmeringssprogs grammatik. JavaCC blev oprindeligt udviklet af Sun Microsystems, men det vedligeholdes nu af MetaMata. Som ethvert anstændigt programmeringsværktøj, JavaCC blev faktisk brugt til at specificere grammatikken for JavaCC inputformat.

I øvrigt, JavaCC giver os mulighed for at definere grammatikker på en måde svarende til EBNF, hvilket gør det let at oversætte EBNF-grammatikker til JavaCC format. Yderligere, JavaCC er den mest populære parsergenerator til Java med en række foruddefinerede JavaCC grammatik til rådighed til brug som udgangspunkt.

Udvikling af en simpel lommeregner

Vi besøger nu vores lille aritmetiske sprog for at opbygge en simpel kommandolinjelommeregner i Java ved hjælp af JavaCC. Først skal vi oversætte EBNF-grammatikken til JavaCC format og gem det i filen Aritmetik.jj:

valgmuligheder {LOOKAHEAD = 2; } PARSER_BEGIN (aritmetik) offentlig klasse aritmetik {} PARSER_END (aritmetik) SKIP: "\ t" TOKEN: dobbelt udtryk (): {} sigt () ("+" udtryk () dobbelt sigt (): {} "/" sigt ()) * dobbelt unary (): {} "-" element () dobbelt element (): {} "(" expr () ")"

Koden ovenfor skal give dig en idé om, hvordan du angiver en grammatik til JavaCC. Det muligheder sektionen øverst angiver et sæt indstillinger for den grammatik. Vi angiver et lookahead på 2. Yderligere indstillinger kontrol JavaCC's fejlfindingsfunktioner og mere. Disse muligheder kan alternativt specificeres på JavaCC kommandolinje.

Det PARSER_BEGIN klausul specificerer, at definitionen af parserklassen følger. JavaCC genererer en enkelt Java-klasse for hver parser. Vi kalder parserklassen Aritmetik. For øjeblikket kræver vi kun en tom klassedefinition; JavaCC tilføjer parseringsrelaterede erklæringer til det senere. Vi slutter klassedefinitionen med PARSER_END klausul.

Det SPRINGE sektion identificerer de tegn, vi vil springe over. I vores tilfælde er det de hvide mellemrumstegn. Dernæst definerer vi tokens for vores sprog i POLET afsnit. Vi definerer tal og cifre som tokens. Noter det JavaCC skelner mellem definitioner for tokens og definitioner for andre produktionsregler, som adskiller sig fra EBNF. Det SPRINGE og POLET sektioner specificerer denne grammatiks leksikale analyse.

Dernæst definerer vi produktionsreglen for ekspr, grammatikelementet på øverste niveau. Bemærk hvordan denne definition markant adskiller sig fra definitionen af ekspr i EBNF. Hvad sker der? Nå viser det sig, at EBNF-definitionen ovenfor er tvetydig, da den tillader flere repræsentationer af det samme program. Lad os for eksempel undersøge udtrykket 1+2*3. Vi kan matche 1+2 ind i en ekspr hvilket giver udtryk * 3, som i figur 1.

Eller alternativt kunne vi først matche 2*3 ind i en ekspr resulterende i 1 + eksprsom vist i figur 2.

Med JavaCC, skal vi entydigt specificere grammatikreglerne. Som et resultat bryder vi definitionen af ekspr i tre produktionsregler, der definerer grammatikelementerne ekspr, semester, unaryog element. Nu, udtrykket 1+2*3 er analyseret som vist i figur 3.

Fra kommandolinjen kan vi køre JavaCC for at kontrollere vores grammatik:

javacc Arithmetic.jj Java Compiler Compiler Version 1.1 (Parser Generator) Copyright (c) 1996-1999 Sun Microsystems, Inc. Copyright (c) 1997-1999 Metamata, Inc. (skriv "javacc" uden argumenter for hjælp) Læsning fra fil Aritmetik.jj. . . Advarsel: Kontrol af tilstrækkelig lookahead udføres ikke, da indstilling LOOKAHEAD er mere end 1. Indstil indstilling FORCE_LA_CHECK til sand for at tvinge kontrol. Parser genereret med 0 fejl og 1 advarsler.

Følgende kontrollerer vores grammatikdefinition for problemer og genererer et sæt Java-kildefiler:

TokenMgrError.java ParseException.java Token.java ASCII_CharStream.java Arithmetic.java ArithmeticConstants.java ArithmeticTokenManager.java

Sammen implementerer disse filer parseren i Java. Du kan påberåbe denne parser ved at starte en instans af Aritmetik klasse:

offentlig klasse Aritmetik implementerer ArithmeticConstants {public Arithmetic (java.io.InputStream stream) {...} public Arithmetic (java.io.Reader stream) {...} public Arithmetic (ArithmeticTokenManager tm) {...} static final public dobbelt expr () kaster ParseException {...} statisk endelig offentlig dobbelt udtryk () kaster ParseException {...} statisk endelig offentlig dobbelt unary () kaster ParseException {...} statisk endelig offentlig dobbelt dobbeltelement () kaster ParseException {. ..} statisk offentlig ugyldighed ReInit (java.io.InputStream stream) {...} statisk offentlig ugyldighed ReInit (java.io.Reader stream) {...} offentlig ugyldig ReInit (ArithmeticTokenManager tm) {...} statisk final public Token getNextToken () {...} static final public Token getToken (int index) {...} static final public ParseException generateParseException () {...} static final public void enable_tracing () {...} static endelig offentlig tomrum deaktiver_sporing () {...}}

Hvis du vil bruge denne parser, skal du oprette en instans ved hjælp af en af konstruktørerne. Konstruktørerne giver dig mulighed for at passere i enten en InputStream, a Læser, eller en ArithmeticTokenManager som kilden til programkildekoden. Derefter angiver du det vigtigste grammatikelement på dit sprog, for eksempel:

Aritmetisk parser = ny aritmetik (System.in); parser.expr ();

Der sker dog ikke meget endnu, fordi i Aritmetik.jj vi har kun defineret grammatikreglerne. Vi har endnu ikke tilføjet den nødvendige kode for at udføre beregningerne. For at gøre dette tilføjer vi passende handlinger til grammatikreglerne. Calcualtor.jj indeholder den komplette lommeregner, herunder handlinger:

valgmuligheder {LOOKAHEAD = 2; } PARSER_BEGIN (lommeregner) offentlig klasse Lommeregner {offentlig statisk ugyldig hoved (String args []) kaster ParseException {Lommeregner parser = ny lommeregner (System.in); while (true) {parser.parseOneLine (); }}} PARSER_END (lommeregner) SKIP: "\ t" TOKEN: ugyldig parseOneLine (): {dobbelt a; } {a = expr () {System.out.println (a); } | | {System.exit (-1); }} dobbelt ekspr (): {dobbelt a; dobbelt b; } {a = term () ("+" b = expr () {a + = b;} | "-" b = expr () {a - = b;}) * {return a; }} dobbelt udtryk (): {dobbelt a; dobbelt b; } {a = unary () ("*" b = term () {a * = b;} | "/" b = term () {a / = b;}) * {return a; }} dobbelt unary (): {dobbelt a; } {"-" a = element () {return -a; } | a = element () {returner a; }} dobbelt element (): {Token t; dobbelt a; } {t = {returner Double.parseDouble (t.toString ()); } | "(" a = expr () ")" {returner a; }}

Hovedmetoden instantierer først et parserobjekt, der læser fra standardinput og derefter kalder op parseOneLine () i en endeløs løkke. Metoden parseOneLine () i sig selv er defineret af en yderligere grammatikregel. Denne regel definerer simpelthen, at vi forventer ethvert udtryk på en linje i sig selv, at det er OK at indtaste tomme linjer, og at vi afslutter programmet, hvis vi når slutningen af filen.

Vi har ændret returtypen for de originale grammatikelementer for at returnere dobbelt. Vi udfører passende beregninger lige hvor vi analyserer dem og sender beregningsresultater op i opkaldstræet. Vi har også transformeret definitionerne af grammatikelementerne til at gemme deres resultater i lokale variabler. For eksempel, a = element () analyserer en element og gemmer resultatet i variablen -en. Det gør det muligt for os at bruge resultaterne af parsede elementer i koden for handlingerne på højre side. Handlinger er blokke af Java-kode, der udføres, når den tilknyttede grammatikregel har fundet et match i inputstrømmen.

Bemærk, hvor lidt Java-kode vi tilføjede for at gøre lommeregneren fuldt funktionsdygtig. Desuden er det let at tilføje yderligere funktionalitet, såsom indbyggede funktioner eller endda variabler.