Lurer du på hvordan Java-kompilatoren fungerer? Trenger du å skrive parsere for markeringsdokumenter som ikke abonnerer på standardformater som HTML eller XML? Eller vil du implementere ditt eget lille programmeringsspråk bare for det? JavaCC lar deg gjøre alt dette på Java. Så om du bare er interessert i å lære mer om hvordan kompilatorer og tolker fungerer, eller om du har konkrete ambisjoner om å skape etterfølgeren til Java-programmeringsspråket, kan du bli med meg på månedens oppgave å utforske JavaCC, fremhevet av konstruksjonen av en hendig liten kommandolinjekalkulator.
Grunnleggende om kompilatorkonstruksjon
Programmeringsspråk er ofte delt, noe kunstig, i kompilerte og tolket språk, selv om grensene har blitt uskarpe. Som sådan, ikke bekymre deg for det. Konseptene som diskuteres her, gjelder like godt både kompilerte og tolket språk. Vi skal bruke ordet kompilator nedenfor, men for omfanget av denne artikkelen, skal det omfatte betydningen av tolk.
Kompilatorer må utføre tre hovedoppgaver når de presenteres med en programtekst (kildekode):
- Leksisk analyse
- Syntaktisk analyse
- Kodegenerering eller utføring
Hovedtyngden av kompilatorens arbeid er rundt trinn 1 og 2, som innebærer å forstå programkildekoden og sikre dens syntaktiske korrekthet. Vi kaller den prosessen analysering, hvilken er den parser 's ansvar.
Leksikalanalyse (lexing)
Leksikalanalyse tar en kort titt på programkildekoden og deler den i riktig tokens. Et token er en viktig del av kildekoden til et program. Tokeneksempler inkluderer nøkkelord, tegnsetting, bokstaver som tall og strenger. Ikke-tokener inkluderer hvite mellomrom, som ofte ignoreres, men brukes til å skille tokens, og kommentarer.
Syntaktisk analyse (parsing)
Under syntaktisk analyse trekker en parser ut mening fra programkildekoden ved å sikre programmets syntaktiske korrekthet og ved å bygge en intern representasjon av programmet.
Dataspråksteori snakker om programmer,grammatikk, og språk. Sånn sett er et program en sekvens av tokens. En bokstavelig er et grunnleggende dataspråkelement som ikke kan reduseres ytterligere. En grammatikk definerer regler for å lage syntaktisk riktige programmer. Bare programmer som spiller etter reglene som er definert i grammatikken, er korrekte. Språket er rett og slett settet med alle programmer som tilfredsstiller alle grammatikkreglene dine.
Under syntaktisk analyse undersøker en kompilator programkildekoden med hensyn til reglene som er definert i språkets grammatikk. Hvis noen grammatikkregel blir brutt, viser kompilatoren en feilmelding. Underveis, mens du undersøker programmet, skaper kompilatoren en lett behandlet intern representasjon av dataprogrammet.
Grammatikkregler for et dataspråk kan spesifiseres entydig og i sin helhet med EBNF (Extended Backus-Naur-Form) -notasjonen (for mer informasjon om EBNF, se Ressurser). EBNF definerer grammatikk i form av produksjonsregler. En produksjonsregel sier at et grammatikkelement - enten bokstavelige eller sammensatte elementer - kan være sammensatt av andre grammatiske elementer. Bokstaver, som ikke kan reduseres, er nøkkelord eller fragmenter av statisk programtekst, for eksempel tegnsettingstegn. Komponerte elementer er avledet ved å anvende produksjonsregler. Produksjonsregler har følgende generelle format:
GRAMMAR_ELEMENT: = liste over grammatikkelementer | alternativ liste over grammatikkelementer
Som et eksempel, la oss se på grammatikkreglene for et lite språk som beskriver grunnleggende aritmetiske uttrykk:
ekspr: = antall | uttrykk '+' uttrykk | uttrykk '-' uttrykk | uttrykk '*' uttrykk | ekspr '/' ekspr | '(' expr ')' | - uttrykk nummer: = siffer + ('.' siffer +)? siffer: = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' Tre produksjonsregler definerer grammatikkelementene:
eksprNummersiffer
Språket definert av den grammatikken lar oss spesifisere aritmetiske uttrykk. An ekspr er enten et nummer eller en av de fire infiksoperatørene som er brukt på to eksprs, en ekspr i parentes, eller en negativ ekspr. EN Nummer er et flytende tall med valgfri desimalbrøk. Vi definerer en siffer å være en av de kjente desimaltegnene.
Kodegenerering eller utføring
Når parseren vellykket har analysert programmet uten feil, eksisterer det i en intern representasjon som er lett å behandle av kompilatoren. Det er nå relativt enkelt å generere maskinkode (eller Java bytecode for den saks skyld) fra den interne representasjonen eller å utføre den interne representasjonen direkte. Hvis vi gjør det første, kompilerer vi; i sistnevnte tilfelle snakker vi om tolking.
JavaCC
JavaCC, tilgjengelig gratis, er en parsergenerator. Den gir en Java-språkutvidelse for å spesifisere grammatikken til et programmeringsspråk. JavaCC ble opprinnelig utviklet av Sun Microsystems, men den vedlikeholdes nå av MetaMata. Som ethvert anstendig programmeringsverktøy, JavaCC ble faktisk brukt til å spesifisere grammatikken til JavaCC inngangsformat.
Videre JavaCC lar oss definere grammatikker på en måte som ligner på EBNF, noe som gjør det enkelt å oversette EBNF-grammatikk til JavaCC format. Lengre, JavaCC er den mest populære parsergeneratoren for Java, med en rekke forhåndsdefinerte JavaCC grammatikk tilgjengelig for utgangspunkt.
Utvikling av en enkel kalkulator
Vi går nå tilbake til det lille aritmetiske språket vårt for å bygge en enkel kommandolinjekalkulator i Java ved hjelp av JavaCC. Først må vi oversette EBNF-grammatikken til JavaCC format og lagre den i filen Aritmetikk.jj:
opsjoner {LOOKAHEAD = 2; } PARSER_BEGIN (Arithmetic) public class Arithmetic {} PARSER_END (Arithmetic) SKIP: "\ t" TOKEN: double expr (): {} term () ("+" expr () double term (): {} "/" term ()) * dobbel unary (): {} "-" element () dobbelt element (): {} "(" expr () ")" Koden ovenfor skal gi deg en ide om hvordan du spesifiserer en grammatikk for JavaCC. De alternativer seksjonen øverst spesifiserer et sett med alternativer for den grammatikken. Vi spesifiserer et utseende på 2. Kontroll av tilleggsalternativer JavaCCsine feilsøkingsfunksjoner og mer. Alternativene kan alternativt spesifiseres på JavaCC kommandolinje.
De PARSER_BEGIN klausul spesifiserer at definisjonen av parserklassen følger. JavaCC genererer en enkelt Java-klasse for hver parser. Vi kaller parser-klassen Aritmetikk. Foreløpig krever vi bare en tom klassedefinisjon; JavaCC vil legge til analyseringsrelaterte erklæringer senere. Vi avslutter klassedefinisjonen med PARSER_END klausul.
De HOPP seksjonen identifiserer tegnene vi vil hoppe over. I vårt tilfelle er det tegnene med hvitt mellomrom. Deretter definerer vi tokens til vårt språk i TOKEN seksjon. Vi definerer tall og sifre som tokens. Noter det JavaCC skiller mellom definisjoner for tokens og definisjoner for andre produksjonsregler, som skiller seg fra EBNF. De HOPP og TOKEN seksjoner spesifiserer denne grammatikkens leksikale analyse.
Deretter definerer vi produksjonsregelen for ekspr, det øverste grammatikkelementet. Legg merke til hvordan den definisjonen markant skiller seg fra definisjonen av ekspr i EBNF. Hva skjer? Vel, det viser seg at EBNF-definisjonen ovenfor er tvetydig, da den tillater flere representasjoner av det samme programmet. La oss for eksempel undersøke uttrykket 1+2*3. Vi kan matche 1+2 inn i en ekspr gi fra seg uttrykk * 3, som i figur 1.
Eller alternativt kan vi først matche 2*3 inn i en ekspr resulterer i 1 + eks, som vist i figur 2.
Med JavaCC, må vi spesifisere grammatikkreglene entydig. Som et resultat bryter vi ut definisjonen av ekspr i tre produksjonsregler, som definerer grammatikkelementene ekspr, begrep, unary, og element. Nå, uttrykket 1+2*3 er analysert som vist i figur 3.
Fra kommandolinjen kan vi løpe JavaCC for å sjekke grammatikken vår:
javacc Arithmetic.jj Java Compiler Compiler Versjon 1.1 (Parser Generator) Copyright (c) 1996-1999 Sun Microsystems, Inc. Copyright (c) 1997-1999 Metamata, Inc. (skriv "javacc" uten argumenter for hjelp) Lesing fra fil Aritmetikk.jj. . . Advarsel: Kontroll av tilstrekkelig utseende er ikke utført siden alternativet LOOKAHEAD er mer enn 1. Sett alternativet FORCE_LA_CHECK til true for force-testing. Parser generert med 0 feil og 1 advarsel.
Følgende kontrollerer grammatikkdefinisjonen vår for problemer og genererer et sett med Java-kildefiler:
TokenMgrError.java ParseException.java Token.java ASCII_CharStream.java Arithmetic.java ArithmeticConstants.java ArithmeticTokenManager.java
Sammen implementerer disse filene parseren i Java. Du kan påkalle denne parseren ved å starte en forekomst av Aritmetikk klasse:
offentlig klasse Aritmetikk implementerer ArithmeticConstants {public Arithmetic (java.io.InputStream stream) {...} public Arithmetic (java.io.Reader stream) {...} public Arithmetic (ArithmeticTokenManager tm) {...} static final public double expr () kaster ParseException {...} statisk endelig offentlig dobbeltbegrep () kaster ParseException {...} statisk endelig offentlig dobbelt unary () kaster ParseException {...} statisk endelig offentlig dobbeltelement () kaster ParseException {. ..} statisk offentlig ugyldig ReInit (java.io.InputStream stream) {...} statisk offentlig ugyldig 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 ugyldig disable_tracing () {...}} Hvis du ønsket å bruke denne parseren, må du opprette en forekomst ved hjelp av en av konstruktørene. Konstruktørene lar deg passere i enten en InputStream, a Leser, eller en ArithmeticTokenManager som kilden til programkildekoden. Deretter angir du hovedgrammatikkelementet til språket ditt, for eksempel:
Aritmetisk parser = ny aritmetikk (System.in); parser.expr ();
Imidlertid skjer det ikke mye ennå fordi i Aritmetikk.jj vi har bare definert grammatikkreglene. Vi har ennå ikke lagt til koden som er nødvendig for å utføre beregningene. For å gjøre dette, legger vi til passende handlinger i grammatikkreglene. Calcualtor.jj inneholder den komplette kalkulatoren, inkludert handlinger:
opsjoner {LOOKAHEAD = 2; } PARSER_BEGIN (Kalkulator) offentlig klasse Kalkulator {offentlig statisk ugyldig hoved (String args []) kaster ParseException {Kalkulator parser = ny Kalkulator (System.in); while (true) {parser.parseOneLine (); }}} PARSER_END (Kalkulator) HOPP: "\ t" TOKEN: ugyldig parseOneLine (): {doble a; } {a = expr () {System.out.println (a); } | | {System.exit (-1); }} dobbel ekspr (): {dobbel a; dobbel b; } {a = term () ("+" b = expr () {a + = b;} | "-" b = expr () {a - = b;}) * {return a; }} dobbeltbegrep (): {dobbelt a; dobbel b; } {a = unary () ("*" b = term () {a * = b;} | "/" b = term () {a / = b;}) * {return a; }} dobbel unary (): {doble a; } {"-" a = element () {return -a; } | a = element () {return a; }} dobbeltelement (): {Token t; doble a; } {t = {return Double.parseDouble (t.toString ()); } | "(" a = expr () ")" {return a; }} Hovedmetoden starter først et parserobjekt som leser fra standardinndata og deretter anrop parseOneLine () i en endeløs løkke. Metoden parseOneLine () i seg selv er definert av en ekstra grammatikkregel. Denne regelen definerer ganske enkelt at vi forventer hvert uttrykk på en linje i seg selv, at det er OK å legge inn tomme linjer, og at vi avslutter programmet hvis vi når slutten av filen.
Vi har endret returtypen til de originale grammatikkelementene for å returnere dobbelt. Vi utfører passende beregninger der vi analyserer dem og sender beregningsresultater opp i anropstreet. Vi har også transformert definisjonene av grammatikkelementene for å lagre resultatene i lokale variabler. For eksempel, a = element () analyserer en element og lagrer resultatet i variabelen en. Det gjør at vi kan bruke resultatene av analyserte elementer i koden til handlingene på høyre side. Handlinger er blokker av Java-kode som utføres når den tilhørende grammatikkregelen har funnet samsvar i inngangsstrømmen.
Vær oppmerksom på hvor lite Java-kode vi la til for å gjøre kalkulatoren fullt funksjonell. Videre er det enkelt å legge til ekstra funksjonalitet, for eksempel innebygde funksjoner eller til og med variabler.
