Cómo construir un intérprete en Java, Parte 1: Los BÁSICOS

Cuando le dije a un amigo que había escrito a un intérprete de BASIC en Java, se rió tanto que casi derrama el refresco que tenía en la ropa. "¿Por qué demonios construirías un intérprete BASIC en Java?" fue la predecible primera pregunta que salió de su boca. La respuesta es simple y compleja. La respuesta simple es que fue divertido escribir un intérprete en Java, y si fuera a escribir un intérprete, también podría escribir uno sobre el que tenga buenos recuerdos de los primeros días de la informática personal. En el lado complejo, me he dado cuenta de que muchas personas que usan Java hoy en día han superado el punto de crear subprogramas de Duke y están pasando a aplicaciones serias. A menudo, al crear una aplicación, le gustaría que fuera configurable.El mecanismo de elección para la reconfiguración es una especie de motor de ejecución dinámica.

Conocida como lenguajes de macro, o lenguajes de configuración, la ejecución dinámica es la característica que permite que el usuario "programe" una aplicación. El beneficio de tener un motor de ejecución dinámico es que las herramientas y aplicaciones se pueden personalizar para realizar tareas complejas sin reemplazar la herramienta. La plataforma Java ofrece una amplia variedad de opciones de motor de ejecución dinámica.

HotJava y otras opciones calientes

Exploremos brevemente algunas de las opciones del motor de ejecución dinámica disponibles y luego veamos la implementación de mi intérprete en profundidad. Un motor de ejecución dinámica es un intérprete integrado. Un intérprete requiere tres instalaciones para funcionar:

  1. Un medio para cargar con instrucciones.
  2. Un formato de módulo, para almacenar instrucciones a ejecutar
  3. Un modelo o entorno para interactuar con el programa anfitrión.

HotJava

El intérprete integrado más famoso tiene que ser el entorno de "applet" de HotJava, que ha remodelado por completo la forma en que la gente ve los navegadores web.

El modelo de "applet" de HotJava se basaba en la noción de que una aplicación Java podía crear una clase base genérica con una interfaz conocida y luego cargar dinámicamente subclases de esa clase y ejecutarlas en tiempo de ejecución. Estos subprogramas proporcionaron nuevas capacidades y, dentro de los límites de la clase base, proporcionaron ejecución dinámica. Esta capacidad de ejecución dinámica es una parte fundamental del entorno Java y una de las cosas que lo hace tan especial. Veremos este entorno particular en profundidad en una columna posterior.

GNU EMACS

Antes de que llegara HotJava, quizás la aplicación más exitosa con ejecución dinámica era GNU EMACS. El lenguaje de macros similar a LISP de este editor se ha convertido en un elemento básico para muchos programadores. En resumen, el entorno EMACS LISP consta de un intérprete LISP y muchas funciones de tipo edición que se pueden utilizar para componer las macros más complejas. No debe considerarse sorprendente que el editor EMACS originalmente se escribiera en macros diseñadas para un editor llamado TECO. Por lo tanto, la disponibilidad de un lenguaje de macros rico (aunque ilegible) en TECO permitió la construcción de un editor completamente nuevo. En la actualidad, GNU EMACS es el editor base y los juegos completos se han escrito en nada más que el código EMACS LISP, conocido como el-code. Esta capacidad de configuración ha convertido a GNU EMACS en un editor principal,mientras que los terminales VT-100 para los que fue diseñado se han convertido en meras notas al pie de la columna de un escritor.

REXX

Uno de mis lenguajes favoritos, que nunca causó el impacto que merecía, fue REXX, diseñado por Mike Cowlishaw de IBM. La empresa necesitaba un lenguaje para controlar aplicaciones en grandes mainframes que ejecutaban el sistema operativo VM. Descubrí REXX en el Amiga donde estaba estrechamente acoplado con una amplia variedad de aplicaciones a través de "puertos REXX". Estos puertos permitían que las aplicaciones se manejaran de forma remota a través del intérprete REXX. Esta combinación de intérprete y aplicación creó un sistema mucho más poderoso de lo que era posible con sus componentes. Afortunadamente, el lenguaje sigue vivo en NETREXX, una versión que Mike escribió y que fue compilada en código Java.

Mientras miraba NETREXX y un lenguaje mucho anterior (LISP en Java), me sorprendió que estos lenguajes formaran partes importantes de la historia de la aplicación Java. ¿Qué mejor manera de contar esta parte de la historia que hacer algo divertido aquí, como resucitar BASIC-80? Más importante aún, sería útil mostrar una forma en que los lenguajes de scripting se pueden escribir en Java y, a través de su integración con Java, mostrar cómo pueden mejorar las capacidades de sus aplicaciones Java.

Requisitos BÁSICOS para mejorar sus aplicaciones Java

BASIC es, simplemente, un lenguaje básico. Hay dos escuelas de pensamiento sobre cómo se puede escribir un intérprete para él. Un enfoque consiste en escribir un ciclo de programación en el que el programa intérprete lee una línea de texto del programa interpretado, lo analiza y luego llama a una subrutina para ejecutarlo. La secuencia de lectura, análisis y ejecución se repite hasta que una de las declaraciones del programa interpretado le dice al intérprete que se detenga.

La segunda y mucho más interesante forma de abordar el proyecto en realidad es analizar el lenguaje en un árbol de análisis y luego ejecutar el árbol de análisis "en su lugar". Así es como operan los intérpretes de tokenización y la forma en que elegí proceder. Los intérpretes de tokenización también son más rápidos ya que no necesitan volver a escanear la entrada cada vez que ejecutan una declaración.

Como mencioné anteriormente, los tres componentes necesarios para lograr la ejecución dinámica son un medio de carga, un formato de módulo y el entorno de ejecución.

El primer componente, un medio de carga, será tratado por un Java InputStream. Como los flujos de entrada son fundamentales en la arquitectura de E / S de Java, el sistema está diseñado para leer en un programa InputStreamy convertirlo en un formato ejecutable. Esto representa una forma muy flexible de introducir código en el sistema. Por supuesto, el protocolo para los datos que pasan por el flujo de entrada será el código fuente BÁSICO. Es importante señalar que se puede utilizar cualquier idioma; no cometa el error de pensar que esta técnica no se puede aplicar a su aplicación.

Una vez que el código fuente del programa interpretado se ingresa en el sistema, el sistema convierte el código fuente en una representación interna. Elegí usar el árbol de análisis como formato de representación interna para este proyecto. Una vez que se crea el árbol de análisis, se puede manipular o ejecutar.

El tercer componente es el entorno de ejecución. Como veremos, los requisitos para este componente son bastante simples, pero la implementación tiene algunos giros interesantes.

Un recorrido BÁSICO muy rápido

Para aquellos de ustedes que quizás nunca hayan oído hablar de BASIC, les daré un breve vistazo del lenguaje, para que puedan comprender los desafíos de análisis y ejecución que se avecinan. Para obtener más información sobre BASIC, recomiendo encarecidamente los recursos al final de esta columna.

BASIC significa Código de instrucción simbólico multiusos para principiantes, y fue desarrollado en la Universidad de Dartmouth para enseñar conceptos de computación a estudiantes de pregrado. Desde su desarrollo, BASIC ha evolucionado hacia una variedad de dialectos. Los más simples de estos dialectos se utilizan como lenguajes de control para controladores de procesos industriales; los dialectos más complejos son lenguajes estructurados que incorporan algunos aspectos de la programación orientada a objetos. Para mi proyecto, elegí un dialecto conocido como BASIC-80 que era popular en el sistema operativo CP / M a finales de los setenta. Este dialecto es solo moderadamente más complejo que los dialectos más simples.

Sintaxis de declaración

Todas las líneas de declaración tienen la forma

[: [: ...]]

donde "Línea" es un número de línea de declaración, "Palabra clave" es una palabra clave de declaración BÁSICA y "Parámetros" son un conjunto de parámetros asociados con esa palabra clave.

El número de línea tiene dos propósitos: sirve como etiqueta para declaraciones que controlan el flujo de ejecución, como una gotodeclaración, y sirve como etiqueta de clasificación para declaraciones insertadas en el programa. Como etiqueta de clasificación, el número de línea facilita un entorno de edición de línea en el que la edición y el procesamiento de comandos se mezclan en una sola sesión interactiva. Por cierto, esto era necesario cuando todo lo que tenías era un teletipo. :-)

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:

  • Análisis léxico para procesar el código como texto.
  • Análisis de expresiones, para construir árboles de análisis de las expresiones
  • Análisis de sentencias, para construir árboles de análisis de las propias sentencias
  • Clases de error para informar errores en el análisis

El grupo de marco consta de objetos que contienen los árboles de análisis y las variables. Éstas incluyen:

  • Un objeto de declaración con muchas subclases especializadas para representar declaraciones analizadas
  • Un objeto de expresión para representar expresiones para evaluación.
  • Un objeto variable con muchas subclases especializadas para representar instancias atómicas de datos.