比lex / yacc更好的解决方案，用于解析C中的DSL

我的一个程序在运行时接受命令（如kill foo）。可以将其视为一种特定于域的语言。以下是一些示例：

kill
kill client
exit

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

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

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

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

我的标准如下：

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

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

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

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

只需一次读取一个字符的输入，在空格处标记（而不是在带引号的字符串中）。每个"命令"将机器置于不同的状态，在其中解析命令参数。";" 或 "" 将计算机重置为其启动状态。

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

奇怪的是，在版本 2 中，它支持生成 C++ 代码，但不支持生成 C，

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

许多发行版都有 ANTLR v2 软件包，有些发行版也有 v3。它有相当好的文档记录（请注意，我使用 v2;我希望v3在这方面不会更糟）。

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

Lex & Yacc 的一个有趣的替代方案是 Lemon 解析器。它有很多优点，但我还没有认真使用它，所以我不完全确定它到底有多好。它由SQLite使用。

你可能要考虑Ragel。我最近开始使用它，一旦你跟上速度，我发现使用起来很愉快。在您的示例中，您可以执行以下操作（注意：未测试！

#include <stdio.h>
#include <string.h>
%%{
    machine my_cmd_lang;
    action pk { printf("Killing %.*sn", fpc-mark, mark); }
    action mk { mark = fpc; }
    k = 'kill'; # creates a machine that doesn't do anything
    x = 'exit' @{ printf("Exitingn"); };
    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 <filename.rl>通过 Ragel 运行它，它会吐出<filename.c>.

你需要

一个无词法解析器（例如，PEG的实现）。由于您使用的是 C 并且已经熟悉 yacc，因此可能值得尝试这样的东西。

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

相关内容

最新更新

热门标签：