我一直在尝试实现 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 编写的程序很容易变得一团糟。这就是为什么我需要一些建议,阅读一些书籍或其他任何东西来让我对这个主题保持清醒。你有什么建议?
最佳答案
您选择了一个很棒的项目 - 编写解释器会很有趣!
但首先,我们所说的解释器是什么意思?有不同类型的解释器。
有纯解释器,您可以在其中简单地解释您找到的每个语言元素。这些是最容易编写的,也是最慢的。
进一步,将每个语言元素转换为某种内部形式,然后对其进行解释。仍然很容易编写。
下一步,将是实际解析语言,生成语法树,然后对其进行解释。这有点难写,但是一旦你做了几次,它就会变得很容易。
一旦有了语法树,就可以相当轻松地为自定义堆栈虚拟机生成代码。一个更难的项目是为现有的虚拟机生成代码,例如 JVM 或 CLR。
在编程中,与大多数工程工作一样,仔细规划会大有帮助,尤其是对于复杂的项目。
所以第一步是决定你想写哪种类型的解释器。如果您还没有读过许多编译器书籍中的任何一本(例如,我总是推荐 Niklaus Wirth 的“编译器构造”作为该主题的最佳介绍之一,现在可以在网上以 PDF 形式免费获得),我会推荐你选择纯解释器。
但是您仍然需要做一些额外的计划。您需要严格定义您要解释的内容。 EBNF 非常适合这个。要深入了解 EBNF,请阅读 http://www.semware.com/html/compiler.html 上的简单编译器的前三部分。这是高中水平写的,应该很容易消化。是的,我先在我的 child 身上试过了 :-)
一旦定义了要解释的内容,就可以编写解释器了。
抽象地说,您将简单的解释器分为扫描器(从技术上讲是词法分析器)、解析器和求值器。在简单的纯插值器情况下,解析器和求值器将结合在一起。
扫描器易于编写和测试,因此我们不会在其上花费任何时间。有关制作简单扫描仪的信息,请参阅上述链接。
让我们(例如)定义您的 goto 语句:
gotostmt -> 'goto' integer
integer -> [0-9]+
这告诉我们,当我们看到 token “goto”(由扫描器传送)时,唯一可以跟随的是一个整数。整数只是一个数字字符串。
在伪代码中,我们可以这样处理:
(token - 是当前的token,也就是刚刚通过scanner返回的当前元素)
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();
}
}
}
希望这足以让您入门。玩得开心!
https://stackoverflow.com/questions/12989149/