Come costruire un interprete in Java, Parte 1: I BASIC

Quando ho detto a un amico che avevo scritto un interprete BASIC in Java, ha riso così forte che ha quasi versato la soda che teneva sui suoi vestiti. "Perché diavolo costruiresti un interprete BASIC in Java?" fu la prevedibile prima domanda che uscì dalla sua bocca. La risposta è sia semplice che complessa. La semplice risposta è che è stato divertente scrivere un interprete in Java, e se avessi intenzione di scrivere un interprete, tanto vale scriverne uno di cui ho bei ricordi sin dai primi giorni del personal computer. Sul lato complesso, ho notato che molte persone che usano Java oggi hanno superato il punto di creare applet Duke cadenti e stanno passando ad applicazioni serie. Spesso, durante la creazione di un'applicazione, vorresti che fosse configurabile.Il meccanismo di scelta per la riconfigurazione è una sorta di motore di esecuzione dinamico.

Conosciuti come linguaggi macro, o linguaggi di configurazione, l'esecuzione dinamica è la caratteristica che consente di "programmare" un'applicazione da parte dell'utente. Il vantaggio di avere un motore di esecuzione dinamico è che gli strumenti e le applicazioni possono essere personalizzati per eseguire attività complesse senza sostituire lo strumento. La piattaforma Java offre un'ampia varietà di opzioni del motore di esecuzione dinamico.

HotJava e altre opzioni calde

Esploriamo brevemente alcune delle opzioni disponibili del motore di esecuzione dinamico e quindi esaminiamo in profondità l'implementazione del mio interprete. Un motore di esecuzione dinamico è un interprete incorporato. Un interprete necessita di tre strutture per poter operare:

  1. Un mezzo per caricare le istruzioni
  2. Un formato modulo, per memorizzare le istruzioni da eseguire
  3. Un modello o un ambiente per interagire con il programma host

HotJava

L'interprete incorporato più famoso deve essere l'ambiente "applet" di HotJava che ha completamente rimodellato il modo in cui le persone guardano ai browser Web.

Il modello di "applet" HotJava era basato sull'idea che un'applicazione Java potesse creare una classe base generica con un'interfaccia nota, quindi caricare dinamicamente le sottoclassi di quella classe ed eseguirle in fase di esecuzione. Queste applet fornivano nuove funzionalità e, entro i confini della classe base, fornivano un'esecuzione dinamica. Questa capacità di esecuzione dinamica è una parte fondamentale dell'ambiente Java e una delle cose che lo rende così speciale. Esamineremo questo particolare ambiente in modo approfondito in una colonna successiva.

GNU EMACS

Prima dell'arrivo di HotJava, forse l'applicazione di maggior successo con l'esecuzione dinamica era GNU EMACS. Il linguaggio macro simile a LISP di questo editor è diventato un punto fermo per molti programmatori. In breve, l'ambiente EMACS LISP è costituito da un interprete LISP e molte funzioni di tipo editing che possono essere utilizzate per comporre le macro più complesse. Non dovrebbe essere considerato sorprendente che l'editor EMACS originariamente fosse scritto in macro progettate per un editor chiamato TECO. Pertanto, la disponibilità di un linguaggio macro ricco (se illeggibile) in TECO ha permesso di costruire un editor completamente nuovo. Oggi, GNU EMACS è l'editor di base e interi giochi sono stati scritti solo con il codice EMACS LISP, noto come el-code. Questa capacità di configurazione ha reso GNU EMACS un editor principale,mentre i terminali VT-100 su cui è stato progettato per funzionare sono diventati semplici note a piè di pagina nella colonna di uno scrittore.

REXX

Uno dei miei linguaggi preferiti, che non ha mai avuto il successo che meritava, era REXX, progettato da Mike Cowlishaw di IBM. L'azienda aveva bisogno di un linguaggio per controllare le applicazioni su mainframe di grandi dimensioni che eseguivano il sistema operativo VM. Ho scoperto REXX su Amiga, dove era strettamente accoppiato con un'ampia varietà di applicazioni tramite "porte REXX". Queste porte consentivano alle applicazioni di essere comandate in remoto tramite l'interprete REXX. Questo accoppiamento di interprete e applicazione ha creato un sistema molto più potente di quanto fosse possibile con le sue parti componenti. Fortunatamente, il linguaggio vive in NETREXX, una versione scritta da Mike che è stata compilata in codice Java.

Mentre stavo guardando NETREXX e un linguaggio molto precedente (LISP in Java), mi ha colpito che questi linguaggi formassero parti importanti della storia dell'applicazione Java. Quale modo migliore per raccontare questa parte della storia che fare qualcosa di divertente qui, come resuscitare il BASIC-80? Ancora più importante, sarebbe utile mostrare un modo in cui i linguaggi di scripting possono essere scritti in Java e, attraverso la loro integrazione con Java, mostrare come possono migliorare le capacità delle vostre applicazioni Java.

Requisiti BASIC per migliorare le tue app Java

BASIC è, molto semplicemente, un linguaggio di base. Ci sono due scuole di pensiero su come si potrebbe scrivere un interprete per questo. Un approccio consiste nello scrivere un ciclo di programmazione in cui il programma interprete legge una riga di testo dal programma interpretato, la analizza e quindi chiama una subroutine per eseguirla. La sequenza di lettura, analisi ed esecuzione viene ripetuta fino a quando una delle istruzioni del programma interpretato dice all'interprete di fermarsi.

Il secondo e molto più interessante modo per affrontare il progetto in realtà è analizzare la lingua in un albero di analisi e quindi eseguire l'albero di analisi "sul posto". Questo è il modo in cui operano gli interpreti di tokenizzazione e il modo in cui ho scelto di procedere. Gli interpreti di tokenizzazione sono anche più veloci in quanto non hanno bisogno di rieseguire la scansione dell'input ogni volta che eseguono un'istruzione.

Come accennato in precedenza, i tre componenti necessari per ottenere l'esecuzione dinamica sono un mezzo per essere caricati, un formato di modulo e l'ambiente di esecuzione.

Il primo componente, un mezzo per essere caricato, sarà gestito da un Java InputStream. Poiché i flussi di input sono fondamentali nell'architettura I / O di Java, il sistema è progettato per leggere un programma da un InputStreame convertirlo in un formato eseguibile. Questo rappresenta un modo molto flessibile per inserire il codice nel sistema. Ovviamente, il protocollo per i dati che passano attraverso il flusso di input sarà il codice sorgente BASIC. È importante notare che è possibile utilizzare qualsiasi lingua; non commettere l'errore di pensare che questa tecnica non possa essere applicata alla tua applicazione.

Dopo che il codice sorgente del programma interpretato è stato inserito nel sistema, il sistema converte il codice sorgente in una rappresentazione interna. Ho scelto di utilizzare l'albero di analisi come formato di rappresentazione interna per questo progetto. Una volta che l'albero di analisi è stato creato, può essere manipolato o eseguito.

Il terzo componente è l'ambiente di esecuzione. Come vedremo, i requisiti per questo componente sono abbastanza semplici, ma l'implementazione ha un paio di interessanti colpi di scena.

Un tour BASIC molto veloce

Per quelli di voi che potrebbero non aver mai sentito parlare di BASIC, vi darò un breve assaggio del linguaggio, in modo che possiate capire le sfide di analisi ed esecuzione future. Per ulteriori informazioni su BASIC, consiglio vivamente le risorse alla fine di questa colonna.

BASIC sta per Beginners All-purpose Symbolic Instructional Code, ed è stato sviluppato presso la Dartmouth University per insegnare concetti di calcolo agli studenti universitari. Dal suo sviluppo, BASIC si è evoluto in una varietà di dialetti. I più semplici di questi dialetti sono usati come linguaggi di controllo per i controllori di processo industriale; i dialetti più complessi sono linguaggi strutturati che incorporano alcuni aspetti della programmazione orientata agli oggetti. Per il mio progetto, ho scelto un dialetto noto come BASIC-80 che era popolare nel sistema operativo CP / M alla fine degli anni settanta. Questo dialetto è solo moderatamente più complesso dei dialetti più semplici.

Sintassi dell'istruzione

Tutte le righe dell'istruzione hanno la forma

[: [: ...]]

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:

  • Analisi lessicale per l'elaborazione del codice come testo
  • Analisi delle espressioni, per costruire alberi di analisi delle espressioni
  • Analisi delle istruzioni, per costruire alberi di analisi delle istruzioni stesse
  • Classi di errore per la segnalazione di errori durante l'analisi

Il gruppo framework è costituito da oggetti che contengono gli alberi di analisi e le variabili. Questi includono:

  • Un oggetto istruzione con molte sottoclassi specializzate per rappresentare istruzioni analizzate
  • Un oggetto espressione per rappresentare espressioni per la valutazione
  • Un oggetto variabile con molte sottoclassi specializzate per rappresentare istanze atomiche di dati