三、AST相關

抽象語法樹是編譯系統中最常見的一種樹形的中間表示形式，用來對前端語言的源代碼進行規范的抽象表示。不同的高級程序設計語言通過其相應的詞法/語法分析過程，會得到不同形式的抽象語法樹，這些抽象語法樹與編程語言的特征緊密相關，一般都包含了部分語言相關的AST節點表示。從這個角度上來講，AST是編程語言相關的， C語言的源代碼經過C語言特定的詞法/語法分析過程，將生成C語言的AST。

1、AST（抽象語法樹）

在gcc中GENERIC是指規范的AST，，即GENERIC形式的AST均能在gcc/tree. h中所表示的樹節點表示。引入GENERIC的目的是尋找一種與前端語言無關的AST統一表示，是一種通用的處理tree_identifier而已。AST這種樹形的中間表示，主要包括：樹節點的種類及其語義、樹節點的存儲、AST操作以及AST的生成過程等。

1.1 樹結點的聲明

樹節點聲明中最基本的4個概念：

• 標識（TREE_CODE）:DEFTREECODE宏定義中的SYM參數，描述了該節點代表的是一個什么樣的節點。
• 名稱（NAME）:DEFTREECODE宏定義中的NAME參數，表示該樹節點的名稱，使用字符串來描述，主要用來進行AST中間結果的顯示，方便用戶直觀地了解該樹節點的信息。
• 類型（TREE_CODE CLASS, TCC）:DEFTREECODE宏定義中的TYPE參數，描述了該樹節點的TREE_CODE所屬的類型。
• 長度：DEFTREECODE宏定義中的LEN參數，用來描述該樹節點所包含的操作數的數目。

用下面這種宏去定義：

DEFTREECODE (ERROR_MARK, "error_mark", tcc_exceptional, 0)

樹節點的類型主要包括了常量節點、類型節點、聲明節點、比較表達式節點、單目運算表達式節點、雙目運算表達式節點等。

1.2 樹結點的結構

1.2.1 tree_node聯合體

tree_node聯合體定義了全部樹結點結構體。

## gcc/tree-core.h
union GTY ((ptr_alias (union lang_tree_node),desc ("tree_node_structure (&%h)"), variable_size)) tree_node {struct tree_base GTY ((tag ("TS_BASE"))) base;struct tree_typed GTY ((tag ("TS_TYPED"))) typed;
.......
}

1.2.2 tree_base結構體

其中最關鍵的是tree_base結構體：該結構體定義了所有樹節點最基本的屬性，是構成其他樹節點存儲結構的基類（類似于面向對象的概念，這個思想在gcc中大量使用）。其主要包括了code字段，用來存儲TREE_CODE，并標識該樹節點的語義，其取值在枚舉類型enum tree_code中取值。tree_base結構體中還定義了大量的標志字段，分別描述該樹節點的某些語法、語義的信息，例如常量標志、無符號標志、只讀標志等。

struct GTY(()) tree_base {ENUM_BITFIELD(tree_code) code : 16;unsigned side_effects_flag : 1;unsigned constant_flag : 1;unsigned addressable_flag : 1;unsigned volatile_flag : 1;unsigned readonly_flag : 1;unsigned asm_written_flag: 1;unsigned nowarning_flag : 1;unsigned visited : 1;unsigned used_flag : 1;unsigned nothrow_flag : 1;unsigned static_flag : 1;unsigned public_flag : 1;unsigned private_flag : 1;unsigned protected_flag : 1;unsigned deprecated_flag : 1;unsigned default_def_flag : 1;.......
}

1.2.3 tree_common結構體

tree chain字段可以將多個有一定關系的樹節點連接成一個鏈表。tree type字段的值在不同的樹節點中有不同的含義。例如，在所有表達式節點中，type字段指向表達式的類型節點；在指針類型節點（其TREE_CODE為POINTER_TYPE）中，此字段指向指針所指向的類型節點；在數組引用節點（其TREE_CODE為ARRAY_TYPE）中，此字段指向數組元素的類型節點；在TREE_CODE為VECTOR_TYPE的樹節點中，該字段指向向量元素的類型節點。通常使用TREE_TYPE（node）宏來訪問node節點的type字段。

struct GTY(()) tree_typed {struct tree_base base;tree type;
};struct GTY(()) tree_common {struct tree_typed typed;tree chain;/**將多個有一定關系的樹節點連接成一個鏈表/
};

1.2.4 常量結構體

gcc中定義了struct tree_int_cst、struct tree_real_cst、struct tree_fixed_cst、struct tree_vector、struct tree_string、struct tree_complex等幾種結構體，分別存儲整型常量、實數常量、定點數常量、向量常量、字符串常量以及復數常量。

//1、整型常量
struct GTY(()) tree_int_cst {struct tree_typed typed;HOST_WIDE_INT val[1];
};  
//2、實數常量
/*結構體struct tree_real_cst用來存儲實數常量*/
struct GTY(()) tree_real_cst {struct tree_typed typed;struct real_value * real_cst_ptr;
};
//3、定點數常量
struct GTY(()) tree_fixed_cst {struct tree_typed typed;struct fixed_value * fixed_cst_ptr;
};
/*
常用的宏定義：#define TREE_FIXED_CST_PTR(NODE) (FIXED_CST_CHECK (NODE)->fixed_cst.fixed_cst_ptr)#define TREE_FIXED_CST(NODE) (*TREE_FIXED_CST_PTR (NODE))
*/
//4、字符串常量
/*字符串使用struct tree_string結構體來存儲*/
struct GTY(()) tree_string {struct tree_typed typed;int length;char str[1];
};
/*這部分可以分析內存信息：字符串常量節點所描述的字符串常量就存儲在struct tree_string中以str成員指向的地址空間中*/
//5．復數常量
struct GTY(()) tree_complex {struct tree_typed typed;tree real;tree imag;
};
/*
下面兩個宏分別用來訪問該實數常量的實部（real字段）和虛部（imag字段），這兩個字段均為指向樹節點的指針。#define TREE_REALPART(NODE) (COMPLEX_CST_CHECK (NODE)->complex.real)#define TREE_IMAGPART(NODE) (COMPLEX_CST_CHECK (NODE)->complex.imag)
*/
//6、向量常量
struct GTY(()) tree_vector {struct tree_typed typed;tree GTY ((length ("TYPE_VECTOR_SUBPARTS (TREE_TYPE ((tree)&%h))"))) elts[1];    //用以獲取節點的各個向量
};

1.2.5 標識符節點

標識符節點使用struct tree_identifier結構體存儲，定義如下：

struct GTY(()) tree_identifier {struct tree_common common;/*struct tree_common common結構體字段描述了該樹節點的基本屬性。*/struct ht_identifier id;
};struct GTY(()) ht_identifier {const unsigned char *str;unsigned int len;unsigned int hash_value;
};

上述的struct ht_identifier在libcpp/include/symtab.h中予以定義，該結構體中的str和len字段分別描述該標識符對應的字符串名稱及其長度，hash_value是該標識符名稱的一個hash值，該hash值在標識符的查找、比較等操作中使用。

注：AST是源代碼在GCC系統中的一種中間表示形式，該中間形式是通過GCC前端的詞法/語法分析所構造的。

其他的樹結點的結構不做詳細介紹，有興趣可自行查看。

2、符號綁定,作用域與block樹節點

2.1 lang_identifier結構體

在前面已知gcc中通過一個tree_identifier結構體來代表一個標識符的樹節點，但實際分配時會為標識符分配一個擴展的lang_identifier節點，其結構如下:

struct GTY(()) lang_identifier {struct