有关如何实现BASIC语言解析器/解释器的任何建议？

Question

我一直在尝试实现一个BASIC语言解释器(在C/C++中),但我还没有找到任何解释语言结构解析过程的书或(全文)文章.有些命令相当复杂且难以解析,尤其是条件和循环,例如IF-THEN-ELSE和FOR-STEP-NEXT,因为它们可以将变量与常量,整个表达式和代码以及其他所有内容混合,例如:

10 IF X = Y + Z THEN GOTO 20 ELSE GOSUB P
20 FOR A = 10 TO B STEP -C : PRINT C$ : PRINT WHATEVER
30 NEXT A

能够解析类似的东西并让它发挥作用似乎是一场噩梦.更糟糕的是,用BASIC编写的程序很容易变得混乱.这就是为什么我需要一些建议,阅读一些书或其他什么来让我明白这个主题.你能提出什么建议？

Answer 1

你选择了一个很棒的项目 - 写口译员可以很有趣!

但首先,我们甚至用翻译来表达什么呢？有不同类型的口译员.

有一个纯粹的解释器,您只需在找到它时解释每个语言元素.这些是最容易编写的,也是最慢的.

一步,将每个语言元素转换为某种内部形式,然后解释它.写起来还算不错.

下一步,将是实际解析语言,并生成语法树,然后解释它.这写起来有点困难,但是一旦你完成了几次,就会变得非常简单.

一旦有了语法树,就可以相当轻松地为自定义堆栈虚拟机生成代码.一个更难的项目是为现有虚拟机生成代码,例如JVM或CLR.

在编程中,像大多数工程工作一样,精心规划极大地帮助了,特别是对于复杂的项目.

因此,第一步是确定您希望编写哪种类型的解释器.如果您还没有阅读过任何一本编译器书籍(例如,我总是推荐Niklaus Wirth的"编译器构造"作为该主题的最佳介绍之一,现在可以在网上免费获得PDF格式),我建议那你和纯粹的翻译一起去.

但是你仍然需要做一些额外的计划.您需要严格定义您将要解释的内容.EBNF非常适合这一点.有关gentile介绍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();
        }
    }
}

希望这足以让你开始.玩得开心!