Comment créer un interpréteur en Java, Partie 1: Les BASIC

Quand j'ai dit à un ami que j'avais écrit à un interprète BASIC en Java, il a ri si fort qu'il a failli renverser le soda qu'il tenait sur ses vêtements. "Pourquoi diable construiriez-vous un interpréteur BASIC en Java?" était la première question prévisible de sa bouche. La réponse est à la fois simple et complexe. La réponse simple est que c'était amusant d'écrire un interpréteur en Java, et si j'allais écrire un interprète, je pourrais aussi bien en écrire un dont j'ai de bons souvenirs des débuts de l'informatique personnelle. Du côté complexe, j'ai remarqué que de nombreuses personnes utilisant Java aujourd'hui ont dépassé le point de créer des applets Duke tumbling et se tournent vers des applications sérieuses. Souvent, lors de la création d'une application, vous souhaitez qu'elle soit configurable.Le mécanisme de choix pour la reconfiguration est une sorte de moteur d'exécution dynamique.

Connu sous le nom de macro langages, ou langages de configuration, l'exécution dynamique est la fonction qui permet à une application d'être "programmée" par l'utilisateur. L'avantage d'avoir un moteur d'exécution dynamique est que les outils et les applications peuvent être personnalisés pour effectuer des tâches complexes sans remplacer l'outil. La plate-forme Java offre une grande variété d'options de moteur d'exécution dynamique.

HotJava et autres options chaudes

Explorons brièvement certaines des options du moteur d'exécution dynamique disponibles, puis examinons en profondeur l'implémentation de mon interpréteur. Un moteur d'exécution dynamique est un interpréteur intégré. Un interprète a besoin de trois installations pour fonctionner:

  1. Un moyen d'être chargé d'instructions
  2. Un format de module, pour stocker les instructions à exécuter
  3. Un modèle ou un environnement pour interagir avec le programme hôte

HotJava

L'interpréteur intégré le plus connu doit être l'environnement «applet» HotJava qui a complètement remodelé la façon dont les gens regardent les navigateurs Web.

Le modèle «applet» HotJava était basé sur l'idée qu'une application Java pouvait créer une classe de base générique avec une interface connue, puis charger dynamiquement les sous-classes de cette classe et les exécuter au moment de l'exécution. Ces applets offraient de nouvelles fonctionnalités et, dans les limites de la classe de base, permettaient une exécution dynamique. Cette capacité d'exécution dynamique est un élément fondamental de l'environnement Java et l'une des choses qui le rend si spécial. Nous examinerons cet environnement en détail dans une colonne ultérieure.

GNU EMACS

Avant l'arrivée de HotJava, l'application la plus réussie avec une exécution dynamique était peut-être GNU EMACS. Le langage macro de type LISP de cet éditeur est devenu un incontournable pour de nombreux programmeurs. En bref, l'environnement EMACS LISP se compose d'un interpréteur LISP et de nombreuses fonctions de type édition permettant de composer les macros les plus complexes. Il n'est pas surprenant que l'éditeur EMACS ait été initialement écrit dans des macros conçues pour un éditeur appelé TECO. Ainsi, la disponibilité d'un macro langage riche (si illisible) dans TECO a permis de construire un éditeur entièrement nouveau. Aujourd'hui, GNU EMACS est l'éditeur de base, et des jeux entiers n'ont été écrits que dans le code EMACS LISP, connu sous le nom de el-code. Cette capacité de configuration a fait de GNU EMACS un éditeur incontournable,tandis que les terminaux VT-100 sur lesquels il était conçu pour fonctionner sont devenus de simples notes de bas de page dans la colonne d'un écrivain.

REXX

L'un de mes langages préférés, qui n'a jamais vraiment fait le bruit qu'il méritait, était REXX, conçu par Mike Cowlishaw d'IBM. L'entreprise avait besoin d'un langage pour contrôler les applications sur de grands mainframes exécutant le système d'exploitation VM. J'ai découvert REXX sur l'Amiga où il était étroitement associé à une grande variété d'applications via les «ports REXX». Ces ports permettaient aux applications d'être pilotées à distance via l'interpréteur REXX. Ce couplage d'interprète et d'application a créé un système beaucoup plus puissant qu'il n'était possible avec ses composants. Heureusement, le langage vit dans NETREXX, une version écrite par Mike qui a été compilée en code Java.

Alors que je regardais NETREXX et un langage beaucoup plus ancien (LISP en Java), j'ai été frappé par le fait que ces langages constituaient des parties importantes de l'histoire de l'application Java. Quelle meilleure façon de raconter cette partie de l'histoire que de faire quelque chose d'amusant ici - comme ressusciter BASIC-80? Plus important encore, il serait utile de montrer une manière dont les langages de script peuvent être écrits en Java et, grâce à leur intégration avec Java, de montrer comment ils peuvent améliorer les capacités de vos applications Java.

Exigences de BASE pour améliorer vos applications Java

BASIC est, tout simplement, un langage de base. Il y a deux écoles de pensée sur la façon dont on pourrait y écrire un interprète. Une approche consiste à écrire une boucle de programmation dans laquelle le programme d'interprétation lit une ligne de texte à partir du programme interprété, l'analyse, puis appelle un sous-programme pour l'exécuter. La séquence de lecture, d'analyse et d'exécution est répétée jusqu'à ce que l'une des instructions du programme interprété dise à l'interpréteur de s'arrêter.

La deuxième manière, et bien plus intéressante, d'aborder le projet est d'analyser le langage dans un arbre d'analyse, puis d'exécuter l'arbre d'analyse «sur place». C'est ainsi que fonctionnent les interprètes tokenizing et la façon dont j'ai choisi de procéder. Les interprètes de tokenisation sont également plus rapides car ils n'ont pas besoin de réexaminer l'entrée chaque fois qu'ils exécutent une instruction.

Comme je l'ai mentionné ci-dessus, les trois composants nécessaires pour réaliser une exécution dynamique sont un moyen d'être chargé, un format de module et l'environnement d'exécution.

Le premier composant, moyen d'être chargé, sera pris en charge par un Java InputStream. Comme les flux d'entrée sont fondamentaux dans l'architecture d'E / S de Java, le système est conçu pour lire un programme à partir d'un InputStreamet le convertir en une forme exécutable. Cela représente une manière très flexible d'introduire du code dans le système. Bien entendu, le protocole pour les données passant par le flux d'entrée sera le code source BASIC. Il est important de noter que n'importe quelle langue peut être utilisée; ne faites pas l'erreur de penser que cette technique ne peut pas être appliquée à votre application.

Une fois que le code source du programme interprété est entré dans le système, le système convertit le code source en une représentation interne. J'ai choisi d'utiliser l'arborescence d'analyse comme format de représentation interne pour ce projet. Une fois l'arborescence d'analyse créée, elle peut être manipulée ou exécutée.

Le troisième composant est l'environnement d'exécution. Comme nous le verrons, les exigences pour ce composant sont assez simples, mais l'implémentation présente quelques rebondissements intéressants.

Un tour de base très rapide

Pour ceux d'entre vous qui n'ont peut-être jamais entendu parler de BASIC, je vais vous donner un bref aperçu du langage, afin que vous puissiez comprendre les défis d'analyse et d'exécution à venir. Pour plus d'informations sur BASIC, je recommande vivement les ressources à la fin de cette colonne.

BASIC signifie Beginners All-purpose Symbolic Instructional Code, et il a été développé à l'Université de Dartmouth pour enseigner les concepts de calcul aux étudiants de premier cycle. Depuis son développement, BASIC a évolué vers une variété de dialectes. Les plus simples de ces dialectes sont utilisés comme langages de contrôle pour les contrôleurs de processus industriels; les dialectes les plus complexes sont des langages structurés qui intègrent certains aspects de la programmation orientée objet. Pour mon projet, j'ai choisi un dialecte appelé BASIC-80 qui était populaire sur le système d'exploitation CP / M à la fin des années soixante-dix. Ce dialecte n'est que modérément plus complexe que les dialectes les plus simples.

Syntaxe de l'instruction

Toutes les lignes de relevé sont de la forme

[: [: ...]]

where "Line" is a statement line number, "Keyword" is a BASIC statement keyword, and "Parameters" are a set of parameters associated with that keyword.

The line number has two purposes: It serves as a label for statements that control execution flow, such as a goto statement, and it serves as a sorting tag for statements inserted into the program. As a sorting tag, the line number facilitates a line editing environment in which editing and command processing are mixed in a single interactive session. By the way, this was required when all you had was a teletype. :-)

While not very elegant, line numbers do give the interpreter environment the ability to update the program one statement at a time. This ability stems from the fact that a statement is a single parsed entity and can be linked in a data structure with line numbers. Without line numbers, often it is necessary to re-parse the entire program when a line changes.

The keyword identifies the BASIC statement. In the example, our interpreter will support a slightly extended set of BASIC keywords, including goto, gosub, return, print, if, end, data, restore, read, on, rem, for, next, let, input, stop, dim, randomize, tron, and troff. Obviously, we won't go over all of these in this article, but there will be some documentation online in my next month's "Java In Depth" for you to explore.

Each keyword has a set of legal keyword parameters that can follow it. For example, the goto keyword must be followed by a line number, the if statement must be followed by a conditional expression as well as the keyword then -- and so on. The parameters are specific to each keyword. I'll cover a couple of these parameter lists in detail a bit later.

Expressions and operators

Often, a parameter specified in a statement is an expression. The version of BASIC I'm using here supports all of the standard mathematical operations, logical operations, exponentiation, and a simple function library. The most important component of the expression grammar is the ability to call functions. The expressions themselves are fairly standard and similar to the ones parsed by the example in my previous StreamTokenizer column.

Variables and data types

Part of the reason BASIC is such a simple language is because it has only two data types: numbers and strings. Some scripting languages, such as REXX and PERL, don't even make this distinction between data types until they are used. But with BASIC, a simple syntax is used to identify data types.

Variable names in this version of BASIC are strings of letters and numbers that always start with a letter. Variables are not case-sensitive. Thus A, B, FOO, and FOO2 are all valid variable names. Furthermore, in BASIC, the variable FOOBAR is equivalent to FooBar. To identify strings, a dollar sign ($) is appended to the variable name; thus, the variable FOO$ is a variable containing a string.

Finally, this version of the language supports arrays using the dim keyword and a variable syntax of the form NAME(index1, index2, ...) for up to four indices.

Program structure

Programs in BASIC start by default at the lowest numbered line and continue until there are either no more lines to process or the stop or end keywords are executed. A very simple BASIC program is shown below:

100 REM This is probably the canonical BASIC example 110 REM Program. Note that REM statements are ignored. 120 PRINT "This is a test program." 130 PRINT "Summing the values between 1 and 100" 140 LET total = 0 150 FOR I = 1 TO 100 160 LET total = total + i 170 NEXT I 180 PRINT "The total of all digits between 1 and 100 is " total 190 END 

The line numbers above indicate the lexical order of the statements. When they are run, lines 120 and 130 print messages to the output, line 140 initializes a variable, and the loop in lines 150 through 170 update the value of that variable. Finally, the results are printed out. As you can see, BASIC is a very simple programming language and therefore an ideal candidate for teaching computation concepts.

Organizing the approach

Typical of scripting languages, BASIC involves a program composed of many statements that run in a particular environment. The design challenge, then, is to construct the objects to implement such a system in a useful way.

When I looked at the problem, a straightforward data structure fairly leaped out at me. That structure is as follows:

The public interface to the scripting language shall consist of

  • A factory method that takes source code as input and returns an object representing the program.
  • An environment that provides the framework in which the program executes, including "I/O" devices for text input and text output.
  • A standard way of modifying that object, perhaps in the form of an interface, that allows the program and the environment to be combined to achieve useful results.

Internally, the structure of the interpreter was a bit more complicated. The question was how to go about factoring the two facets of the scripting language, parsing and execution? Three groups of classes resulted -- one for parsing, one for the structural framework of representing parsed and executable programs, and one that formed the base environment class for execution.

In the parsing group, the following objects are required:

  • Analyse lexicale pour traiter le code sous forme de texte
  • Analyse d'expressions, pour construire des arbres d'analyse des expressions
  • Analyse des instructions, pour construire des arbres d'analyse des instructions elles-mêmes
  • Classes d'erreur pour signaler des erreurs lors de l'analyse

Le groupe de structure se compose d'objets qui contiennent les arbres d'analyse et les variables. Ceux-ci inclus:

  • Un objet instruction avec de nombreuses sous-classes spécialisées pour représenter des instructions analysées
  • Un objet expression pour représenter des expressions à évaluer
  • Un objet variable avec de nombreuses sous-classes spécialisées pour représenter des instances atomiques de données