使用Flex/Bison实现解释器的REPL

Question

我用Flex和Bison为扫描器/解析器编写了类似C语言的语言的解释器。当执行完整程序文件时它可以正常工作。

现在我正在尝试为解释器实现REPL以供交互使用。我希望它能像Ruby或ML中的命令行解释器一样工作：

1. 显示提示符
2. 接受一条或多条语句
3. 如果表达式不完整
   1. 显示继续提示符
   2. 允许用户继续输入行
4. 当行以完整表达式结尾时，
   1. 回显评估最后一个表达式的结果
   2. 显示主提示符

我的语法从top_level开始，代表语言中的单个语句。 词法分析器被配置为在stdin上进行交互模式。 我在完整文件和REPL模式下都使用相同的扫描器和语法，因为两个界面没有语义上的区别。

我的主要评估循环结构如下。

while (!interpreter.done) {
    if (interpreter.repl)
        printf(prompt);
    int status = yyparse(interpreter);
    if (status) {
        if (interpreter.error)
            report_error(interpreter);
    }
    else {
        if (interpreter.repl)
            puts(interpreter.result);
    }
}            

除了提示和回显逻辑外，这段代码运行良好。如果用户在一行上输入多个语句，则此循环会打印出多余的提示和表达式。如果表达式跨越多行，则此代码不会打印出连续提示符。这些问题的发生是因为提示/回显逻辑的粒度是语法中的top_level语句，但读取行的逻辑深入到词法分析器中。

如何重新构造评估循环以处理REPL提示和回显是最佳方法呢？也就是说：

• 如何每行显示一个提示符
• 如何在正确的时间显示继续提示
• 如何判断完整表达式是否是该行上的最后一个表达式

（我不想更改扫描器语言以传递换行符标记，因为那将严重改变语法。修改YY_INPUT并向Bison语法添加几个操作将是可以接受的。此外，我正在使用带有Xcode的标准Flex 2.5.35和Bison 2.3。）

- Jay Lieske

Answer 1

在研究Python和SML/NJ等语言如何处理REPL后，我在我的解释器中成功实现了一个好用的REPL。与其将提示/回显逻辑放在最外层的解析器驱动循环中，我将其放在最内层的词法分析器输入例程中。在解析器和词法分析器中设置的动作会设置控制输入例程提示的标志。

我正在使用可重入扫描仪，因此yyextra包含在解释器各层之间传递的状态。它大致如下：

typedef struct Interpreter {
    char* ps1; // prompt to start statement
    char* ps2; // prompt to continue statement
    char* echo; // result of last statement to display
    BOOL eof; // set by the EOF action in the parser
    char* error; // set by the error action in the parser
    BOOL completeLine // managed by yyread
    BOOL atStart; // true before scanner sees printable chars on line
    // ... and various other fields needed by the interpreter
} Interpreter;

词法分析器输入程序：

size_t yyread(FILE* file, char* buf, size_t max, Interpreter* interpreter)
{
    // Interactive input is signaled by yyin==NULL.
    if (file == NULL) {
        if (interpreter->completeLine) {
            if (interpreter->atStart && interpreter->echo != NULL) {
                fputs(interpreter->echo, stdout);
                fputs("\n", stdout);
                free(interpreter->echo);
                interpreter->echo = NULL;
            }
            fputs(interpreter->atStart ? interpreter->ps1 : interpreter->ps2, stdout);
            fflush(stdout);
        }

        char ibuf[max+1]; // fgets needs an extra byte for \0
        size_t len = 0;
        if (fgets(ibuf, max+1, stdin)) {
            len = strlen(ibuf);
            memcpy(buf, ibuf, len);
            // Show the prompt next time if we've read a full line.
            interpreter->completeLine = (ibuf[len-1] == '\n');
        }
        else if (ferror(stdin)) {
            // TODO: propagate error value
        }
        return len;
    }
    else { // not interactive
        size_t len = fread(buf, 1, max, file);
        if (len == 0 && ferror(file)) {
            // TODO: propagate error value
        }
        return len;
    }
}

顶层解释器循环如下：

while (!interpreter->eof) {
    interpreter->atStart = YES;
    int status = yyparse(interpreter);
    if (status) {
        if (interpreter->error)
            report_error(interpreter);
    }
    else {
        exec_statement(interpreter);
        if (interactive)
            interpreter->echo = result_string(interpreter);
    }
}

Flex文件获得了这些新定义：

%option extra-type="Interpreter*"

#define YY_INPUT(buf, result, max_size) result = yyread(yyin, buf, max_size, yyextra)

#define YY_USER_ACTION  if (!isspace(*yytext)) { yyextra->atStart = NO; }

YY_USER_ACTION处理语言语法中令牌与输入行之间的棘手交互。我的语言类似于C和ML，需要一个特殊字符（';'）来结束语句。在输入流中，该字符可以是换行符以表示行结尾，也可以是隶属于新语句的字符。如果自上次语句结束以来只扫描了换行符或其他空格，则输入程序需要显示主提示;否则，应该显示续行提示。

- Jay Lieske

---

感谢您的清晰解释！ - Ruslan R. Laishev

Answer 2

我也在开发这样的解释器，但我还没有做出 REPL，所以我的讨论可能有些模糊。

如果给定一行语句序列，只打印最后一个表达式的结果，这是否可接受？因为你可以像这样重构你的顶层语法规则：

top_level = top_level statement | statement ;

然后你的 top_level 的输出可以是语句的链表，而 interpreter.result 将是该列表尾部的评估结果。

- wmercer

---

这大致是我在为 REPL 重构语法之前所拥有的。递归模式的挑战在于它是贪婪的：解析器将继续请求向前看标记（即来自扫描仪的新输入行），直到其中一个分支失败或达到 EOF。 - Jay Lieske

如何看待右递归：top_level = statement top_level | statement - Foo Bah