Как да изградя интерпретатор в Java, част 1: ОСНОВНИТЕ

Когато казах на приятел, че съм написал BASIC устен преводач на Java, той се засмя толкова силно, че едва не разля содата, която държеше по дрехите си. „Защо изобщо бихте изградили BASIC интерпретатор в Java?“ беше първият предсказуем въпрос от устата му. Отговорът е едновременно прост и сложен. Простият отговор е, че беше забавно да пиша интерпретатор на Java и ако щях да пиша интерпретатор, бих могъл да напиша и такъв, за който имам хубави спомени от ранните дни на личните компютри. От сложната страна забелязах, че много хора, използващи 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 е основният редактор и цели игри са написани само с EMACS LISP код, известен като el-code. Тази способност за конфигуриране направи GNU EMACS главен редактор,докато терминалите VT-100, на които е проектиран да работят, се превърнаха в бележки под линия в колоната на писателя.

REXX

Един от любимите ми езици, който никога не направи така оживения шум, който заслужаваше, беше REXX, проектиран от Майк Коулишоу от IBM. Компанията се нуждаеше от език за управление на приложения на големи мейнфреймове, работещи с операционната система VM. Открих REXX на Amiga, където беше тясно свързан с голямо разнообразие от приложения чрез „REXX портове“. Тези портове позволиха приложенията да се управляват дистанционно чрез интерпретатора REXX. Това свързване на интерпретатор и приложение създаде много по-мощна система, отколкото беше възможно с нейните съставни части. За щастие езикът живее в NETREXX, версия, която Майк написа, компилирана в Java код.

Докато разглеждах NETREXX и много по-ранния език (LISP в Java), ми направи впечатление, че тези езици формират важни части от историята на приложението Java. Какъв по-добър начин да разкажете тази част от историята, отколкото да направите нещо забавно тук - като възкресете BASIC-80? По-важното е, че би било полезно да покажете един начин, по който скриптовите езици могат да бъдат написани в Java, и чрез тяхната интеграция с Java, да покажете как те могат да подобрят възможностите на вашите Java приложения.

ОСНОВНИ изисквания за подобряване на вашите Java приложения

BASIC е, просто, основен език. Има две школи на мисъл за това как може да се започне да се пише преводач за него. Един от подходите е да се напише програмен цикъл, в който програмата за интерпретация чете един ред текст от интерпретираната програма, анализира го и след това извиква подпрограма за изпълнението му. Последователността на четене, анализиране и изпълнение се повтаря, докато едно от изявленията на интерпретираната програма не каже на интерпретатора да спре.

Вторият и много по-интересен начин за справяне с проекта всъщност е да се анализира езика в дърво за синтактичен анализ и след това да се изпълни дървото за синтактичен анализ на място. Ето как работят токенизиращите преводачи и начина, по който избрах да продължа. Токенизиращите интерпретатори също са по-бързи, тъй като не е необходимо да сканират отново входа всеки път, когато изпълняват оператор.

Както споменах по-горе, трите компонента, необходими за постигане на динамично изпълнение, са средство за зареждане, модулен формат и среда за изпълнение.

Първият компонент, средство за зареждане, ще бъде разгледан от Java InputStream. Тъй като входните потоци са основни в I / O архитектурата на Java, системата е проектирана да чете в програма от InputStreamи да я конвертира в изпълнима форма. Това представлява много гъвкав начин за подаване на код в системата. Разбира се, протоколът за данните, преминаващи през входния поток, ще бъде BASIC изходен код. Важно е да се отбележи, че може да се използва всеки език; не правете грешката да мислите, че тази техника не може да се приложи към вашето приложение.

След като изходният код на интерпретираната програма бъде въведен в системата, системата преобразува изходния код във вътрешно представяне. Избрах да използвам синтактичното дърво като вътрешен формат на представяне за този проект. След като дървото за разбор е създадено, то може да бъде манипулирано или изпълнено.

Третият компонент е средата за изпълнение. Както ще видим, изискванията за този компонент са доста прости, но изпълнението има няколко интересни обрата.

Много бърза обиколка на BASIC

За тези от вас, които може би никога не са чували за BASIC, ще ви дам кратък поглед на езика, за да можете да разберете предизвикателствата за синтактичен анализ и изпълнение. За повече информация относно BASIC горещо препоръчвам ресурсите в края на тази колона.

BASIC означава универсален символичен кодекс за начинаещи за начинаещи и е разработен в университета в Дартмут, за да преподава изчислителни концепции за студенти. От своето развитие, BASIC еволюира в различни диалекти. Най-простите от тези диалекти се използват като контролни езици за контролери на промишлени процеси; най-сложните диалекти са структурирани езици, които включват някои аспекти на обектно-ориентираното програмиране. За моя проект избрах диалект, известен като BASIC-80, който беше популярен в операционната система CP / M в края на седемдесетте. Този диалект е само умерено по-сложен от най-простите диалекти.

Синтаксис на изявление

Всички редове с изявления са във формата

[: [: ...]]

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:

  • Лексикален анализ за обработка на кода като текст
  • Анализ на израза, за да се конструират синтактични дървета на изразите
  • Синтактичен анализ на изявление, за да се конструират синтактични дървета на самите изявления
  • Класове грешки за докладване на грешки при синтактичния анализ

Рамковата група се състои от обекти, които държат синтактичните дървета и променливите. Те включват:

  • Обект на изявление с много специализирани подкласове за представяне на анализирани изрази
  • Обект на израз, който представлява изрази за оценка
  • Променлив обект с много специализирани подкласове за представяне на атомни екземпляри от данни