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

Question

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

Answer 1

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

 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) 性；前两个解决方案适用于任何上下文无关语法。