Programmēšana

Leksiskā analīze un Java: 1. daļa

Leksiskā analīze un parsēšana

Rakstot Java lietojumprogrammas, viena no izplatītākajām lietām, kas jums būs jāveido, ir parsētājs. Parsētāji svārstās no vienkāršiem līdz sarežģītiem un tiek izmantoti visam, sākot no komandrindas opciju apskates līdz Java avota koda interpretācijai. In JavaWorlddecembra numurā es jums parādīju Džeku - automātisku parsētāja ģeneratoru, kas pārveido augsta līmeņa gramatikas specifikācijas Java klasēs, kas ievieš šajās specifikācijās aprakstīto parsētāju. Šajā mēnesī es jums parādīšu resursus, ko Java nodrošina mērķtiecīgu leksisko analizatoru un parsētāju rakstīšanai. Šie nedaudz vienkāršākie parsētāji aizpilda plaisu starp vienkāršu virkņu salīdzināšanu un sarežģītajām gramatikām, kuras Džeks sastāda.

Leksisko analizatoru mērķis ir uzņemt ievades rakstzīmju plūsmu un atšifrēt tās augstāka līmeņa marķieros, kurus parsētājs var saprast. Parsētāji patērē leksiskā analizatora izvadi un darbojas, analizējot atgriezto žetonu secību. Parsētājs saskaņo šīs sekvences ar gala stāvokli, kas var būt viens no, iespējams, daudzajiem gala stāvokļiem. Gala stāvokļi definē mērķus parsētāja. Kad ir sasniegts beigu stāvoklis, programma, kas izmanto parsētāju, veic kādu darbību - vai nu izveido datu struktūras, vai izpilda kādu darbību raksturojošu kodu. Turklāt parsētāji var noteikt no apstrādāto žetonu secības, kad nevar sasniegt juridisko galīgo stāvokli; tajā brīdī parsētājs identificē pašreizējo stāvokli kā kļūdas stāvokli. Lietotnei ir jāizlemj, kādas darbības veikt, kad parsētājs identificē beigu vai kļūdas stāvokli.

Standarta Java klases bāzē ietilpst pāris leksisko analizatoru klases, taču tajā nav definētas vispārējas nozīmes parsētāja klases. Šajā slejā es padziļināti apskatīšu leksiskos analizatorus, kas nāk ar Java.

Java leksiskie analizatori

Java valodas specifikācijas 1.0.2 versija nosaka divas leksisko analizatoru klases, StringTokenizer un StreamTokenizer. Pēc viņu vārdiem to var secināt StringTokenizer izmanto Stīga objekti kā tā ievade, un StreamTokenizer izmanto InputStream objektiem.

StringTokenizer klase

No divām pieejamajām leksisko analizatoru klasēm visvieglāk ir saprast StringTokenizer. Kad jūs uzbūvējat jaunu StringTokenizer objekts, konstruktora metode nomināli ņem divas vērtības - ievades virkni un atdalītāja virkni. Pēc tam klase izveido žetonu secību, kas attēlo rakstzīmes starp atdalītāja rakstzīmēm.

Kā leksiskais analizators StringTokenizer formāli varētu definēt, kā parādīts zemāk.

[~ norobežot1, norobežot2, ..., norobežotN] :: Žetons 

Šī definīcija sastāv no regulāras izteiksmes, kas atbilst visiem rakstzīmēm izņemot atdalītāja rakstzīmes. Visas blakus esošās atbilstošās rakstzīmes tiek apkopotas vienā marķierī un atgrieztas kā marķieris.

Visbiežāk izmantotais StringTokenizer klase ir paredzēta parametru kopas izdalīšanai, piemēram, ar komatiem atdalītu skaitļu sarakstu. StringTokenizer ir ideāls šajā lomā, jo tas noņem atdalītājus un atgriež datus. The StringTokenizer klase nodrošina arī mehānismu, kā identificēt sarakstus, kuros ir "nulles" žetoni. Jūs izmantosiet nulles marķierus lietojumprogrammās, kurās dažiem parametriem ir vai nu noklusējuma vērtības, vai arī tiem nav jābūt visos gadījumos.

Zemāk esošais sīklietotne ir vienkārša StringTokenizer trenažieris. StringTokenizer sīklietotnes avots ir šeit. Lai izmantotu sīklietotni, ievades virknes apgabalā ierakstiet analizējamo tekstu, pēc tam apgabalā Atdalītāja virkne ierakstiet virkni, kas sastāv no atdalītājzīmēm. Visbeidzot, noklikšķiniet uz Tokenize! pogu. Rezultāts tiks parādīts marķieru sarakstā zem ievades virknes un tiks sakārtots kā viens marķieris katrā rindā.

Lai redzētu šo sīklietotni, jums ir nepieciešama Java pārlūkprogramma.

Apskatīsim kā piemēru virkni "a, b, d", kas nodota a StringTokenizer objekts, kas ir izveidots ar komatu (,) kā atdalītāja rakstzīmi. Ievietojot šīs vērtības iepriekš esošajā trenažiera sīklietotnē, redzēsit, ka Tokenizer objekts atgriež virknes "a", "b" un "d". Ja jūsu nolūks bija atzīmēt, ka trūkst viena parametra, iespējams, esat pārsteigts, ka marķiera secībā neredzat nekādas norādes par to. Spēju noteikt trūkstošos marķierus iespējo atgriezeniskā atdalītāja būla, kuru var iestatīt, izveidojot Tokenizer objekts. Ar šo parametru iestatiet, kad Tokenizer ir konstruēts, katrs atdalītājs arī tiek atgriezts. Iepriekš esošajā sīklietotnē atzīmējiet izvēles rūtiņu Return Separator un atstājiet virkni un atdalītāju atsevišķi. Tagad Tokenizer atgriež "a, komatu, b, komatu, komatu un d". Atzīmējot, ka secīgi iegūstat divas atdalītāja rakstzīmes, varat noteikt, vai ievades virknē tika iekļauts "null" marķieris.

Veiksmīgas izmantošanas triks StringTokenizer parsētājā definē ievadi tā, ka atdalītāja raksturs neparādās datos. Protams, jūs varat izvairīties no šī ierobežojuma, izstrādājot to savā lietojumprogrammā. Tālāk aprakstīto metodes definīciju var izmantot kā sīklietotnes daļu, kas savā parametru plūsmā pieņem krāsu sarkanā, zaļā un zilā formā.

 / ** * Parsējiet formas “10,20,30” parametru kā * RGB kopu krāsu vērtībai. * / 1 Color getColor (virknes nosaukums) {2 virknes dati; 3 StringTokenizer st; 4 int sarkans, zaļš, zils; 5 6 dati = getParameter (nosaukums); 7 if (dati == null) 8 atgriež null; 9 10 st = jauns StringTokenizer (dati, ","); 11 mēģiniet {12 sarkans = Integer.parseInt (st.nextToken ()); 13 zaļš = Integer.parseInt (st.nextToken ()); 14 zils = Integer.parseInt (st.nextToken ()); 15} catch (izņēmums e) {16 return null; // (KĻŪDAS STĀVOKLIS) to nevarēja parsēt 17} 18 atgriezt jaunu krāsu (sarkana, zaļa, zila); // (END STATE) izdarīts. 19} 

Iepriekš minētais kods ievieš ļoti vienkāršu parsētāju, kas nolasa virkni "skaitlis, skaitlis, skaitlis" un atgriež jaunu Krāsa objekts. 10. rindā kods izveido jaunu StringTokenizer objekts, kas satur parametru datus (pieņemsim, ka šī metode ir sīklietotnes daļa), un atdalītāju rakstzīmju saraksts, kas sastāv no komatiem. Tad 12., 13. un 14. rindā katrs marķieris tiek izvilkts no virknes un pārveidots par skaitli, izmantojot veselu skaitli parseInt metodi. Šos pārveidojumus ieskauj a mēģināt / noķert bloks gadījumā, ja skaitļu virknes nav derīgi skaitļi vai Tokenizer izmet izņēmumu, jo tam ir beigušies marķieri. Ja visi skaitļi tiek pārveidoti, tiek sasniegts gala stāvoklis un a Krāsa objekts tiek atgriezts; pretējā gadījumā kļūdas stāvoklis ir sasniegts un nulle tiek atgriezta.

Viena iezīme StringTokenizer klase ir tā, ka to var viegli sakraut. Apskatiet nosaukto metodi getColor zemāk, kas ir iepriekšminētās metodes 10. līdz 18. rinda.

 / ** * Parsējiet krāsainu virkni "r, g, b" AWT Krāsa objekts. * / 1 Krāsa getColor (Stīgu dati) {2 int sarkana, zaļa, zila; 3 StringTokenizer st = jauns StringTokenizer (dati, ","); 4 mēģiniet {5 sarkans = Integer.parseInt (st.nextToken ()); 6 zaļš = Integer.parseInt (st.nextToken ()); 7 zils = Integer.parseInt (st.nextToken ()); 8} catch (izņēmums e) {9 return null; // (KĻŪDAS STĀVOKLIS) to nevarēja parsēt. 10} 11 atgriezt jaunu krāsu (sarkana, zaļa, zila); // (END STATE) izdarīts. 12} 

Nedaudz sarežģītāks parsētājs ir parādīts zemāk esošajā kodā. Šis parsētājs ir ieviests metodē getColors, kas definēts, lai atgrieztu masīvu Krāsa objektiem.

 / ** * Parsējiet krāsu kopu "r1, g1, b1: r2, g2, b2: ...: rn, gn, bn" * AWT Color objektu masīvā. * / 1 Krāsa [] getColors (Stīgu dati) {2 Vektoru uzkrājums = jauns Vektors (); 3 krāsa cl, rezultāts []; 4 StringTokenizer st = jauns StringTokenizer (dati, ":"); 5, kamēr (st.hasMoreTokens ()) {6 cl = getColor (st.nextToken ()); 7 if (cl! = Null) {8 akumul.addElement (cl); 9} else {10 System.out.println ("Kļūda - slikta krāsa."); 11} 12} 13 if (umul.size () == 0) 14 atgriež nulli; 15 rezultāts = jauna krāsa [akumulatora izmērs ()]; 16 (int i = 0; i <akumulatora izmērs (); i ++) {17 rezultāts [i] = (krāsa) akumul.elementAt (i); 18} 19 atgriešanās rezultāts; 20} 

Iepriekš aprakstītajā metodē, kas tikai nedaudz atšķiras no getColor metodi kods no 4. līdz 12. rindiņai rada jaunu Tokenizer lai izvilktu žetonus, kurus ieskauj resnās zarnas (:) raksturs. Kā jūs varat izlasīt metodes dokumentācijas komentārā, šī metode paredz, ka krāsu kopas tiks atdalītas ar kolu. Katrs zvans uz nextToken iekš StringTokenizer klase atgriezīs jaunu marķieri, līdz virkne būs izsmelta. Atgrieztie marķieri būs ciparu virknes, atdalītas ar komatiem; šīs žetonu virknes tiek padotas getColor, kas pēc tam no trim skaitļiem izvelk krāsu. Jauna veidošana StringTokenizer objektu, izmantojot marķieri, kuru atdeva cits StringTokenizer objekts ļauj mūsu uzrakstītajam parsētāja kodam būt nedaudz sarežģītākam, kā tas interpretē virknes ievadi.

Lai cik noderīgs tas būtu, jūs galu galā izsmelsiet StringTokenizer klasē un jāpārceļas pie sava lielā brāļa StreamTokenizer.

StreamTokenizer klase

Kā norāda klases nosaukums, a StreamTokenizer objekts sagaida, ka tā ievadīšana notiks no InputStream klasē. Kā StringTokenizer Iepriekš šī klase pārveido ievades straumi gabalos, kurus var interpretēt jūsu parsēšanas kods, taču ar to līdzība beidzas.

StreamTokenizer ir galda vadīts leksiskais analizators. Tas nozīmē, ka katram iespējamam ievades rakstzīmei tiek piešķirta nozīme, un skeneris izmanto pašreizējā rakstzīmes nozīmi, lai izlemtu, ko darīt. Īstenojot šo klasi, rakstzīmēm tiek piešķirta viena no trim kategorijām. Šie ir:

  • Baltā telpa rakstzīmes - to leksiskā nozīme ir ierobežota ar vārdu atdalīšanu

  • Vārds rakstzīmes - tās jāapkopo, kad tās atrodas blakus citam vārda simbolam

  • Parasts rakstzīmes - tās nekavējoties jāatgriež parsētājam

Iedomājieties šīs klases ieviešanu kā vienkāršu stāvokļa mašīnu, kurai ir divi stāvokļi - tukšgaitā un uzkrāt. Katrā štatā ievade ir raksturs no vienas no iepriekšminētajām kategorijām. Klase nolasa rakstzīmi, pārbauda tās kategoriju un veic kādu darbību, un pāriet uz nākamo stāvokli. Nākamajā tabulā parādīta šī stāvokļa mašīna.

ValstsIevadeDarbībaJauna valsts
tukšgaitāvārdu rakstursatgrūst rakstursuzkrāt
parasts rakstursatgriešanās raksturstukšgaitā
atstarpe raksturspatērē raksturutukšgaitā
uzkrātvārdu raksturspievienot pašreizējam vārdamuzkrāt
parasts raksturs

atgriezt pašreizējo vārdu

atgrūst raksturs

tukšgaitā
atstarpe raksturs

atgriezt pašreizējo vārdu

patērē raksturu

tukšgaitā

Papildus šim vienkāršajam mehānismam StreamTokenizer klase pievieno vairākas heiristikas. Tie ietver skaitļu apstrādi, citēto virkņu apstrādi, komentāru apstrādi un rindas beigu apstrādi.

Pirmais piemērs ir skaitļu apstrāde. Dažas rakstzīmju secības var interpretēt kā skaitliskas vērtības. Piemēram, 1., 0, 0,. Un 0 rakstzīmju secība, kas atrodas blakus ievades straumē, attēlo skaitlisko vērtību 100.0. Kad visas ciparu rakstzīmes (no 0 līdz 9), punktu rakstzīme (.) Un mīnus (-) ir norādītas kā vārdu komplekts, StreamTokenizer klasei var likt interpretēt vārdu, kuru tas atgriež, kā iespējamo skaitli. Šī režīma iestatīšana tiek panākta, izsaucot parseNumbers metode jūsu marķiera objektā, kuru esat izveidojis (tas ir noklusējums). Ja analizators ir akumulācijas stāvoklī, un nākamais raksturs to izdarītu būt skaitļa daļai, tiek pārbaudīts, vai vārds ir derīgs. Ja tas ir derīgs, tas tiek atgriezts, un skeneris pāriet uz nākamo atbilstošo stāvokli.

Nākamais piemērs ir citēto virkņu apstrāde. Bieži vien ir vēlams kā vienu marķieri nodot virkni, kuru ieskauj pēdiņa (parasti dubultā (") vai viena (') pēdiņa). StreamTokenizer klase ļauj norādīt jebkuru rakstzīmi kā citējošu rakstzīmi. Pēc noklusējuma tās ir vienas pēdiņas (') un dubultās pēdiņas ("). Valsts mašīna tiek modificēta, lai patērētu rakstzīmes uzkrājuma stāvoklī, līdz tiek apstrādāta cita citāta rakstzīme vai rindas beigu rakstzīme. Lai ļautu jums citējot rakstzīmi, analizators pēdiņas rakstzīmi, kurai pirms ievades straumes un pēdiņas iekšpusē ir aizmugures slīpsvītra (\), uzskata par vārda rakstzīmi.