LLVM平臺，短短幾年間，改變了眾多編程語言的走向，也催生了一大批具有特色的編程語言的出現，不愧為編譯器架構的王者，也榮獲2012年ACM軟件系統獎 —— 題記 版權聲明：本文為 西風逍遙游 原創文章，轉載請注明出處 西風世界 [http://blog.csdn.net/xfxyy_sxfancy](http://blog.csdn.net/xfxyy_sxfancy) # 語法樹模型的基本結構 上次我們看了Lex和Yacc的翻譯文件，可能一些朋友并不了解其中的執行部分，而且，對這個抽象語法樹是怎么構建起來的還不清楚。今天我們就再詳細介紹一下如果方便的構建一棵抽象語法樹（AST） ### Node節點鏈接的左孩子，右兄弟二叉樹 AST語法樹，由于是一棵多叉樹，直接表示不大好弄，所以我們采用計算機樹中的一個經典轉換，將多叉樹轉換為左孩子右兄弟的二叉樹。  其實思路很簡單，每一層其實就是一個鏈表，將兄弟節點串起來，這樣就可以了。 ~~~ class Node { public: Node(); Node(Node* n); ~Node(); // 構建列表部分 void addChildren(Node* n); void addBrother (Node* n); static Node* make_list(int num, ...); static Node* getList(Node* node); Node* getNext() { return next; } Node* getChild() { return child; } protected: Node* next; Node* child; }; ~~~ 于是我們構建一個Node類，這就是上次我們腳本中看到的那個節點類。是不是很簡單呢？ 另外我們在寫個make_list，方便我們構造一個鏈表，至于怎么寫，我們一會兒再談。 ### 類型支持 我們發現，我們的語法樹還不能保存任何數據，我們寫AST，是為了在每個節點上存儲數據的，有字符串、字符、整數、浮點數、標識符等等。 而且不但有這個要求，更重要的是語法樹能夠方便的構造LLVM語句，所以方便的一個設計就是利用多態，雖然效率或內存占用不像用union那么實在，但確實比較方便。 于是我們建立了一堆類，分別從Node派生，當然Node也需要添加一些功能來判斷當前的節點類型。 Node.h ~~~ enum NodeType // 類型枚舉 { node_t = 0, int_node_t, float_node_t, char_node_t, id_node_t, string_node_t }; class CodeGenContext; class Node { public: Node(); Node(Node* n); // 直接將n作為孩子加入這個節點下 ~Node(); // 構建列表部分 void addChildren(Node* n); void addBrother (Node* n); bool isSingle(); static Node* make_list(int num, ...); static Node* getList(Node* node); void print(int k); // 打印當前節點 Node* getNext() { return next; } Node* getChild() { return child; } virtual Value* codeGen(CodeGenContext* context); LLVM的代碼生成 // 這里負責獲取或設置當前節點的LLVM類型, 未知類型返回NULL virtual Type* getLLVMType(); virtual void setLLVMType(Type* t); // 如果是含有字符串的節點，則返回所含字符串，否則將報錯 std::string& getStr(); // 類型相關 std::string getTypeName(); virtual NodeType getType(); bool isNode(); bool isIntNode(); bool isFloatNode(); bool isIDNode(); bool isStringNode(); bool isCharNode(); protected: virtual void printSelf(); // 打印自己的名字 void init(); Type* llvm_type; Node* next; Node* child; }; ~~~ IDNode.h 是我們的標識符類，就繼承自Node，其他類型同理，我就不一一列舉，詳細代碼請參考 [github上的源碼](https://github.com/sunxfancy/RedApple) ~~~ #include "Node.h" #include <string> using namespace std; class IDNode: public Node { public: IDNode(const char* _value){ this->value = _value; } IDNode(char _value){ this->value = _value; } std::string& getStr() { return value; } virtual Value* codeGen(CodeGenContext* context); virtual NodeType getType(); protected: virtual void printSelf(); private: string value; }; ~~~ ### AST構建中的一個問題 語法樹構建時，有一個特別的問題，主要是因為這里有個地方設計的不大好，我沒有單獨做一個List類型，來存儲孩子元素，而是將其直接打包到Node中了。那么當前正等待構建的節點，是一個元素，還是一個元素列表就很難判斷。于是我制作了一個isSingle函數來判斷當前元素是不是單獨的元素，方法就是檢測其Next指針是否為空即可。如果是單一元素，構建列表時，可以將其直接插入到當前序列的末尾，如果不是，則新建一個Node節點，然后將其孩子指針指向待插入元素。 于是我們的make_list和getList函數就是這樣寫出來的： ~~~ Node* Node::make_list(int num, ...) { va_list argp; Node* para = NULL; Node* ans = NULL; va_start( argp, num ); for (int i = 0; i < num; ++i) { para = va_arg( argp, Node* ); if (!para->isSingle()) para = new Node(para); if ( ans == NULL ) ans = para; else ans->addBrother(para); } va_end( argp ); return ans; } Node* Node::getList(Node* node) { if (!node->isSingle()) return new Node(node); return node; } ~~~ ### 基本的LLVM語句生成 我們構建這么多類的目的是用其生成LLVM語句的，那么我們就先來生成幾個簡單的語句 首先要介紹的是LLVM類型系統的使用，因為LLVM的每條語句都是帶有類型的，LLVM語句可以轉換成Value型指針，那么我們用如下的方法就可以獲取到當前的類型： ~~~ Type* t = value->getType(); ~~~ Type類型也很容易使用，例如獲取其指針就可以： ~~~ PointerType* ptr_type = t->getPointerTo(); ~~~ Type類型中還有很多靜態函數可供生成基本類型： ~~~ // 獲取基本類型 static Type * getVoidTy (LLVMContext &C) static Type * getFloatTy (LLVMContext &C) static Type * getDoubleTy (LLVMContext &C) static Type * getMetadataTy (LLVMContext &C) // 獲取不同長度整形類型 static IntegerType * getInt8Ty (LLVMContext &C) static IntegerType * getInt16Ty (LLVMContext &C) static IntegerType * getInt32Ty (LLVMContext &C) static IntegerType * getInt64Ty (LLVMContext &C) // 獲取指向不同類型的指針類型 static PointerType * getFloatPtrTy (LLVMContext &C, unsigned AS=0) static PointerType * getDoublePtrTy (LLVMContext &C, unsigned AS=0) static PointerType * getInt8PtrTy (LLVMContext &C, unsigned AS=0) static PointerType * getInt16PtrTy (LLVMContext &C, unsigned AS=0) static PointerType * getInt32PtrTy (LLVMContext &C, unsigned AS=0) static PointerType * getInt64PtrTy (LLVMContext &C, unsigned AS=0) ~~~ 我們剛才AST語法樹中的基本類型，其實都是語法中的常量（除了IDNode)，那么這些都應該是生成常量類型 常量類型的基類是Constant，而常用的一般是ConstantInt、ConstantFP和ConstantExpr 下面我們就直接寫出整形、全局字符串、浮點數對應的LLVM代碼 ~~~ Value* IntNode::codeGen(CodeGenContext* context) { Type* t = Type::getInt64Ty(*(context->getContext())); setLLVMType(t); return ConstantInt::get(t, value); } Value* FloatNode::codeGen(CodeGenContext* context) { Type* t = Type::getFloatTy(*(context->getContext())); setLLVMType(t); return ConstantFP::get(t, value); } Value* StringNode::codeGen(CodeGenContext* context) { Module* M = context->getModule(); LLVMContext& ctx = M->getContext(); // 千萬別用Global Context Constant* strConstant = ConstantDataArray::getString(ctx, value); Type* t = strConstant->getType(); setLLVMType(t); GlobalVariable* GVStr = new GlobalVariable(*M, t, true, GlobalValue::InternalLinkage, strConstant, ""); Constant* zero = Constant::getNullValue(IntegerType::getInt32Ty(ctx)); Constant* indices[] = {zero, zero}; Constant* strVal = ConstantExpr::getGetElementPtr(GVStr, indices, true); return strVal; } ~~~ 這里最復雜的應該就屬常量字符串了，首先，常量字符串要用ConstantDataArray::getString類型，然而，往往函數卻不接收一個字符串類型的變量，你需要像C語言一樣，將它的首地址作為參數傳進去，記得我們之前寫過的printf函數的定義么？第一個參數就是一個char*指針。 所以我們這里用一條語句，ConstantExpr::getGetElementPtr，對其取地址，indices是一個數組，第一個值是假設指針是個數組，取數組的第幾位的地址，第二個值是假設指針指向的是一個結構體，取結構體中第幾條元素的地址。 這里我們都傳常量0就可以了。另外一個需要注意的是，這里取地址的常量0好像不能用int64類型，大概是數據范圍太大怕越界吧，一般int32長的數組也夠用了。之前我沒注意，用int64，總出莫名其妙的問題。 ### 附： Node類的完整實現 ~~~ /* * @Author: sxf * @Date: 2015-09-22 19:21:40 * @Last Modified by: sxf * @Last Modified time: 2015-11-01 21:05:14 */ #include "Node.h" #include <stdarg.h> #include <stdio.h> #include "nodes.h" #include <iostream> void Node::init() { llvm_type = NULL; next = child = NULL; } Node::Node() { init(); } Node::Node(Node* n) { init(); addChildren(n); } Node::~Node() { } void Node::addChildren(Node* n) { if (child == NULL) { child = n; } else { child->addBrother(n); } } void Node::addBrother (Node* n) { Node* p = this; while (p->next != NULL) { p = p->next; } p->next = n; } void Node::print(int k) { for (int i = 0; i < k; ++i) printf(" "); printSelf(); printf("\n"); Node* p = child; int t = 0; while (p != NULL) { p->print(k+1); p = p->next; ++t; } if (t >= 3) printf("\n"); } void Node::printSelf() { printf("Node"); } NodeType Node::getType() { return node_t; } bool Node::isSingle() { return next == NULL; } Node* Node::make_list(int num, ...) { va_list argp; Node* para = NULL; Node* ans = NULL; va_start( argp, num ); for (int i = 0; i < num; ++i) { para = va_arg( argp, Node* ); if (!para->isSingle()) para = new Node(para); if ( ans == NULL ) ans = para; else ans->addBrother(para); } va_end( argp ); return ans; } Node* Node::getList(Node* node) { if (!node->isSingle()) return new Node(node); return node; } Type* Node::getLLVMType() { return llvm_type; } void Node::setLLVMType(Type* t) { llvm_type = t; } bool Node::isNode() { return getType() == node_t; } bool Node::isIntNode() { return getType() == int_node_t; } bool Node::isFloatNode() { return getType() == float_node_t; } bool Node::isIDNode() { return getType() == id_node_t; } bool Node::isStringNode() { return getType() == string_node_t; } bool Node::isCharNode() { return getType() == char_node_t; } std::string Node::getTypeName() { switch (getType()) { case node_t: return "Node"; case int_node_t: return "IntNode"; case string_node_t: return "StringNode"; case id_node_t: return "IDNode"; case char_node_t: return "CharNode"; case float_node_t: return "FloatNode"; } } std::string& Node::getStr() { if (this->isStringNode()) { StringNode* string_this = (StringNode*)this; return string_this->getStr(); } if (this->isIDNode()) { IDNode* string_this = (IDNode*)this; return string_this->getStr(); } std::cerr << "getStr() - 獲取字符串錯誤, 該類型不正確：" << getTypeName() << std::endl; exit(1); } ~~~