如何将 CFG 转换为 C++ 代码

Question

我有上下文无关语法 (CFG)。我想写一个c++代码来做像CFG一样的事情。

是否有任何内置函数或简单的转换方法？或者，执行 CFG 的东西？

Answer 1

您可能想看看 bison，yacc 的 GNU 实现，它代表 yet another compiler compiler，并且会根据您提供的语法生成解析器.

Answer 2

没有这样的 C++ 内置函数，但您有一些替代方法。

解析器生成器：Flex+Bison 允许您根据语法描述以 (LA)LR 或 GLR 形式生成 C 或 C++ 中的解析器。如果你对 CFG 有很好的掌握，学习 Bison 语法会很容易。 Bison 和 Flex 会输出 C 代码，但它们可以在语义动作中优雅地处理 C++。
自上而下的解析器：如果您的语法是 LL(k) 形式并且您不想学习额外的语言，那么您可以轻松地从语法中派生递归下降解析器。这很快，但是 LL 不如 (G)LR 强大，如果您不对所有边缘情况都非常小心，那么维护一个手写的解析器很快就会变成一场噩梦。 LL 解析器也可以实现为 table 解析器（就像 LR 一样），但是手动编辑 table 迟早会变得一团糟。

Bison 也可以发出 C++ class 而不是函数，只需添加：

%skeleton "lalr1.cc"
%language "c++"
%define parser_class_name {Parser}

序幕。唯一的区别是现在标记是枚举的成员，不再定义，所以你必须使用 Parser::token::TOKEN_NAME 而不是 TOKEN_NAME。

Flex 也可以嗯...敲打...生成 C++ class，但是将 Bison C++ 和 Flex C++ 单击在一起并不是非常简单，值得单独提问。

Answer 3

您正在寻找 parser generators (sometimes called compiler-compilers). You already know about bison. You could try ANTLR3 (or ANTLR4 for Java). Here is a comparison.

顺便说一句，大多数时候编程语言并不是真正的上下文无关（例如，因为它们需要一些 symbol table）。

还有一些解析器是手写的recursive descent ones, (e.g. GCC, see this)

请注意 context-free grammar is a specification for some formal syntax (which you could implement in some parser). But semantics and pragmatics 也很重要。

Answer 4

另一种选择是使用 boost::spirit 制作解析器 - 纯 C++ 解决方案，但需要依赖 Boost

如何将 CFG 转换为 C++ 代码

how to convert a CFG to c++ code

c

c++

context-free-grammar