C和C++的面向对象专题（8）——更为高级的预处理器PHP

本专栏文章列表

一、何为面向对象

二、C语言也能实现面向对象

三、C++中的不优雅特性

四、解决封装，避免接口

五、合理使用模板，避免代码冗余

六、C++也能反射

七、单例模式解决静态成员对象和全局对象的构造顺序难题

八、更为高级的预处理器PHP

九、Gtkmm的最佳实践

本系列文章由 西风逍遥游 原创，转载请注明出处：西风广场 http://sunxfancy.github.io/

八、更为高级的预处理器PHP

C++的宏在某些情况下非常难用，例如将代码展开成为这样：

Macro( A, B, C, D )

=>

func(“A”, A);
func(“B”, B);
func(“C”, C);
func(“D”, D);

test(A);
test(B);
test(C);
test(D);

这对于宏来说，太困难了，为了能实现复杂的宏展开，我们希望用更高级的预处理器来实现该功能。

我们这里使用PHP进行代码的预处理工作，将PHP代码当做C++的宏使用。
当然，你也可以用python做代码生成工作，但由于php是内嵌式的，处理起来可能更方便一些，当然，其他语言配上模板也是可以的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* main.php */
<?php $return_m = "return a + b;" ?>

#include <iostream>

using namespace std;

int func(int a, int b) {
    <?php echo $return_m; ?> 
}
int main() {
    cout << func(1, 2) << endl;
    return 0;
}

我们用如下指令生成C++代码：

php main.php > main.cpp

好的，下面就和正常的项目编译一样了，你甚至可以将php的命令写入到makefile中，自动化生成

C和C++的面向对象专题（9）——Gtkmm的最佳实践

本专栏文章列表

一、何为面向对象

二、C语言也能实现面向对象

三、C++中的不优雅特性

四、解决封装，避免接口

五、合理使用模板，避免代码冗余

六、C++也能反射

七、单例模式解决静态成员对象和全局对象的构造顺序难题

八、更为高级的预处理器PHP

九、Gtkmm的最佳实践

本系列文章由 西风逍遥游 原创，转载请注明出处：西风广场 http://sunxfancy.github.io/

九、Gtkmm的最佳实践

在跨平台的gui开发中，Qt一直是非常受欢迎的GUI开发框架，但Qt一个是依赖反射，需要特殊的预处理步骤，一个是库太过庞大，这就造成了一些不便的地方。今天介绍给大家的是Gtk库的C++绑定，Gtkmm，一个方便的跨平台GUI开发框架。

由于是C++的封装，GTK不再那么的难以使用，变得简洁优雅，而且效率非常高，编译也较QT快许多。
虽然C也能编写，而且我们之前也介绍过了GObject的使用。但比较其实现起来较为繁琐，代码行数较C++多一些，而且每个成员函数都要手动传入this指针，较为不便。

现在C++如果合理的封装和按照之前的设计思想进行设计，结构十分紧凑，而且书写非常方便，非常易用。

Gtkmm版的2048程序设计

为了更好的实践，我们举一个简单的2048小游戏的程序作为实例。大家会发现，合理的设计，能够使代码既清晰明了，又方便维护，可靠性很高。
我们简要的进行一下程序设计，这里我们不是要学会2048如何制作，而是要体会程序设计中的思想，以及设计中的美感和艺术感。

首先，2048作为一个简单的小游戏，广受大家喜欢，原理很简单，在一个4×4的数组中，让数字不断向各个方向合并，每次进行后，随机位置创建新数字。

程序界面，一个窗口，上面一行标签书写当前得分，下面一个绘图界面，自由绘图，画上4×4个的矩阵，上面书写内容。

程序结构设计，按照一般程序架构设计，可以用MVC的结构，一个界面类，负责显示，一个控制类，负责游戏逻辑，一个模型类，负责数据的存储与管理。

但由于数据的管理太过简单，就放弃了模型类，直接使用一个4×4的矩阵就完成任务。

程序实践

由于Gtkmm的良好封装，我们并不需要太多复杂的处理，首先是Main文件引导程序的启动，所有gtk程序集合都是这样引导。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 
* @Author: sxf
* @Date:   2015-05-07 12:22:40
* @Last Modified by:   sxf
* @Last Modified time: 2015-05-20 21:58:16
*/

#include <gtkmm.h>
#include "game.h"
int main(int argc, char *argv[])
{
    Glib::RefPtr<Gtk::Application> app = Gtk::Application::create(argc, argv, "org.abs.gtk2048");

    Game game;
    //Shows the window and returns when it is closed.
    return app->run(game);
}

Game类作为最核心的窗口类，也是游戏的主要控制类，并不需要暴露什么方法给外部成员使用，所以它的定义很简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/* 
* @Author: sxf
* @Date:   2015-05-19 11:20:42
* @Last Modified by:   sxf
* @Last Modified time: 2015-05-20 21:58:35
*/

#ifndef GAME_H
#define GAME_H

#include <gtkmm/window.h>

class Game_private;
class Game : public Gtk::Window
{
public:
    Game();
    virtual ~Game();

private:
    Game_private* priv;
};


#endif // GAME_H

这种写法，就是在前几章提到的增强代码封装性的方法，通过一个priv指针，解决了C++封装不完善的问题。

这样还有一个很大的好处就是，由于priv指针的书写较为繁琐，如果在public方法中，反复的通过priv指针调用函数，就会显得无比麻烦，但这正提醒你，你的写法有问题，因为一般的方法，要尽可能写成内部的private的，这样你在不自觉的时刻，就形成了最大化private方法，最小化接口的设计习惯，这对于提升程序的内聚性，很有意义。

于是我们的Game类的内部定义就变得十分复杂，但这就使得代码内聚性更高，暴露给外层的接口就更简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Game_private
{
public:
    Game_private(Game* game);
    ~Game_private();
    
 	Game* game;
    MyArea m_area;		// 渲染类
    Gtk::Box m_box;		// 布局控件
    Gtk::Label m_score;	// 得分标签
    int score;			// 得分具体数字
    const static int fx[4][2];

    int data[4][4];		// 数据模型

    bool combine(int i, int j, int k); 	// 将一个位置的数字向下合并

    bool randomNew();	// 随机创建新数字

    void cleanData();	// 删除全部数字，用来开局初始化

    void gameWin();		// 显示用户胜利

    void gameOver();	// 显示游戏结束

    void gameRun(int k);	// 游戏控制循环

    bool on_key_press_event(GdkEventKey* event); // 监听键盘事件响应
};

我不喜欢比脸还长的函数，但这里的函数设计的还是不是那么尽如人意，虽然如此，这里也是本着简单易懂的方式设计的。

这里的combine方法设计的很特殊，因为合并时，还有可能出现游戏胜利的情况，所以里面包含了判断胜利的条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bool combine(int i, int j, int k) {
    int ni = i; int nj = j;
    ni += fx[k][0];	// fx是方向数组
    nj += fx[k][1];
    int obji = i, objj = j;
    while ( 0 <= ni && ni < 4 &&
            0 <= nj && nj < 4 )		
    // 防止越界，我这里比较贪便宜，很多人处理越界是通过在数组外增加一个特殊值的外边框来处理的
    {
        if (data[ni][nj] == 0) {
            obji = ni; objj = nj;
        } else {
            if (data[ni][nj] == data[i][j]) {
                score += (1 << data[ni][nj]);	// 处理得分
                ++data[ni][nj];
                data[i][j] = 0;
                if (data[ni][nj] == 12) return true; // 处理胜利条件
                return false;
            } else break;
        }
        ni += fx[k][0];
        nj += fx[k][1];
    }
    if (!(obji == i && objj == j)) {	// 未能合并的情况
        data[obji][objj] = data[i][j];
        data[i][j] = 0;
    }
    return false;
}

这个函数设计的很健壮，考虑了许多边界条件，这么做是在模拟物体碰撞时，碰撞面不断挤压的情况。例如下面的情况：
1 1 2 4
0 0 0 0
0 0 0 0
0 0 0 0
向左合并，能够一次就被合成为8，但这也是和外层的合并顺序控制是分不开的
在游戏主循环控制时，是这样处理的，对于不同的方向，循环顺序是不一样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
void gameRun(int k) {
        bool winflag = false;
        switch (k) {
            case 0 : 
                for (int i = 0; i < 4; ++i)
                    for (int j = 0; j < 4; ++j)
                        if (combine(i,j,k)) winflag = true;
            break;
            case 1 : 
                for (int j = 3; j >= 0; --j)
                    for (int i = 0; i < 4; ++i)
                        if (combine(i,j,k)) winflag = true;
            break;
            case 2 : 
                for (int i = 3; i >= 0; --i)
                    for (int j = 0; j < 4; ++j)
                        if (combine(i,j,k)) winflag = true;
            break;
            case 3 : 
                for (int j = 0; j < 4; ++j)
                    for (int i = 0; i < 4; ++i)
                        if (combine(i,j,k)) winflag = true;
            break;
        }

        // 判断胜负条件
        if (winflag) {
            gameWin();
            return;
        }
        if (!randomNew()) {
            gameOver();
        }

        Glib::RefPtr<Gdk::Window> win = game->get_window();
        if (win)
        {
            m_area.setData(data);
            Gdk::Rectangle r(0, 0, 600, 600);
            win->invalidate_rect(r, false);
            m_area.show();
            char score_text[20]; memset(score_text, 0, 20);
            sprintf(score_text, "Score : %d", score);
            m_score.set_text(score_text);
        }
    }

而创建新数字的方式也很清晰，但这里使用模拟栈的方式进行了处理。
设计很独特，由于目前的位置数目有限，直接rand的方式，效率较低，我们先扫描所有可能的位置，然后将其入栈，random时，直接找一个位置，然后直接随机从其中找一个就可以了。数组模拟栈的方式，主要是希望避免vector的低效率，实现较简易。而且扩展较方便，如果你想random跟多，修改起来也十分方便。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool randomNew() {
    int empty_block[17][2]; int sum = 0;
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            if (data[i][j] == 0) {
                empty_block[sum][0] = i; 
                empty_block[sum][1] = j;
                ++sum;
            }
        }
    }
    if (sum < 1) return false;

    int t = rand() % sum;
    data[ empty_block[t][0] ][ empty_block[t][1] ] = (rand() % 4) < 3 ? 1 : 2;
    empty_block[t][0] = empty_block[sum-1][0];
    empty_block[t][1] = empty_block[sum-1][1]; 
    --sum;
    
    return true;
}

渲染类十分简单，主要就是根据数组中的数值，渲染出对应的图像，设计思想就是不断将问题抽象，不断简化，将复杂的问题从上层一层层拨开，这样就使得结构更加简洁优雅。

整个项目完整代码已经放到Github上了，需要的可以参考：
【github仓库】

C和C++的面向对象专题（1）——何为面向对象

面向对象是一种思想，而不是一门语言
我们上哪去找对象，都面向对象去了

本专栏文章列表

一、何为面向对象

二、C语言也能实现面向对象

三、C++中的不优雅特性

四、解决封装，避免接口

五、合理使用模板，避免代码冗余

六、C++也能反射

七、单例模式解决静态成员对象和全局对象的构造顺序难题

八、更为高级的预处理器PHP

九、Gtkmm的最佳实践

本系列文章由 西风逍遥游 原创，转载请注明出处：西风广场 http://sunxfancy.github.io/

一、何为面向对象

现在学软件开发，都讲面向对象的编程模型，其实也很简单。用一句话来总结，面向对象就是将方法和方法的属性整合在一起，让每个方法引用的属性值尽可能在对象内部，对外保持简洁的接口。

实现面向对象的设计，目标不是写类，而是设计结构，对每一个对象设计良好的接口和封装模式，将优雅的接口提供给使用者，最大程度的降低代码耦合。

面向对象的设计，可以用一本书来讲解，但我们这里将演示面向对象的基本思想和如何实现

从一个简单的例子看对象

恩，那好，我们现在构建一个对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class window {
public:
    window(int x, int y, int width, int height) {
        this.x = x; this.y = y;
        this.width = width;
        this.height = height;
    }
    void Show();

private:
    int x, y, width, height;

    // 也许你还可以添加更多属性，例如透明度、子元素列表、菜单、状态栏等待
};

这是一个基本的窗口对象，也许它并不能给你直观的印象，但我希望能通过其说明一些问题。
对象有公开方法，有私有属性，我们在构造这个对象的时候，将一些参数传入，那么我们发现，这个过程简化了我们对于某些方法的使用。

例如在C函数中，如何你希望绘制一些内容，那么你可能需要做的是写这样一个函数：

int Draw(struct window*, int, int, int, int);

将全部的参数传入进去，但如果使用次数多后，我们发现参数大多一样，那么不如把他们都打包进入window结构体中，于是函数变成了这样：

int Draw(struct window*);

这样我们只需要改变结构体中的值就可以了，这个思想，就是面向对象的基础，而C++正是让这要传入的结构体自动传入，进而演变为了this指针。

面向对象的设计原则

几乎软件的设计原则都是高内聚，低耦合。

C++的设计也是一样，类的公共方法应该尽可能清晰明确，简单好用，而不必要外部了解的信息，和细节过程，都放入到私有成员中，避免被误用。

避免过度继承和重载，虽然继承和重载很大程度上能够降低两个模块间的耦合，但其实现复杂，结构混乱，容易使得代码不够清晰。同样，也要避免设计模式的滥用。

C++的开发应该本着面向对象的思想，利用类的封装特性，将模块内部的部分高效的组织在一起，而接口，可以采用多态调用的方式，保证灵活性。

编译器架构的王者LLVM——（8）函数的调用及基本运算符

LLVM平台，短短几年间，改变了众多编程语言的走向，也催生了一大批具有特色的编程语言的出现，不愧为编译器架构的王者，也荣获2012年ACM软件系统奖 —— 题记

版权声明：本文为 西风逍遥游 原创文章，转载请注明出处 西风世界 http://blog.csdn.net/xfxyy_sxfancy

函数的调用及基本运算符

之前我们提到了函数的定义，那么，定义好的函数如何调用才行呢？今天我们就来了解一下，函数的调用。

函数调用的宏形式

我们去读之前对函数调用的语法树翻译形式：

1
printf("%d\n", y);

会被翻译为：

1
2
3
4
5
Node
             String call
             String printf
             String %d\n
             ID y

这个宏的名字是call，是个不定参数的：

1
(call 函数名 参数表... )

于是我们就需要扫描参数表，获取全部调用参数。

调用宏的基本形式

调用宏其实很简单，就是不断循环判断有多少参数即可。

1
2
3
4
5
6
7
8
static Value* call_macro(CodeGenContext* context, Node* node) {
    // 参数一 函数名
    
    // 其余参数 要传入的参数
    for (Node* p = node->getNext(); p != NULL; p = p->getNext()) {
        // 循环获取参数
    }
}

另外我们查阅一下LLVM的文档，找到其中CallInst这个指令，LLVM的指令都派生自Instruction，可以发现构建的方法很简单：

1
static CallInst * Create (Value *Func, ArrayRef< Value * > Args, const Twine &NameStr, BasicBlock *InsertAtEnd)

但是我们发现，Value中要传输的是一个Function对象，如何获取呢？当然还是从符号表中获取，我们下次会讲符号表的实现，这次也和上节一样，将接口先写出来。

1
2
3
4
5
6
7
// 参数一 函数名
Value* func = context->getFunction(node);
if (func == NULL) {
    errs() << "找不到函数的定义：";
    errs() << node->getStr().c_str() << "\n";
    exit(1);
}

函数调用在生成时，如果这个函数还没有被扫描到，那么在生成时会报函数定义找不到的问题，这就是我们为什么要用多遍扫描。只有充分的多次扫描语法树，才能获取每个函数后面的函数定义。虽然像C语言那样强制声明也可以，但我个人不大喜欢这种风格。

至于参数的获取，就十分简单的，但有一点要注意，参数是递归生成的，例如：

1
printf("%d", add(3, 5));

这时，我们在获取参数时，就会发现，其中一个参数是表达式，那么我们就要先对其进行处理：

1
2
3
4
5
6
7
// 其余参数 要传入的参数
std::vector<Value*> args;
for (Node* p = node->getNext(); p != NULL; p = p->getNext()) {
    Value* v = p->codeGen(context); // 递归地生成参数
    if (v != NULL)
        args.push_back(v);
}

Node类下面有实现codeGen方法，其作用就是重新调用了完整的对当前节点的代码生成，方便递归调用：

1
2
3
Value* Node::codeGen(CodeGenContext* context) {
    return context->MacroMake(this); // MacroMake是核心的代码生成接口
}

于是我们递归地生成了这些代码，就可以产生一条Call语句，那么别忘记将其返回给上一层：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static Value* call_macro(CodeGenContext* context, Node* node) {
    // 参数一 函数名
    Value* func = context->getFunction(node);
    if (func == NULL) {
        errs() << "找不到函数的定义：";
        errs() << node->getStr().c_str() << "\n";
        exit(1);
    }

    // 其余参数 要传入的参数
    std::vector<Value*> args;
    for (Node* p = node->getNext(); p != NULL; p = p->getNext()) {
        Value* v = p->codeGen(context);
        if (v != NULL)
            args.push_back(v);
    }

    CallInst *call = CallInst::Create(func, args, "", context->getNowBlock());
    return call;
}

简单运算符计算

对于计算机，加减乘除这些基本运算，就是几个指令而已，但对于编译器，却也要分好几种情况讨论，因为，全部的运算符有这么多：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Standard binary operators...
 FIRST_BINARY_INST( 8)
HANDLE_BINARY_INST( 8, Add  , BinaryOperator)
HANDLE_BINARY_INST( 9, FAdd , BinaryOperator)
HANDLE_BINARY_INST(10, Sub  , BinaryOperator)
HANDLE_BINARY_INST(11, FSub , BinaryOperator)
HANDLE_BINARY_INST(12, Mul  , BinaryOperator)
HANDLE_BINARY_INST(13, FMul , BinaryOperator)
HANDLE_BINARY_INST(14, UDiv , BinaryOperator)
HANDLE_BINARY_INST(15, SDiv , BinaryOperator)
HANDLE_BINARY_INST(16, FDiv , BinaryOperator)
HANDLE_BINARY_INST(17, URem , BinaryOperator)
HANDLE_BINARY_INST(18, SRem , BinaryOperator)
HANDLE_BINARY_INST(19, FRem , BinaryOperator)

// Logical operators (integer operands)
HANDLE_BINARY_INST(20, Shl  , BinaryOperator) // Shift left  (logical)
HANDLE_BINARY_INST(21, LShr , BinaryOperator) // Shift right (logical)
HANDLE_BINARY_INST(22, AShr , BinaryOperator) // Shift right (arithmetic)
HANDLE_BINARY_INST(23, And  , BinaryOperator)
HANDLE_BINARY_INST(24, Or   , BinaryOperator)
HANDLE_BINARY_INST(25, Xor  , BinaryOperator)

这些定义很难找，在文档中并没有真正写出来，而是在头文件的llvm/IR/Instruction.def里面，这是宏定义的专属部分。
这些还仅仅是数值运算，还不算比较运算的部分呢。

当然，这和计算机体系结构有关，浮点数的运算和整数肯定是不一样的，而我们知道，右移位也分算数右移和逻辑右移。所以必然，会有大量不同的运算符。

创建指令则很简单：

1
static BinaryOperator * Create (BinaryOps Op, Value *S1, Value *S2, const Twine &Name, BasicBlock *InsertAtEnd)

两个运算数，可以是常量，也可以是变量load出值后，还可以是表达式返回值，只要两个Value调用getType，符合运算规则，就可以。
注意，浮点数不能直接和整数运算，必须先将整形转为浮点才可以。

于是以下是简单的运算符操作，我只写了整数的运算操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static Value* opt2_macro(CodeGenContext* context, Node* node) {
    std::string opt = node->getStr();

    Node* op1 = (node = node->getNext());
    if (node == NULL) return NULL;
    Node* op2 = (node = node->getNext());
    if (node == NULL) return NULL;

    Instruction::BinaryOps instr;
    if (opt == "+") { instr = Instruction::Add;  goto binOper; }
    if (opt == "-") { instr = Instruction::Sub;  goto binOper; }
    if (opt == "*") { instr = Instruction::Mul;  goto binOper; }
    if (opt == "/") { instr = Instruction::SDiv; goto binOper; }

    // 未知运算符
    return NULL;

binOper:
    return BinaryOperator::Create(instr, op1->codeGen(context), 
        op2->codeGen(context), "", context->getNowBlock());

附：文档参考及源代码

CallInst类参考
BinaryOperator类参考
github源码-函数调用及基本运算符

编译器架构的王者LLVM——（10）变量的存储与读取

LLVM平台，短短几年间，改变了众多编程语言的走向，也催生了一大批具有特色的编程语言的出现，不愧为编译器架构的王者，也荣获2012年ACM软件系统奖 —— 题记

版权声明：本文为 西风逍遥游 原创文章，转载请注明出处 西风世界 http://blog.csdn.net/xfxyy_sxfancy

变量的存储与读取

变量是一款编程语言中的核心，说编译语言是一种符号处理工具，其实是有些道理的。栈式符号表可以方便的记录编译过程中的变量和语法符号，我们上节已经了解了其中的实现方法。那么，还有没有其他的办法能够简单的实现变量的存取呢？

LLVM的内置符号表

其实LLVM还提供了一个内部符号表，这个和我们的符号表不一样，它的符号是以函数为界的，函数内的是局部符号，外面的是全局符号。这个符号表的作用，主要是供LLVM找到各个底层的语法元素而设计的，所以它的功能较为有限。

例如下面这段字节码：

1
2
3
4
define void @print(i64 %k1) {
entry:
    ...
}

我们可以通过符号表，找到k1这个元素。

这个符号表的获取也很简单，只要你有basicblock，你就能够找到这个符号表的指针：

1
2
3
BasicBlock* bb = context->getNowBlock();
   ValueSymbolTable* st = bb->getValueSymbolTable();
   Value* v = st->lookup(value);

栈上变量空间的分配，AllocaInst语句

AllocaInst是LLVM的一条标准语句，负责栈上空间的分配，你无需考虑栈的增长的操作，它会自动帮你完成，并返回给你对应空间的指针。

千万不要认为这个语句能够动态分配堆内存，堆内存实际上是通过调用Malloc语句来分配的。

1
%k = alloca i64

以上语句，会让k的类型变为你分配类型的指针。

这个语句的C++接口非常的好用，像这样：

1
AllocaInst *alloc = new AllocaInst(t, var_name, context->getNowBlock());

t对应分配的类型，var_name对应语句返回的那个变量名（上面的‘k’），最后一个参数当然是插入的basicblock。

这时，返回的语句，就代表k这个指针了。

变量的存储

LLVM中，变量的存储，都需要知道要存储地址的指针，注意，一定是指针，而不是值。

原型：

1
StoreInst (Value *Val, Value *Ptr, bool isVolatile, BasicBlock *InsertAtEnd)

使用示例：

1
new StoreInst(value2, value1, false, context->getNowBlock());

这个value1，就是目标的存储指针，而value2则是要放入的值。false表示不是易变的，这个参数相当与C语言中的volatile关键字，主要是防止这个变量在重复读取时的编译器优化。因为一般的编译器优化，都会将一个变量在没有改变情况下的多次读取，认为取到同一个值，虽然这在多线程和硬中断的环境下并不成立。

变量的读取

变量的读取，就用Load语句：

1
LoadInst (Value *Ptr, const Twine &NameStr, bool isVolatile, unsigned Align, BasicBlock *InsertAtEnd)

使用示例：

1
new LoadInst(v, "", false, bb);

我们这里暂时没有考虑内存对齐的问题，当然，一般在Clang中，都是4字节对齐的。我们注意到，其实Load语句也是从指针中取值的，返回的则是一个值类型。

打造一个赋值语句

赋值语句其实是一个挺尴尬的语句，左边要赋值的，应该是一个指针地址，而右边的部分，则应该是一个获取到的值。而之前我们的运算，函数调用等等，绝大部分都是依赖值类型的。

我们先要为变量实现一个值的获取，这部分因为很通用，我们放到IDNode节点的代码生成中：

1
2
3
4
5
6
7
8
9
10
11
Value* IDNode::codeGen(CodeGenContext* context) {
    BasicBlock* bb = context->getNowBlock();
    ValueSymbolTable* st = bb->getValueSymbolTable();
    Value* v = st->lookup(value);
    if (v == NULL || v->hasName() == false) {
        errs() << "undeclared variable " << value << "\n";
        return NULL;
    }
    Value* load = new LoadInst(v, "", false, bb);
    return load;
}

value是我们类的成员变量，记录的是变量名。

然而赋值语句有时还会要求获取到的是指针，不是值，现在我们要为赋值语句实现一个符号指针的获取：

1
2
3
4
5
6
7
8
9
10
11
12
Value* IDNode::codeGen(CodeGenContext* context) {
    BasicBlock* bb = context->getNowBlock();
    ValueSymbolTable* st = bb->getValueSymbolTable();
    Value* v = st->lookup(value);
    if (v == NULL || v->hasName() == false) {
        errs() << "undeclared variable " << value << "\n";
        return NULL;
    }
    if (context->isSave()) return v; // 我们在上下文类中记录了一个变量，看当前状态是存还是取
    Value* load = new LoadInst(v, "", false, bb);
    return load;
}

那么我们在调用时，只需要这样做：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static Value* opt2_macro(CodeGenContext* context, Node* node) {
    std::string opt = node->getStr();

    Node* op1 = (node = node->getNext());
    if (node == NULL) return NULL;
    Node* op2 = (node = node->getNext());
    if (node == NULL) return NULL;

    if (opt == "=") {
        context->setIsSave(true); // 这两句设置的目前是为下面的节点解析时,返回指针而不是load后的值
        Value* ans1 = op1->codeGen(context);
        context->setIsSave(false);
        Value* ans2 = op2->codeGen(context);
        return new StoreInst(ans2, ans1, false, context->getNowBlock());
    }

    ...
}

其实我们这里也可以单独实现一个函数来处理这个功能，但由于两个函数功能太像，所以也不怎么想添加一个类似的函数了。
这个部分暂时先这样处理一下，待整体结构完善后，应该有更好的实现方法。

编译器架构的王者LLVM——（1）现代编译器架构

LLVM平台，短短几年间，改变了众多编程语言的走向，也催生了一大批具有特色的编程语言的出现，不愧为编译器架构的王者，也荣获2012年ACM软件系统奖 —— 题记

现代编译器架构

编译器技术，作为计算机科学的皇后，从诞生起，就不断推进着计算机科学的发展，编译器的发展史，简直就是计算机发展史的缩影，而编译器的架构也逐句变得更加优雅，独立性更强。

但说到编译器的架构，可能还留存着编译原理课程的印象，5个经典流程：
词法分析 -> 语法分析 -> 语义分析 -> 中间代码优化 -> 目标代码生成

一般，我们会将编译器分为一个前端，一个后端，前端负责处理源代码，后端负责生成目标代码。
但软件工程，就是在不断的抽象和分层，分层解决问题是重要的特点，分层能够增加层之间的独立性，更好的完成任务。

LLVM中间代码优化

LLVM的一大特色就是，有着独立的、完善的、严格约束的中间代码表示。这种中间代码，就是LLVM的字节码，是LLVM抽象的精髓，前端生成这种中间代码，后端自动进行各类优化分析，让用LLVM开发的编译器，都能用上最先见的后端优化技术。

LLVM另外一大特色就是自带JIT，要知道，这可是在原来很难想象的技术，一个编译器要想实现JIT，是需要进行大量努力的，即时翻译代码，还要兼顾效率和编译时间，可不是一件简单的事情。
但如果你用上了LLVM，JIT只是其中的副产品，直接就可以使用的。

LLVM将中间代码优化这个流程做到了极致，LLVM工具链，不但可以生成所支持的各个后端平台的代码，更可以方便的将各语言的前端编译后的模块链接到一起，你可以方便的在你的语言中调用C函数。

可读的中间代码

LLVM中间代码是非常易读的，而且拥有很多高级结构，例如类型和结构体、元数据等，使用起来非常方便。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
; Declare the string constant as a global constant.
@.str = private unnamed_addr constant [13 x i8] c"hello world\0A\00"

; External declaration of the puts function
declare i32 @puts(i8* nocapture) nounwind

; Definition of main function
define i32 @main() {   ; i32()*
  ; Convert [13 x i8]* to i8  *...
  %cast210 = getelementptr [13 x i8], [13 x i8]* @.str, i64 0, i64 0

  ; Call puts function to write out the string to stdout.
  call i32 @puts(i8* %cast210)
  ret i32 0
}

; Named metadata
!0 = !{i32 42, null, !"string"}
!foo = !{!0}

这是一段HelloWorld的LLVM字节码，我们发现很清晰，而且几乎所有的位置都有注明类型，这也是在强调，LLVM是强类型的，每个变量和临时值，都要有明确的类型定义。

下面是结构体的声明：

1
%mytype = type { %mytype*, i32 }

非常遗憾的是，这个结构体的定义只有类型序列信息，没有对应子成员的名称，这是让编译器前端自行保存和查表，来记录这些信息。

C函数的调用非常方便，只需要简单的声明

1
2
declare i32 @printf(i8* noalias nocapture, ...)
declare i32 @atoi(i8 zeroext)

你可以将源码用LLVM编译成.bc，然后用llc编译成.o，再拿Clang链接上各个库就可以了。

编译器架构的王者LLVM——（2）开发LLVM项目

LLVM平台，短短几年间，改变了众多编程语言的走向，也催生了一大批具有特色的编程语言的出现，不愧为编译器架构的王者，也荣获2012年ACM软件系统奖 —— 题记

开发LLVM项目

介绍了LLVM这么多，那么我们能用LLVM做一款自己的编程语言么？答案是，有点难度，但不是不可行。只要你熟悉C++编程，而且有足够的热情，那么就没有什么能阻止你了。

下面我就来介绍一下，LLVM项目的基本方法。
需要的东西： LLVM平台库，文档，CMAKE，C++编译器

环境搭建

首先我的系统是Ubuntu14.04，我就介绍Ubuntu下的配置方法了，用Windows的朋友就不好意思了。
安装llvm-3.6及其开发包：

1
sudo apt-get install llvm-3.6*

一般是推荐将文档和示例都下载下来的，因为比较这些对应版本的参考很重要，很多网上的代码，都是特定版本有效，后来就有API变更的情况。
所以大家一定注意版本问题，我开发的时候，源里面的版本最高就3.6，我也不追求什么最新版本，新特性什么的，所以声明一下，本系列教程的LLVM版本均为3.6版，文档参考也为3.6版。

1
sudo apt-get install clang cmake

clang编译器，我个人感觉比gcc好用许多倍，而且这个编译器就是用llvm作为后端，能够帮助我们编译一些C代码到LLVM中间码，方便我们有个正确的中间码参考。

CMAKE管理项目

CMake作为C++项目管理的利器，也是非常好用的一个工具，这样我们就不用自己很烦的写Makefile了，

下面是一个CMake示例，同时还带有FLex和Bison的配置：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
cmake_minimum_required(VERSION 2.8)
project(RedApple)

set(LLVM_TARGETS_TO_BUILD X86)
set(LLVM_BUILD_RUNTIME OFF)
set(LLVM_BUILD_TOOLS OFF)

find_package(LLVM REQUIRED CONFIG)
message(STATUS "Found LLVM ${LLVM_PACKAGE_VERSION}")
message(STATUS "Using LLVMConfig.cmake in: ${LLVM_DIR}")

find_package(BISON)
find_package(FLEX)

SET (CMAKE_CXX_COMPILER_ENV_VAR "clang++")
SET (CMAKE_CXX_FLAGS "-std=c++11")
SET (CMAKE_CXX_FLAGS_DEBUG   "-g")
SET (CMAKE_CXX_FLAGS_MINSIZEREL  "-Os -DNDEBUG")
SET (CMAKE_CXX_FLAGS_RELEASE  "-O4 -DNDEBUG")
SET (CMAKE_CXX_FLAGS_RELWITHDEBINFO "-O2 -g")

SET(EXECUTABLE_OUTPUT_PATH ${PROJECT_SOURCE_DIR}/bin)

include_directories(${LLVM_INCLUDE_DIRS})
add_definitions(${LLVM_DEFINITIONS})

FLEX_TARGET(MyScanner ${CMAKE_CURRENT_SOURCE_DIR}/src/redapple_lex.l
                      ${CMAKE_CURRENT_BINARY_DIR}/redapple_lex.cpp COMPILE_FLAGS -w)
BISON_TARGET(MyParser ${CMAKE_CURRENT_SOURCE_DIR}/src/redapple_parser.y
                      ${CMAKE_CURRENT_BINARY_DIR}/redapple_parser.cpp)
ADD_FLEX_BISON_DEPENDENCY(MyScanner MyParser)

include_directories(Debug Release build include src src/Model src/Utils)

file(GLOB_RECURSE source_files  ${CMAKE_CURRENT_SOURCE_DIR}/src/*.cpp
                                ${CMAKE_CURRENT_SOURCE_DIR}/src/Model/*.cpp
                                ${CMAKE_CURRENT_SOURCE_DIR}/src/Macro/*.cpp
                                ${CMAKE_CURRENT_SOURCE_DIR}/src/Utils/*.cpp)
add_executable(redapple ${source_files} 
                        ${BISON_MyParser_OUTPUTS} 
                        ${FLEX_MyScanner_OUTPUTS})

install(TARGETS redapple RUNTIME DESTINATION bin)

# Find the libraries that correspond to the LLVM components
# that we wish to use
llvm_map_components_to_libnames(llvm_libs 
    support core irreader executionengine interpreter 
    mc mcjit bitwriter x86codegen target)

# Link against LLVM libraries
target_link_libraries(redapple ${llvm_libs})

Ubuntu的默认安装，有时LLVM会出bug，cmake找不到许多配置文件，我仔细查看了它的CMake配置，发现有一行脚本路径写错了：
/usr/share/llvm-3.6/cmake/ 是llvm的cmake配置路径

其中的LLVMConfig.cmake第48行，它原来的路径是这样的：

1
set(LLVM_CMAKE_DIR "/usr/share/llvm-3.6/share/llvm/cmake")

应该改成：

1
set(LLVM_CMAKE_DIR "/usr/share/llvm-3.6/cmake")

Ubuntu下的llvm文档和示例都在如下目录：
/usr/share/doc/llvm-3.6-doc
/usr/share/doc/llvm-3.6-examples

我们将example下的HowToUseJIT复制到工作目录中，测试编译一下，懒得找的可以粘我后面附录给的内容。
然后再用简单修改后的CMake测试编译一下。

项目结构是这样的：

1
2
3
4
HowToUseJIT -- src
                + --- HowToUseJIT.cpp
        +  --- CMakeLists.txt
        +  --- build

在项目根目录执行如下指令：

1
2
3
cd build
cmake ..
make

如果编译通过了，那么恭喜你，你已经会构建LLVM项目了

附： CMakeLists.txt 和 HowToUseJIT.cpp

CMakeLists.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
cmake_minimum_required(VERSION 2.8)
project(llvm_test)

set(LLVM_TARGETS_TO_BUILD X86)
set(LLVM_BUILD_RUNTIME OFF)
set(LLVM_BUILD_TOOLS OFF)

find_package(LLVM REQUIRED CONFIG)

message(STATUS "Found LLVM ${LLVM_PACKAGE_VERSION}")
message(STATUS "Using LLVMConfig.cmake in: ${LLVM_DIR}")


SET (CMAKE_CXX_COMPILER_ENV_VAR "clang++")

SET (CMAKE_CXX_FLAGS "-std=c++11")
SET (CMAKE_CXX_FLAGS_DEBUG   "-g")
SET (CMAKE_CXX_FLAGS_MINSIZEREL  "-Os -DNDEBUG")
SET (CMAKE_CXX_FLAGS_RELEASE  "-O4 -DNDEBUG")
SET (CMAKE_CXX_FLAGS_RELWITHDEBINFO "-O2 -g")

SET(EXECUTABLE_OUTPUT_PATH ${PROJECT_SOURCE_DIR}/bin)

include_directories(${LLVM_INCLUDE_DIRS})
add_definitions(${LLVM_DEFINITIONS})

file(GLOB_RECURSE source_files "${CMAKE_CURRENT_SOURCE_DIR}/src/*.cpp")
add_executable(llvm_test ${source_files})
install(TARGETS llvm_test RUNTIME DESTINATION bin)

# Find the libraries that correspond to the LLVM components
# that we wish to use
llvm_map_components_to_libnames(llvm_libs 
    Core
    ExecutionEngine
    Interpreter
    MC
    Support
    nativecodegen)

# Link against LLVM libraries
target_link_libraries(llvm_test ${llvm_libs})

HowToUseJIT.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
//===-- examples/HowToUseJIT/HowToUseJIT.cpp - An example use of the JIT --===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//  This small program provides an example of how to quickly build a small
//  module with two functions and execute it with the JIT.
//
// Goal:
//  The goal of this snippet is to create in the memory
//  the LLVM module consisting of two functions as follow: 
//
// int add1(int x) {
//   return x+1;
// }
//
// int foo() {
//   return add1(10);
// }
//
// then compile the module via JIT, then execute the `foo'
// function and return result to a driver, i.e. to a "host program".
//
// Some remarks and questions:
//
// - could we invoke some code using noname functions too?
//   e.g. evaluate "foo()+foo()" without fears to introduce
//   conflict of temporary function name with some real
//   existing function name?
//
//===----------------------------------------------------------------------===//

#include "llvm/ExecutionEngine/GenericValue.h"
#include "llvm/ExecutionEngine/Interpreter.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/Support/ManagedStatic.h"
#include "llvm/Support/TargetSelect.h"
#include "llvm/Support/raw_ostream.h"

using namespace llvm;

int main() {
  
  InitializeNativeTarget();

  LLVMContext Context;
  
  // Create some module to put our function into it.
  std::unique_ptr<Module> Owner = make_unique<Module>("test", Context);
  Module *M = Owner.get();

  // Create the add1 function entry and insert this entry into module M.  The
  // function will have a return type of "int" and take an argument of "int".
  // The '0' terminates the list of argument types.
  Function *Add1F =
    cast<Function>(M->getOrInsertFunction("add1", Type::getInt32Ty(Context),
                                          Type::getInt32Ty(Context),
                                          (Type *)0));

  // Add a basic block to the function. As before, it automatically inserts
  // because of the last argument.
  BasicBlock *BB = BasicBlock::Create(Context, "EntryBlock", Add1F);

  // Create a basic block builder with default parameters.  The builder will
  // automatically append instructions to the basic block `BB'.
  IRBuilder<> builder(BB);

  // Get pointers to the constant `1'.
  Value *One = builder.getInt32(1);

  // Get pointers to the integer argument of the add1 function...
  assert(Add1F->arg_begin() != Add1F->arg_end()); // Make sure there's an arg
  Argument *ArgX = Add1F->arg_begin();  // Get the arg
  ArgX->setName("AnArg");            // Give it a nice symbolic name for fun.

  // Create the add instruction, inserting it into the end of BB.
  Value *Add = builder.CreateAdd(One, ArgX);

  // Create the return instruction and add it to the basic block
  builder.CreateRet(Add);

  // Now, function add1 is ready.


  // Now we're going to create function `foo', which returns an int and takes no
  // arguments.
  Function *FooF =
    cast<Function>(M->getOrInsertFunction("foo", Type::getInt32Ty(Context),
                                          (Type *)0));

  // Add a basic block to the FooF function.
  BB = BasicBlock::Create(Context, "EntryBlock", FooF);

  // Tell the basic block builder to attach itself to the new basic block
  builder.SetInsertPoint(BB);

  // Get pointer to the constant `10'.
  Value *Ten = builder.getInt32(10);

  // Pass Ten to the call to Add1F
  CallInst *Add1CallRes = builder.CreateCall(Add1F, Ten);
  Add1CallRes->setTailCall(true);

  // Create the return instruction and add it to the basic block.
  builder.CreateRet(Add1CallRes);

  // Now we create the JIT.
  ExecutionEngine* EE = EngineBuilder(std::move(Owner)).create();

  outs() << "We just constructed this LLVM module:\n\n" << *M;
  outs() << "\n\nRunning foo: ";
  outs().flush();

  // Call the `foo' function with no arguments:
  std::vector<GenericValue> noargs;
  GenericValue gv = EE->runFunction(FooF, noargs);

  // Import result of execution:
  outs() << "Result: " << gv.IntVal << "\n";
  delete EE;
  llvm_shutdown();
  return 0;
}

编译器架构的王者LLVM——（3）用代码生成代码

LLVM平台，短短几年间，改变了众多编程语言的走向，也催生了一大批具有特色的编程语言的出现，不愧为编译器架构的王者，也荣获2012年ACM软件系统奖 —— 题记

版权声明：本文为 西风逍遥游 原创文章，转载请注明出处 西风世界 http://blog.csdn.net/xfxyy_sxfancy

用代码生成代码

LLVM的开发思路很简单，就是用C++代码去不断生成llvm字节码。

RedApple语言示例

这是我花了两周多的时间制作的一门实验型语言，主要是想验证一个编译器的设计思路，宏翻译系统。
它的架构和一般的编译器很不一样，首先，编译器前端会先将语法转换为很通用的AST语法树节点，一般的编译器，往往是直接在这些节点上进行语义分析，然后进行代码生成。
这次我采用了类似lisp的表示方法，将源文件转换为语法树，然后遍历整棵语法树，根据上面标注的宏提示，去按照各个宏的规则进行翻译工作。

整个编译器1500行左右的代码，非常的小巧，不过功能也比较有限，而且好多地方还不完善，主要支持的就是函数的定义，结构体的定义，函数调用，结构体访问，分配内存，基本逻辑控制语句这些基本的特性。

大家可以作为学习llvm的一个示例吧。
Github地址：https://github.com/sunxfancy/RedApple

同样，非常精品的示例还推荐大家看以下两位网友写的：

构建Toy编译器：基于Flex、Bison和LLVM
http://lesliezhu.github.io/public/write-your-toy-compiler.html

用LLVM来开发自己的编译器系列
http://my.oschina.net/linlifeng/blog/97457

当然，这些示例不是说要大家一下都看懂，那么也就没有教程的意义了，下面我会继续介绍各个关键的LLVM平台API以及相关工具链。大家可以将以上三个项目和LLVM官网example中的作为参考，在实践中加以印证。

工具链简介

工具 功能
clang -emit-llvm 指令，可以生成.bc的字节码文件
lli llvm解释器，直接执行.bc字节码文件
llc llvm编译器，将.bc编译成.o

以上三个最常用，其他小工具备用

工具 功能
llvm-as 汇编器
llvm-dis 反汇编器
llvm-ar 打包器
llvm-link 字节码链接器

唉，太多了，好多我也木有用过，还有需要的请查看官方文档：
http://llvm.org/docs/CommandGuide/index.html

常用类

LLVM类 功能
LLVMContext 上下文类，基本是最核心的保存上下文符号的类
Module 模块类，一般一个文件是一个模块，里面有函数列表和全局变量表
Function 函数类，函数类，生成出来就是一个C函数
Constant 常量类，各种常量的定义，都是从这里派生出来的
Value 各值类型的基类，几乎所以的函数、常量、变量、表达式，都可以转换成Value型
Type 类型类，表示各种内部类型或用户类型，每一个Value都有个getType方法来获取其类型。
BasicBlock 基本块，一般是表示一个标签，注意这个块不是嵌套形式的结构，而是每个块结尾可以用指令跳转 到其他块，类似C语言中的标签的功能

尝试先来生成个小函数

就拿printf开练吧，这个函数第一有用，第二简单，第三只要声明不要内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void register_printf(llvm::Module *module) {
    std::vector<llvm::Type*> printf_arg_types; // 这里是参数表
    printf_arg_types.push_back(llvm::Type::getInt8PtrTy(module->getContext()));

    llvm::FunctionType* printf_type =
        llvm::FunctionType::get(
            llvm::Type::getInt32Ty(module->getContext()), printf_arg_types, true); 
            // 这里的true表示后面接不定参数

    llvm::Function *func = llvm::Function::Create(
                printf_type, llvm::Function::ExternalLinkage,
                llvm::Twine("printf"),
                module
           );
    func->setCallingConv(llvm::CallingConv::C); // 一定注意调用方式的正确性
}

怎么样，是不是也很简单？

编写主函数和调试上下文

下面我们来编写一个主函数，来测试一下我们的函数是否正确，这里，也是LLVM最核心的启动和调试流程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int main(){
    InitializeNativeTarget();
    LLVMContext Context;
    Module* M = new Module("main", Context);

    register_printf(M);

    // 校验问题, 这个函数需要一个输出流来打印错误信息
    if (verifyModule(*M, &errs())) {
        errs() << "构建LLVM字节码出错!\n";
        exit(1);
    }

    // 输出llvm字节码
    outs() << "LLVM module:\n\n" << *M;
    outs() << "\n\n";
    outs().flush();

    // 输出二进制BitCode到.bc文件
    std::error_code ErrInfo;
    raw_ostream *out = new raw_fd_ostream("a.bc", ErrInfo, sys::fs::F_None);
    WriteBitcodeToFile(M, *out);
    out->flush(); delete out;

    // 关闭LLVM释放内存
    llvm_shutdown();
    return 0;
}

运行效果：

对了，我们好像没有提该引用哪些头文件，请见附录

附：完整示例

只是头文件有点长，具体功能有的我也记不清了，一般我是习惯性把一片粘过去 →_→

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

/* 
* @Author: sxf
* @Date:   2015-11-06 20:37:15
* @Last Modified by:   sxf
* @Last Modified time: 2015-11-06 20:46:43
*/

#include "llvm/IR/Verifier.h"
#include "llvm/ExecutionEngine/GenericValue.h"
#include "llvm/ExecutionEngine/Interpreter.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/Support/ManagedStatic.h"
#include "llvm/Support/TargetSelect.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Bitcode/ReaderWriter.h"
#include "llvm/Support/FileSystem.h"
#include "llvm/IR/ValueSymbolTable.h"

using namespace llvm;

void register_printf(llvm::Module *module) {
    std::vector<llvm::Type*> printf_arg_types;
    printf_arg_types.push_back(llvm::Type::getInt8PtrTy(module->getContext()));

    llvm::FunctionType* printf_type =
        llvm::FunctionType::get(
            llvm::Type::getInt32Ty(module->getContext()), printf_arg_types, true);

    llvm::Function *func = llvm::Function::Create(
                printf_type, llvm::Function::ExternalLinkage,
                llvm::Twine("printf"),
                module
           );
    func->setCallingConv(llvm::CallingConv::C);
}


int main(){
    InitializeNativeTarget();
    LLVMContext Context;
    Module* M = new Module("main", Context);

    register_printf(M);

    // 校验问题, 这个函数需要一个输出流来打印错误信息
    if (verifyModule(*M, &errs())) {
        errs() << "构建LLVM字节码出错!\n";
        exit(1);
    }

    // 输出llvm字节码
    outs() << "LLVM module:\n\n" << *M;
    outs() << "\n\n";
    outs().flush();

    // 输出二进制BitCode到.bc文件
    std::error_code ErrInfo;
    raw_ostream *out = new raw_fd_ostream("a.bc", ErrInfo, sys::fs::F_None);
    WriteBitcodeToFile(M, *out);
    out->flush(); delete out;

    // 关闭LLVM释放内存
    llvm_shutdown();
    return 0;
}

编译器架构的王者LLVM——（4）简单的词法和语法分析

LLVM平台，短短几年间，改变了众多编程语言的走向，也催生了一大批具有特色的编程语言的出现，不愧为编译器架构的王者，也荣获2012年ACM软件系统奖 —— 题记

版权声明：本文为 西风逍遥游 原创文章，转载请注明出处 西风世界 http://blog.csdn.net/xfxyy_sxfancy

简单的词法和语法分析

Lex和Yacc真是太好用了，非常方便我们构建一门语言的分析程序。

如果你对Lex和Yacc不了解的话，建议先看下我之前写的两篇文章，分别介绍了Lex和Yacc的用法。

Lex识别C风格字符串和注释
http://blog.csdn.net/xfxyy_sxfancy/article/details/45024573

创造新语言（2）——用Lex&Yacc构建简单的分析程序
http://blog.csdn.net/xfxyy_sxfancy/article/details/45046465

FLex创建一门语言的词法分析程序

我们创建的是一门编程语言，那么词法分析程序就不能像做实验一样那么草率，必须考虑周全，一般一门语言的词法分析程序大概需要囊括如下的几个方面：

识别关键字、识别标识符、识别基本常量（数字、浮点数、字符串、字符）、识别注释、识别运算符

这些都是非常重要的，而且是一门语言语法中必不可少的部分。

于是RedApple的词法分析部分，我就设计成了这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
%{
#include <string>
#include "Model/nodes.h"
#include <list>
using namespace std;

#include "redapple_parser.hpp"
#include "StringEscape.h"

#define SAVE_TOKEN     yylval.str = maketoken(yytext, yyleng)
#define SAVE_STRING    yylval.str = makestring(yytext, yyleng, 2)
#define SAVE_STRING_NC yylval.str = makestring(yytext, yyleng, 3)
extern "C" int yywrap() { return 1; }
char* maketoken(const char* data, int len);
char* makestring(const char* data, int len, int s);

%}

%option yylineno

%%

"/*"([^\*]|(\*)*[^\*/])*(\*)*"*/" ; /* 就是这种注释 */ 

#[^\n]*\n               ; /* 井号注释 */ 
"//"[^\n]*\n            ; /* 双线注释 */ 

[ \t\v\n\f]             ; /* 过滤空白字符 */


"=="                    return CEQ;
"<="                    return CLE;
">="                    return CGE;
"!="                    return CNE;

"<"                     return '<';
"="                     return '=';
">"                     return '>';
"("                     return '(';
")"                     return ')';
"["                     return '[';
"]"                     return ']';
"{"                     return '{';
"}"                     return '}';
"."                     return '.';
","                     return ',';
":"                     return ':';
";"                     return ';';
"+"                     return '+';
"-"                     return '-';
"*"                     return '*';
"/"                     return '/';
"%"                     return '%';
"^"                     return '^';
"&"                     return '&';
"|"                     return '|';
"~"                     return '~';

    /* 宏运算符 */
"@"                     return '@';
",@"                    return MBK;

    /* 下面声明要用到的关键字 */

    /* 控制流 */
"if"                    return IF;
"else"                  return ELSE;
"while"                 return WHILE;
"do"                    return DO;
"goto"                  return GOTO;
"for"                   return FOR;
"foreach"               return FOREACH;

    /* 退出控制 */
"break"|"continue"|"exit"   SAVE_TOKEN; return KWS_EXIT;

"return"                return RETURN;

    /* 特殊运算符 */
"new"                   return NEW;
"this"                  return THIS;
    
    /* 特殊定义 */
"delegate"              return DELEGATE;
"def"                   return DEF;
"define"                return DEFINE;
"import"                return IMPORT;
"using"                 return USING;
"namespace"             return NAMESPACE;

"try"|"catch"|"finally"|"throw"  SAVE_TOKEN; return KWS_ERROR; /* 异常控制 */

"null"|"true"|"false"               SAVE_TOKEN; return KWS_TSZ; /* 特殊值 */

"struct"|"enum"|"union"|"module"|"interface"|"class"     SAVE_TOKEN; return KWS_STRUCT; /* 结构声明 */

"public"|"private"|"protected"  SAVE_TOKEN; return KWS_FWKZ; /* 访问控制 */

"const"|"static"|"extern"|"virtual"|"abstract"|"in"|"out"        SAVE_TOKEN; return KWS_FUNC_XS; /* 函数修饰符 */

"void"|"double"|"int"|"float"|"char"|"bool"|"var"|"auto"  SAVE_TOKEN; return KWS_TYPE; /* 基本类型 */

[a-zA-Z_][a-zA-Z0-9_]*  SAVE_TOKEN; return ID; /* 标识符 */

[0-9]*\.[0-9]*          SAVE_TOKEN; return DOUBLE;
[0-9]+                  SAVE_TOKEN; return INTEGER;

\"(\\.|[^\\"])*\"       SAVE_STRING; return STRING; /* 字符串 */
@\"(\\.|[^\\"])*\"      SAVE_STRING_NC; return STRING; /* 无转义字符串 */
\'(\\.|.)\'             SAVE_STRING; return CHAR;   /* 字符 */

.                       printf("Unknown Token!\n"); yyterminate();

%%


char* maketoken(const char* data, int len) {
    char* str = new char[len+1];
    strncpy(str, data, len);
    str[len] = 0;
    return str;
}

char* makestring(const char* data, int len, int s) {
    char* str = new char[len-s+1];
    strncpy(str, data+s-1, len-s);
    str[len-s] = 0;
    if (s == 3) return str;
    printf("source: %s\n",str);
    char* ans = CharEscape(str);
    printf("escape: %s\n",ans);
    delete[] str; 
    return ans; 
}

看起来非常的长，但主要多的就是枚举了大量的关键字和运算符，当然，这个你在开发一门语言的前期，不用面面俱到，可以选自己用到的先写，不足的再日后补充。

要注意，这里最难的应该就是：

1
"/*"([^\*]|(\*)*[^\*/])*(\*)*"*/" ; /* 就是这种注释 */

乍看起来，非常恐怖的正则式，但其实就是在枚举多种可能情况，来保障注释范围的正确性。

1
"/*"   (  [^\*]   |   (\*)* [^\*/]   )*   (\*)*    "*/" ; /* 就是这种注释 */

用Bison创建通用的语法分析程序

这里我编写的是类C语言的语法，要注意的是，很多情况会造成规约-规约冲突和移入-规约冲突。这里我简要介绍一个bison的工作原理。

这种算法在编译原理中，被称为LALR(1)分析法，是自底向上规约的算法之一，而且又会向前看一个token，Bison中的每一行，被称为一个产生式（或BNF范式）

例如下面这行：

1
def_module_statement : KWS_STRUCT ID '{' def_statements '}'

左边的是要规约的节点， 冒号右边是描述这个语法节点是用哪些节点产生的。
这是一个结构体定义的语法描述，KWS_STRUCT是终结符，来自Lex里的元素，看了上面的Lex描述，你应该能找到它的定义：

1
"struct"|"enum"|"union"|"module"|"interface"|"class"     SAVE_TOKEN; return KWS_STRUCT; /* 结构声明 */

其实就是可能的一些关键字。而def_statements是另外的语法节点，由其他定义得来。

规约-规约冲突，是说，在当前产生式结束后，后面跟的元素还确定的情况下，能够规约到两个不同的语法节点:

1
2
3
4
5
6
def_module_statement : KWS_STRUCT ID '{' def_statements '}' ;
def_class_statement : KWS_STRUCT ID '{' def_statements '}' ;

statement : def_module_statement ';' 
          | def_class_statement ';' 
          ;

以上文法便会产生规约-规约冲突，这是严重的定义错误，必须加以避免。
注意，我为了体现这个语法的错误，特意加上了上下文环境，不是说一样的语法定义会产生规约规约冲突，而是说后面可能跟的终结符都一样时，（在这里是’;’）才会产生规约规约冲突，所以避免这种问题也简单，就是把相似的语法节点合并在一起就可以了。

说道移入-规约冲突，就要谈起if-else的摇摆问题：

1
2
3
4
5
6
7
if_state : IF '(' expr ')' statement 
         | IF '(' expr ')' statement ELSE statement 
         ;

statement : if_state
          | ...
          ;

正如这个定义一样，在 if的前半部识别完成后，下一个元素是ELSE终结符，此时可以规约，可以移入
说规约合法的理由是，if_state也是statement，而if第二条statement后面就是ELSE。
根据算法，这里规约是合理的，而移入同样是合理的。

为了避免这种冲突，一般Bison会优先选择移入，这样ELSE会和最近的IF匹配。
所以说，移入-规约冲突在你清楚的知道是哪的问题的时候，可以不加处理。但未期望的移入-规约冲突有可能让你的分析器不正确工作，这点还需要注意。

下面是我的Bison配置文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
%{
#include "Model/nodes.h"
#include <list>
using namespace std;

#define YYERROR_VERBOSE 1

Node *programBlock; /* the top level root node of our final AST */

extern int yylex();
extern int yylineno;
extern char* yytext;
extern int yyleng;

void yyerror(const char *s);

%}

 

/* Represents the many different ways we can access our data */

%union {
    Node *nodes;
    char *str;
    int token;
}

 

/* Define our terminal symbols (tokens). This should

   match our tokens.l lex file. We also define the node type

   they represent.

 */

%token <str> ID INTEGER DOUBLE
%token <token> CEQ CNE CGE CLE MBK
%token <token> '<' '>' '=' '+' '-' '*' '/' '%' '^' '&' '|' '~' '@'
%token <str> STRING CHAR
%token <token> IF ELSE WHILE DO GOTO FOR FOREACH  
%token <token> DELEGATE DEF DEFINE IMPORT USING NAMESPACE
%token <token> RETURN NEW THIS 
%token <str> KWS_EXIT KWS_ERROR KWS_TSZ KWS_STRUCT KWS_FWKZ KWS_FUNC_XS KWS_TYPE

/* 
   Define the type of node our nonterminal symbols represent.
   The types refer to the %union declaration above. Ex: when
   we call an ident (defined by union type ident) we are really
   calling an (NIdentifier*). It makes the compiler happy.
 */

%type <nodes> program
%type <nodes> def_module_statement
%type <nodes> def_module_statements
%type <nodes> def_statement
%type <nodes> def_statements
%type <nodes> for_state
%type <nodes> if_state
%type <nodes> while_state
%type <nodes> statement
%type <nodes> statements
%type <nodes> block
%type <nodes> var_def
%type <nodes> func_def
%type <nodes> func_def_args
%type <nodes> func_def_xs 
%type <nodes> numeric
%type <nodes> expr
%type <nodes> call_arg 
%type <nodes> call_args 
%type <nodes> return_state

//%type <token> operator 这个设计容易引起规约冲突，舍弃
/* Operator precedence for mathematical operators */


%left '~'
%left '&' '|'
%left CEQ CNE CLE CGE '<' '>' '='
%left '+' '-'
%left '*' '/' '%' '^'
%left '.'
%left MBK '@'

%start program

%%

program : def_statements { programBlock = Node::getList($1); }
        ;

def_module_statement : KWS_STRUCT ID '{' def_statements '}' { $$ = Node::make_list(3, StringNode::Create($1), StringNode::Create($2), $4); }
                     | KWS_STRUCT ID ';' { $$ = Node::make_list(3, StringNode::Create($1), StringNode::Create($2), Node::Create()); }
                     ;

def_module_statements  : def_module_statement { $$ = Node::getList($1); }
                       | def_module_statements def_module_statement { $$ = $1; $$->addBrother(Node::getList($2)); }
                       ;

func_def_xs : KWS_FUNC_XS { $$ = StringNode::Create($1); }
            | func_def_xs KWS_FUNC_XS {$$ = $1; $$->addBrother(StringNode::Create($2)); }
            ;

def_statement : var_def ';' { $$ = $1; }
              | func_def 
              | def_module_statement 
              | func_def_xs func_def { $$ = $2; $2->addBrother(Node::getList($1)); } 
              ;

def_statements : def_statement { $$ = Node::getList($1); }
               | def_statements def_statement { $$ = $1; $$->addBrother(Node::getList($2)); }
               ;

statements : statement { $$ = Node::getList($1); }
           | statements statement { $$ = $1; $$->addBrother(Node::getList($2)); }
           ;

statement : def_statement 
          | expr ';' { $$ = $1; } 
          | block 
          | if_state
          | while_state
          | for_state
          | return_state
          ;

if_state : IF '(' expr ')' statement { $$ = Node::make_list(3, StringNode::Create("if"), $3, $5); }
         | IF '(' expr ')' statement ELSE statement { $$ = Node::make_list(4, StringNode::Create("if"), $3, $5, $7); }
         ;

while_state : WHILE '(' expr ')' statement { $$ = Node::make_list(3, StringNode::Create("while"), $3, $5); }
            ;

for_state : FOR '(' expr ';' expr ';' expr ')' statement { $$ = Node::make_list(5, StringNode::Create("for"), $3, $5, $7, $9); }
          | FOR '(' var_def ';' expr ';' expr ')' statement { $$ = Node::make_list(5, StringNode::Create("for"), Node::Create($3), $5, $7, $9); }
          ;

return_state : RETURN ';' { $$ = StringNode::Create("return"); }
             | RETURN expr ';' { $$ = StringNode::Create("return"); $$->addBrother($2); }              

block : '{' statements '}' { $$ = Node::Create($2); }
      | '{' '}' { $$ = Node::Create(); }
      ; 

var_def : KWS_TYPE ID { $$ = Node::make_list(3, StringNode::Create("set"), StringNode::Create($1), StringNode::Create($2)); }
        | ID ID { $$ = Node::make_list(3, StringNode::Create("set"), StringNode::Create($1), StringNode::Create($2)); }
        | KWS_TYPE ID '=' expr { $$ = Node::make_list(4, StringNode::Create("set"), StringNode::Create($1), StringNode::Create($2), $4); }
        | ID ID '=' expr { $$ = Node::make_list(4, StringNode::Create("set"), StringNode::Create($1), StringNode::Create($2), $4); }
        ;

func_def : ID ID '(' func_def_args ')' block
            { $$ = Node::make_list(5, StringNode::Create("function"), StringNode::Create($1), StringNode::Create($2), $4, $6); }
         | KWS_TYPE ID '(' func_def_args ')' block
            { $$ = Node::make_list(5, StringNode::Create("function"), StringNode::Create($1), StringNode::Create($2), $4, $6); }
         | ID ID '(' func_def_args ')' ';'
            { $$ = Node::make_list(5, StringNode::Create("function"), StringNode::Create($1), StringNode::Create($2), $4); }
         | KWS_TYPE ID '(' func_def_args ')' ';'
            { $$ = Node::make_list(5, StringNode::Create("function"), StringNode::Create($1), StringNode::Create($2), $4); }
         ;

func_def_args : var_def { $$ = Node::Create(Node::Create($1)); }
              | func_def_args ',' var_def { $$ = $1; $$->addChildren(Node::Create($3)); }
              | %empty  { $$ = Node::Create(); }
              ;

numeric : INTEGER { $$ = IntNode::Create($1); }
        | DOUBLE { $$ = FloatNode::Create($1); }
        ;

expr : expr '=' expr { $$ = Node::make_list(4, StringNode::Create("opt2"), StringNode::Create("="), $1, $3); }
     | ID '(' call_args ')' { $$ = Node::make_list(2, StringNode::Create("call"), StringNode::Create($1)); $$->addBrother($3); }
     | ID { $$ = IDNode::Create($1); }
     | numeric { $$ = $1; }
     | STRING { $$ = StringNode::Create($1); }
     | KWS_TSZ 
     | NEW ID '(' call_args ')' { $$ = Node::make_list(3, StringNode::Create("new"), StringNode::Create($2), $4); }
     | expr CEQ expr { $$ = Node::make_list(4, StringNode::Create("opt2"), StringNode::Create("=="), $1, $3); }
     | expr CNE expr { $$ = Node::make_list(4, StringNode::Create("opt2"), StringNode::Create("!="), $1, $3); }
     | expr CLE expr { $$ = Node::make_list(4, StringNode::Create("opt2"), StringNode::Create("<="), $1, $3); }
     | expr CGE expr { $$ = Node::make_list(4, StringNode::Create("opt2"), StringNode::Create(">="), $1, $3); }
     | expr '<' expr { $$ = Node::make_list(4, StringNode::Create("opt2"), StringNode::Create("<"), $1, $3); }
     | expr '>' expr { $$ = Node::make_list(4, StringNode::Create("opt2"), StringNode::Create(">"), $1, $3); }
     | expr '+' expr { $$ = Node::make_list(4, StringNode::Create("opt2"), StringNode::Create("+"), $1, $3); }
     | expr '-' expr { $$ = Node::make_list(4, StringNode::Create("opt2"), StringNode::Create("-"), $1, $3); }
     | expr '*' expr { $$ = Node::make_list(4, StringNode::Create("opt2"), StringNode::Create("*"), $1, $3); }
     | expr '/' expr { $$ = Node::make_list(4, StringNode::Create("opt2"), StringNode::Create("/"), $1, $3); }
     | expr '%' expr { $$ = Node::make_list(4, StringNode::Create("opt2"), StringNode::Create("%"), $1, $3); }
     | expr '^' expr { $$ = Node::make_list(4, StringNode::Create("opt2"), StringNode::Create("^"), $1, $3); }
     | expr '&' expr { $$ = Node::make_list(4, StringNode::Create("opt2"), StringNode::Create("&"), $1, $3); }
     | expr '|' expr { $$ = Node::make_list(4, StringNode::Create("opt2"), StringNode::Create("|"), $1, $3); }
     | expr '.' expr { $$ = Node::make_list(4, StringNode::Create("opt2"), StringNode::Create("."), $1, $3); }
     | '~' expr { $$ = Node::make_list(4, StringNode::Create("opt1"), StringNode::Create("~"), $2); }
     | '(' expr ')'  /* ( expr ) */  { $$ = $2; }
     ;


call_arg  :  expr { $$ = $1;  }
          |  ID ':' expr { $$ = Node::make_list(3, StringNode::Create(":"), $1, $3); }
          ;

call_args : %empty { $$ = Node::Create(); }
          | call_arg { $$ = Node::getList($1); }
          | call_args ',' call_arg  { $$ = $1; $$->addBrother(Node::getList($3)); }
          ;

%%

void yyerror(const char* s){
    fprintf(stderr, "%s \n", s);    
    fprintf(stderr, "line %d: ", yylineno);
    fprintf(stderr, "text %s \n", yytext);
    exit(1);
}

编译器架构的王者LLVM——（5）语法树模型的基本结构

LLVM平台，短短几年间，改变了众多编程语言的走向，也催生了一大批具有特色的编程语言的出现，不愧为编译器架构的王者，也荣获2012年ACM软件系统奖 —— 题记

版权声明：本文为 西风逍遥游 原创文章，转载请注明出处 西风世界 http://blog.csdn.net/xfxyy_sxfancy

语法树模型的基本结构

上次我们看了Lex和Yacc的翻译文件，可能一些朋友并不了解其中的执行部分，而且，对这个抽象语法树是怎么构建起来的还不清楚。今天我们就再详细介绍一下如果方便的构建一棵抽象语法树（AST）

Node节点链接的左孩子，右兄弟二叉树

AST语法树，由于是一棵多叉树，直接表示不大好弄，所以我们采用计算机树中的一个经典转换，将多叉树转换为左孩子右兄弟的二叉树。

其实思路很简单，每一层其实就是一个链表，将兄弟节点串起来，这样就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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上的源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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函数就是这样写出来的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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型指针，那么我们用如下的方法就可以获取到当前的类型：

1
Type* t = value->getType();

Type类型也很容易使用，例如获取其指针就可以：

1
PointerType* ptr_type = t->getPointerTo();

Type类型中还有很多静态函数可供生成基本类型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 获取基本类型
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代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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类的完整实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/* 
* @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);
}