Vous recherchez lex et yacc pour Java? Tu ne connais pas Jack

Sun a publié Jack, un nouvel outil écrit en Java qui génère automatiquement des analyseurs en compilant une spécification grammaticale de haut niveau stockée dans un fichier texte. Cet article servira d'introduction à ce nouvel outil. La première partie de l'article couvre une brève introduction à la génération d'analyseurs automatiques et mes premières expériences avec eux. Ensuite, l'article se concentrera sur Jack et comment vous pouvez l'utiliser pour générer des analyseurs et des applications construits avec ces analyseurs, en fonction de votre grammaire de haut niveau.

Génération automatique d'analyseur de compilateur

Un analyseur est l'un des composants les plus courants d'une application informatique. Il convertit le texte qui peut être lu par les humains en structures de données appelées arbres d'analyse, qui sont compris par l'ordinateur. Je me souviens distinctement de mon introduction à la génération d'analyseurs automatiques: au collège, j'avais terminé un cours sur la construction de compilateurs. Avec l'aide de ma future épouse, j'avais écrit un compilateur simple qui pouvait transformer des programmes écrits dans un langage conçu pour la classe en programmes exécutables. Je me souviens m'être senti très accompli à ce moment-là.

Dans mon premier "vrai" travail après l'université, j'ai eu la mission de créer un nouveau langage de traitement graphique à compiler en commandes pour un coprocesseur graphique. J'ai commencé avec une grammaire fraîchement composée et je me suis préparé à me lancer dans le projet de plusieurs semaines consistant à assembler un compilateur. Puis un ami m'a montré les utilitaires Unix lex et yacc . Lex a construit des analyseurs lexicaux à partir d'expressions régulières, et yacc a réduit une spécification grammaticale en un compilateur basé sur des tables qui pouvait produire du code lorsqu'il avait analysé avec succès les productions de cette grammaire. J'ai utilisé lex et yacc, et en moins d'une semaine, mon compilateur était opérationnel! Plus tard, le projet GNU de la Free Software Foundation a produit des versions "améliorées" de lex et yacc - appelées flex et bison - pour une utilisation sur des plates-formes qui n'exécutaient pas un dérivé du système d'exploitation Unix.

Le monde de la génération d'analyseurs automatiques a de nouveau progressé lorsque Terrence Parr, alors étudiant à l'Université Purdue, a créé le Purdue Compiler Construction Tool Set ou PCCTS. Deux composants de PCCTS - DFA et ANTLR - fournissent les mêmes fonctions que lex et yacc ; cependant les grammaires acceptées par ANTLR sont des grammaires LL (k) par opposition aux grammaires LALR utilisées par yacc . De plus, le code généré par PCCTS est beaucoup plus lisible que le code généré par yacc. En générant un code plus facile à lire, PCCTS permet à un humain de lire le code plus facilement pour comprendre ce que font les différentes pièces. Cette compréhension peut être essentielle lorsque vous essayez de diagnostiquer des erreurs dans la spécification grammaticale. PCCTS a rapidement développé un groupe de personnes qui ont trouvé ses fichiers plus faciles à utiliser que yacc.

La puissance de la génération d'analyseur automatique est qu'elle permet aux utilisateurs de se concentrer sur la grammaire et de ne pas se soucier de l'exactitude de l'implémentation. Cela peut être un gain de temps considérable dans les projets simples et complexes.

Jack s'approche de l'assiette

J'évalue les outils en fonction de la généralité du problème qu'ils résolvent. Comme l'exigence d'analyser la saisie de texte revient encore et encore, la génération automatique d'analyseur parseur est assez élevée dans ma boîte à outils. Combinée au cycle de développement rapide de Java, la génération d'analyseur automatique fournit un outil de conception de compilateur difficile à battre.

Jack (rime avec yacc) est un générateur d'analyseurs, dans l'esprit PCCTS, que Sun a publié gratuitement pour la communauté de programmation Java. Jack est un outil exceptionnellement facile à décrire: en termes simples, vous lui donnez un ensemble de règles grammaticales et de lexing combinées sous la forme d'un fichier .jack et exécutez l'outil, et il vous rend une classe Java qui analysera cette grammaire. Qu'est-ce qui pourrait être plus facile?

Obtenir Jack est également assez facile. Commencez par télécharger une copie depuis la page d'accueil de Jack. Cela vous vient sous la forme d'une classe Java à décompression automatique appelée install. Pour installer Jack vous devez appeler cette installclasse, qui, sur une machine Windows 95 est effectuée à l' aide de la commande: C:>java install.

La commande illustrée ci-dessus suppose que la javacommande se trouve dans votre chemin de commande et que le chemin de classe a été configuré de manière appropriée. Si la commande ci-dessus n'a pas fonctionné ou si vous ne savez pas si les choses sont correctement configurées, ouvrez une fenêtre MS-DOS en parcourant les éléments de menu Démarrer-> Programmes-> Invite MS-DOS. Si Sun JDK est installé, vous pouvez saisir ces commandes:

C:> chemin C: \ java \ bin;% chemin% C:> set CLASSPATH = .; c: \ java \ lib \ classes.zip 

Si Symantec Cafe version 1.2 ou ultérieure est installé, vous pouvez taper ces commandes:

C:> chemin C: \ cafe \ java \ bin;% chemin% 

Le chemin de classe doit déjà être configuré dans un fichier appelé sc.ini dans le répertoire bin de Cafe.

Ensuite, tapez la java installcommande ci-dessus. Le programme d'installation vous demandera dans quel répertoire vous souhaitez installer, et le sous-répertoire Jack sera créé en dessous.

Utilisation de Jack

Jack est entièrement écrit en Java, donc avoir les classes Jack signifie que cet outil est instantanément disponible sur toutes les plateformes prenant en charge la machine virtuelle Java. Cependant, cela signifie également que sur les boîtes Windows, vous devez exécuter Jack à partir de la ligne de commande. Disons que vous avez choisi le nom de répertoire JavaTools lorsque vous avez installé Jack sur votre système. Pour utiliser Jack, vous devrez ajouter les classes de Jack à votre chemin de classe. Vous pouvez le faire dans votre fichier autoexec.bat ou dans votre fichier .cshrc si vous êtes un utilisateur Unix. La commande critique est quelque chose comme la ligne ci-dessous:

C:> set CLASSPATH = .; C: \ JavaTools \ Jack \ java; C: \ java \ lib \ classes.zip 

Notez que les utilisateurs de Symantec Cafe peuvent modifier le fichier sc.ini et y inclure les classes Jack, ou ils peuvent définir CLASSPATHexplicitement comme indiqué ci-dessus.

La définition de la variable d'environnement comme indiqué ci-dessus place les classes Jack CLASSPATHentre "." (le répertoire courant) et les classes système de base pour Java. La classe principale pour Jack est COM.sun.labs.jack.Main. La capitalisation est importante! Il y a exactement quatre lettres majuscules dans la commande («C», «O», «M» et un autre «M»). Pour exécuter Jack manuellement, tapez la commande:

C:> java COM.sun.labs.jack.Main parser-input.jack

Si vous n'avez pas les fichiers Jack dans votre chemin de classe, vous pouvez utiliser cette commande:

C:> java -classpath.; C: \ JavaTools \ Jack \ java; c: \ java \ lib \ classes.zip COM.sun.labs.jack.Main parser-input.jack 

Comme vous pouvez le voir, cela devient un peu long. Pour minimiser la saisie, j'ai mis l'invocation dans un fichier .bat nommé Jack.bat . À un moment donné dans le futur, un simple programme wrapper C deviendra disponible, peut-être même lorsque vous lirez ceci. Consultez la page d'accueil de Jack pour connaître la disponibilité de ce programme et d'autres programmes.

Lorsque Jack est lancé, il crée plusieurs fichiers dans le répertoire courant que vous compilerez plus tard dans votre analyseur. La plupart sont soit préfixés par le nom de votre analyseur, soit communs à tous les analyseurs. L'un d'eux, cependant, ASCII_CharStream.javapeut entrer en collision avec d'autres analyseurs, c'est donc probablement une bonne idée de commencer dans un répertoire contenant uniquement le fichier .jack que vous allez utiliser pour générer l'analyseur.

Une fois que vous exécutez Jack, si la génération s'est bien déroulée, vous aurez un tas de .javafichiers dans le répertoire actuel avec divers noms intéressants. Ce sont vos analyseurs. Je vous encourage à les ouvrir avec un éditeur et à les examiner. Lorsque vous êtes prêt, vous pouvez les compiler avec la commande

C:> javac -d. ParserName.java

ParserNameest le nom que vous avez donné à votre analyseur dans le fichier d'entrée. Plus à ce sujet dans un instant. Si tous les fichiers de votre analyseur ne sont pas compilés, vous pouvez utiliser la méthode de frappe par force brute:

C:> javac * .java 

Cela compilera tout dans le répertoire. À ce stade, votre nouvel analyseur est prêt à être utilisé.

Descriptions de l'analyseur Jack

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 : { }    

Ces définitions couvrent les terminaux de base dans lesquels la grammaire est spécifiée. Le premier, nommé IGNORE_IN_BNF , est un jeton spécial. Tous les jetons lus par l'analyseur qui correspondent aux caractères définis dans un jeton IGNORE_IN_BNF sont supprimés en silence. Comme vous pouvez le voir dans notre exemple, cela oblige l'analyseur à ignorer les caractères d'espacement, les tabulations et les caractères de retour chariot dans l'entrée.