Лексикален анализ и Java: Част 1

Лексикален анализ и разбор

Когато пишете Java приложения, едно от най-често срещаните неща, които ще трябва да създадете, е парсер. Анализаторите варират от прости до сложни и се използват за всичко - от разглеждане на опциите на командния ред до интерпретиране на изходния код на Java. В декемврийския брой на JavaWorld ви показах Jack, автоматичен генератор на парсер, който преобразува граматичните спецификации на високо ниво в Java класове, които изпълняват парсера, описан от тези спецификации. Този месец ще ви покажа ресурсите, които Java предоставя за писане на целеви лексикални анализатори и анализатори. Тези малко по-опростени анализатори запълват празнината между простото сравнение на низове и сложните граматики, които Джак компилира.

Целта на лексикалните анализатори е да поемат поток от входни символи и да ги декодират в символи от по-високо ниво, които анализаторът може да разбере. Анализаторите консумират изхода на лексикалния анализатор и работят, като анализират последователността на върнатите символи. Анализаторът съчетава тези последователности с крайно състояние, което може да е едно от многото крайни състояния. Крайните състояния определят целитена парсера. Когато се достигне крайно състояние, програмата, използваща анализатора, извършва някои действия - или настройва структури от данни, или изпълнява някакъв специфичен за действие код. Освен това анализаторите могат да открият - от последователността на обработените символи - когато не може да бъде достигнато юридическо крайно състояние; в този момент анализаторът идентифицира текущото състояние като състояние на грешка. Приложението трябва да реши какво действие да предприеме, когато анализаторът идентифицира или крайно състояние, или състояние на грешка.

Стандартната база на Java клас включва няколко класа лексикален анализатор, но не дефинира никакви класове за синтактичен анализ. В тази колона ще разгледам задълбочено лексикалните анализатори, които се доставят с Java.

Лексикалните анализатори на Java

Спецификацията на езика Java, версия 1.0.2, дефинира два класа лексикален анализатор StringTokenizerи StreamTokenizer. От техните имена можете да заключите, че StringTokenizerизползва Stringобекти като свой вход и StreamTokenizerизползва InputStreamобекти.

Класът StringTokenizer

От двата налични класа лексикален анализатор най-лесно е да се разбере StringTokenizer. Когато конструирате нов StringTokenizerобект, методът на конструктора номинално приема две стойности - входен низ и низ разделител. След това класът конструира поредица от символи, която представлява символите между разделителите.

Като лексикален анализатор StringTokenizerможе да бъде официално дефиниран, както е показано по-долу.

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

Тази дефиниция се състои от регулярен израз, който съответства на всеки символ, с изключение на разделителите. Всички съседни съвпадащи символи се събират в един жетон и се връщат като Токен.

Най-често се използва StringTokenizerкласът за отделяне на набор от параметри - като списък с числа, разделени със запетая. StringTokenizerе идеален в тази роля, защото премахва разделителите и връща данните. В StringTokenizerклас също така предвижда механизъм за установяване на списъци, в които има "нулеви" жетони. Бихте използвали нулеви маркери в приложения, в които някои параметри имат стойности по подразбиране или не се изисква да присъстват във всички случаи.

Аплетът по-долу е прост StringTokenizerупражнител. Източникът на аплета StringTokenizer е тук. За да използвате аплета, въведете малко текст, който ще се анализира, в областта на входния низ, след това въведете низ, състоящ се от разделителни знаци в областта на разделителния низ. Накрая кликнете върху Tokenize! бутон. Резултатът ще се покаже в списъка с маркери под входния низ и ще бъде организиран като един знак на ред.

За да видите този аплет, ви е необходим браузър с активиран Java.

Помислете за пример низ, "a, b, d", предаден на StringTokenizerобект, който е конструиран със запетая (,) като разделител. Ако поставите тези стойности в аплета на тренировката по-горе, ще видите, че Tokenizerобектът връща низовете "a", "b" и "d." Ако вашето намерение е било да забележите, че липсва един параметър, може да сте били изненадани, за да не видите индикация за това в последователността на маркерите. Възможността за откриване на липсващи маркери се активира от булевото значение Return Separator, което може да бъде зададено, когато създавате Tokenizerобект. С този параметър, зададен, когато Tokenizerе конструиран, всеки разделител също се връща. Поставете отметка в квадратчето за Return Separator в аплета по-горе и оставете низа и разделителя сами. СегаTokenizerвръща "a, запетая, b, запетая, запетая и d." Като отбелязвате, че получавате два разделителни знака последователно, можете да определите, че във входния низ е включен маркер „null“.

Трикът за успешно използване StringTokenizerв парсер е дефинирането на входа по такъв начин, че разделителят да не се появява в данните. Ясно е, че можете да избегнете това ограничение, като го проектирате във вашето приложение. Дефиницията на метода по-долу може да се използва като част от аплет, който приема цвят под формата на червени, зелени и сини стойности в своя поток от параметри.

/ ** * Анализирайте параметър от формата „10,20,30“ като * RGB кортеж за стойност на цвета. * / 1 Цвят getColor (Име на низ) {2 String данни; 3 StringTokenizer st; 4 int червено, зелено, синьо; 5 6 данни = getParameter (име); 7 if (data == null) 8 връща null; 9 10 st = нов StringTokenizer (данни, ","); 11 опитайте {12 red = Integer.parseInt (st.nextToken ()); 13 зелено = Integer.parseInt (st.nextToken ()); 14 синьо = Integer.parseInt (st.nextToken ()); 15} catch (Изключение e) {16 return null; // (ГРЕШКА СЪСТОЯНИЕ) не може да го анализира 17} 18 връща нов цвят (червен, зелен, син); // (END STATE) готово. 19}

Кодът по-горе реализира много прост парсер, който чете низа "число, число, число" и връща нов Colorобект. В ред 10 кодът създава нов StringTokenizerобект, който съдържа данните за параметрите (приемете, че този метод е част от аплет) и списък със символи за разделител, който се състои от запетаи. След това в редове 12, 13 и 14 всеки жетон се извлича от низа и се преобразува в число, използвайки метода Integer parseInt. Тези преобразувания са заобиколени от try/catchблок, в случай че низовете с числа не са валидни числа или Tokenizerизхвърлят изключение, тъй като са изтекли символите. Ако всички числа се преобразуват, достига се крайното състояние и Colorсе връща обект; в противен случай се достига до състоянието на грешката и се връща null .

Една особеност на StringTokenizerкласа е, че той лесно се подрежда. Погледнете метода, посочен getColorпо-долу, който е редове 10 до 18 от горния метод.

/ ** * Анализира цветна кортеж „r, g, b“ в AWT Colorобект. * / 1 Цвят getColor (String данни) {2 int червено, зелено, синьо; 3 StringTokenizer st = нов StringTokenizer (данни, ","); 4 опитайте {5 red = Integer.parseInt (st.nextToken ()); 6 зелено = Integer.parseInt (st.nextToken ()); 7 синьо = Integer.parseInt (st.nextToken ()); 8} catch (Изключение e) {9 return null; // (ГРЕШКА СЪСТОЯНИЕ) не може да го анализира 10} 11 връща нов цвят (червен, зелен, син); // (END STATE) готово. 12 }

Малко по-сложен парсер е показан в кода по-долу. Този парсер е реализиран в метода getColors, който е дефиниран за връщане на масив от Colorобекти.

/ ** * Анализирайте набор от цветове "r1, g1, b1: r2, g2, b2: ...: rn, gn, bn" в * масив от цветни обекти AWT. * / 1 Цвят [] getColors (String данни) {2 Vector accum = new Vector (); 3 цвят cl, резултат []; 4 StringTokenizer st = нов StringTokenizer (данни, ":"); 5 докато (st.hasMoreTokens ()) {6 cl = getColor (st.nextToken ()); 7 if (cl! = Null) {8 accum.addElement (cl); 9} else {10 System.out.println ("Грешка - лош цвят."); 11} 12} 13 if (accum.size () == 0) 14 return null; 15 резултат = нов цвят [accum.size ()]; 16 за (int i = 0; i <accum.size (); i ++) {17 резултат [i] = (Color) accum.elementAt (i); 18} 19 резултат от връщане; 20}

В метода по-горе, който е само малко по-различен от getColorметода, кодът в редове 4 до 12 създава нов Tokenizerза извличане на символи, заобиколен от двоеточие (:) знак. Както можете да прочетете в коментара на документацията за метода, този метод очаква цветни кортежи да бъдат разделени с двоеточие. Всяко обаждане до nextTokenв StringTokenizerкласа ще връща нов маркер, докато низът не бъде изчерпан. Върнатите символи ще бъдат низове от числа, разделени със запетаи; към тези символни низове се подава getColor, който след това извлича цвят от трите числа. Създаването на нов StringTokenizerобект с помощта на маркер, върнат от друг StringTokenizerобект, позволява на парсерния код, който сме написали, да бъде малко по-сложен за това как той интерпретира въвеждането на низа.

Колкото и да е полезно, в крайна сметка ще изчерпите способностите на StringTokenizerкласа и ще трябва да преминете към големия му брат StreamTokenizer.

Класът StreamTokenizer

Както подсказва името на класа, StreamTokenizerобектът очаква неговото въвеждане да идва от InputStreamклас. Подобно на StringTokenizerгорното, този клас преобразува входния поток в парчета, които вашият синтактичен код може да интерпретира, но тук приликата свършва.

StreamTokenizerе лексикален анализатор, управляван от таблица . Това означава, че на всеки възможен въведен знак се присвоява значимост и скенерът използва значението на текущия знак, за да реши какво да прави. При изпълнението на този клас на знаците се присвоява една от трите категории. Това са:

  • Whitespace characters -- their lexical significance is limited to separating words

  • Word characters -- they should be aggregated when they are adjacent to another word character

  • Ordinary characters -- they should be returned immediately to the parser

Imagine the implementation of this class as a simple state machine that has two states -- idle and accumulate. In each state the input is a character from one of the above categories. The class reads the character, checks its category and does some action, and moves on to the next state. The following table shows this state machine.

State Input Action New state
idle word character push back character accumulate
ordinary character return character idle
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.

Следващият пример е цитирана обработка на низове. Често е желателно да се предаде низ, който е заобиколен от кавичка (обикновено двойна (") или единична (') кавичка) като единичен маркер. StreamTokenizerКласът ви позволява да посочите всеки символ като кавичен знак. По подразбиране те са символите с единични кавички (') и двойни кавички ("). Машината на състоянието е модифицирана, за да консумира символи в състоянието на натрупване, докато не бъде обработен или друг символ на кавичка, или знак в края на реда. За да ви позволи да кавирате символа на кавичката, анализаторът третира символа на кавичките, предшестван от обратна наклонена черта (\) във входния поток и вътре в кавичка като знак от дума.