Вы выбрали отличный проект — написание интерпретаторов может быть очень увлекательным занятием!
Но сначала, что мы подразумеваем под переводчиком? Существуют разные типы переводчиков.
Есть чистый интерпретатор, в котором вы просто интерпретируете каждый элемент языка по мере его нахождения. Их легче всего писать и они самые медленные.
Шагом вперед было бы преобразование каждого языкового элемента в какую-то внутреннюю форму, а затем интерпретация этого. Все еще довольно легко писать.
Следующим шагом будет фактический анализ языка и создание синтаксического дерева, а затем его интерпретация. Это несколько сложнее написать, но как только вы сделаете это несколько раз, это станет довольно легко.
Когда у вас есть синтаксическое дерево, вы можете довольно легко сгенерировать код для виртуальной машины с пользовательским стеком. Гораздо сложнее создать код для существующей виртуальной машины, такой как JVM или CLR.
В программировании, как и в большинстве инженерных начинаний, очень помогает тщательное планирование, особенно при работе со сложными проектами.
Итак, первый шаг — решить, какой тип интерпретатора вы хотите написать. Если вы не читали какую-либо из книг по компиляторам (например, я всегда рекомендую книгу Никлауса Вирта «Строительство компилятора» как одно из лучших вступлений в предмет, и теперь она находится в свободном доступе в Интернете в формате PDF), я бы порекомендовал что вы идете с чистым интерпретатором.
Но вам все еще нужно сделать некоторые дополнительные планирования. Вы должны четко определить, что именно вы собираетесь интерпретировать. EBNF отлично подходит для этого. Для нееврейского введения в EBNF прочитайте первые три части простого компилятора по адресу http://www.semware.com/html/compiler.html Он написан на уровне средней школы и должен быть легким для восприятия. Да, я сначала попробовала на своих детях :-)
Как только вы определили, что именно вы хотите интерпретировать, вы готовы написать свой интерпретатор.
Абстрактно, ваш простой интерпретатор будет разделен на сканер (технически это лексический анализатор), парсер и оценщик. В случае простого чистого интерполятора синтаксический анализатор и вычислитель будут объединены.
Сканеры легко писать и легко тестировать, поэтому мы не будем тратить на них время. См. Вышеупомянутую ссылку для получения информации о создании простого сканера.
Позволяет (например) определить ваш оператор goto:
gotostmt -> 'goto' integer
integer -> [0-9]+
Это говорит нам о том, что когда мы видим токен «goto» (как доставленный сканером), единственное, что может следовать, — это целое число. А целое число — это просто строка цифр.
В псевдокоде мы могли бы обработать это так:
(токен - это текущий токен, который является текущим элементом, только что возвращенным через сканер)
loop
if token == "goto"
goto_stmt()
elseif token == "gosub"
gosub_stmt()
elseif token == .....
endloop
proc goto_stmt()
expect("goto") -- redundant, but used to skip over goto
if is_numeric(token)
--now, somehow set the instruction pointer at the requested line
else
error("expecting a line number, found '%s'\n", token)
end
end
proc expect(s)
if s == token
getsym()
return true
end
error("Expecting '%s', found: '%s'\n", curr_token, s)
end
Посмотри, как это просто? На самом деле, в простом интерпретаторе сложно разобраться только с обработкой выражений. Хороший рецепт для их обработки находится по адресу: http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm В сочетании с вышеупомянутыми ссылками у вас должно быть достаточно для обработки выражений, с которыми вы столкнетесь в BASIC.
Хорошо, время для конкретного примера. Это из более крупного «чистого интерпретатора», который обрабатывает расширенную версию Tiny BASIC (но достаточно большой, чтобы запустить Tiny Star Trek :-))
/*------------------------------------------------------------------------
Simple example, pure interpreter, only supports 'goto'
------------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <setjmp.h>
#include <ctype.h>
enum {False=0, True=1, Max_Lines=300, Max_Len=130};
char *text[Max_Lines+1]; /* array of program lines */
int textp; /* used by scanner - ptr in current line */
char tok[Max_Len+1]; /* the current token */
int cur_line; /* the current line number */
int ch; /* current character */
int num; /* populated if token is an integer */
jmp_buf restart;
int error(const char *fmt, ...) {
va_list ap;
char buf[200];
va_start(ap, fmt);
vsprintf(buf, fmt, ap);
va_end(ap);
printf("%s\n", buf);
longjmp(restart, 1);
return 0;
}
int is_eol(void) {
return ch == '\0' || ch == '\n';
}
void get_ch(void) {
ch = text[cur_line][textp];
if (!is_eol())
textp++;
}
void getsym(void) {
char *cp = tok;
while (ch <= ' ') {
if (is_eol()) {
*cp = '\0';
return;
}
get_ch();
}
if (isalpha(ch)) {
for (; !is_eol() && isalpha(ch); get_ch()) {
*cp++ = (char)ch;
}
*cp = '\0';
} else if (isdigit(ch)) {
for (; !is_eol() && isdigit(ch); get_ch()) {
*cp++ = (char)ch;
}
*cp = '\0';
num = atoi(tok);
} else
error("What? '%c'", ch);
}
void init_getsym(const int n) {
cur_line = n;
textp = 0;
ch = ' ';
getsym();
}
void skip_to_eol(void) {
tok[0] = '\0';
while (!is_eol())
get_ch();
}
int accept(const char s[]) {
if (strcmp(tok, s) == 0) {
getsym();
return True;
}
return False;
}
int expect(const char s[]) {
return accept(s) ? True : error("Expecting '%s', found: %s", s, tok);
}
int valid_line_num(void) {
if (num > 0 && num <= Max_Lines)
return True;
return error("Line number must be between 1 and %d", Max_Lines);
}
void goto_line(void) {
if (valid_line_num())
init_getsym(num);
}
void goto_stmt(void) {
if (isdigit(tok[0]))
goto_line();
else
error("Expecting line number, found: '%s'", tok);
}
void do_cmd(void) {
for (;;) {
while (tok[0] == '\0') {
if (cur_line == 0 || cur_line >= Max_Lines)
return;
init_getsym(cur_line + 1);
}
if (accept("bye")) {
printf("That's all folks!\n");
exit(0);
} else if (accept("run")) {
init_getsym(1);
} else if (accept("goto")) {
goto_stmt();
} else {
error("Unknown token '%s' at line %d", tok, cur_line); return;
}
}
}
int main() {
int i;
for (i = 0; i <= Max_Lines; i++) {
text[i] = calloc(sizeof(char), (Max_Len + 1));
}
setjmp(restart);
for (;;) {
printf("> ");
while (fgets(text[0], Max_Len, stdin) == NULL)
;
if (text[0][0] != '\0') {
init_getsym(0);
if (isdigit(tok[0])) {
if (valid_line_num())
strcpy(text[num], &text[0][textp]);
} else
do_cmd();
}
}
}
Надеюсь, этого будет достаточно, чтобы вы начали. Повеселись!
person
Sammy Mitchell
schedule
29.09.2013
