c++ - 在运行时从语法构建解析器

Question

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

Answer 1

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

 A = B C D ;

通过递归下降解析这样的规则很容易:调用对应于找到 B 的例程，然后调用找到 C 的例程，然后调用找到 D 的例程。如果你正在做一个通用解析器，你总是可以调用一个“parse_next_sentential_form(x)”函数，并将所需形式(终端或非终端标记)的名称作为 x(例如，“B”、“C”、“D”)传递。

在处理这样的规则时，解析器想要生成一个 A，方法是找到 B，然后是 C，然后是 D。要找到 B(或 C 或 D)，您需要在中有一组索引规则所有的左边都是一样的，所以可以很容易地枚举出B的产生规则，并递归处理它们的内容。如果您的解析器出现故障，它只会回溯。

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

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

如果您想让它运行得更快，我想您可以简单地取出 Bison 的内脏并将其制作成图书馆。然后，如果您有语法文本或语法规则(Bison 的不同入口点)，您可以启动它并让它在内存中生成它的表(它必须以某种形式进行)。不要吐出来；只需构建一个使用它们的 LR 解析引擎。瞧，即时高效的解析器生成。如果这样做，您必须担心歧义和语法的 LALR(1)ness；前两个解决方案适用于任何上下文无关语法。