在运行时根据语法构建解析器



许多(大多数)c++正则表达式库允许在运行时从字符串创建表达式。有人知道任何c++解析器生成器允许在运行时将表示为字符串的语法(最好是BNF)提供给生成器吗?我发现的所有实现要么需要运行显式代码生成器,要么需要通过巧妙的模板元编程来表达语法。

构建一个接受语法作为输入的递归下降、回溯解析器应该是相当容易的。您可以将所有规则简化为以下形式(或者就像这样做一样):

 A = B C D ;

通过递归下降解析这样的规则很容易:调用对应于查找B的例程,然后调用查找C的例程,然后调用查找D的例程。给定您正在做一个通用解析器,您总是可以调用"parse_next_sentential_form(x)"函数,并将所需形式(终端或非终端令牌)的名称传递为x(例如,"B","C","D")。

在处理这样的规则时,解析器希望通过找到B,然后C,然后D来生成a。为了找到B(或C或D),您希望有一个索引规则集,其中所有左侧都是相同的,因此可以轻松枚举生成B的规则,并递归处理它们的内容。如果您的解析器出现故障,它将简单地回溯。

这不会是一个闪电般的解析器,但如果实现得好,应该不会很糟糕。

还可以使用Earley解析器,它通过创建部分处理规则的状态来进行解析。

如果你想让它更快,我想你可以简单地把Bison的内脏变成一个库。然后,如果您有语法文本或语法规则(进入Bison的不同入口点),您可以启动它并让它在内存中生成它的表(它必须以某种形式这样做)。不要吐出来;只需构建一个使用它们的LR解析引擎。瞧,实时高效的解析器生成。如果你这样做,你必须担心语法的歧义和LALR(1)性;前面两个解决方案适用于任何与上下文无关的语法。

我不知道有这样的库。但是,如果性能和健壮性不是很重要,那么您可以剥离bison或任何其他生成C代码的工具(通过popen(3)或类似的工具),在生成的代码上剥离gcc,将其链接到共享库,并通过dlopen(3)/dlsym(3)加载库。在Windows上——DLL和LoadLibrary()代替

最简单的选择是嵌入一些脚本语言,甚至是一个成熟的VM(例如,Mono),并在其上运行生成的解析器。Lua有一个非常强大的JIT编译器,不错的元编程能力和几个Packrat实现,所以它可能是最省力的方法。

我刚刚看到这个http://cocom.sourceforge.net/ammunition++-13.html
最后一个是Earley Parser,它似乎将语法作为字符串。
其中一个函数是:

公共函数' parse_grammar'

         `int parse_grammar (int strict_p, const char *description)'

是另一个将解析器调整为给定语法的函数。语法由字符串' description'给出。描述与YACC类似。

实际代码在http://sourceforge.net/projects/cocom/

编辑

更新的版本在https://github.com/vnmakarov/yaep

boost::spirit是一个c++解析框架,可用于在运行时动态构造解析器。

最新更新