2

我一直在尝试实现一个 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 编写的程序很容易变得一团糟。这就是为什么我需要一些建议，阅读一些书或其他任何东西来让我对这个主题保持清醒。你有什么建议？

4

3 回答 3

7

你选择了一个很棒的项目——编写解释器会很有趣！

但首先，我们所说的口译员是什么意思？有不同类型的口译员。

有一个纯解释器，您只需在找到每个语言元素时对其进行解释。这些是最容易编写的，也是最慢的。

更进一步，将每个语言元素转换为某种内部形式，然后对其进行解释。还是很容易写的。

下一步是实际解析语言，生成语法树，然后解释它。这有点难写，但是一旦你做了几次，它就变得很容易了。

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

在编程中，就像大多数工程工作一样，仔细的计划非常有帮助，尤其是对于复杂的项目。

所以第一步是决定你想写哪种类型的解释器。如果您还没有阅读任何编译器书籍（例如，我总是推荐 Niklaus Wirth 的“编译器构造”作为对该主题的最佳介绍之一，并且现在可以在网络上以 PDF 形式免费获得），我会推荐你和纯粹的翻译一起去。

但是你仍然需要做一些额外的计划。您需要严格定义要解释的内容。EBNF 非常适合这一点。有关 EBNF 的异教徒介绍，请阅读http://www.semware.com/html/compiler.html上的 Simple Compiler 的前三部分。它是在高中级别编写的，应该很容易消化。是的，我先在我的孩子身上试过:-)

一旦你定义了你想要解释的内容，你就可以编写你的解释器了。

抽象地说，你的简单解释器将分为扫描器（技术上，词法分析器）、解析器和评估器。在简单的纯插值器情况下，解析器和求值器将结合在一起。

扫描仪很容易编写，也很容易测试，所以我们不会花时间在他们身上。有关制作简单扫描仪的信息，请参阅上述链接。

让（例如）定义您的 goto 语句：

gotostmt -> 'goto' integer

integer -> [0-9]+

这告诉我们，当我们看到令牌“goto”（由扫描仪提供）时，唯一可以跟随的就是一个整数。整数只是一个数字字符串。

在伪代码中，我们可以这样处理：

（token - 是当前的token，也就是刚刚通过扫描仪返回的当前元素）

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();
        }
    }
}

希望这足以让您入门。玩得开心！

于 2013-09-29T14:33:27.103 回答
3

说这话我肯定会被打败……但是……：

首先，我实际上正在开发一个独立的库（作为一种爱好），它由以下组成：

  • 一个标记器，从源文本构建标记的线性（平面列表）并遵循与文本相同的序列（从文本流创建的词法）。
  • 手动解析器（语法分析；伪编译器）
  • 没有“伪代码”或“虚拟 CPU/机器”。
  • 指令（例如“return”、“if”、“for”、“while”……然后是算术表达式）由基本的 c++-struct/class 表示，并且是对象本身。基础对象，我将其命名为atom，有一个名为“eval”的虚拟方法，以及其他常见成员，即“执行/分支”本身。所以无论我有一个'if'语句及其可能的分支（单个语句或语句/指令块）作为真或假条件，它都会从基本虚拟原子：：eval（）......等等对于一切都是atom.
  • 甚至诸如变量之类的“对象”也是“原子”。'eval()' 将简单地从variant原子本身持有的容器返回其值（指针，指的是持有'atom'的'本地'变体实例（实例变体本身）或由原子持有的另一个变体在给定的“块/堆栈”中创建。所以“原子”是“就地”指令/对象。

到目前为止，作为一个例子，下面的一些没有真正意义的“代码”可以正常工作：

r = 5!; // 5! : (factorial of 5 )
Response = 1 + 4 - 6 * --r * ((3+5)*(3-4) * 78);
if (Response != 1){ /* '<>' also is not equal op. */
 return r^3;
} 
else{
 return 0;
}

表达式（算术）内置于binary tree expression：

A = b+c; =>
    =
   / \
  A   +
     / \
    b   c

因此，上述表达式的“指令”/语句是树条目原子，在上述情况下，它是“=”（二进制）运算符。

树是用 atom::r0,r1,r2 构建的： atom 'A' ：

    r0
     |
     A
    / \
   r1  r2

关于 c++ 运行时和“脚本”库之间的“全双工”机制，我做了class_adaptor和adaptor<>：

前任。：

template<typename R, typename ...Args> adaptor_t<T,R, Args...>& import_method(const lstring& mname, R (T::*prop)(Args...)) { ... }

template<typename R, typename ...Args> adaptor_t<T,R, Args...>& import_property(const lstring& mname, R (T::*prop)(Args...)) { ... }

第二：我知道那里有很多工具和库，例如 lua、boost::bind<*>、QML、JSON 等……但在我的情况下，我需要创建自己的 [edit] 'independant ' [/edit] 用于“实时脚本”的库。我害怕我的“解释器”会占用大量内存，但令我惊讶的是它没有使用 QML、jscript 甚至 lua 大:-)

谢谢 ：-）

于 2015-02-11T14:55:26.540 回答
1

不要费心手动破解解析器。使用解析器生成器。lex+yacc是经典的词法分析器/解析器生成器组合，但谷歌搜索会发现很多其他的。

于 2012-10-20T14:04:15.390 回答