Sidste måned kiggede jeg på de klasser, som Java leverer til grundlæggende leksikalsk analyse. Denne måned går jeg gennem en simpel applikation, der bruger StreamTokenizer at implementere en interaktiv lommeregner.
For at gennemgå sidste måneds artikel kort er der to leksikale-analysatorklasser, der er inkluderet i standard Java-distributionen: StringTokenizer og StreamTokenizer. Disse analysatorer konverterer deres input til diskrete tokens, som en parser kan bruge til at forstå et givet input. Parseren implementerer en grammatik, der er defineret som en eller flere måltilstande nået ved at se forskellige sekvenser af tokens. Når en parsers måltilstand er nået, udfører den en eller anden handling. Når parseren registrerer, at der ikke er nogen mulige måltilstande givet den aktuelle række af tokens, definerer den dette som en fejltilstand. Når en parser når en fejltilstand, udfører den en gendannelseshandling, som bringer parseren tilbage til et punkt, hvor den kan begynde at parses igen. Dette implementeres typisk ved at forbruge tokens, indtil parseren er tilbage til et gyldigt startpunkt.
Sidste måned viste jeg dig nogle metoder, der brugte en StringTokenizer for at analysere nogle inputparametre. Denne måned viser jeg dig et program, der bruger en StreamTokenizer gøre indsigelse mod at analysere en inputstrøm og implementere en interaktiv lommeregner.
Opbygning af en applikation
Vores eksempel er en interaktiv lommeregner, der ligner Unix bc (1) -kommandoen. Som du vil se, skubber det StreamTokenizer klasse lige til kanten af dets anvendelighed som en leksikalsk analysator. Det tjener således som en god demonstration af, hvor grænsen mellem "enkle" og "komplekse" analysatorer kan trækkes. Dette eksempel er et Java-program og kører derfor bedst fra kommandolinjen.
Som en hurtig oversigt over dets evner accepterer lommeregneren udtryk i formularen
[variabelnavn] "=" udtryk
Variabelnavnet er valgfrit og kan bestå af en hvilken som helst streng af tegn i standardordområdet. (Du kan bruge træningsapplet fra sidste måneds artikel til at opdatere din hukommelse på disse tegn.) Hvis variabelnavnet udelades, udskrives udtrykkets værdi simpelthen. Hvis variabelnavnet er til stede, tildeles variablen værdien af udtrykket. Når variabler er tildelt, kan de bruges i senere udtryk. Således udfylder de rollen som "minder" på en moderne håndholdt lommeregner.
Udtrykket er sammensat af operander i form af numeriske konstanter (dobbeltpræcision, konstanter med flydende punkt) eller variable navne, operatorer og parenteser til gruppering af bestemte beregninger. De juridiske operatorer er addition (+), subtraktion (-), multiplikation (*), division (/), bitvis OG (&), bitvis ELLER (|), bitvis XOR (#), eksponentiering (^) og unary negation med enten minus (-) for resultatet af det to komplement eller bang (!) for resultatet af det ene komplement.
Ud over disse udsagn kan vores lommeregnerapplikation også tage en af fire kommandoer: "dump", "clear", "help" og "quit." Det dump kommando udskriver alle de variabler, der aktuelt er defineret, samt deres værdier. Det klar kommando sletter alle de aktuelt definerede variabler. Det Hjælp kommando udskriver et par linjer hjælpetekst for at få brugeren i gang. Det Afslut kommandoen får applikationen til at afslutte.
Hele eksemplet på applikationen består af to parsere - en til kommandoer og udsagn og en til udtryk.
Opbygning af en kommandoparser
Kommandoparseren implementeres i applikationsklassen til eksemplet STExample.java. (Se afsnittet Ressourcer for en markør til koden.) vigtigste Metoden til denne klasse er defineret nedenfor. Jeg går igennem stykkerne for dig.
1 offentlig statisk ugyldig hoved (String args []) kaster IOException {2 Hashtable-variabler = ny Hashtable (); 3 StreamTokenizer st = ny StreamTokenizer (System.in); 4 st.eolIsSignificant (sand); 5 st.lowerCaseMode (sand); 6. st. OrdinærChar ('/'); 7. st. Ordinær Char ('-'); I koden ovenfor er det første, jeg gør, at allokere en java.util.Hashtable klasse til at indeholde variablerne. Derefter tildeler jeg en StreamTokenizer og juster den lidt fra dens standardindstillinger. Begrundelsen for ændringerne er som følger:
eolIsSignificant er indstillet til rigtigt så tokeniseren returnerer en indikation af slutningen af linjen. Jeg bruger slutningen af linjen som det punkt, hvor udtrykket slutter.
lavereCaseMode er indstillet til rigtigt så variabelnavne altid returneres med små bogstaver. På denne måde er variabelnavne ikke store og små bogstaver.
Skråstregstegnet (/) er indstillet til at være et almindeligt tegn, så det ikke bruges til at angive starten på en kommentar og kan i stedet bruges som divisionsoperator.
Minustegnet (-) er indstillet til at være et almindeligt tegn, så strengen "3-3" segmenterer i tre tokens - "3", "-" og "3" - snarere end blot "3" og "-3." (Husk, at nummerparsing er som standard indstillet til "til").
Når tokeniseren er konfigureret, kører kommandoparseren i en uendelig løkke (indtil den genkender kommandoen "afslut" på hvilket tidspunkt den afsluttes). Dette er vist nedenfor.
8 mens (sand) {9 Udtryksopgørelse; 10 int c = StreamTokenizer.TT_EOL; 11 streng varName = null; 12 13 System.out.println ("Indtast et udtryk ..."); 14 prøv {15 mens (sandt) {16 c = st.nextToken (); 17 hvis (c == StreamTokenizer.TT_EOF) {18 System.exit (1); 19} ellers hvis (c == StreamTokenizer.TT_EOL) {20 fortsætter; 21} ellers hvis (c == StreamTokenizer.TT_WORD) {22 if (st.sval.compareTo ("dump") == 0) {23 dumpVariables (variabler); 24 fortsæt; 25} ellers hvis (st.sval.compareTo ("clear") == 0) {26 variabler = ny Hashtable (); 27 fortsæt; 28} ellers hvis (st.sval.compareTo ("quit") == 0) {29 System.exit (0); 30} ellers hvis (st.sval.compareTo ("exit") == 0) {31 System.exit (0); 32} ellers hvis (st.sval.compareTo ("hjælp") == 0) {33 hjælp (); 34 fortsæt; 35} 36 varName = st.sval; 37 c = st.nextToken (); 38} 39 pause 40} 41 if (c! = '=') {42 smid nyt SyntaxError ("manglende initial '=' tegn."); 43} Som du kan se i linje 16 kaldes det første token ved at påberåbe sig næsteToken på den StreamTokenizer objekt. Dette returnerer en værdi, der angiver den type token, der blev scannet. Returværdien er enten en af de definerede konstanter i StreamTokenizer klasse, eller det vil være en tegnværdi. "Meta" tokens (dem, der ikke blot er tegnværdier) defineres som følger:
TT_EOF- Dette indikerer, at du er i slutningen af inputstrømmen. I modsætning tilStringTokenizer, der er ingenhasMoreTokensmetode.TT_EOL- Dette fortæller dig, at objektet lige har passeret en slut-af-linjesekvens.TT_NUMBER- Denne token-type fortæller din parserkode, at der er set et tal på input.TT_WORD- Denne token-type angiver, at et helt "ord" blev scannet.
Når resultatet ikke er en af ovenstående konstanter, er det enten tegnværdien, der repræsenterer et tegn i det "almindelige" tegninterval, der blev scannet, eller et af de citattegn, du har angivet. (I mit tilfælde er der ikke angivet et citattegn.) Når resultatet er et af dine citattegn, kan den citerede streng findes i strenginstansvariablen sval af StreamTokenizer objekt.
Koden i linje 17 til 20 omhandler indikationer fra slutningen af linjen og slutningen af filen, hvorimod i linje 21 tages if-klausulen, hvis et ordtoken blev returneret. I dette enkle eksempel er ordet enten en kommando eller et variabelnavn. Linjer 22 til 35 omhandler de fire mulige kommandoer. Hvis linje 36 nås, skal det være et variabelt navn; Derfor opbevarer programmet en kopi af variabelnavnet og får det næste token, som skal være et lighedstegn.
Hvis symbolet i linje 41 ikke var et lighedstegn, registrerer vores enkle parser en fejltilstand og kaster en undtagelse for at signalere det. Jeg skabte to generiske undtagelser, Syntaks fejl og ExecError, for at skelne parse-time-fejl fra run-run-fejl. Det vigtigste metoden fortsætter med linje 44 nedenfor.
44 res = ParseExpression.expression (st); 45} fange (SyntaxError se) {46 res = null; 47 varName = null; 48 System.out.println ("\ nSyntax-fejl opdaget! -" + se.getMsg ()); 49 mens (c! = StreamTokenizer.TT_EOL) 50 c = st.nextToken (); 51 fortsæt; 52} I linje 44 tolkes udtrykket til højre for lighedstegnet med det udtryk, der er defineret i ParseExpression klasse. Bemærk, at linje 14 til 44 er pakket ind i en prøve / fangst-blok, der fælder syntaksfejl og håndterer dem. Når der opdages en fejl, er parserens gendannelseshandling at forbruge alle tokens til og med det næste slut-af-line-token. Dette er vist i linje 49 og 50 ovenfor.
På dette tidspunkt, hvis en undtagelse ikke blev kastet, har applikationen korrekt analyseret en erklæring. Den sidste kontrol er at se, at det næste token er slutningen af linjen. Hvis det ikke er tilfældet, er en fejl uopdaget. Den mest almindelige fejl vil være uoverensstemmende parenteser. Denne kontrol vises i linje 53 til 60 i nedenstående kode.
53 c = st.nextToken (); 54 if (c! = StreamTokenizer.TT_EOL) {55 if (c == ')') 56 System.out.println ("\ nSyntax-fejl opdaget! - For mange lukkende parener."); 57 andet 58 System.out.println ("\ nBogus-token på input -" + c); 59 mens (c! = StreamTokenizer.TT_EOL) 60 c = st.nextToken (); 61} andet { Når det næste token er slutningen på linjen, udfører programmet linierne 62 til og med 69 (vist nedenfor). Dette afsnit af metoden evaluerer det parsede udtryk. Hvis variabelnavnet blev indstillet i linje 36, gemmes resultatet i symboltabellen. I begge tilfælde, hvis der ikke kastes nogen undtagelse, udskrives udtrykket og dets værdi til System.out-strømmen, så du kan se, hvad parseren afkodede.
62 prøv {63 Dobbelt z; 64 System.out.println ("Analyseret udtryk:" + res.unparse ()); 65 z = ny dobbelt (res.værdi (variabler)); 66 System.out.println ("Værdi er:" + z); 67 hvis (varName! = Null) {68 variables.put (varName, z); 69 System.out.println ("Tildelt til:" + varName); 70} 71} catch (ExecError ee) {72 System.out.println ("Execution error," + ee.getMsg () + "!"); 73} 74} 75} 76} I STeksempel klasse, den StreamTokenizer bruges af en parser til kommandoprocessoren. Denne type parser vil almindeligvis blive brugt i et shell-program eller i enhver situation, hvor brugeren udsteder kommandoer interaktivt. Den anden parser er indkapslet i ParseExpression klasse. (Se afsnittet Ressourcer for den komplette kilde.) Denne klasse analyserer regnemaskinens udtryk og påberåbes i linje 44 ovenfor. Det er her det StreamTokenizer står over for sin stiveste udfordring.
Opbygning af en udtryksparser
Grammatikken til lommeregnerens udtryk definerer en algebraisk syntaks af formularen "[item] operator [item]." Denne type grammatik kommer op igen og igen og kaldes en operatør grammatik. En praktisk notation for en operatørgrammatik er:
id ("OPERATOR" id) * Koden ovenfor læses "En ID-terminal efterfulgt af nul eller flere forekomster af en operatør-id-tuple." Det StreamTokenizer klasse synes at være ret ideel til at analysere sådanne strømme, fordi designet naturligvis bryder inputstrømmen ind i ord, nummerog almindelig karakter tokens. Som jeg vil vise dig, er dette sandt op til et punkt.
Det ParseExpression klasse er en ligefrem, recursiv afstamnings-parser til udtryk lige fra en bachelor-kompilator-design klasse. Det Udtryk metode i denne klasse er defineret som følger:
1 statisk udtryksudtryk (StreamTokenizer st) kaster SyntaxError {2 Ekspressionsresultat; 3 boolsk udført = falsk; 4 5 resultat = sum (st); 6 mens (! Færdig) {7 prøv {8 switch (st.nextToken ()) 9 sag '&': 10 resultat = nyt udtryk (OP_AND, resultat, sum (st)); 11 pause 12 tilfælde '23} fangst (IOException ioe) {24 kast ny SyntaxError ("Fik en I / O-undtagelse."); 25} 26} 27 returresultat; 28}
