1. AST的基本结构

首先用OpenCL的程序来展示下clang中语法树的结构，如下所示为要编译的OpenCL kernel:

C++

__kernel void add_kernel(global int *a, global int *b, global int *c)

{

  int i = get_global_id(0);

  c[i]=a[i]+b[i];

}

使用下面命令dump其语法树结构：

Bash

clang -c -target spir -x cl -cl-std=CL1.0 -Xclang -ast-dump -Xclang -finclude-default-header input.cl

语法树结构如下所示：

C++

TranslationUnitDecl 0x55ff6668d008 <<invalid sloc>> <invalid sloc>

|-TypedefDecl 0x55ff666aa1e8 <<invalid sloc>> <invalid sloc> implicit NSConstantString 'struct NSConstantString_tag'

| `-RecordType 0x55ff6668dfc0 'struct __NSConstantString_tag'

|  `-Record 0x55ff6668df48 '__NSConstantString_tag'

|-TypedefDecl 0x55ff666aa248 <<invalid sloc>> <invalid sloc> implicit referenced sampler_t 'sampler_t'

| `-BuiltinType 0x55ff6668dca0 'sampler_t'

|-TypedefDecl 0x55ff666aa2a8 <<invalid sloc>> <invalid sloc> implicit referenced event_t 'event_t'

| `-BuiltinType 0x55ff6668dcc0 'event_t'

...

...

-FunctionDecl 0x55ff66d4ee28 <input.cl:1:1, line:5:1> line:1:15 add_kernel 'void (global int *, global int *, __global int *)'

 |-ParmVarDecl 0x55ff66d4ec20 <col:26, col:38> col:38 used a '__global int *'

 |-ParmVarDecl 0x55ff66d4ec98 <col:41, col:53> col:53 used b '__global int *'

 |-ParmVarDecl 0x55ff66d4ed10 <col:55, col:67> col:67 used c '__global int *'

 |-CompoundStmt 0x55ff66d4f2d0 <line:2:1, line:5:1>

 | |-DeclStmt 0x55ff66d4f098 <line:3:5, col:29>

 | | `-VarDecl 0x55ff66d4ef30 <col:5, col:28> col:9 used i 'int' cinit

 | |  `-ImplicitCastExpr 0x55ff66d4f080 <col:13, col:28> 'int' <IntegralCast>

 | |   `-CallExpr 0x55ff66d4f040 <col:13, col:28> 'size_t':'unsigned int'

 | |    |-ImplicitCastExpr 0x55ff66d4f028 col:13 'size_t (*)(uint)' <FunctionToPointerDecay>

 | |    | `-DeclRefExpr 0x55ff66d4ef90 col:13 'size_t (uint)' Function 0x55ff6685b330 'get_global_id' 'size_t (uint)'

 | |    `-ImplicitCastExpr 0x55ff66d4f068 col:27 'uint':'unsigned int' <IntegralCast>

 | |     `-IntegerLiteral 0x55ff66d4efb0 col:27 'int' 0

 | `-BinaryOperator 0x55ff66d4f2b0 <line:4:5, col:22> 'int' '='

 |  |-ArraySubscriptExpr 0x55ff66d4f121 <col:5, col:8> '__global int' lvalue

 |  | |-ImplicitCastExpr 0x55ff66d4f0f0 col:5 '__global int *' <LValueToRValue>

 |  | | `-DeclRefExpr 0x55ff66d4f0b0 col:5 'global int *' lvalue ParmVar 0x55ff66d4ed10 'c' 'global int *'

 |  | `-ImplicitCastExpr 0x55ff66d4f108 col:7 'int' <LValueToRValue>

 |  |  `-DeclRefExpr 0x55ff66d4f0d0 col:7 'int' lvalue Var 0x55ff66d4ef30 'i' 'int'

 |  `-BinaryOperator 0x55ff66d4f290 <col:12, col:22> 'int' '+'

 |   |-ImplicitCastExpr 0x55ff66d4f260 <col:12, col:15> 'int' <LValueToRValue>

 |   | `-ArraySubscriptExpr 0x55ff66d4f1b0 <col:12, col:15> '__global int' lvalue

 |   |  |-ImplicitCastExpr 0x55ff66d4f180 col:12 '__global int *' <LValueToRValue>

 |   |  | `-DeclRefExpr 0x55ff66d4f140 col:12 'global int *' lvalue ParmVar 0x55ff66d4ec20 'a' 'global int *'

 |   |  `-ImplicitCastExpr 0x55ff66d4f198 col:14 'int' <LValueToRValue>

 |   |   `-DeclRefExpr 0x55ff66d4f160 col:14 'int' lvalue Var 0x55ff66d4ef30 'i' 'int'

 |   `-ImplicitCastExpr 0x55ff66d4f278 <col:19, col:22> 'int' <LValueToRValue>

 |    `-ArraySubscriptExpr 0x55ff66d4f240 <col:19, col:22> '__global int' lvalue

 |     |-ImplicitCastExpr 0x55ff66d4f210 col:19 '__global int *' <LValueToRValue>

 |     | `-DeclRefExpr 0x55ff66d4f1d0 col:19 'global int *' lvalue ParmVar 0x55ff66d4ec98 'b' 'global int *'

 |     `-ImplicitCastExpr 0x55ff66d4f228 col:21 'int' <LValueToRValue>

 |      `-DeclRefExpr 0x55ff66d4f1f0 col:21 'int' lvalue Var 0x55ff66d4ef30 'i' 'int'

 `-OpenCLKernelAttr 0x55ff66d4eed8 line:1:1

从以上输出可以看出，每一行包括AST node的类型，行号、列号以及类型的信息。最顶部一般是TranslationUnitDecl，一个cl/c/cpp文件以及那些#include包括的文件称为翻译单元（TranslaitonUnit）。在上述代码中，FunctionDecl之前的语法树都是解析OpenCL头文件得来的，大多是一些typedef的声明，FunctionDecl表示的是kernel函数add_kernel，里面又嵌套函数参数（ParmVarDecl）、定义语句（DeclStmt）、变量声明（VarDecl)等结构。

clang的AST和其他编译器的AST不同，例如LJMICRO的语法树有一个共同的node节点，其他node节点都是在这个父节点上继承而来，但clang的AST没有共同的节点，取而代之的是三个重要的基类，主要是分为Decl、Stmt、Type。其中Decl表示声明，如函数声明、变量声明、结构声明等都是基于Decl类继承而来；Stmt表示语句，语句中又有声明语句、实现语句、返回语句等；Type用来管理数据类型，包括标准数据类型和自定义的数据类型。另外有些特别的类不由这三种基类继承而来，如CXXBaseSpecifier单独用来表示C++中的基类。

一个翻译单元生成的语法树的所有信息都保存在ASTContext对象中。ASTContext中有一个重要的成员函数getTranslationUnitDecl，获取TranslationUnitDecl（其父类是Decl，DeclContext），这是AST树的顶层（top level）结构，可以通过其decls_begin()/decls_end()遍历其保存的nodes。

AST树的本地化存储和读入借助ASTWriter和ASTReader，Clang还提供了一些高层次的类ASTUnit，将AST树保存为二进制文件，也可以加载AST文件构建ASTContext。

C++

ASTUnit::LoadFromASTFile("input.ast", Diags,opts);

AST基类和派生的子类有一个关键的回调函数HandleTranslationUnit，该函数会在处理完一个翻译单元后每调用，不同的子类完成的任务不一样，其实现也不同，如ASTPrinter类，负责打印输出AST节点信息，其HandleTranslationUnit函数的功能是获取当前翻译单元声明，遍历并打印

C++

void HandleTranslationUnit(ASTContext &Context) override {

   TranslationUnitDecl *D = Context.getTranslationUnitDecl();

   if (FilterString.empty())

     return print(D);

   TraverseDecl(D);

}