Лексикален анализ, Част 2: Изграждане на приложение

Миналия месец разгледах класовете, които Java предоставя, за да направя основен лексикален анализ. Този месец ще разгледам просто приложение, което използва StreamTokenizerза внедряване на интерактивен калкулатор.

За да разгледаме накратко статията от миналия месец, има два класа на лексикален анализатор, които са включени в стандартното разпределение на Java: StringTokenizerи StreamTokenizer. Тези анализатори преобразуват входа си в дискретни символи, които анализаторът може да използва, за да разбере даден вход. Анализаторът изпълнява граматика, която се определя като едно или повече състояния на целта, постигнати чрез виждане на различни поредици от символи. Когато се достигне състояние на целта на анализатора, той изпълнява някакво действие. Когато анализаторът открие, че не са възможни състояния на целите, като се има предвид текущата последователност от маркери, той определя това като състояние на грешка. Когато анализаторът достигне състояние на грешка, той изпълнява действие за възстановяване, което връща анализатора обратно до точка, в която той може да започне да анализира отново. Обикновено това се реализира чрез консумиране на жетони, докато парсерът се върне към валидна начална точка.

Миналия месец ви показах някои методи, които използваха a StringTokenizerза анализиране на някои входни параметри. Този месец ще ви покажа приложение, което използва StreamTokenizerобект за синтактичен анализ на входния поток и внедряване на интерактивен калкулатор.

Изграждане на приложение

Нашият пример е интерактивен калкулатор, подобен на командата Unix bc (1). Както ще видите, той изтласква StreamTokenizerкласа точно до ръба на полезността му като лексикален анализатор. По този начин той служи като добра демонстрация на това къде може да се направи границата между "прости" и "сложни" анализатори. Този пример е приложение на Java и следователно работи най-добре от командния ред.

Като кратко обобщение на своите способности, калкулаторът приема изрази във формата

[име на променлива] "=" израз 

Името на променливата не е задължително и може да бъде произволен низ от знаци в обхвата на думите по подразбиране. (Можете да използвате аплета за тренировка от статията от миналия месец, за да освежите паметта си върху тези символи.) Ако името на променливата е пропуснато, стойността на израза просто се отпечатва. Ако името на променливата е налице, стойността на израза се присвоява на променливата. След като променливите са присвоени, те могат да бъдат използвани в по-късни изрази. По този начин те изпълняват ролята на „спомени“ на съвременен ръчен калкулатор.

Изразът е съставен от операнди под формата на числови константи (двойна точност, константи с плаваща запетая) или имена на променливи, оператори и скоби за групиране на определени изчисления. Законовите оператори са събиране (+), изваждане (-), умножение (*), деление (/), побитово И (&), побитово ИЛИ (|), побитово XOR (#), степенуване (^) и еднократно отрицание или с минус (-) за резултата от допълването на двамата, или с гръм и трясък (!) за резултата за допълване на двамата

В допълнение към тези изявления, нашето приложение за калкулатор също може да поеме една от четирите команди: „dump“, „clear“, „help“ и „quit“. На dumpотпечатъците командни извън всички променливи, които понастоящем са определени, както и техните стойности. В clearкоманда изтрива всички определените понастоящем променливи. На helpотпечатъците командни извън няколко реда помощен текст, за да започнете потребителя. В quitкоманда предизвиква прилагането на излизане.

Цялото примерно приложение се състои от два парсера - един за команди и изрази и един за изрази.

Изграждане на синтактичен анализатор на команди

Анализаторът на команди е реализиран в класа на приложението за пример STExample.java. (Вижте раздела Ресурси за указател към кода.) mainМетодът за този клас е дефиниран по-долу. Ще мина през парчетата за теб.

1 публична статична void main (String args []) хвърля IOException {2 Hashtable променливи = new Hashtable (); 3 StreamTokenizer st = нов StreamTokenizer (System.in); 4 st.eolIsSignificant (true); 5 st.lowerCaseMode (вярно); 6 st.ordinaryChar ('/'); 7 st.ordinaryChar ('-');

В кода по-горе първото нещо, което правя, е да разпределя java.util.Hashtableклас за задържане на променливите. След това разпределям а StreamTokenizerи го коригирам леко от настройките по подразбиране. Обосновката за промените е следната:

  • eolIsSignificant е зададено на true, така че токенизаторът да връща индикация за края на реда. Използвам края на реда като точка, където изразът завършва.

  • lowerCaseMode е зададено на true, така че имената на променливите винаги ще бъдат връщани с малки букви. По този начин имената на променливите не са чувствителни към малки и големи букви.

  • Наклонената черта (/) е настроена на обикновен знак, така че няма да се използва за обозначаване на началото на коментар и вместо това може да се използва като оператор на разделяне.

  • Символът минус (-) е зададен да бъде обикновен знак, така че низът "3-3" ще се сегментира в три символа - "3", "-" и "3" - вместо само "3" и "-3." (Не забравяйте, че разборът на числа е зададен по подразбиране на „включен“.)

След като токенизаторът е настроен, анализаторът на команди работи в безкраен цикъл (докато разпознае командата "quit", в който момент излиза). Това е показано по-долу.

8 while (вярно) {9 Израз на разрешаване; 10 int c = StreamTokenizer.TT_EOL; 11 String varName = null; 12 13 System.out.println ("Въведете израз ..."); 14 опитайте {15 while (true) {16 c = st.nextToken (); 17 if (c == StreamTokenizer.TT_EOF) {18 System.exit (1); 19} иначе ако (c == StreamTokenizer.TT_EOL) {20 продължавам; 21} else if (c == StreamTokenizer.TT_WORD) {22 if (st.sval.compareTo ("dump") == 0) {23 dumpVariables (променливи); 24 продължете; 25} else if (st.sval.compareTo ("clear") == 0) {26 променливи = нова Hashtable (); 27 продължават; 28} else if (st.sval.compareTo ("quit") == 0) {29 System.exit (0); 30} иначе ако (st.sval.compareTo ("изход") == 0) {31 System.exit (0); 32} else if (st.sval.compareTo ("help") == 0) {33 help (); 34 продължи; 35} 36 varName = st.sval; 37 c = st.nextToken ();38} 39 почивка; 40} 41 if (c! = '=') {42 хвърли нов SyntaxError ("липсващ начален '=' знак."); 43}

Както можете да видите на ред 16, първият маркер се извиква чрез извикване nextTokenна StreamTokenizerобекта. Това връща стойност, указваща вида на сканирания маркер. Връщаната стойност или ще бъде една от дефинираните константи в StreamTokenizerкласа, или ще бъде символна стойност. „Мета“ жетоните (тези, които не са просто символни стойности) се дефинират както следва:

  • TT_EOF- Това показва, че сте в края на входния поток. За разлика от това StringTokenizer, няма hasMoreTokensметод.

  • TT_EOL - Това ви казва, че обектът току-що е преминал последователност от края на реда.

  • TT_NUMBER - Този тип токен съобщава на кода на анализатора, че на входа е видян номер.

  • TT_WORD - Този тип маркер показва, че е сканирана цяла „дума“.

Когато резултатът не е една от горните константи, това е или стойността на символа, представляваща символ в „обикновения“ диапазон от знаци, който е сканиран, или един от зададените от вас кавички. (В моя случай не е зададен знак за кавички.) Когато резултатът е един от вашите символи за кавички, цитираният низ може да бъде намерен в променливата svalна екземпляра на низа на StreamTokenizerобекта.

Кодът в редове от 17 до 20 се занимава с индикации за края на файла и края на файла, докато в ред 21 се взема клаузата if, ако е върнат маркер на дума. В този прост пример думата е или команда, или име на променлива. Редове 22 до 35 се занимават с четирите възможни команди. Ако се стигне до ред 36, това трябва да е име на променлива; следователно програмата съхранява копие на името на променливата и получава следващия маркер, който трябва да е знак за равенство.

Ако в ред 41 маркерът не е знак за равенство, нашият прост анализатор открива състояние на грешка и хвърля изключение, за да го сигнализира. Създадох две общи изключения SyntaxErrorи ExecError, за да разгранича грешките при анализиране на времето от грешките по време на изпълнение. В mainметода продължава с линия 44 по-долу.

44 res = ParseExpression.expression (st); 45} catch (SyntaxError se) {46 res = null; 47 varName = null; 48 System.out.println ("\ nСъздадена е грешка в синтаксиса! -" + se.getMsg ()); 49 докато (c! = StreamTokenizer.TT_EOL) 50 c = st.nextToken (); 51 продължават; 52}

В ред 44 изразът отдясно на знака за равенство се анализира с анализатора на израза, дефиниран в ParseExpressionкласа. Имайте предвид, че редове от 14 до 44 са обвити в блок try / catch, който улавя синтаксисните грешки и се справя с тях. Когато се открие грешка, действието за възстановяване на анализатора е да консумира всички маркери до и включително следващия маркер на края на реда. Това е показано в редове 49 и 50 по-горе.

At this point, if an exception was not thrown, the application has successfully parsed a statement. The final check is to see that the next token is the end of line. If it isn't, an error has gone undetected. The most common error will be mismatched parentheses. This check is shown in lines 53 through 60 of the code below.

53 c = st.nextToken(); 54 if (c != StreamTokenizer.TT_EOL) { 55 if (c == ')') 56 System.out.println("\nSyntax Error detected! - To many closing parens."); 57 else 58 System.out.println("\nBogus token on input - "+c); 59 while (c != StreamTokenizer.TT_EOL) 60 c = st.nextToken(); 61 } else { 

When the next token is an end of line, the program executes lines 62 through 69 (shown below). This section of the method evaluates the parsed expression. If the variable name was set in line 36, the result is stored in the symbol table. In either case, if no exception is thrown, the expression and its value are printed to the System.out stream so that you can see what the parser decoded.

62 try { 63 Double z; 64 System.out.println("Parsed expression : "+res.unparse()); 65 z = new Double(res.value(variables)); 66 System.out.println("Value is : "+z); 67 if (varName != null) { 68 variables.put(varName, z); 69 System.out.println("Assigned to : "+varName); 70 } 71 } catch (ExecError ee) { 72 System.out.println("Execution error, "+ee.getMsg()+"!"); 73 } 74 } 75 } 76 } 

In the STExample class, the StreamTokenizer is being used by a command-processor parser. This type of parser commonly would be used in a shell program or in any situation in which the user issues commands interactively. The second parser is encapsulated in the ParseExpression class. (See the Resources section for the complete source.) This class parses the calculator's expressions and is invoked in line 44 above. It is here that StreamTokenizer faces its stiffest challenge.

Building an expression parser

The grammar for the calculator's expressions defines an algebraic syntax of the form "[item] operator [item]." This type of grammar comes up again and again and is called an operator grammar. A convenient notation for an operator grammar is:

id ( "OPERATOR" id )* 

The code above would be read "An ID terminal followed by zero or more occurrences of an operator-id tuple." The StreamTokenizer class would seem pretty ideal for analyzing such streams, because the design naturally breaks the input stream into word, number, and ordinary character tokens. As I'll show you, this is true up to a point.

The ParseExpression class is a straightforward, recursive-descent parser for expressions, right out of an undergraduate compiler-design class. The Expression method in this class is defined as follows:

1 статичен израз на израз (StreamTokenizer st) изхвърля SyntaxError {2 резултат на израз; 3 boolean done = false; 4 5 резултат = сума (st); 6 докато (! Готово) {7 опитайте {8 switch (st.nextToken ()) 9 case '&': 10 result = new Expression (OP_AND, result, sum (st)); 11 почивка; 12 случай '23} catch (IOException ioe) {24 хвърли нов SyntaxError ("Получих I / O изключение."); 25} 26} 27 върнат резултат; 28}