Clang AST

  • 作者：adolsai
  • 时间：April 2, 2021
  • 分类：Objective-C

LLVM编译器架构

llvm.png

Frontend: 前端

词法分析、语法分析、语义分析、生成中间代码

Optimizer: 优化器

中间代码优化

Backend: 后端

生成机器码

Clang

LLVM项目的一个子项目，基于LLVM架构的C/C++/Objective-C编译器前端。

llvm_clang.png

Clang 不仅仅可以作为一个编译器前端，同时还可以通过库的形式提供代码解析功能，将 C/C++ 程序源码转换为 abstract syntax tree （AST）语法树以及提供相应接口去操作 AST 语法树。

使用Clang 命令输出AST

语法分析，生成语法树(AST，Abstract Syntax Tree):

$ clang -fmodules -fsyntax-only -Xclang -ast-dump test.m

test.m源码：

#include <stdio.h>
void test(int a, int b) {
  int c = a + b -3
}

clang输出：

`-FunctionDecl 0x7fc46e075608 <line:2:1, line:4:1> line:2:6 test 'void (int, int)'
  |-ParmVarDecl 0x7fc46e075488 <col:11, col:15> col:15 used a 'int'
  |-ParmVarDecl 0x7fc46e075508 <col:18, col:22> col:22 used b 'int'
  `-CompoundStmt 0x7fc46e075880 <col:25, line:4:1>
    `-DeclStmt 0x7fc46e075868 <line:3:3, col:19>
      `-VarDecl 0x7fc46e075730 <col:3, col:18> col:7 c 'int' cinit
        `-BinaryOperator 0x7fc46e075848 <col:11, col:18> 'int' '-'
          |-BinaryOperator 0x7fc46e075808 <col:11, col:15> 'int' '+'
          | |-ImplicitCastExpr 0x7fc46e0757d8 <col:11> 'int' <LValueToRValue>
          | | `-DeclRefExpr 0x7fc46e075798 <col:11> 'int' lvalue ParmVar 0x7fc46e075488 'a' 'int'
          | `-ImplicitCastExpr 0x7fc46e0757f0 <col:15> 'int' <LValueToRValue>
          |   `-DeclRefExpr 0x7fc46e0757b8 <col:15> 'int' lvalue ParmVar 0x7fc46e075508 'b' 'int'
          `-IntegerLiteral 0x7fc46e075828 <col:18> 'int' 3

两个简单示例

代码示例1:

1+3*(4-1)+2

AST:

simple_code_ast_1.png

代码示例2:

while (b != 0) {
    if (a > b) {
        a = a - b
    } else {
        b = b - a
    }
}

AST：
simple_code_ast_2.png

AST 结构基础

AST 中的每个节点都是 Decl 或 Stmt 类的一个实例:

  • Decl : 表示声明。Decl 下级还包含不同类型的子类用于标识不同的声明类型；
    例如 FunctionDecl 类用于函数声明，ParmVarDecl 类用于函数参数声明。

  • Stmt : 表示语句（代码块）。同样存在Stmt的子类，对于不同的语句类型；
    例如 IfStmt 用于标识 if 语句, ReturnStmt 类用于标识函数返回。

Example AST

一段演示代码：

//Example.c
#include <stdio.h>
int global;
void myPrint(int param) {
    if (param == 1)
        printf("param is 1");
    for (int i = 0 ; i < 10 ; i++ ) {
        global += i;
    }
}
int main(int argc, char *argv[]) {
    int param = 1;
    myPrint(param);
    return 0;
}

使用Clang输出AST：

|-VarDecl 0x7fdc6300bc88 <line:2:1, col:5> col:5 used global 'int'
|-FunctionDecl 0x7fdc6300be48 <line:3:1, line:9:1> line:3:6 used myPrint 'void (int)'
| |-ParmVarDecl 0x7fdc6300bd68 <col:14, col:18> col:18 used param 'int'
| `-CompoundStmt 0x7fdc64865748 <col:25, line:9:1>
|   |-IfStmt 0x7fdc648654d8 <line:4:5, line:5:28>
|   | |-BinaryOperator 0x7fdc6300bf60 <line:4:9, col:18> 'int' '=='
|   | | |-ImplicitCastExpr 0x7fdc6300bf48 <col:9> 'int' <LValueToRValue>
|   | | | `-DeclRefExpr 0x7fdc6300bf08 <col:9> 'int' lvalue ParmVar 0x7fdc6300bd68 'param' 'int'
|   | | `-IntegerLiteral 0x7fdc6300bf28 <col:18> 'int' 1
|   | `-CallExpr 0x7fdc64865480 <line:5:9, col:28> 'int'
|   |   |-ImplicitCastExpr 0x7fdc64865468 <col:9> 'int (*)(const char *, ...)' <FunctionToPointerDecay>
|   |   | `-DeclRefExpr 0x7fdc6300c3a0 <col:9> 'int (const char *, ...)' Function 0x7fdc6300bf88 'printf' 'int (const char *, ...)'
|   |   `-ImplicitCastExpr 0x7fdc648654c0 <col:16> 'const char *' <NoOp>
|   |     `-ImplicitCastExpr 0x7fdc648654a8 <col:16> 'char *' <ArrayToPointerDecay>
|   |       `-StringLiteral 0x7fdc64865400 <col:16> 'char [11]' lvalue "param is 1"
|   `-ForStmt 0x7fdc64865710 <line:6:5, line:8:5>
|     |-DeclStmt 0x7fdc64865590 <line:6:10, col:20>
|     | `-VarDecl 0x7fdc64865508 <col:10, col:18> col:14 used i 'int' cinit
|     |   `-IntegerLiteral 0x7fdc64865570 <col:18> 'int' 0
|     |-<<<NULL>>>
|     |-BinaryOperator 0x7fdc64865618 <col:22, col:26> 'int' '<'
|     | |-ImplicitCastExpr 0x7fdc64865600 <col:22> 'int' <LValueToRValue>
|     | | `-DeclRefExpr 0x7fdc648655a8 <col:22> 'int' lvalue Var 0x7fdc64865508 'i' 'int'
|     | `-IntegerLiteral 0x7fdc648655e0 <col:26> 'int' 10
|     |-UnaryOperator 0x7fdc64865658 <col:31, col:32> 'int' postfix '++'
|     | `-DeclRefExpr 0x7fdc64865638 <col:31> 'int' lvalue Var 0x7fdc64865508 'i' 'int'
|     `-CompoundStmt 0x7fdc648656f8 <col:37, line:8:5>
|       `-CompoundAssignOperator 0x7fdc648656c8 <line:7:9, col:19> 'int' '+=' ComputeLHSTy='int' ComputeResultTy='int'
|         |-DeclRefExpr 0x7fdc64865670 <col:9> 'int' lvalue Var 0x7fdc6300bc88 'global' 'int'
|         `-ImplicitCastExpr 0x7fdc648656b0 <col:19> 'int' <LValueToRValue>
|           `-DeclRefExpr 0x7fdc64865690 <col:19> 'int' lvalue Var 0x7fdc64865508 'i' 'int'
`-FunctionDecl 0x7fdc648659f0 <line:10:1, line:14:1> line:10:5 main 'int (int, char **)'
  |-ParmVarDecl 0x7fdc64865780 <col:10, col:14> col:14 argc 'int'
  |-ParmVarDecl 0x7fdc648658a0 <col:20, col:31> col:26 argv 'char **':'char **'
  `-CompoundStmt 0x7fdc64865c80 <col:34, line:14:1>
    |-DeclStmt 0x7fdc64865b58 <line:11:5, col:18>
    | `-VarDecl 0x7fdc64865ad0 <col:5, col:17> col:9 used param 'int' cinit
    |   `-IntegerLiteral 0x7fdc64865b38 <col:17> 'int' 1
    |-CallExpr 0x7fdc64865c10 <line:12:5, col:18> 'void'
    | |-ImplicitCastExpr 0x7fdc64865bf8 <col:5> 'void (*)(int)' <FunctionToPointerDecay>
    | | `-DeclRefExpr 0x7fdc64865b70 <col:5> 'void (int)' Function 0x7fdc6300be48 'myPrint' 'void (int)'
    | `-ImplicitCastExpr 0x7fdc64865c38 <col:13> 'int' <LValueToRValue>
    |   `-DeclRefExpr 0x7fdc64865b90 <col:13> 'int' lvalue Var 0x7fdc64865ad0 'param' 'int'
    `-ReturnStmt 0x7fdc64865c70 <line:13:5, col:12>
      `-IntegerLiteral 0x7fdc64865c50 <col:12> 'int' 0

完整语法树：
clang_ast_demo_full.png

Decl — 详细示例

  1. 一个函数的根节点是一个 FunctionDecl 实例

clang_ast_decl_1.png

  1. 一个 FunctionDecl 可以通过一个 ParmVarDecl 来标识参数，注意 ParmVarDecl 与 FunctionDecl 两个类是同级的，都属于 Decl 子类

  2. 函数体是一个 Stmt 实例，其中函数体使用 CompoundStmt 来标识，同样的它也是 Stmt 的一个子类

clang_ast_decl_2.png

  1. VarDecl 用于标识局部和全局变量的声明，注意如果变量声明时有个初始值，那么 VarDecl 就会有一个初始值的子节点

clang_ast_decl_3.png

  1. FunctionDecl、ParmVarDecl 和 VarDecl 都有一个名称和一个声明类型，在遍历节点查找我们想要的代码块是非常好用的

clang_ast_decl_4.png

Stmt — 详细示例

  1. Stmt 用于标识代码语句，包含的子类：

    CompoundStmt类 用来标识代码块

    DeclStmt类 用来标识局部变量声明

    ReturnStmt类 标识函数返回

clang_ast_stmt_1.png

  1. Expr 作为 Stmt 的子类，用于标识表达式：

    CallExpr 标识函数调用

    ImplicitCastExpr 用于标识隐式强转换的类型

    DeclRefExpr 标识引用声明的变量和函数

    IntegerLiteral 用于整型文字

clang_ast_stmt_2.png

  1. Stmt 可能包含一些有着附加信息的子节点，例如 CompoundStmt 标识在一个大括号中代码块的语句，其中的每个语句都是一个包含其他信息的子节点

clang_ast_stmt_3.png

  1. 在包含附加信息的子节点中，例如 CallExpr 函数调用类，它的第一个子元素是函数指针，其他的子元素是函数参数，其他节点同理

clang_ast_stmt_4.png

  1. Expr类 会有一个表达式的类型，例如 CallExpr 中的节点有个 void 的类型。一些 Expr 的子类会包含一个值，例如 初始化的局部或全局变量 IntegerLiteral 子节点，就有一个 1 ‘int’

clang_ast_stmt_5.png

  1. 现在让我们关注下更复杂一点的 myPrint 函数，可以看到在其函数体中包含了 IfStmt 和 ForStmt 两种 Stmt 子类

clang_ast_stmt_6.png

  1. IfStmt 有 4 中子节点:

    条件变量

    条件判断节点

    if 判断的代码段

    Else 的代码段

clang_ast_stmt_7.png

  1. ForStmt 有 5 个子节点:

    1. for 循环判断的初始化语句，for(int i = 0; i < 10; i++)；
    2. VarDecl类标识的 for 的条件变量定义
    3. for 判断条件，for(int i = 0; i < 10; i++)
    4. ++段，for(int i = 0; i < 10; i++)
    5. Stmt 标识 for 中的循环代码块

clang_ast_stmt_8.png

  1. BinaryOperator 二元操作符，存在两个子节点; UnaryOperator 一元操作符，只有一个子节点

clang_ast_stmt_9.png

引用：

Clang AST 基础学习
AST(抽象语法树)超详细

标签：clang, clangast, ast, abstract syntax tree