I forrige måned så jeg på klassene som Java tilbyr for å gjøre grunnleggende leksikalanalyse. Denne måneden går jeg gjennom et enkelt program som bruker StreamTokenizer å implementere en interaktiv kalkulator.
For å gjennomgå artikkelen i forrige måned, er det to leksikale analysatorklasser som er inkludert i standard Java-distribusjon: StringTokenizer og StreamTokenizer. Disse analysatorene konverterer sine innganger til diskrete tokens som en parser kan bruke for å forstå en gitt inngang. Parseren implementerer en grammatikk, som er definert som en eller flere måltilstander nådd ved å se forskjellige sekvenser av tokens. Når en parsers målstatus er nådd, utfører den noe. Når parseren oppdager at det ikke er noen mulige måltilstander gitt den nåværende tokensekvensen, definerer den dette som en feiltilstand. Når en parser når en feiltilstand, utfører den en gjenopprettingshandling som får parseren tilbake til et punkt der den kan begynne å parses igjen. Vanligvis implementeres dette ved å konsumere tokens til parseren er tilbake til et gyldig startpunkt.
I forrige måned viste jeg deg noen metoder som brukte en StringTokenizer for å analysere noen inngangsparametere. Denne måneden viser jeg deg et program som bruker en StreamTokenizer motsette seg å analysere en inngangsstrøm og implementere en interaktiv kalkulator.
Bygg en applikasjon
Eksemplet vårt er en interaktiv kalkulator som ligner på Unix bc (1) -kommandoen. Som du ser, skyver det StreamTokenizer klasse helt til kanten av verktøyet som en leksikalsk analysator. Dermed fungerer det som en god demonstrasjon av hvor linjen mellom "enkle" og "komplekse" analysatorer kan trekkes. Dette eksemplet er et Java-program og kjører derfor best fra kommandolinjen.
Som en rask oppsummering av evnene, godtar kalkulatoren uttrykk i skjemaet
[variabelnavn] "=" uttrykk
Variabelnavnet er valgfritt og kan være en hvilken som helst streng med tegn i standard ordområdet. (Du kan bruke treningsappleten fra forrige måneds artikkel for å oppdatere minnet ditt på disse tegnene.) Hvis variabelnavnet er utelatt, blir verdien av uttrykket ganske enkelt skrevet ut. Hvis variabelnavnet er tilstede, tilordnes verdien av uttrykket variabelen. Når variabler er tildelt, kan de brukes i senere uttrykk. Dermed fyller de rollen som "minner" på en moderne håndholdt kalkulator.
Uttrykket er sammensatt av operander i form av numeriske konstanter (dobbel presisjon, flytende punktkonstanter) eller variabelnavn, operatorer og parenteser for gruppering av bestemte beregninger. De juridiske operatorene er addisjon (+), subtraksjon (-), multiplikasjon (*), divisjon (/), bitvis OG (&), bitvis ELLER (|), bitvis XOR (#), eksponentiering (^) og unary negasjon med enten minus (-) for resultatene for to komplement eller bang (!) for resultatene for komplement.
I tillegg til disse uttalelsene, kan kalkulatorprogrammet vårt ta en av fire kommandoer: "dump", "clear", "help" og "quit." De dump kommandoen skriver ut alle variablene som er definert for øyeblikket, samt verdiene. De klar kommandoen sletter alle de nåværende definerte variablene. De hjelp kommandoen skriver ut noen få linjer med hjelpetekst for å få brukeren i gang. De slutte kommandoen får applikasjonen til å avslutte.
Hele eksempelapplikasjonen består av to parsere - en for kommandoer og utsagn og en for uttrykk.
Bygg en kommandoparser
Kommandoparseren er implementert i applikasjonsklassen for eksemplet STExample.java. (Se delen Ressurser for en peker til koden.) hoved- Metoden for den klassen er definert nedenfor. Jeg går gjennom bitene for deg.
1 offentlig statisk ugyldig hoved (String args []) kaster IOException {2 Hashtable-variabler = ny Hashtable (); 3 StreamTokenizer st = ny StreamTokenizer (System.in); 4 st.eolIsSignificant (true); 5 st.lowerCaseMode (sann); 6 st. OrdinærChar ('/'); 7. st. Ordinær Char ('-'); I koden over er det første jeg gjør å tildele en java.util.hashtable klasse for å holde variablene. Etter det tildeler jeg en StreamTokenizer og juster den litt fra standardinnstillingene. Begrunnelsen for endringene er som følger:
eolIsSignificant er satt til ekte slik at tokenizer vil returnere en indikasjon på slutten av linjen. Jeg bruker slutten av linjen som punktet hvor uttrykket slutter.
lowerCaseMode er satt til ekte slik at variabelnavnene alltid returneres med små bokstaver. På denne måten er ikke variablenavn store og små bokstaver.
Slash-tegnet (/) er satt til å være et vanlig tegn slik at det ikke vil bli brukt til å indikere starten på en kommentar, og kan brukes i stedet som divisjonsoperatør.
Minustegnet (-) er satt til å være et vanlig tegn slik at strengen "3-3" vil segmentere i tre tokens - "3", "-" og "3" - i stedet for bare "3" og "-3." (Husk at antall parsing er satt til "på" som standard.)
Når tokenisatoren er satt opp, kjører kommandoparseren i en uendelig løkke (til den gjenkjenner "avslutte" -kommandoen på hvilket tidspunkt den går ut). Dette er vist nedenfor.
8 while (true) {9 Expression res; 10 int c = StreamTokenizer.TT_EOL; 11 streng varName = null; 12 13 System.out.println ("Skriv inn et uttrykk ..."); 14 prøv {15 mens (sann) {16 c = st.nextToken (); 17 hvis (c == StreamTokenizer.TT_EOF) {18 System.exit (1); 19} annet hvis (c == StreamTokenizer.TT_EOL) {20 fortsetter; 21} annet hvis (c == StreamTokenizer.TT_WORD) {22 if (st.sval.compareTo ("dump") == 0) {23 dumpVariables (variabler); 24 fortsette; 25} annet hvis (st.sval.compareTo ("clear") == 0) {26 variabler = ny Hashtable (); 27 fortsett; 28} annet hvis (st.sval.compareTo ("quit") == 0) {29 System.exit (0); 30} annet hvis (st.sval.compareTo ("exit") == 0) {31 System.exit (0); 32} annet hvis (st.sval.compareTo ("hjelp") == 0) {33 hjelp (); 34 fortsett; 35} 36 varName = st.sval; 37 c = st.nextToken (); 38} 39 pause; 40} 41 if (c! = '=') {42 kaste nytt SyntaxError ("mangler initial '=' tegn."); 43} Som du kan se i linje 16, kalles det første token ved å påkalle nesteToken på StreamTokenizer gjenstand. Dette returnerer en verdi som indikerer typen token som ble skannet. Returverdien vil enten være en av de definerte konstantene i StreamTokenizer klasse eller det vil være en tegnverdi. "Meta" -tegnene (de som ikke bare er tegnverdier) er definert som følger:
TT_EOF- Dette indikerer at du er på slutten av inngangsstrømmen. I motsetning tilStringTokenizer, det er ingenhasMoreTokensmetode.TT_EOL- Dette forteller deg at objektet nettopp har passert en sluttsekvens.TT_NUMBER- Denne token-typen forteller parserkoden at det er sett et tall på inngangen.TT_WORD- Denne symboltypen indikerer at et helt "ord" ble skannet.
Når resultatet ikke er en av de ovennevnte konstantene, er det enten tegnverdien som representerer et tegn i det "vanlige" tegnområdet som ble skannet, eller et av sitattegnene du har angitt. (I mitt tilfelle er det ikke angitt noe sitattegn.) Når resultatet er et av sitattegnene dine, kan den siterte strengen finnes i strenginstansvariabelen. sval av StreamTokenizer gjenstand.
Koden i linje 17 til 20 omhandler indikasjoner på slutten av linjen og slutten av filen, mens i ledd 21 tas if-leddet hvis et ordtegn ble returnert. I dette enkle eksemplet er ordet enten en kommando eller et variabelnavn. Linjene 22 til 35 omhandler de fire mulige kommandoene. Hvis linje 36 er nådd, må den være et variabelnavn; følgelig beholder programmet en kopi av variabelnavnet og får neste token, som må være et likhetstegn.
Hvis symbolet i linje 41 ikke var et likhetstegn, oppdager vår enkle parser en feiltilstand og kaster et unntak for å signalisere det. Jeg opprettet to generiske unntak, Syntaksfeil og ExecError, for å skille parse-time feil fra runtime feil. De hoved- metoden fortsetter med linje 44 nedenfor.
44 res = ParseExpression.expression (st); 45} fange (SyntaxError se) {46 res = null; 47 varName = null; 48 System.out.println ("\ nSyntaksfeil oppdaget! -" + se.getMsg ()); 49 mens (c! = StreamTokenizer.TT_EOL) 50 c = st.nextToken (); 51 fortsett; 52} I linje 44 blir uttrykket til høyre for likhetstegnet analysert med uttrykket parser definert i ParseExpression klasse. Merk at linjene 14 til 44 er pakket inn i en prøve / fangst-blokk som fanger syntaksfeil og behandler dem. Når en feil oppdages, er parserens gjenopprettingshandling å konsumere alle tokens til og med neste end-of-line-token. Dette er vist i linjene 49 og 50 ovenfor.
På dette punktet, hvis et unntak ikke ble kastet, har applikasjonen vellykket analysert en uttalelse. Den siste kontrollen er å se at neste token er slutten på linjen. Hvis det ikke er det, har en feil blitt oppdaget. Den vanligste feilen vil være feilparenteser i parentes. Denne sjekken vises i linjene 53 til 60 i koden nedenfor.
53 c = st.nextToken (); 54 if (c! = StreamTokenizer.TT_EOL) {55 if (c == ')') 56 System.out.println ("\ nSyntaksfeil oppdaget! - For mange avsluttende foreldre."); 57 annet 58 System.out.println ("\ nBogus-token på inngang -" + c); 59 mens (c! = StreamTokenizer.TT_EOL) 60 c = st.nextToken (); 61} annet { Når neste token er slutten på linjen, utfører programmet linjene 62 til og med 69 (vist nedenfor). Denne delen av metoden evaluerer det analyserte uttrykket. Hvis variabelnavnet ble satt i linje 36, lagres resultatet i symboltabellen. I begge tilfeller, hvis ingen unntak blir kastet, blir uttrykket og verdien skrevet ut til System.out-strømmen slik at du kan se hva parseren dekodet.
62 prøv {63 Dobbel z; 64 System.out.println ("Analysert uttrykk:" + res.unparse ()); 65 z = ny dobbel (res.verdi (variabler)); 66 System.out.println ("Verdien er:" + z); 67 hvis (varName! = Null) {68 variables.put (varName, z); 69 System.out.println ("Tildelt til:" + varName); 70} 71} fangst (ExecError ee) {72 System.out.println ("Utførelsesfeil," + ee.getMsg () + "!"); 73} 74} 75} 76} I STeksempel klasse, den StreamTokenizer brukes av en kommandoprosessor-parser. Denne typen parsere vil ofte bli brukt i et skallprogram eller i enhver situasjon der brukeren utsteder kommandoer interaktivt. Den andre parseren er innkapslet i ParseExpression klasse. (Se Ressursdelen for hele kilden.) Denne klassen analyserer kalkulatorens uttrykk og blir påkalt i linje 44 ovenfor. Det er her det StreamTokenizer møter sin stiveste utfordring.
Å bygge en uttrykksparser
Grammatikken for kalkulatorens uttrykk definerer en algebraisk syntaks av skjemaet "[item] operator [item]." Denne typen grammatikk kommer opp igjen og igjen og kalles en operatør grammatikk. En praktisk notasjon for en brukergrammatikk er:
id ("OPERATOR" id) * Koden ovenfor vil bli lest "En ID-terminal etterfulgt av null eller flere forekomster av en operatør-id-tuple." De StreamTokenizer klasse virker ganske ideell for å analysere slike strømmer, fordi designet naturlig bryter inngangsstrømmen inn i ord, Nummer, og vanlig karakter tokens. Som jeg skal vise deg, er dette opp til et punkt.
De ParseExpression klasse er en enkel, rekursiv nedstignings-parser for uttrykk, rett ut av en lavere kompilator-design klasse. De Uttrykk Metoden i denne klassen er definert som følger:
1 statisk uttrykk uttrykk (StreamTokenizer st) kaster SyntaxError {2 Uttrykk resultat; 3 boolsk ferdig = falsk; 4 5 resultat = sum (st); 6 mens (! Ferdig) {7 prøv {8 switch (st.nextToken ()) 9 case '&': 10 result = new Expression (OP_AND, result, sum (st)); 11 pause; 12 tilfelle '23} fangst (IOException ioe) {24 kast ny SyntaxError ("Fikk et I / O-unntak."); 25} 26} 27 returresultat; 28}
