从 AST 生成 C 类型声明的算法

Question

我需要从抽象语法树生成 C 代码。类型声明很棘手。有没有写下任何地方的算法？

之前有几个关于反向的问题。我不是要解析 C 声明，而是要生成它们。

我已经尝试检查 cdecl 的代码，这是我所知道的唯一合理的短程序，但是当我删除所有代码时，显然不是生成 C 声明的代码，我最终得到一个空文件，所以我显然在那里遗漏了一些东西。

抽象语法树对C类型语义进行编码，其中节点种类为：

基本类型（int、char等）
类型指针
类型数组（有或没有大小）
获取参数类型列表并返回类型的函数

所以问题在于将其呈现为 C 语法。

Answer 1

如果你能用 C++ 实现 AST，STL 提供了 std::type_info::name()，return 是类型 T 的名称。在某些编译器（包括 MSVC）上，此 return 是人类可读的名称。在其他人中，包括 gcc，它 return 是一个错位的名字。 GCC 提供了一个 abi::__cxa_demangle 内置函数来对其进行分解，Boost provides a more portable function 为此，boost::core::demangle.

为了实现运行时多态性，你可以使用typeid操作符在运行时得到一个std::type_info对象，或者你可以让每个类型的AST节点继承一个抽象基class.那可能有一个纯虚函数::name()，其实现可能类似于

#include <boost/core/demangle.hpp>
#include <typeinfo>

template<typename T>
  const char* AST<T>::name() {
    return boost::core::demangle( typeid(T).name() );
  }

或者使用一堆 #ifdef 块来支持不同的编译器。

如果您想自己动手，these answers 提供一些在编译时使用模板元编程连接常量字符串的方法。会有几个繁琐的位，例如：将 const、volatile 和 signed 等限定符放入规范顺序，将指向 T(Args...) 的指针表示为 T(*)(Args...)，以及指向数组的指针的等价物。如果你想用模板元编程消除所有运行时开销，你可能会定义你自己的 type_name<T> 模板，使用 std::enable_if 和 <type_traits> 库分别专门化它，并为复合类型提供覆盖以正确的方式将组件的类型名称与 *、(、)、[ 和 ] 连接起来。如果您可以承受少量的开销，您可以将它们设为 const std::string 并将它们与 +.

连接起来

您可能希望自下而上地执行此操作，从简单类型的名称开始，然后提供递归查找的 array-of-t、pointer-to-array-of-T 等的实现建立积木的名称。它与函数式语言中的模式保护非常相似。

用 C 来做会困难得多。

编辑

在 C 中完成它不一定会那么难。（在我们的聊天中，你说你实际上是在用 Kotlin 做这件事。）

形式语法你应该查阅语言标准（或a recent draft），但你感兴趣的语言子集似乎有三种情况：

简单类型，通过附加 *、
派生类型，通过在中间添加 (*) 和
指向派生类型的指针，其中您已经有类似 (**) 的内容，并向其添加另一个星号。（千万不要真的写出三星级的代码！）

这可以写成一个算法，其中类型有 left、middle 和 right 部分。对于简单类型，left是整个类型，另外两个为空。对于数组，left 是元素类型，right 是边界。对于函数原型，left 是 return 类型，right 是参数列表。无论哪种方式，middle 都是空的。对于派生类型的指针，middle 是中间括号内的星号。因此，例如，double(*)[4][4] 有一个 double 的 left，一个 * 的 middle 和一个右 [4][4].

大多数操作有两种特殊情况，这取决于middle是空的还是非空的。（这些可以实现为泛型的特化、模式匹配、重载对象方法或 case 块。由于我们假设在 C 中执行此操作，因此我们可能拼写为 strlen(middle) ? ... : ...。）

我要从这里开始拼字符串连接⧺

如果给定的类型有一个空的 middle，它在 C 中的名称是 left ⧺ right，声明为left ⧺ " " ⧺ name ⧺ right.

如果给定的类型有一个非空的middle，它在C中的名称是left ⧺ "(" ⧺ middle ⧺ ")" ⧺ right 并且使用它的声明是 left ⧺ "(" ⧺ middle ⧺ name ⧺ ")" ⧺ right.比如在声明中int(*callback)(handle)，left就是int，middle就是*，name是callback，right是(handle).

形成指向一个类型的指针有三种情况：如果有一个非空的中间，将*追加到中间。如果有一个空的中间和一个非空的right，设置middle为*。如果 middle 和 right 都为空，则将 * 附加到 left.

如果你想支持 const 和 volatile 指针、K&R 风格的不完整函数类型或 C++ 引用，有些特殊情况需要更多调整。

从 AST 生成 C 类型声明的算法

Algorithm to produce C type declarations from AST

c

types

code-generation

编辑