Търсите lex и yacc за Java? Не познаваш Джак

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

Автоматично генериране на анализатор на компилатор

Анализаторът е един от най-често срещаните компоненти на компютърно приложение. Той преобразува текст, който може да бъде прочетен от хората, в структури от данни, известни като анализиране на дървета, които се разбират от компютъра. Ясно си спомням въведението си в автоматичното генериране на парсер: В колежа бях завършил клас по конструиране на компилатор. С помощта на съпругата ми да бях написал прост компилатор, който можеше да превърне програми, написани на език, създаден за класа, в изпълними програми. Спомням си, че се чувствах много постигнат в този момент.

В първата си „истинска“ работа след колежа получих задача да създам нов език за обработка на графики, който да компилирам в команди за графичен копроцесор. Започнах с прясно съставена граматика и се подготвих да стартирам многоседмичния проект за съставяне на компилатор. Тогава един приятел ми показа помощните програми Unix lex и yacc . Lex изгради лексикални анализатори от регулярни изрази и yacc намали спецификацията на граматиката в компилатор, управляван от таблица, който може да произвежда код, когато успешно анализира продукцията от тази граматика. Използвах lex и yacc, и за по-малко от седмица компилаторът ми беше стартиран и работещ! По-късно проектът на Фондацията за свободен софтуер GNU създаде „подобрени“ версии на lex и yacc - наречени flex и bison - за използване на платформи, които не изпълняват производни на операционната система Unix.

Светът на автоматичното генериране на парсер отново напредна, когато Терънс Пар, тогава студент в университета Purdue, създаде набора от инструменти за изграждане на компилатор Purdue или PCCTS. Два компонента на PCCTS - DFA и ANTLR - предоставят същите функции като lex и yacc ; обаче граматиките, които ANTLR приема са граматики LL (k), за разлика от граматиките LALR, използвани от yacc . Освен това кодът, който генерира PCCTS, е много по-четлив от кода, генериран от yacc. Чрез генериране на код, който е по-лесен за четене, PCCTS улеснява човека, който чете кода, да разбере какво правят различните парчета. Това разбиране може да бъде от съществено значение при опит за диагностициране на грешки в спецификацията на граматиката. PCCTS бързо разработи поредица от хора, които намериха файловете си по-лесни за използване от yacc.

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

Джак пристъпва към чинията

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

Jack (римува се с yacc) е генератор на синтактичен анализатор, в духа на PCCTS, който Sun пусна безплатно за програмната общност на Java. Jack е изключително лесен инструмент за описване: Просто казано, вие му давате набор от комбинирани граматични и лексикационни правила под формата на .jack файл и стартирате инструмента и ви връща Java клас, който ще анализира тази граматика. Какво може да бъде по-лесно?

Да се ​​добереш до Джак също е доста лесно. Първо изтегляте копие от началната страница на Jack. Това идва при вас под формата на саморазопаковащ се Java клас, наречен install. За да инсталирате Джак трябва да се позове на този installклас, който, на 95 машина Windows е направено с помощта на командата: C:>java install.

Показаната по-горе команда предполага, че javaкомандата е във вашия команден път и че пътят на класа е настроен по подходящ начин. Ако горната команда не работи или ако не сте сигурни дали нещата са настроени правилно или не, отворете прозорец на MS-DOS, като прекосите елементите от менюто Start-> Programs-> MS-DOS Prompt. Ако имате инсталиран Sun JDK, можете да въведете следните команди:

C:> път C: \ java \ bin;% път% C:> задайте CLASSPATH = .; c: \ java \ lib \ classes.zip 

Ако е инсталирана Symantec Cafe версия 1.2 или по-нова, можете да въведете следните команди:

C:> път C: \ cafe \ java \ bin;% път% 

Пътят на класа трябва вече да е настроен във файл, наречен sc.ini в директорията на bin на Cafe.

След това въведете java installкомандата отгоре. Инсталационната програма ще ви попита в коя директория искате да инсталирате и под нея ще бъде създадена поддиректория Jack.

Използване на Джак

Jack е написан изцяло на Java, така че наличието на класове Jack означава, че този инструмент е незабавно достъпен на всяка платформа, която поддържа Java виртуалната машина. Това обаче означава също, че на кутиите на Windows трябва да стартирате Jack от командния ред. Да приемем, че сте избрали името на директорията JavaTools, когато сте инсталирали Jack на вашата система. За да използвате Джак, ще трябва да добавите класовете на Джак към пътя си към класа. Можете да направите това във вашия файл autoexec.bat или във вашия .cshrc файл, ако сте потребител на Unix. Критичната команда е нещо като реда, показан по-долу:

C:> задайте CLASSPATH =; C: \ JavaTools \ Jack \ java; C: \ java \ lib \ classes.zip 

Обърнете внимание, че потребителите на Symantec Cafe могат да редактират файла sc.ini и да включват там класовете Jack, или могат да зададат CLASSPATHизрично, както е показано по-горе.

Задаването на променливата на средата, както е показано по-горе, поставя класовете Jack в CLASSPATHмежду "." (текущата директория) и основните системни класове за Java. Основният клас за Джак е COM.sun.labs.jack.Main. Капитализацията е важна! В командата има точно четири главни букви („C“, „O“, „M“ и още „M“). За да стартирате Jack ръчно, въведете командата:

C:> java COM.sun.labs.jack.Основен парсер-input.jack

Ако нямате файловете Jack в класа си, можете да използвате тази команда:

C:> java -classpath.; C: \ JavaTools \ Jack \ java; c: \ java \ lib \ classes.zip COM.sun.labs.jack.Основен парсер-input.jack 

Както можете да видите, това става малко по-дълго. За да сведем до минимум въвеждането, поставих извикването в .bat файл на име Jack.bat . В някакъв момент в бъдещето ще се появи проста програма за обвиване на C, може би дори докато четете това. Вижте началната страница на Jack за наличността на тази и други програми.

Когато стартирате Jack, той създава няколко файла в текущата директория, които по-късно ще компилирате във вашия парсер. Повечето са с префикс на името на вашия парсер или са общи за всички парсери. Един от тях обаче ASCII_CharStream.javaможе да се сблъска с други парсери, така че вероятно е добра идея да започнете в директория, съдържаща само файла .jack, който ще използвате, за да генерирате анализатора.

След като стартирате Джак, ако поколението е преминало гладко, ще имате куп .javaфайлове в текущата директория с различни интересни имена. Това са вашите парсери. Препоръчвам ви да ги отворите с редактор и да ги прегледате. Когато сте готови, можете да ги компилирате с командата

C:> javac -d. ParserName.java

къде ParserNameе името, което сте дали на вашия парсер във входния файл. Повече за това след малко. Ако всички файлове за вашия парсер не се компилират, можете да използвате метода на груба сила за въвеждане:

C:> javac * .java 

Това ще компилира всичко в директорията. На този етап вашият нов парсер е готов за използване.

Описания на анализатора на Джак

Jack parser description files have the extension .jack and are divided into three basic parts: options and base class; lexical tokens; and non-terminals. Let's look at a simple parser description (this is included in the examples directory that comes with Jack).

options { LOOKAHEAD = 1; } PARSER_BEGIN(Simple1) public class Simple1 { public static void main(String args[]) throws ParseError { Simple1 parser = new Simple1(System.in); parser.Input(); } } PARSER_END(Simple1) 

The first few lines above describe options for the parser; in this case LOOKAHEAD is set to 1. There are other options, such as diagnostics, Java Unicode handling, and so on, that also can be set here. Following the options comes the base class of the parser. The two tags PARSER_BEGIN and PARSER_END bracket the class that becomes the base Java code for the resulting parser. Note that the class name used in the parser specification must be the same in the beginning, middle, and ending part of this section. In the example above, I've put the class name in bold face to make this clear. As you can see in the code above, this class defines a static main method so that the class can be invoked by the Java interpreter on the command line. The main method simply instantiates a new parser with an input stream (in this case System.in) and then invokes the Input method. The Input method is a non-terminal in our grammar, and it is defined in the form of an EBNF element. EBNF stands for Extended Backus-Naur Form. The Backus-Naur form is a method for specifying context-free grammars. The specification consists of a terminal on the left-hand side, a production symbol, which is typically "::=", and one or more productions on the right-hand side. The notation used is typically something like this:

 Keyword ::= "if" | "then" | "else" 

This would be read as, "The Keyword terminal is one of the string literals 'if', 'then', or 'else.'" In Jack, this form is extended to allow the left-hand part to be represented by a method, and the alternate expansions may be represented by regular expressions or other non-terminals. Continuing with our simple example, the file contains the following definitions:

void Input() : {} { MatchedBraces() "\n"  } void MatchedBraces() : {} { "{" [ MatchedBraces() ] "}" } 

This simple parser parses the grammar shown below:

Input ::= MatchedBraces "\n"
MatchedBraces ::= "{" [ MatchedBraces ] "}"

I've used italics to show the non-terminals on the right side of the productions and boldface to show literals. As you can see, the grammar simply parses matched sets of brace "{" and "}" characters. There are two productions in the Jack file to describe this grammar. The first terminal, Input, is defined by this definition to be three items in sequence: a MatchedBraces terminal, a newline character, and an end-of-file token. The token is defined by Jack so that you don't have to specify it for your platform.

When this grammar is generated, the left-hand sides of the productions are turned into methods inside the Simple1 class; when compiled, the Simple1 class reads characters from System.in and verifies that they contain a matching set of braces. This is accomplished by invoking the generated method Input, which is transformed by the generation process into a method that parses an Input non-terminal. If the parse fails, the method throws the exception ParseError, which the main routine can catch and then complain about if it so chooses.

Of course there's more. The block delineated by "{" and "}" after the terminal name -- which is empty in this example -- can contain arbitrary Java code that is inserted at the front of the generated method. Then, after each expansion, there is another optional block that can contain arbitrary Java code to be executed when the parser successfully matches that expansion.

A more complicated example

So how about an example that's a bit more complicated? Consider the following grammar, again broken down into pieces. This grammar is designed to interpret mathematical equations using the four basic operators -- addition, multiplication, subtraction, and division. The source can be found here:

options { LOOKAHEAD=1; } PARSER_BEGIN(Calc1) public class Calc1 { public static void main(String args[]) throws ParseError { Calc1 parser = new Calc1(System.in); while (true) { System.out.print("Enter Expression: "); System.out.flush(); try { switch (parser.one_line()) { case -1: System.exit(0); default: break; } } catch (ParseError x) { System.out.println("Exiting."); throw x; } } } } PARSER_END(Calc1) 

The first part is nearly the same as Simple1, except that the main routine now calls the terminal one_line repeatedly until it fails to parse. Next comes the following code:

IGNORE_IN_BNF : {}  " "  TOKEN : { } {  } TOKEN : /* OPERATORS */ { }    TOKEN : { }    

Тези определения обхващат основните терминали, в които е посочена граматиката. Първият, наречен IGNORE_IN_BNF , е специален знак. Всички токени, прочетени от анализатора, които съответстват на символите, дефинирани в IGNORE_IN_BNF маркер, се изхвърлят мълчаливо. Както можете да видите в нашия пример, това води до това, че анализаторът пренебрегва интервалите, раздели и символи за връщане на карета във входа.