Lexikální analýza a Java: 1. část

Lexikální analýza a analýza

Při psaní aplikací Java je jednou z nejběžnějších věcí, které budete od výroby vyžadovat, analyzátor. Analyzátory se pohybují od jednoduchých po složité a používají se ke všemu, od pohledu na možnosti příkazového řádku až po interpretaci zdrojového kódu Java. v JavaWorldV prosincovém čísle jsem vám ukázal Jacka, automatický generátor syntaktického analyzátoru, který převádí specifikace gramatiky na vysoké úrovni do tříd Java, které implementují syntaktický analyzátor popsaný v těchto specifikacích. Tento měsíc vám ukážu zdroje, které Java poskytuje k psaní cílených lexikálních analyzátorů a analyzátorů. Tyto poněkud jednodušší analyzátory vyplňují mezeru mezi jednoduchým porovnáním řetězců a složitými gramatikami, které Jack sestavuje.

Účelem lexikálních analyzátorů je převzít proud vstupních znaků a dekódovat je do tokenů vyšší úrovně, kterým analyzátor porozumí. Analyzátory spotřebovávají výstup lexikálního analyzátoru a pracují analýzou sekvence vrácených tokenů. Analyzátor odpovídá těmto sekvencím do koncového stavu, což může být jeden z možných mnoha koncových stavů. Koncové stavy definují cíle analyzátoru. Když je dosaženo koncového stavu, program pomocí syntaktického analyzátoru provede nějakou akci - buď nastavení datových struktur, nebo provedení nějakého kódu specifického pro akci. Kromě toho mohou analyzátory detekovat - ze sledu tokenů, které byly zpracovány - když nelze dosáhnout žádného legálního konečného stavu; v tomto bodě analyzátor identifikuje aktuální stav jako chybový stav. Je na aplikaci, aby se rozhodla, co má podniknout, když analyzátor identifikuje buď koncový stav, nebo chybový stav.

Standardní základna tříd Java obsahuje několik tříd lexikálních analyzátorů, nedefinuje však žádné třídy analyzátorů pro všeobecné účely. V tomto sloupci se podrobně podívám na lexikální analyzátory dodávané s Javou.

Lexikální analyzátory Java

Specifikace jazyka Java, verze 1.0.2, definuje dvě lexikální třídy analyzátorů, StringTokenizer a StreamTokenizer. Z jejich jmen to můžete odvodit StringTokenizer používá Tětiva objekty jako jeho vstup a StreamTokenizer používá InputStream předměty.

Třída StringTokenizer

Ze dvou dostupných lexikálních tříd analyzátorů je nejjednodušší pochopit StringTokenizer. Když postavíte nový StringTokenizer objekt, metoda konstruktoru nominálně přijímá dvě hodnoty - vstupní řetězec a řetězec oddělovače. Třída poté vytvoří sekvenci tokenů, která představuje znaky mezi znaky oddělovače.

Jako lexikální analyzátor StringTokenizer lze formálně definovat, jak je uvedeno níže.

[~ oddělovač1, oddělovač2, ..., oddělovačN] :: Token 

Tato definice se skládá z regulárního výrazu, který odpovídá každému znaku až na znaky oddělovače. Všechny sousedící odpovídající znaky jsou shromážděny do jednoho tokenu a vráceny jako token.

Nejběžnější použití StringTokenizer třída slouží k oddělení sady parametrů - například seznam čísel oddělených čárkami. StringTokenizer je v této roli ideální, protože odstraní oddělovače a vrátí data. The StringTokenizer třída také poskytuje mechanismus pro identifikaci seznamů, ve kterých jsou tokeny „null“. V aplikacích, ve kterých mají některé parametry buď výchozí hodnoty, nebo nemusí být přítomny ve všech případech, byste použili nulové tokeny.

Níže uvedený applet je jednoduchý StringTokenizer cvičenec. Zdroj appletu StringTokenizer je zde. Chcete-li použít applet, zadejte do oblasti vstupního řetězce nějaký text, který má být analyzován, a potom zadejte řetězec skládající se ze znaků oddělovače v oblasti řetězce oddělovače. Nakonec klikněte na Tokenize! knoflík. Výsledek se zobrazí v seznamu tokenů pod vstupním řetězcem a bude uspořádán jako jeden token na řádek.

Vezměme si jako příklad řetězec „a, b, d“ předaný a StringTokenizer objekt, který byl zkonstruován s čárkou (,) jako oddělovacím znakem. Pokud tyto hodnoty vložíte do appletu cvičence výše, uvidíte, že Tokenizer objekt vrací řetězce „a“, „b“ a „d“. Pokud jste chtěli poznamenat, že chybí jeden parametr, možná vás překvapilo, že to v sekvenci tokenů nevidíte. Schopnost detekovat chybějící tokeny umožňuje logický návratový oddělovač, který lze nastavit při vytváření Tokenizer objekt. S tímto parametrem nastaveným, když Tokenizer je zkonstruován, každý oddělovač je také vrácen. Zaškrtněte políčko Oddělovač návratů v appletu výše a nechte řetězec a oddělovač na pokoji. Nyní Tokenizer vrátí "a, čárku, b, čárku, čárku a d." Pokud si všimnete, že získáte dva oddělovací znaky v pořadí, můžete určit, že do vstupního řetězce byl zahrnut token „null“.

Trik k úspěšnému použití StringTokenizer v analyzátoru definuje vstup takovým způsobem, aby se oddělovací znak v datech neobjevil. Je zřejmé, že se tomuto omezení můžete vyhnout tím, že jej navrhnete ve své aplikaci. Níže uvedenou definici metody lze použít jako součást appletu, který ve svém proudu parametrů přijímá barvu ve formě červené, zelené a modré hodnoty.

 / ** * Analyzuje parametr formuláře "10,20,30" jako * n-tici RGB pro barevnou hodnotu. * / 1 Barva getColor (název řetězce) {2 data řetězce; 3 StringTokenizer st; 4 int červená, zelená, modrá; 5 6 data = getParameter (jméno); 7 if (data == null) 8 return null; 9 10 st = nový StringTokenizer (data, ","); 11 try {12 red = Integer.parseInt (st.nextToken ()); 13 zelená = Integer.parseInt (st.nextToken ()); 14 modrá = Integer.parseInt (st.nextToken ()); 15} catch (Výjimka e) {16 return null; // (STAV CHYBY) jej nemohl analyzovat 17} 18 vrátit novou barvu (červená, zelená, modrá); // (END STATE) hotovo. 19} 

Výše uvedený kód implementuje velmi jednoduchý parser, který načte řetězec „number, number, number“ a vrátí nový Barva objekt. V řádku 10 vytvoří kód nový StringTokenizer objekt, který obsahuje data parametrů (předpokládejme, že tato metoda je součástí appletu), a seznam znaků oddělovače, který se skládá z čárek. Pak na řádcích 12, 13 a 14 je každý token extrahován z řetězce a převeden na číslo pomocí Integer analyzovat metoda. Tyto převody jsou obklopeny a Zkus chytit blok v případě, že číselné řetězce nebyly platná čísla nebo Tokenizer vyvolá výjimku, protože jí došly tokeny. Pokud se všechna čísla převedou, dosáhne se koncového stavu a a Barva objekt je vrácen; jinak je dosažen chybový stav a nula je vrácen.

Jednou z funkcí StringTokenizer třída je, že je snadno stohovatelná. Podívejte se na pojmenovanou metodu getColor níže, což je řádky 10 až 18 výše uvedené metody.

 / ** * Analyzuje barevnou n-tici "r, g, b" na AWT Barva objekt. * / 1 Barva getColor (String data) {2 int červená, zelená, modrá; 3 StringTokenizer st = nový StringTokenizer (data, ","); 4 zkuste {5 red = Integer.parseInt (st.nextToken ()); 6 zelená = Integer.parseInt (st.nextToken ()); 7 modrá = Integer.parseInt (st.nextToken ()); 8} catch (Výjimka e) {9 return null; // (STAV CHYBY) jej nemohl analyzovat 10} 11 vrátit novou barvu (červená, zelená, modrá); // (END STATE) hotovo. 12} 

Trochu složitější analyzátor je uveden v kódu níže. Tento analyzátor je implementován v metodě getColors, který je definován pro vrácení pole Barva předměty.

 / ** * Analyzuje sadu barev "r1, g1, b1: r2, g2, b2: ...: rn, gn, bn" na * pole objektů AWT Color. * / 1 Color [] getColors (String data) {2 Vector akum = nový Vector (); 3 Barevný tř., Výsledek []; 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 - špatná barva."); 11} 12} 13 if (akum.size () == 0) 14 return null; 15 výsledek = nová barva [akum. Velikost ()]; 16 pro (int i = 0; i <akum. Velikost (); i ++) {17 výsledek [i] = (Barva) akum.elementAt (i); 18} 19 návratový výsledek; 20} 

Ve výše uvedené metodě, která se jen mírně liší od metody getColor metoda, kód v řádcích 4 až 12 vytvoří nový Tokenizer extrahovat tokeny obklopené dvojtečkou (:). Jak si můžete přečíst v komentáři k metodě, tato metoda očekává, že barevné n-tice budou odděleny dvojtečkami. Každé volání na nextToken v StringTokenizer třída vrátí nový token, dokud nebude řetězec vyčerpán. Vrácené tokeny budou řetězce čísel oddělené čárkami; tyto řetězce tokenů jsou přiváděny getColor, který poté extrahuje barvu ze tří čísel. Vytváření nového StringTokenizer objekt pomocí tokenu vráceného jiným StringTokenizer Object umožňuje, aby kód analyzátoru, který jsme napsali, byl trochu propracovanější v tom, jak interpretuje vstup řetězce.

Jakkoli je to užitečné, nakonec vyčerpáte schopnosti StringTokenizer třídy a musí přejít ke svému velkému bratrovi StreamTokenizer.

Třída StreamTokenizer

Jak název třídy napovídá, a StreamTokenizer objekt očekává, že jeho vstup bude pocházet z InputStream třída. Jako StringTokenizer výše tato třída převádí vstupní proud na bloky, které může váš parsovací kód interpretovat, ale tím podobnost končí.

StreamTokenizer je řízený stolem lexikální analyzátor. To znamená, že každému možnému vstupnímu znaku je přiřazen význam a skener používá význam aktuálního znaku k rozhodnutí, co má dělat. Při implementaci této třídy jsou znakům přiřazena jedna ze tří kategorií. Tyto jsou:

• Mezery znaky - jejich lexikální význam je omezen na oddělování slov

• Slovo znaky - měly by být agregovány, pokud sousedí s jiným znakem slova

• Obyčejný znaky - měly by být okamžitě vráceny analyzátoru

Představte si implementaci této třídy jako jednoduchý stavový stroj, který má dva stavy - líný a akumulovat. V každém stavu je vstupem znak z jedné z výše uvedených kategorií. Třída načte znak, zkontroluje jeho kategorii a provede nějakou akci a přejde do dalšího stavu. Následující tabulka ukazuje tento stavový automat.

Kromě tohoto jednoduchého mechanismu StreamTokenizer třída přidává několik heuristik. Patří mezi ně zpracování čísel, zpracování citovaných řetězců, zpracování komentářů a zpracování na konci řádku.

Prvním příkladem je zpracování čísel. Určité posloupnosti znaků lze interpretovat tak, že představují číselnou hodnotu. Například posloupnost znaků 1, 0, 0,. A 0 vedle sebe ve vstupním proudu představuje číselnou hodnotu 100,0. Když jsou všechny číselné znaky (0 až 9), tečkovaný znak (.) A znak mínus (-) zadány jako součást slovo nastav StreamTokenizer třídě lze říci, aby interpretovala slovo, které se chystá vrátit, jako možné číslo. Nastavení tohoto režimu je dosaženo voláním analyzovat čísla metoda na objektu tokenizéru, který jste vytvořili (toto je výchozí nastavení). Pokud je analyzátor ve stavu akumulace a další znak by byl ne být součástí čísla, zkontroluje se aktuálně nahromaděné slovo, zda se jedná o platné číslo. Pokud je platný, vrátí se a skener přejde do dalšího příslušného stavu.

Dalším příkladem je citované zpracování řetězce. Často je žádoucí předat řetězec, který je obklopen znakem uvozovky (obvykle dvojitá (") nebo jednoduchá (') nabídka) jako jediný token. StreamTokenizer Třída umožňuje určit libovolný znak jako citující znak. Ve výchozím nastavení se jedná o znaky jednoduché uvozovky (') a dvojité uvozovky ("). Stavový stroj je upraven tak, aby spotřebovával znaky ve stavu hromadění, dokud nebude zpracován buď jiný znak nabídky, nebo znak konce řádku. Chcete-li povolit citovat znak uvozovky, analyzátor považuje znak uvozovky, kterému předchází zpětné lomítko (\) ve vstupním proudu a uvnitř citace jako znak slova.