在 C 中解析 DSL 比 lex/yacc 更好的解决方案？

Question

我的一个程序在运行时接受命令（例如 kill foo）。将其视为一种特定于领域的语言。这里有几个例子：

kill
kill client
exit

而且，链式命令是允许的，并且命令前后的空格并不重要，因此以下示例也是有效的：

kill ; say "that was fun"
  kill  ;  kill      ; kill;

我目前已经使用 lex/yacc （具体来说是 flex/bison）实现了这一点，并且引起了很多头痛。词法分析器在很大程度上取决于上下文（例如，通常不会返回空格标记，除非在 kill 关键字之后）并且具有许多不同的状态。语法过去常常存在冲突，而且我不太喜欢指定它的格式（尤其是 $1、$2、$3、... 使用非终结符的参数）。此外，野牛（在解析时）提供的错误消息有时是准确的，但通常不是（带有可选参数的 kill 命令会导致错误消息，例如 Unexpected $undefined, Expected $end或 ; 用于kill clont 而不是kill client）。最后，yacc 的 C API 很残酷（到处都是外部定义）。

我并不是要求您解决所有上述问题（如果没有办法绕过 lex/yacc，我将打开单独的线程，其中包含更具体的描述和代码）。相反，我对 lex/yacc 的替代品感兴趣。

我的标准如下：

• 输入是字符串（const char *），没有输出，但应该为每个不同的关键字调用一些代码。
• 我想将其与 C (C99) 一起使用。
• 该软件应该已经包含在主要的 Linux 发行版中，或者至少易于捆绑/打包。
• 它应该有详细记录。
• 描述我的语言的语法应该很简单。
• 它应该在解析错误时输出有意义的错误消息。
• 性能并不是那么重要（当然它应该很快，但典型的用例是交互式使用，而不是处理大量的命令）。

Answer 1

至于非常简单和小的语法，我会考虑手动编写词法分析器/解析器 - 通常不需要那么多工作。

几乎所有 Linux 发行版都附带了 lex/yacc 的变体。除此之外，另外两个广泛使用的解析器生成器是 lemon 和 antlr。

Answer 2

由于您的语言看起来非常简单，因此我建议实现一个有限状态机来标记和解析输入。

只需一次读取一个字符，在空白处进行标记（而不是在带引号的字符串中）。每个“命令”使机器处于不同的状态，在该状态下解析命令参数。 “;”或“\n”将机器重置为其启动状态。

Answer 3

我非常喜欢 ANTLR，在生产系统中使用过几次。

奇怪的是，在版本 2 中它支持生成 C++ 代码但不支持 C，而在版本 3 中它支持生成 C 代码但不支持 C++。我喜欢 C++，所以仍然使用 ANTLR v2，但您可能会喜欢 v3。这对你来说更好。

许多发行版都有 ANTLR v2 软件包，有些还有 v3。它有相当详细的文档（请注意，我使用 v2；我希望 v3 在这方面不会更差）。

ANTLR 不会“开箱即用”生成超级棒的解析错误消息。这似乎是大多数通用解析器系统的共同点，并且从根本上来说不是一个容易解决的问题。然而，通过一些工作，我看到了来自基于 ANTLR 的系统的一些不错的诊断输出（应用程序有一些逻辑来帮助弄清楚要对用户说些什么——ANTLR 这里没有太多魔力）。

Answer 4

Lex & 的一个有趣的替代品Yacc 是 Lemon 解析器。它有很多优点，但我还没有认真使用它，所以我不完全确定它的实际效果如何。它由 SQLite 使用。

Answer 5

您可能需要考虑Ragel。我最近开始使用它，并且发现一旦你熟悉了它的速度，使用它是一种乐趣。在您的示例中，您可能会执行类似的操作（注意：未测试！）：

#include <stdio.h>
#include <string.h>

%%{
    machine my_cmd_lang;

    action pk { printf("Killing %.*s\n", fpc-mark, mark); }
    action mk { mark = fpc; }

    k = 'kill'; # creates a machine that doesn't do anything
    x = 'exit' @{ printf("Exiting\n"); };
    arg = alpha+ >mk; # arg to kill is built in machine 'alpha' 1 or more times
    cmd = ((k space arg) @pk space* ';'?) | x;
    main := cmd* ;
}%%

%% write data;

int main(int argc, char* argv[]) {
    int cs;
    char* p = "kill client";
    char* pe = p + strlen(p);
    char* mark;

    %% write init;
    %% write exec;

    return 0;
}

使用 ragel 通过 Ragel 运行它，它会输出 ;。

Answer 6

您需要一个无词法分析器（例如，PEG 的实现）。由于您正在使用 C 并且已经熟悉 yacc，因此 this 之类的东西可能值得尝试。

如果您的语法足够简单，您可以实现一个临时递归下降解析器。