Lexikálna analýza a Java: 1. časť

Lexikálna analýza a analýza

Pri písaní aplikácií Java je jednou z najbežnejších vecí, ktoré budete musieť vytvoriť, syntaktický analyzátor. Analyzátory sa pohybujú od jednoduchých po zložité a používajú sa na všetko, od pohľadu na možnosti príkazového riadku až po interpretáciu zdrojového kódu Java. V JavaWorldV decembrovom vydaní som vám ukázal Jacka, automatický generátor syntaktického analyzátora, ktorý prevádza špecifikácie gramatiky na vysokej úrovni do tried Java, ktoré implementujú syntaktický analyzátor opísaný v týchto špecifikáciách. Tento mesiac vám ukážem zdroje, ktoré Java poskytuje na písanie cielených lexikálnych analyzátorov a analyzátorov. Tieto trochu jednoduchšie analyzátory vypĺňajú medzeru medzi jednoduchým porovnaním reťazcov a zložitými gramatikami, ktoré Jack zostavuje.

Účelom lexikálnych analyzátorov je zobrať prúd vstupných znakov a dekódovať ich do tokenov vyššej úrovne, ktorým syntaktický analyzátor dokáže porozumieť. Analyzátory spotrebúvajú výstup lexikálneho analyzátora a pracujú s analýzou postupnosti vrátených tokenov. Analyzátor priraďuje tieto sekvencie k koncovému stavu, ktorý môže byť jedným z možných mnohých koncových stavov. Koncové štáty definujú Ciele analyzátora. Keď sa dosiahne konečný stav, program pomocou syntaktického analyzátora vykoná určitú akciu - buď nastavenie dátových štruktúr, alebo vykonanie kódu špecifického pre danú akciu. Analyzátory navyše môžu zistiť - zo sledu tokenov, ktoré boli spracované -, kedy nie je možné dosiahnuť žiadny legálny konečný stav; v tom okamihu syntaktický analyzátor identifikuje aktuálny stav ako chybový stav. Je na aplikácii, aby rozhodla, aké kroky podnikne, keď syntaktický analyzátor identifikuje buď koncový stav, alebo chybový stav.

Štandardná základňa triedy Java obsahuje niekoľko tried lexikálneho analyzátora, nedefinuje však žiadne triedy syntaktického analyzátora. V tomto stĺpci sa podrobne pozriem na lexikálne analyzátory dodávané s jazykom Java.

Lexické analyzátory Java

Špecifikácia jazyka Java, verzia 1.0.2, definuje dve triedy lexikálnych analyzátorov, StringTokenizer a StreamTokenizer. Podľa ich mien to môžete odvodiť StringTokenizer používa String objekty ako jeho vstup a StreamTokenizer používa InputStream predmety.

Trieda StringTokenizer

Z dvoch dostupných tried lexikálnych analyzátorov je najľahšie pochopiteľné StringTokenizer. Keď postavíte nový StringTokenizer objekt, metóda konštruktora nominálne nadobúda dve hodnoty - vstupný reťazec a reťazec oddeľovača. Trieda potom zostrojí sekvenciu tokenov, ktorá predstavuje znaky medzi znakmi oddeľovača.

Ako lexikálny analyzátor StringTokenizer formálne definované, ako je uvedené nižšie.

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

Táto definícia pozostáva z regulárneho výrazu, ktorý sa zhoduje s každým znakom okrem znaky oddeľovača. Všetky susediace zodpovedajúce znaky sa zhromaždia do jedného tokenu a vrátia sa ako token.

Najbežnejšie použitie StringTokenizer trieda slúži na oddelenie množiny parametrov - napríklad zoznam čísel oddelených čiarkami. StringTokenizer je v tejto role ideálny, pretože odstraňuje oddeľovače a vracia údaje. The StringTokenizer trieda tiež poskytuje mechanizmus na identifikáciu zoznamov, v ktorých sú „nulové“ tokeny. Nulové tokeny by ste použili v aplikáciách, v ktorých majú niektoré parametre buď predvolené hodnoty, alebo sa nemusí vo všetkých prípadoch vyskytovať.

Nižšie uvedený applet je jednoduchý StringTokenizer cvičenec. Zdroj appletu StringTokenizer je tu. Ak chcete použiť applet, zadajte do oblasti vstupného reťazca text, ktorý sa má analyzovať, a potom do oblasti oddeľovacieho reťazca zadajte reťazec pozostávajúci z oddeľovacích znakov. Nakoniec kliknite na Tokenize! tlačidlo. Výsledok sa zobrazí v zozname tokenov pod vstupným reťazcom a bude usporiadaný ako jeden token na riadok.

Za príklad považujte reťazec „a, b, d“ odovzdaný znaku a StringTokenizer objekt, ktorý bol skonštruovaný s čiarkou (,) ako oddeľovačom znaku. Ak dáte tieto hodnoty do appletu cvičenca vyššie, uvidíte, že Tokenizer objekt vráti reťazce „a“, „b“ a „d“. Ak ste si chceli všimnúť, že chýbal jeden parameter, možno vás prekvapilo, že to v sekvencii tokenov nevidíte. Schopnosť detekovať chýbajúce tokeny umožňuje boolean Return Separator, ktorý je možné nastaviť pri vytváraní súboru Tokenizer objekt. S týmto parametrom nastaveným, keď Tokenizer je skonštruovaný, vráti sa aj každý oddeľovač. Začiarknite políčko oddeľovača návratov v applete vyššie a nechajte reťazec a oddeľovač na pokoji. Teraz Tokenizer vráti „a, čiarku, b, čiarku, čiarku a d.“ Poznamenaním, že získate dva oddeľovacie znaky v poradí, môžete určiť, že do vstupného reťazca bol zahrnutý token „null“.

Trik na úspešné použitie StringTokenizer v syntaktickom analyzátore definuje vstup tak, aby sa v dátach neobjavil oddeľovač. Je zrejmé, že sa môžete vyhnúť tomuto obmedzeniu tým, že ho navrhnete vo svojej aplikácii. Nižšie uvedenú definíciu metódy možno použiť ako súčasť appletu, ktorý vo svojom toku parametrov prijíma farbu vo forme červenej, zelenej a modrej hodnoty.

 / ** * Analyzujte parameter formulára „10,20,30“ ako * n-ticu RGB pre hodnotu farby. * / 1 Farba getColor (názov reťazca) {2 údaje reťazca; 3 StringTokenizer st; 4 int červená, zelená, modrá; 5 6 data = getParameter (meno); 7 if (data == null) 8 return null; 9 10 st = nový StringTokenizer (data, ","); 11 vyskúšajte {12 red = Integer.parseInt (st.nextToken ()); 13 zelená = Integer.parseInt (st.nextToken ()); 14 modrá = Integer.parseInt (st.nextToken ()); 15} catch (Výnimka e) {16 return null; // (CHYBOVÝ ŠTÁT) ho nebolo možné analyzovať 17} 18 vrátiť novú farbu (červená, zelená, modrá); // (KONIEC ŠTÁT) hotovo. 19} 

Vyššie uvedený kód implementuje veľmi jednoduchý syntaktický analyzátor, ktorý načíta reťazec „number, number, number“ a vráti nový Farba objekt. V riadku 10 vytvorí kód nový StringTokenizer objekt, ktorý obsahuje údaje parametrov (predpokladajme, že táto metóda je súčasťou appletu), a zoznam znakov oddeľovača, ktorý sa skladá z čiarok. Potom na riadkoch 12, 13 a 14 je každý token extrahovaný z reťazca a prevedený na číslo pomocou Integer parseInt metóda. Tieto konverzie sú obklopené a Skús chytiť blok v prípade, že číselné reťazce neboli platné čísla alebo Tokenizer hodí výnimku, pretože sa jej minuli tokeny. Ak sa prevedú všetky čísla, dosiahne sa koncový stav a a Farba objekt je vrátený; inak sa dosiahne chybový stav a nulový sa vracia.

Jednou z funkcií StringTokenizer trieda je, že sa dá ľahko stohovať. Pozrite sa na pomenovanú metódu getColor dole, čo sú riadky 10 až 18 vyššie uvedenej metódy.

 / ** * Analyzujte farebnú n-ticu "r, g, b" na AWT Farba objekt. * / 1 Farba getColor (údaje reťazca) {2 int červená, zelená, modrá; 3 StringTokenizer st = nový StringTokenizer (data, ","); 4 vyskúšajte {5 red = Integer.parseInt (st.nextToken ()); 6 zelená = Integer.parseInt (st.nextToken ()); 7 modrá = Integer.parseInt (st.nextToken ()); 8} catch (Výnimka e) {9 return null; // (CHYBOVÝ ŠTÁT) ho nebolo možné analyzovať 10} 11 vrátiť novú farbu (červená, zelená, modrá); // (KONIEC ŠTÁT) hotovo. 12} 

O niečo zložitejší syntaktický analyzátor je uvedený v kóde nižšie. Tento syntaktický analyzátor je implementovaný v metóde getColors, ktorý je definovaný na vrátenie poľa Farba predmety.

 / ** * Analyzujte množinu farieb "r1, g1, b1: r2, g2, b2: ...: rn, gn, bn" na * pole objektov AWT Color. * / 1 Farba [] getColors (údaje reťazca) {2 Vector akum = nový Vector (); 3 Farebné kl, výsledok []; 4 StringTokenizer st = nový StringTokenizer (data, ":"); 5 while (st.hasMoreTokens ()) {6 cl = getColor (st.nextToken ()); 7 if (cl! = Null) {8 akum.addElement (cl); 9} else {10 System.out.println ("Chyba - zlá farba."); 11} 12} 13 if (akum.size () == 0) 14 return null; 15 výsledok = nová farba [akum.size ()]; 16 pre (int i = 0; i <akum.size (); i ++) {17 výsledok [i] = (farba) akum.elementAt (i); 18} 19 návratový výsledok; 20} 

Vo vyššie uvedenej metóde, ktorá sa iba mierne líši od metódy getColor metódou vytvorí kód v riadkoch 4 až 12 nový Tokenizer extrahovať tokeny obklopené dvojbodkou (:). Ako si môžete prečítať v komentári k dokumentácii k metóde, táto metóda očakáva, že farebné n-tice budú oddelené dvojbodkami. Každé volanie na číslo nextToken v StringTokenizer triedy vráti nový token, kým sa nevyčerpá reťazec. Vrátené tokeny budú reťazce čísel oddelené čiarkami; tieto reťazce tokenov sú napájané getColor, ktorá potom extrahuje farbu z troch čísel. Vytvára sa nový StringTokenizer objekt pomocou tokenu vráteného iným StringTokenizer Object umožňuje, aby bol analyzovaný kód, ktorý sme napísali, trochu sofistikovanejší v tom, ako interpretuje vstup do reťazca.

Akokoľvek je to užitočné, nakoniec vyčerpáte schopnosti StringTokenizer triedy a musí prejsť k svojmu veľkému bratovi StreamTokenizer.

Trieda StreamTokenizer

Ako naznačuje názov triedy, a StreamTokenizer objekt očakáva, že jeho vstup bude pochádzať z InputStream trieda. Ako StringTokenizer vyššie táto trieda prevádza vstupný prúd na kúsky, ktoré môže váš syntaktický kód interpretovať, ale tým podobnosť končí.

StreamTokenizer je a riadený stolom lexikálny analyzátor. To znamená, že každému možnému vstupnému znaku je priradený význam a skener pri rozhodovaní o tom, čo urobí, použije význam aktuálneho znaku. Pri implementácii tejto triedy sú znakom priradená jedna z troch kategórií. Sú to:

• Biely vesmír znaky - ich lexikálny význam sa obmedzuje na oddeľovanie slov

• Slovo znaky - mali by sa agregovať, ak susedia s iným slovným znakom

• Obyčajné znaky - mali by sa okamžite vrátiť syntaktickému analyzátoru

Predstavte si implementáciu tejto triedy ako jednoduchý stavový stroj, ktorý má dva stavy - nečinný a hromadiť. V každom štáte je vstupom znak z jednej z vyššie uvedených kategórií. Trieda prečíta znak, skontroluje jeho kategóriu, urobí nejaké kroky a prejde do ďalšieho stavu. Nasledujúca tabuľka zobrazuje tento stavový automat.

Okrem tohto jednoduchého mechanizmu StreamTokenizer trieda pridáva niekoľko heuristík. Medzi ne patrí spracovanie čísel, spracovanie citovaných reťazcov, spracovanie komentárov a spracovanie na konci riadku.

Prvým príkladom je spracovanie čísel. Určité postupnosti znakov možno interpretovať ako predstavujúce číselnú hodnotu. Napríklad postupnosť znakov 1, 0, 0,. A 0 navzájom susediacich vo vstupnom toku predstavuje číselnú hodnotu 100,0. Keď sú všetky číslice (0 až 9), bodka (.) A znak mínus (-) špecifikované ako súčasť znaku slovo nastaviť StreamTokenizer triede sa dá povedať, aby interpretovala slovo, ktoré sa chystá vrátiť, ako možné číslo. Nastavenie tohto režimu sa dosiahne zavolaním na parseNumbers metóda na objekte tokenizéra, ktorý ste vytvorili inštanciou (toto je predvolené nastavenie). Ak je analyzátor v akumulovanom stave a nasledujúci znak by bol nie byť súčasťou čísla, skontroluje sa aktuálne nahromadené slovo, aby sa zistilo, či ide o platné číslo. Ak je platný, vráti sa a skener sa presunie do ďalšieho príslušného stavu.

Ďalším príkladom je spracovanie citovaného reťazca. Často je žiaduce vložiť reťazec, ktorý je obklopený úvodzovkou (zvyčajne dvojitá (") alebo jednoduchá (') úvodzovka) ako jediný token. StreamTokenizer trieda umožňuje určiť ľubovoľný znak ako znak v úvodzovkách. Predvolene sú to znaky jednoduchých úvodzoviek (') a dvojitých úvodzoviek ("). Stavový automat je upravený tak, aby spotrebovával znaky v hromadnom stave, kým nebude spracovaný ďalší znak úvodzovky alebo koniec riadku. Aby ste mohli ak citujete znak úvodzovky, analyzátor zaobchádza s znakom úvodzovky, ktorému predchádza spätné lomítko (\) vo vstupnom toku a vo vnútri citácie, ako so slovným znakom.