Leksisk analyse og Java: Del 1

Leksisk analyse og parsing

Når du skriver Java-applikasjoner, er en av de vanligste tingene du må lage en parser. Parsere spenner fra enkle til komplekse og brukes til alt fra å se på kommandolinjealternativer til å tolke Java-kildekode. I JavaWorldI desember-utgaven viste jeg deg Jack, en automatisk parsergenerator som konverterer grammatikkspesifikasjoner på høyt nivå til Java-klasser som implementerer parseren beskrevet av disse spesifikasjonene. Denne måneden viser jeg deg ressursene som Java tilbyr for å skrive målrettede leksikale analysatorer og parsere. Disse litt enklere parserne fyller gapet mellom enkel strengesammenligning og de komplekse grammatikkene som Jack kompilerer.

Hensikten med leksikale analysatorer er å ta en strøm av inngangskarakterer og dekode dem til tokener på høyere nivå som en parser kan forstå. Parsere forbruker utdataene fra den leksikale analysatoren og opererer ved å analysere sekvensen av poletter som returneres. Parseren matcher disse sekvensene til en sluttilstand, som kan være en av muligens mange slutttilstander. Sluttstatene definerer mål av parseren. Når en sluttilstand er nådd, gjør programmet ved hjelp av parseren noen handlinger - enten å sette opp datastrukturer eller å utføre en handlingsspesifikk kode. I tillegg kan parsere oppdage - fra sekvensen av tokens som er behandlet - når ingen juridisk slutttilstand kan nås; på det tidspunktet identifiserer parseren gjeldende tilstand som en feiltilstand. Det er opp til applikasjonen å bestemme hvilken handling som skal utføres når parseren identifiserer enten en slutttilstand eller en feiltilstand.

Standard Java-klassebase inkluderer et par leksikale analysatorklasser, men den definerer ikke noen generelle parserklasser. I denne kolonnen vil jeg se nærmere på de leksikale analysatorene som følger med Java.

Java's leksikale analysatorer

Java Language Specification, versjon 1.0.2, definerer to leksikale analysatorklasser, StringTokenizer og StreamTokenizer. Fra navnene deres kan du trekke det StringTokenizer bruker String objekter som input, og StreamTokenizer bruker InputStream gjenstander.

StringTokenizer-klassen

Av de to tilgjengelige leksikale analysatorklassene er det enklest å forstå StringTokenizer. Når du konstruerer en ny StringTokenizer objekt, tar konstruktormetoden nominelt to verdier - en inngangsstreng og en avgrensningsstreng. Klassen konstruerer deretter en sekvens med tokens som representerer tegnene mellom skilletegnene.

Som en leksikalanalysator, StringTokenizer kan formelt defineres som vist nedenfor.

[~ delim1, delim2, ..., delimN] :: Token 

Denne definisjonen består av et regulært uttrykk som samsvarer med alle tegn unntatt skilletegnene. Alle tilstøtende samsvarende tegn samles i ett enkelt token og returneres som et token.

Den vanligste bruken av StringTokenizer klasse er for å skille ut et sett med parametere - for eksempel en komma-separert liste over tall. StringTokenizer er ideell i denne rollen fordi den fjerner skilletegnene og returnerer dataene. De StringTokenizer klasse gir også en mekanisme for å identifisere lister der det er "null" tokens. Du bruker nulltegn i applikasjoner der noen parametere enten har standardverdier eller ikke er pålagt å være til stede i alle tilfeller.

Appleten nedenfor er enkel StringTokenizer mosjonist. Kilden til StringTokenizer-appleten er her. For å bruke appleten, skriv inn tekst som skal analyseres i området for inngangsstreng, og skriv deretter en streng som består av skilletegn i området Separatorstreng. Til slutt klikker du på Tokenize! knapp. Resultatet vises i token-listen under inngangsstrengen og vil bli organisert som ett token per linje.

Tenk som eksempel på en streng, "a, b, d", sendt til a StringTokenizer objekt som er konstruert med komma (,) som skilletegn. Hvis du legger disse verdiene i treningsappleten ovenfor, ser du at Tokenizer objektet returnerer strengene "a", "b" og "d." Hvis intensjonen din var å merke seg at en parameter manglet, kan det hende du har blitt overrasket over å ikke se noen indikasjon på dette i tokensekvensen. Evnen til å oppdage manglende tokens er aktivert av Return Separator boolean som kan angis når du oppretter en Tokenizer gjenstand. Med denne parameteren angitt når Tokenizer er konstruert, returneres også hver separator. Klikk i avkrysningsruten for Return Separator i appleten ovenfor, og la strengen og separatoren være alene. Nå er det Tokenizer returnerer "a, komma, b, komma, komma og d." Ved å merke seg at du får to skilletegn i rekkefølge, kan du bestemme at et "null" -token ble inkludert i inngangsstrengen.

Trikset med hell å bruke StringTokenizer i en parser defineres inngangen på en slik måte at skilletegnet ikke vises i dataene. Det er klart at du kan unngå denne begrensningen ved å designe den i applikasjonen din. Metodedefinisjonen nedenfor kan brukes som en del av en applet som godtar en farge i form av røde, grønne og blå verdier i parameterstrømmen.

 / ** * Analyser en parameter i skjemaet "10,20,30" som en * RGB-tuple for en fargeverdi. * / 1 Farge getColor (strengnavn) {2 strengdata; 3 StringTokenizer st; 4 int rød, grønn, blå; 5 6 data = getParameter (navn); 7 hvis (data == null) 8 returnerer null; 9 10 st = ny StringTokenizer (data, ","); 11 prøv {12 rød = Integer.parseInt (st.nextToken ()); 13 grønn = Integer.parseInt (st.nextToken ()); 14 blå = Integer.parseInt (st.nextToken ()); 15} fange (Unntak e) {16 return null; // (FEILSTAT) kunne ikke analysere det 17} 18 returnere ny Farge (rød, grønn, blå); // (SLUTTSTATUS) ferdig. 19} 

Koden ovenfor implementerer en veldig enkel parser som leser strengen "nummer, nummer, nummer" og returnerer en ny Farge gjenstand. I linje 10 lager koden en ny StringTokenizer objekt som inneholder parameterdataene (antar at denne metoden er en del av en applet), og en skilletegnliste som består av komma. I linje 12, 13 og 14 ekstraheres hvert token fra strengen og konverteres til et tall ved hjelp av heltallet parseInt metode. Disse konverteringene er omgitt av en prøve / fange blokker i tilfelle antall strengene ikke var gyldige tall eller Tokenizer kaster et unntak fordi det har gått tom for tokens. Hvis alle tallene konverterer, nås slutttilstanden og a Farge gjenstand returneres; ellers er feiltilstanden nådd og null blir returnert.

En funksjon av StringTokenizer klassen er at den lett kan stables. Se på metoden som heter getColor nedenfor, som er linjene 10 til 18 i fremgangsmåten ovenfor.

 / ** * Analyser en fargetuple "r, g, b" i en AWT Farge gjenstand. * / 1 Farge getColor (strengdata) {2 int rød, grønn, blå; 3 StringTokenizer st = ny StringTokenizer (data, ","); 4 prøv {5 rød = Integer.parseInt (st.nextToken ()); 6 grønn = Integer.parseInt (st.nextToken ()); 7 blå = Integer.parseInt (st.nextToken ()); 8} fange (Unntak e) {9 return null; // (FEILSTAT) kunne ikke analysere den 10} 11 returnere ny Farge (rød, grønn, blå); // (SLUTTSTATUS) ferdig. 12} 

En litt mer kompleks parser vises i koden nedenfor. Denne parseren er implementert i metoden getColors, som er definert for å returnere en matrise av Farge gjenstander.

 / ** * Del et sett med farger "r1, g1, b1: r2, g2, b2: ...: rn, gn, bn" i * en rekke AWT-fargeobjekter. * / 1 Farge [] getColors (String data) {2 Vector accum = new Vector (); 3 Fargekl, resultat []; 4 StringTokenizer st = new StringTokenizer (data, ":"); 5 mens (st.hasMoreTokens ()) {6 cl = getColor (st.nextToken ()); 7 hvis (cl! = Null) {8 accum.addElement (cl); 9} annet {10 System.out.println ("Feil - dårlig farge."); 11} 12} 13 hvis (akkum.størrelse () == 0) 14 returnerer null; 15 resultat = ny farge [akkum.størrelse ()]; 16 for (int i = 0; i <accum.size (); i ++) {17 result [i] = (Color) accum.elementAt (i); 18} 19 returresultat; 20} 

I metoden ovenfor, som bare er litt forskjellig fra getColor metode, lager koden i linje 4 til 12 en ny Tokenizer for å trekke ut tokens omgitt av kolon (:). Som du kan lese i dokumentasjonskommentaren for metoden, forventer denne metoden at fargetupper skal skilles fra kolon. Hver samtale til nesteToken i StringTokenizer klasse returnerer et nytt token til strengen er oppbrukt. Tokene som returneres vil være strengene med tall atskilt med komma; disse token strengene blir matet til getColor, som deretter trekker ut en farge fra de tre tallene. Å lage et nytt StringTokenizer objekt ved hjelp av et token returnert av en annen StringTokenizer objektet gjør at parserkoden vi har skrevet er litt mer sofistikert om hvordan den tolker strenginngangen.

Så nyttig som det er, vil du til slutt utnytte evnene til StringTokenizer klasse og må gå videre til storebror StreamTokenizer.

StreamTokenizer-klassen

Som navnet på klassen antyder, a StreamTokenizer objektet forventer at innspillene kommer fra et InputStream klasse. Som StringTokenizer ovenfor konverterer denne klassen inngangsstrømmen til biter som analysekoden din kan tolke, men det er der likheten ender.

StreamTokenizer er en borddrevet leksikalanalysator. Dette betyr at alle mulige inngangskarakterer tildeles en betydning, og skanneren bruker betydningen av det nåværende tegnet til å bestemme hva som skal gjøres. I implementeringen av denne klassen tildeles tegn en av tre kategorier. Disse er:

• Mellomrom tegn - deres leksikale betydning er begrenset til å skille ord

• Ord tegn - de skal samles når de grenser til et annet ordtegn

• Vanlig tegn - de skal returneres umiddelbart til parseren

Tenk deg implementeringen av denne klassen som en enkel tilstandsmaskin som har to tilstander - tomgang og akkumulere. I hver tilstand er inngangen et tegn fra en av kategoriene ovenfor. Klassen leser karakteren, sjekker kategorien og gjør noe, og går videre til neste tilstand. Tabellen nedenfor viser denne tilstandsmaskinen.

På toppen av denne enkle mekanismen StreamTokenizer klasse legger til flere heuristikker. Disse inkluderer nummerbehandling, sitert strengbehandling, kommentarbehandling og end-of-line-behandling.

Det første eksemplet er nummerbehandling. Visse tegnsekvenser kan tolkes som å representere en numerisk verdi. For eksempel representerer rekkefølgen av tegn 1, 0, 0,. Og 0 ved siden av hverandre i inngangsstrømmen den numeriske verdien 100.0. Når alle siffertegnene (0 til 9), punkttegnet (.) Og minustegnet (-) er spesifisert som en del av ord sett StreamTokenizer klassen kan få beskjed om å tolke ordet det er i ferd med å returnere som et mulig tall. Innstilling av denne modusen oppnås ved å ringe til parseNumbers metoden på tokenizer-objektet du instantierte (dette er standard). Hvis analysatoren er i akkumulert tilstand, og neste tegn ville ikke være en del av et tall, blir det akkumulerte ordet sjekket for å se om det er et gyldig nummer. Hvis den er gyldig, returneres den, og skanneren går til neste passende tilstand.

Det neste eksemplet er sitert strengbehandling. Det er ofte ønskelig å sende en streng som er omgitt av et anførselstegn (vanligvis dobbelt (") eller enkelt (') sitat) som et enkelt token. StreamTokenizer klasse kan du spesifisere hvilket som helst tegn som et siteringstegn. Som standard er det tegnene med enkelt anførselstegn (') og dobbelt anførselstegn ("). Tilstandsmaskinen er modifisert for å konsumere tegn i akkumulert tilstand til enten et annet sitattegn eller et end-of-line-tegn er behandlet. For å tillate deg å sitere sitattegnet, behandler analysatoren sitattegnet foran en skråstrek (\) i inngangsstrømmen og inne i et sitat som et ordtegn.