자바로 인터프리터를 구축하는 방법, Part 1 : 기본

내가 자바로 BASIC 인터프리터를 썼다고 친구에게 말했을 때 그는 너무 심하게 웃어서 옷 전체에 들고 있던 탄산 음료를 거의 쏟았다. "왜 세계에서 자바로 BASIC 인터프리터를 구축하겠습니까?" 그의 입에서 나온 예측 가능한 첫 번째 질문이었습니다. 답은 간단하면서도 복잡합니다. 간단한 대답은 자바로 인터프리터를 작성하는 것이 즐거웠다는 것이고, 인터프리터를 작성한다면 개인 컴퓨팅 초기부터 좋은 기억이있는 하나를 쓰는 것이 좋을 것입니다. 복잡한 측면에서 저는 오늘날 Java를 사용하는 많은 사람들이 텀블링 Duke 애플릿을 만드는 시점을지나 심각한 애플리케이션으로 이동하고 있음을 알았습니다. 종종 응용 프로그램을 빌드 할 때 구성 할 수 있기를 원합니다.재구성을위한 선택 메커니즘은 일종의 동적 실행 엔진입니다.

매크로 언어 또는 구성 언어로 알려진 동적 실행은 사용자가 응용 프로그램을 "프로그래밍"할 수 있도록하는 기능입니다. 동적 실행 엔진의 이점은 도구를 교체하지 않고도 복잡한 작업을 수행하도록 도구와 응용 프로그램을 사용자 지정할 수 있다는 것입니다. Java 플랫폼은 다양한 동적 실행 엔진 옵션을 제공합니다.

HotJava 및 기타 핫 옵션

사용 가능한 동적 실행 엔진 옵션 중 일부를 간략하게 살펴본 다음 인터프리터의 구현을 자세히 살펴 보겠습니다. 동적 실행 엔진은 임베디드 인터프리터입니다. 통역사는 운영을 위해 세 가지 시설이 필요합니다.

  1. 지침을로드하는 수단
  2. 실행할 명령을 저장하기위한 모듈 형식
  3. 호스트 프로그램과 상호 작용하기위한 모델 또는 환경

HotJava

가장 유명한 임베디드 인터프리터는 사람들이 웹 브라우저를 보는 방식을 완전히 바꿔 놓은 HotJava "애플릿"환경이어야합니다.

HotJava "애플릿"모델은 Java 응용 프로그램이 알려진 인터페이스를 사용하여 일반 기본 클래스를 만든 다음 해당 클래스의 하위 클래스를 동적으로로드하고 런타임에 실행할 수 있다는 개념을 기반으로합니다. 이러한 애플릿은 새로운 기능을 제공했으며 기본 클래스의 범위 내에서 동적 실행을 제공했습니다. 이 동적 실행 기능은 Java 환경의 기본 부분이며이를 특별하게 만드는 요소 중 하나입니다. 이 특정 환경은 이후 칼럼에서 자세히 살펴 보겠습니다.

GNU EMACS

HotJava가 도착하기 전에 동적 실행을 사용하는 가장 성공적인 애플리케이션은 GNU EMACS였습니다. 이 편집기의 LISP와 유사한 매크로 언어는 많은 프로그래머에게 필수 요소가되었습니다. 간단히 말해서, EMACS LISP 환경은 LISP 인터프리터와 가장 복잡한 매크로를 구성하는 데 사용할 수있는 많은 편집 유형 기능으로 구성됩니다. EMACS 편집기가 원래 TECO라는 편집 기용으로 설계된 매크로로 작성되었다는 것은 놀라운 일이 아닙니다. 따라서 TECO에서 풍부한 (읽을 수없는 경우) 매크로 언어를 사용할 수있어 완전히 새로운 편집기를 만들 수있었습니다. 오늘날 GNU EMACS는 기본 편집기이며 전체 게임은 el-code로 알려진 EMACS LISP 코드로 작성되었습니다. 이 구성 기능은 GNU EMACS를 주요 편집기로 만들었습니다.실행되도록 설계된 VT-100 터미널은 작가 칼럼의 각주에 불과했습니다.

REXX

제가 가장 좋아하는 언어 중 하나는 IBM의 Mike Cowlishaw가 디자인 한 REXX였습니다. 이 회사는 VM 운영 체제를 실행하는 대형 메인 프레임에서 애플리케이션을 제어 할 언어가 필요했습니다. Amiga에서 REXX가 "REXX 포트"를 통해 다양한 응용 프로그램과 밀접하게 결합되어 있음을 발견했습니다. 이러한 포트를 통해 REXX 인터프리터를 통해 애플리케이션을 원격으로 구동 할 수 있습니다. 인터프리터와 응용 프로그램의 이러한 결합은 구성 요소로 가능한 것보다 훨씬 더 강력한 시스템을 만들었습니다. 다행히도이 언어는 Mike가 작성한 Java 코드로 컴파일 된 버전 인 NETREXX에 있습니다.

NETREXX와 훨씬 이전의 언어 (Java의 LISP)를 살펴 보았을 때 이러한 언어가 Java 애플리케이션 스토리의 중요한 부분을 형성한다는 사실에 놀랐습니다. 부활 BASIC-80 같은 재미있는 일을하는 것보다 이야기의이 부분을 전달하는 더 좋은 방법이 있을까요? 더 중요한 것은 스크립팅 언어가 Java로 작성 될 수있는 한 가지 방법을 보여주고 Java와의 통합을 통해 Java 애플리케이션의 기능을 향상시킬 수있는 방법을 보여주는 것이 유용 할 것입니다.

Java 앱 향상을위한 기본 요구 사항

BASIC은 아주 간단하게 기본 언어입니다. 통역사를 작성하는 방법에 대한 두 가지 생각 학교가 있습니다. 한 가지 접근 방식은 인터프리터 프로그램이 해석 된 프로그램에서 텍스트 한 줄을 읽고 구문 분석 한 다음이를 실행하기 위해 서브 루틴을 호출하는 프로그래밍 루프를 작성하는 것입니다. 해석 된 프로그램의 명령문 중 하나가 인터프리터에게 중지하라고 지시 할 때까지 읽기, 구문 분석 및 실행 순서가 반복됩니다.

실제로 프로젝트를 처리하는 두 번째이자 훨씬 더 흥미로운 방법은 언어를 구문 분석 트리로 구문 분석 한 다음 구문 분석 트리를 "제자리에서"실행하는 것입니다. 이것이 토큰 화 통역사가 작동하는 방식과 제가 진행하기로 선택한 방식입니다. 토큰 화 인터프리터는 명령문을 실행할 때마다 입력을 다시 스캔 할 필요가 없기 때문에 더 빠릅니다.

위에서 언급했듯이 동적 실행을 달성하는 데 필요한 세 가지 구성 요소는로드 수단, 모듈 형식 및 실행 환경입니다.

로드되는 수단 인 첫 번째 구성 요소는 Java에서 처리됩니다 InputStream. 입력 스트림은 Java I / O 아키텍처의 기본이므로 시스템은에서 프로그램을 읽고 InputStream실행 가능한 형식으로 변환 하도록 설계되었습니다 . 이것은 시스템에 코드를 공급하는 매우 유연한 방법을 나타냅니다. 물론 입력 스트림을 통과하는 데이터의 프로토콜은 BASIC 소스 코드입니다. 모든 언어를 사용할 수 있다는 점에 유의하는 것이 중요합니다. 이 기술을 응용 프로그램에 적용 할 수 없다고 생각하는 실수를하지 마십시오.

해석 된 프로그램의 소스 코드가 시스템에 입력 된 후 시스템은 소스 코드를 내부 표현으로 변환합니다. 이 프로젝트의 내부 표현 형식으로 구문 분석 트리를 사용하기로 선택했습니다. 구문 분석 트리가 생성되면 조작하거나 실행할 수 있습니다.

세 번째 구성 요소는 실행 환경입니다. 보시다시피이 구성 요소의 요구 사항은 매우 간단하지만 구현에는 몇 가지 흥미로운 변형이 있습니다.

매우 빠른 기본 둘러보기

BASIC에 대해 들어 본 적이없는 분들을 위해 언어에 대해 간략히 설명하여 앞으로의 구문 분석 및 실행 문제를 이해할 수 있도록하겠습니다. BASIC에 대한 자세한 내용은이 칼럼 끝에있는 리소스를 적극 권장합니다.

BASIC은 Beginners All-purpose Symbolic Instructional Code의 약자이며 학부생에게 계산 개념을 가르치기 위해 Dartmouth University에서 개발되었습니다. 개발 이후 BASIC은 다양한 방언으로 진화했습니다. 이러한 방언 중 가장 간단한 것은 산업 공정 컨트롤러의 제어 언어로 사용됩니다. 가장 복잡한 방언은 객체 지향 프로그래밍의 일부 측면을 통합하는 구조화 된 언어입니다. 제 프로젝트에서는 70 년대 후반에 CP / M 운영 체제에서 인기가 있었던 BASIC-80이라는 방언을 선택했습니다. 이 방언은 가장 단순한 방언보다 약간 더 복잡합니다.

문 구문

모든 명세서 행은 다음과 같은 형식입니다.

[: [: ...]]

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:

  • 코드를 텍스트로 처리하기위한 어휘 분석
  • 식 구문 분석, 식의 구문 분석 트리 구성
  • 명령문 구문 분석, 명령문 자체의 구문 분석 트리 구성
  • 파싱 ​​오류보고를위한 오류 클래스

프레임 워크 그룹은 구문 분석 트리와 변수를 보유하는 개체로 구성됩니다. 여기에는 다음이 포함됩니다.

  • 구문 분석 된 명령문을 나타내는 많은 특수 하위 클래스가있는 명령문 객체
  • 평가할 식을 나타내는 식 개체
  • 데이터의 원자 적 인스턴스를 나타내는 많은 특수 하위 클래스가있는 변수 객체