Javaでインタプリタを構築する方法、パート1:基本

私がJavaでBASICインタープリターを書いたと友人に話したとき、彼はとても笑い、服全体に持っていたソーダをこぼしそうになりました。 「なぜ世界でJavaでBASICインタープリターを構築するのですか?」彼の口からの予測可能な最初の質問でした。答えは単純でも複雑でもあります。簡単な答えは、Javaでインタプリタを書くのは楽しかったということです。インタプリタを書くつもりなら、パーソナルコンピューティングの初期の頃から懐かしいものを書くほうがよいでしょう。複雑な面では、今日Javaを使用している多くの人々が、タンブリングDukeアプレットを作成する段階を過ぎて、本格的なアプリケーションに移行していることに気づきました。多くの場合、アプリケーションを構築する際に、構成可能にする必要があります。再構成に最適なメカニズムは、ある種の動的実行エンジンです。

マクロ言語または構成言語として知られる動的実行は、ユーザーがアプリケーションを「プログラム」できるようにする機能です。動的実行エンジンを使用する利点は、ツールとアプリケーションをカスタマイズして、ツールを置き換えることなく複雑なタスクを実行できることです。Javaプラットフォームは、さまざまな動的実行エンジンオプションを提供します。

HotJavaおよびその他のホットオプション

利用可能な動的実行エンジンオプションのいくつかを簡単に調べてから、インタープリターの実装について詳しく見ていきましょう。動的実行エンジンは、組み込みインタープリターです。通訳者が操作するには、次の3つの機能が必要です。

  1. 指示をロードする手段
  2. 実行する命令を格納するためのモジュール形式
  3. ホストプログラムと対話するためのモデルまたは環境

HotJava

最も有名な組み込みインタプリタは、人々がWebブラウザを見る方法を完全に変えたHotJava「アプレット」環境でなければなりません。

HotJavaの「アプレット」モデルは、Javaアプリケーションが既知のインターフェイスを備えた汎用基本クラスを作成し、そのクラスのサブクラスを動的にロードして実行時に実行できるという概念に基づいていました。これらのアプレットは新しい機能を提供し、基本クラスの範囲内で動的な実行を提供しました。この動的実行機能は、Java環境の基本的な部分であり、Java環境を特別なものにしているものの1つです。この特定の環境については、後のコラムで詳しく説明します。

GNU EMACS

HotJavaが登場する前は、動的実行で最も成功したアプリケーションはおそらくGNUEMACSでした。このエディタのLISPのようなマクロ言語は、多くのプログラマーにとって定番となっています。簡単に言うと、EMACS LISP環境は、LISPインタープリターと、最も複雑なマクロを構成するために使用できる多くの編集タイプの関数で構成されています。 EMACSエディターが元々TECOと呼ばれるエディター用に設計されたマクロで書かれていたことは驚くべきことではありません。したがって、TECOで豊富な(読み取り不可能な場合)マクロ言語を利用できるため、まったく新しいエディターを構築できました。今日、GNU EMACSは基本エディターであり、ゲーム全体はel-codeとして知られるEMACSLISPコードにすぎません。この構成機能により、GNUEMACSは主力のエディターになりました。VT-100端末は、それが実行されるように設計されていましたが、ライターのコラムの単なる脚注になっています。

REXX

私のお気に入りの言語の1つは、それにふさわしいスプラッシュを作ることは決してありませんでしたが、IBMのMikeCowlishawによって設計されたREXXでした。同社は、VMオペレーティングシステムを実行している大規模なメインフレーム上のアプリケーションを制御するための言語を必要としていました。私はAmigaでREXXを発見しました。そこでは、「REXXポート」を介してさまざまなアプリケーションと緊密に結合されていました。これらのポートにより、アプリケーションをREXXインタープリターを介してリモートで駆動することができました。インタプリタとアプリケーションのこの結合により、そのコンポーネントパーツで可能であったよりもはるかに強力なシステムが作成されました。幸いなことに、この言語は、JavaコードにコンパイルされたMikeが作成したバージョンであるNETREXXに存在します。

NETREXXとはるかに初期の言語(JavaのLISP)を見ていたとき、これらの言語がJavaアプリケーションのストーリーの重要な部分を形成していることに気づきました。ストーリーのこの部分を伝えるには、ここで何か楽しいことをするよりも良い方法はありますか?たとえば、BASIC-80を復活させるなどです。さらに重要なことは、スクリプト言語をJavaで記述できる1つの方法を示し、Javaとの統合を通じて、Javaアプリケーションの機能をどのように強化できるかを示すことが役立つでしょう。

Javaアプリを強化するための基本的な要件

BASICは、非常に簡単に言えば、基本的な言語です。通訳を書く方法については、2つの考え方があります。1つのアプローチは、インタープリタープログラムがインタープリタープログラムから1行のテキストを読み取り、それを解析してから、サブルーチンを呼び出して実行するプログラミングループを作成することです。読み取り、解析、および実行のシーケンスは、解釈されたプログラムのステートメントの1つがインタープリターに停止するように指示するまで繰り返されます。

プロジェクトに取り組むための2番目の、そしてはるかに興味深い方法は、実際には言語を解析して解析ツリーにし、解析ツリーを「その場で」実行することです。これが、トークン化インタープリターの動作方法であり、私が続行することを選択した方法です。トークン化インタープリターは、ステートメントを実行するたびに入力を再スキャンする必要がないため、より高速です。

前述したように、動的実行を実現するために必要な3つのコンポーネントは、ロードの手段、モジュール形式、および実行環境です。

ロードの手段である最初のコンポーネントは、Javaによって処理されますInputStream。入力ストリームはJavaのI / Oアーキテクチャの基本であるため、システムはからプログラムを読み込んでInputStream実行可能形式に変換するように設計されています。これは、システムにコードを供給する非常に柔軟な方法を表しています。もちろん、入力ストリームを通過するデータのプロトコルは、BASICソースコードになります。どの言語でも使用できることに注意することが重要です。この手法をアプリケーションに適用できないと誤解しないでください。

インタープリター型プログラムのソースコードがシステムに入力された後、システムはソースコードを内部表現に変換します。このプロジェクトの内部表現形式として解析ツリーを使用することを選択しました。解析ツリーが作成されると、それを操作または実行できます。

3番目のコンポーネントは実行環境です。後で説明するように、このコンポーネントの要件はかなり単純ですが、実装にはいくつかの興味深い工夫があります。

非常に迅速なBASICツアー

BASICのことを聞いたことがない方のために、言語を簡単に紹介します。これにより、解析と実行の課題を理解することができます。BASICの詳細については、このコラムの最後にあるリソースを強くお勧めします。

BASICはBeginnersAll-Purpose Symbolic Instructional Codeの略で、ダートマス大学で学部生に計算の概念を教えるために開発されました。その開発以来、BASICはさまざまな方言に進化してきました。これらの方言の中で最も単純なものは、産業用プロセスコントローラーの制御言語として使用されます。最も複雑な方言は、オブジェクト指向プログラミングのいくつかの側面を組み込んだ構造化言語です。私のプロジェクトでは、70年代後半にCP / Mオペレーティングシステムで普及したBASIC-80と呼ばれる方言を選択しました。この方言は、最も単純な方言よりも適度に複雑です。

ステートメント構文

すべてのステートメント行は次の形式です

[:[:...]]

ここで、「Line」はステートメントの行番号、「Keyword」はBASICステートメントのキーワード、「Parameters」はそのキーワードに関連付けられたパラメーターのセットです。

行番号には2つの目的があります。ステートメントなどの実行フローを制御するステートメントのラベルとしてgoto機能することと、プログラムに挿入されるステートメントのソートタグとして機能することです。ソートタグとして、行番号は、編集とコマンド処理が単一の対話型セッションに混在する行編集環境を容易にします。ちなみに、これはあなたが持っていたのがテレタイプだけだったときに必要でした。:-)

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:

  • コードをテキストとして処理するための字句解析
  • 式の解析、式の解析ツリーを構築する
  • ステートメント自体の解析ツリーを構築するためのステートメント解析
  • 解析のエラーを報告するためのエラークラス

フレームワークグループは、解析ツリーと変数を保持するオブジェクトで構成されます。これらには以下が含まれます:

  • 解析されたステートメントを表すための多くの特殊なサブクラスを持つステートメントオブジェクト
  • 評価用の式を表す式オブジェクト
  • データのアトミックインスタンスを表すための多くの特殊なサブクラスを持つ変数オブジェクト