Leksička analiza i Java: 1. dio

Leksička analiza i raščlanjivanje

Pri pisanju Java aplikacija, jedna od najčešćih stvari koju ćete morati proizvesti je raščlanjivač. Analizatori se kreću od jednostavnih do složenih i koriste se za sve, od gledanja opcija naredbenog retka do tumačenja Java izvornog koda. U decembarskom izdanju JavaWorlda pokazao sam vam Jack, automatski generator parsera koji pretvara gramatičke specifikacije visoke razine u Java klase koje implementiraju parser opisan tim specifikacijama. Ovaj mjesec pokazat ću vam resurse koje Java nudi za pisanje ciljanih leksičkih analizatora i parsera. Ovi nešto jednostavniji raščlanjivači popunjavaju prazninu između jednostavne usporedbe nizova i složenih gramatika koje Jack sastavlja.

Svrha leksičkih analizatora je uzeti tok ulaznih znakova i dekodirati ih u žetone više razine koje parser može razumjeti. Analizatori troše izlaz leksičkog analizatora i djeluju analizirajući slijed vraćenih tokena. Raščlanjivač podudara ove sekvence s krajnjim stanjem, koje može biti jedno od možda mnogih krajnjih stanja. Krajnja stanja definiraju ciljeveparsera. Kad se postigne krajnje stanje, program koji koristi parser vrši neke radnje - postavljajući strukture podataka ili izvršavajući neki kôd specifičan za akciju. Uz to, raščlanjivači mogu otkriti - iz niza obrađenih tokena - kada nije moguće dostići pravno krajnje stanje; u tom trenutku parser identificira trenutno stanje kao stanje pogreške. Na aplikaciji je da odluči koju će radnju poduzeti kada parser identificira ili krajnje stanje ili stanje pogreške.

Standardna baza Java klase uključuje nekoliko klasa leksičkog analizatora, međutim ne definira nijednu klasu raščlanjivača opće namjene. U ovoj ću kolumni detaljno pogledati leksičke analizatore koji dolaze s Javom.

Javini leksički analizatori

Specifikacija jezika Java, verzija 1.0.2, definira dvije klase leksičkog analizatora StringTokenizeri StreamTokenizer. Iz njihovih imena možete zaključiti da StringTokenizerkoristi Stringpredmete kao svoj ulaz i StreamTokenizerkoristi InputStreampredmete.

Klasa StringTokenizer

Od dvije dostupne klase leksičkog analizatora, najlakše je razumjeti StringTokenizer. Kada konstruirate novi StringTokenizerobjekt, metoda konstruktora nominalno uzima dvije vrijednosti - ulazni niz i niz graničnika. Klasa zatim konstruira slijed žetona koji predstavlja znakove između razgraničenja.

Kao leksički analizator, StringTokenizermogao bi se formalno definirati kako je prikazano u nastavku.

[~ delim1, delim2, ..., delim N ] :: Token

Ova se definicija sastoji od regularnog izraza koji se podudara sa svim znakovima, osim znakova za razdvajanje. Svi susjedni odgovarajući znakovi prikupljaju se u jedan žeton i vraćaju kao žeton.

StringTokenizerKlasa se najčešće koristi za izdvajanje skupa parametara - poput popisa brojeva odvojenih zarezom. StringTokenizerje idealan u ovoj ulozi jer uklanja separatore i vraća podatke. StringTokenizerRazred također pruža mehanizam za identifikaciju liste u kojima postoje „null” žetona. Upotrebljavali biste null tokene u aplikacijama u kojima neki parametri imaju zadane vrijednosti ili ne moraju biti prisutni u svim slučajevima.

Aplet u nastavku je jednostavan StringTokenizervježbač. Izvor alata StringTokenizer je ovdje. Da biste koristili aplet, u područje teksta ulaznog niza unesite tekst koji će se analizirati, a zatim u područje Separator String unesite niz koji se sastoji od znakova razdvajača. Na kraju, kliknite na Tokenize! dugme. Rezultat će se prikazati na popisu tokena ispod ulaznog niza i bit će organiziran kao jedan žeton u retku.

Da biste vidjeli ovaj aplet, potreban vam je preglednik s omogućenom Java.

Razmotrimo kao primjer niz "a, b, d", proslijeđen StringTokenizerobjektu koji je konstruiran zarezom (,) kao znak razdvajanja. Ako ove vrijednosti stavite u program za vježbanje iznad, vidjet ćete da Tokenizerobjekt vraća nizove "a", "b" i "d." Ako ste namjeravali primijetiti da nedostaje jedan parametar, možda ste bili iznenađeni jer u nizu tokena niste vidjeli nikakve naznake o tome. Mogućnost otkrivanja nedostajućih tokena omogućava boolean Return Separator koji se može postaviti kada kreirate Tokenizerobjekt. Ako se ovaj parametar postavi kada Tokenizerse konstruira, vraća se i svaki separator. Kliknite potvrdni okvir za Return Separator u gore navedenom apletu i ostavite niz i separator na miru. SadaTokenizervraća "a, zarez, b, zarez, zarez i d." Primjećujući da uzastopno dobivate dva znaka za razdvajanje, možete utvrditi je li u ulazni niz bio uključen "null" token.

Trik za uspješnu upotrebu StringTokenizeru parseru je definiranje unosa na takav način da se znak za razdvajanje ne pojavljuje u podacima. Jasno je da ovo ograničenje možete izbjeći tako što ćete ga dizajnirati u svojoj aplikaciji. Definicija metode u nastavku može se koristiti kao dio apleta koji u svom toku parametara prihvaća boju u obliku crvene, zelene i plave vrijednosti.

/ ** * Analizirajte parametar oblika "10,20,30" kao * RGB tuple za vrijednost boje. * / 1 Boja getColor (naziv niza) {2 podaci o nizu; 3 StringTokenizer st; 4 int crvena, zelena, plava; 5 6 podataka = getParameter (ime); 7 if (podaci == null) 8 return null; 9 10 st = novi StringTokenizer (podaci, ","); 11 pokušaj {12 crvena = Integer.parseInt (st.nextToken ()); 13 zeleno = Integer.parseInt (st.nextToken ()); 14 plava = Integer.parseInt (st.nextToken ()); 15} catch (Iznimka e) {16 return null; // (ERROR STATE) nije mogao raščlaniti 17} 18 vraća novu boju (crvena, zelena, plava); // (END STATE) gotovo. 19}

Gornji kod implementira vrlo jednostavan parser koji čita niz "broj, broj, broj" i vraća novi Colorobjekt. U retku 10 kôd stvara novi StringTokenizerobjekt koji sadrži podatke o parametrima (pretpostavimo da je ova metoda dio apleta) i popis znakova za razdvajanje koji se sastoji od zareza. Zatim se u redovima 12, 13 i 14 svaki žeton ekstrahira iz niza i pretvara u broj metodom Integer parseInt. Te su pretvorbe okružene try/catchblokom u slučaju da nizovi brojeva nisu valjani brojevi ili ako Tokenizerizuzmu izuzetak jer je ponestalo žetona. Ako se svi brojevi pretvore, postiže se krajnje stanje i Colorvraća se objekt; u suprotnom se postiže stanje pogreške i vraća se null .

Jedna je značajka StringTokenizerklase da se lako slaže. Pogledajte metodu koja je navedena u getColornastavku, a to su redovi od 10 do 18 gore navedene metode.

/ ** * Analizirajte korpicu boja "r, g, b" u AWT Colorobjekt. * / 1 Boja getColor (podaci niza) {2 int crvena, zelena, plava; 3 StringTokenizer st = novi StringTokenizer (podaci, ","); 4 pokušaj {5 crvena = Integer.parseInt (st.nextToken ()); 6 zeleno = Integer.parseInt (st.nextToken ()); 7 plava = Integer.parseInt (st.nextToken ()); 8} catch (Iznimka e) {9 return null; // (DRŽAVA POGREŠKE) nije mogao raščlaniti 10} 11 vratiti novu boju (crvena, zelena, plava); // (END STATE) gotovo. 12}

Nešto složeniji parser prikazan je u donjem kodu. Ovaj parser implementiran je u metodu getColorskoja je definirana za vraćanje niza Colorobjekata.

/ ** * Analizirajte skup boja "r1, g1, b1: r2, g2, b2: ...: rn, gn, bn" u * niz AWT Color objekata. * / 1 Boja [] getColors (podaci o nizu) {2 Vector accum = novi vektor (); 3 boja cl, rezultat []; 4 StringTokenizer st = novi StringTokenizer (podaci, ":"); 5 while (st.hasMoreTokens ()) {6 cl = getColor (st.nextToken ()); 7 if (cl! = Null) {8 accum.addElement (cl); 9} else {10 System.out.println ("Pogreška - loša boja."); 11} 12} 13 if (accum.size () == 0) 14 return null; 15 rezultat = nova boja [accum.size ()]; 16 za (int i = 0; i <accum.size (); i ++) {17 rezultat [i] = (Boja) accum.elementAt (i); 18} 19 povratni rezultat; 20}

U gornjoj metodi, koja se samo malo razlikuje od getColormetode, kod u redovima 4 do 12 stvara novi Tokenizerza izdvajanje tokena okružen dvotačkom (:) znakom. Kao što možete pročitati u komentaru dokumentacije za metodu, ova metoda očekuje da će se nabori boja odvojiti dvotočkom. Svaki poziv nextTokenu StringTokenizerrazred vraćat će novi token sve dok se niz ne iscrpi. Vraćeni tokeni bit će nizovi brojeva odvojeni zarezima; napajaju se ovi nizovi žetona getColor, koji zatim izvlače boju iz tri broja. Stvaranje novog StringTokenizerobjekta pomoću tokena koji je vratio drugi StringTokenizerobjekt omogućuje da parser kôd koji smo napisali bude malo sofisticiraniji kako tumači unos niza.

Koliko god bio koristan, na kraju ćete iscrpiti sposobnosti StringTokenizerrazreda i morati prijeći na njegovog starijeg brata StreamTokenizer.

Klasa StreamTokenizer

Kao što naziv klase sugerira, StreamTokenizerobjekt očekuje da njegov unos dolazi iz InputStreamklase. Kao i StringTokenizergore, i ova klasa pretvara ulazni tok u dijelove koje vaš kod za raščlanjivanje može protumačiti, ali tu sličnost završava.

StreamTokenizerje stolni leksički analizator. To znači da se svakom mogućem ulaznom znaku pripisuje značaj, a skener koristi značaj trenutnog znaka da odluči što će učiniti. U provedbi ove klase znakovima se dodjeljuje jedna od tri kategorije. Ovi su:

  • Razmaci - njihov leksički značaj ograničen je na razdvajanje riječi

  • Znakovi riječi - trebali bi se objediniti kad su u blizini drugog znaka riječi

  • Obični znakovi - treba ih odmah vratiti u parser

Zamislite implementaciju ove klase kao jednostavnog državnog stroja koji ima dva stanja - u praznom hodu i akumuliranom . U svakom stanju unos je znak iz jedne od gornjih kategorija. Klasa čita znak, provjerava njegovu kategoriju i poduzima neke radnje te prelazi u sljedeće stanje. Sljedeća tablica prikazuje ovaj državni stroj.

država Ulazni Akcijski Nova država
besposlen riječ karakter odgurnuti lik akumulirati
običan lik znak za povratak besposlen
whitespace character consume character idle
accumulate word character add to current word accumulate
ordinary character

return current word

push back character

idle
whitespace character

return current word

consume character

idle

On top of this simple mechanism the StreamTokenizer class adds several heuristics. These include number processing, quoted string processing, comment processing, and end-of-line processing.

The first example is number processing. Certain character sequences can be interpreted as representing a numerical value. For example, the sequence of characters 1, 0, 0, ., and 0 adjacent to each other in the input stream represent the numerical value 100.0. When all of the digit characters (0 through 9), the dot character (.), and the minus (-) character are specified as being part of the word set, the StreamTokenizer class can be told to interpret the word it is about to return as a possible number. Setting this mode is achieved by calling the parseNumbers method on the tokenizer object that you instantiated (this is the default). If the analyzer is in the accumulate state, and the next character would not be part of a number, the currently accumulated word is checked to see if it is a valid number. If it is valid, it is returned, and the scanner moves to the next appropriate state.

Sljedeći je primjer citirana obrada niza. Često je poželjno proslijediti niz koji je okružen znakom navoda (obično dvostrukim (") ili pojedinačnim (') navodnikom) kao jedan token. StreamTokenizerKlasa vam omogućuje da bilo koji znak navedete kao znak citiranja. Prema zadanim postavkama su znakovi s jednim navodnikom (') i dvostrukim navodnicima ("). Stroj stanja modificiran je tako da troši znakove u stanju akumuliranja dok se ne obradi bilo koji drugi znak navodnika ili znak kraja retka. Da biste mogli citirati znak navodnika, analizator znak citata kojem prethodi stražnja kosa crta (\) u ulaznom toku i unutar navodnika obrađuje kao znak riječi.