TinyCompiler

序言

项目概述

本项目是基于flex，bison以及LLVM，使用c++11实现的类C语法编译器，使用flex结合yacc对源代码进行词法、语法分析；在语法分析阶段生成整个源代码相应的抽象语法树后，根据LLVM IR（Intermediate Representation）模块中定义的中间代码语法输出符合LLVM中间语言语法、机器无关的中间代码；最后，本项目通过调用LLVM Back ends模块的接口，根据本地指令集与操作系统架构，将中间代码编译成二进制目标代码。编译生成的目标代码之后可直接编译生成可执行文件，或与其他目标代码链接生成可执行文件。

本项目解析的语法与是C语言的一个子集，但部分语法存在区别，这些将在最后的测试用例中具体说明。目前已支持的数据类型包括：
- void
- int
- float
- double
- char
- string
- bool
- 自定义结构体
- 数组（包括多维数组）
支持的主要语法包括：
- 变量的声明、初始化（包括一维数组初始化，多维数组暂不支持初始化，只能逐个元素赋值使用）
- 函数声明，函数调用（传递参数类型可以是任意已支持类型）
- 外部函数声明和调用
- 控制流语句if-else、for、while及任意层级的嵌套使用
- 单行注释（#）
- 二元运算符、赋值、函数参数的隐式类型转换
- 全局变量的使用
- ...
以上提到的类型和语法均已通过编译成目标代码并生成二进制文件运行测试。
相关术语
- LLVM：LLVM是一个自由软件项目，它是一种编译器基础设施，以C++写成。LLVM基于静态单赋值形式（SSA）的编译策略提供了完整编译系统的中间层，它会将中间语言（Intermediate form，IF）从编译器取出与最优化，最优化后的IF接着被转换及链接到目标平台的汇编语言。LLVM支持与语言无关的指令集架构及类型系统。每个在静态单赋值形式（SSA）的指令集代表着，每个变量（被称为具有类型的寄存器）仅被赋值一次，这简化了变量间相依性的分析。LLVM允许代码被静态的编译，包含在传统的GCC系统底下，或是类似JAVA等后期编译才将IF编译成机器码所使用的即时编译（JIT）技术。
- flex：flex（快速词法分析产生器，英语：fast lexical analyzer generator）是一种词法分析程序。它是lex的开放源代码版本，以BSD许可证发布。通常与GNU bison一同运作，但是它本身不是GNU计划的一部分。
- GNU bison：GNU bison是一个自由软件，用于自动生成语法分析器程序，实际上可用于所有常见的操作系统。Bison把LALR形式的上下文无关文法描述转换为可做语法分析的C或C++程序。在新近版本中，Bison增加了对GLR语法分析算法的支持。
主要源代码结构

TinyCompiler
├── ASTNodes.h 抽象语法树节点的定义
├── CodeGen.cpp 抽象语法树生成中间代码
├── CodeGen.h
├── Makefile
├── ObjGen.cpp 中间代码生成目标代码
├── ObjGen.h
├── Readme.md
├── TypeSystem.cpp 类型系统实现
├── TypeSystem.h
├── grammar.y 语法分析yacc文件
├── main.cpp TinyCompiler程序入口
├── test.input 用于测试词法、语法、语义分析的源代码
├── testmain.cpp 用于测试链接目标文件的源代码
├── token.l 词法分析lex文件
├── tests 测试用例及结果图
│   ├── testArray.input
│   ├── testArray.png
│   ├── testArrayAST.png
│   ├── testBasic.input
│   ├── testBasic.png
│   ├── testBasicAST.png
│   ├── testStruct.input
│   ├── testStruct.png
│   └── testStructAST.png
└── utils.cpp 通用函数实现
运行环境

本项目已在 OSX Sierra 12.1（64位）以及 Ubuntu LTS 14.04（64位）下，使用LLVM 3.9平台进行测试，测试截图见最后一节。

Windows平台可自行搭建LLVM环境后测试。
使用说明

注：本项目使用LLVM 3.9.0版本的接口，据测试不同版本可能无法直接编译
- 编译TinyCompiler
```
make
```
- 使用TinyCompiler编译test.c文件，将目标代码输出到output.o
```
cat test.c | compiler
```
用g++链接output.o生成可执行文件
```
g++ output.o -o test
./test
```
使用test.input, testmain.cpp文件自动测试编译、链接
```
make test
make testlink
```
参考资料

LLVM Language Reference Manual

LLVM Tutorial

gnuu - writing your own toy compiler

语法定义

本编译器实现的语法是类似标准C的语法，引入的几个区别包括：

去掉了标准C的每个语句后的分号
不显式提供指针类型，但可以对变量取地址
暂不支持多维数组初始化
强制要求写return语句
数组初始化列表使用中括号而非大括号
if-else，for，while等语句强制使用大括号
...

基本语法

int func(int a, int b){
    if( a > b ){
        return func(b * 0.5)
    }else if( a == b ){
        return func(a * b)
    }else{
        return 0
    }
}

int main(int argc, string[1] argv){
    int i = 0
    for( ; i<argc; i=i+1){
        func(i, argc)
    }
    while( 1 ){}
    return 0
}

结构体使用

struct Point{
    int x
    int y
}
int func(struct Point p){
    return p.x
}
int test(){
    struct Point p
    p.x = 1
    p.y = 3
    func(p)
    return 0
}

数组使用

int testArray(){
    int[10] oneDim = [1,2,3,4]
    int[3][4] twoDim
    int i, j
    for(i=0; i<3; i=i+1){
        for(j=0; j<4; j=j+1){
            twoDim[i][j] = 0
        }
    }
    return 0
}

外部函数使用


extern int printf(string format)
extern int scanf(string format)

int testExtern(){
    string input
    scanf("%s", &input)
    printf("%d, %f, input = %s", 1, 0.1, input)
    return 0
}

词法分析

实现方式

词法分析是编译器实现中相对简单的一步。想好所需要实现的语法后，需要将输入转化为一系列的内部标记token。本项目定义的token包括：C语言关键字if、else、return、for、while、struct、int、double、extern等每个关键字对应的token，加减乘除、位运算、括号、逗号、取地址等符号token，以及表示用户自定义的标志符（identifier）的token、数字常量token（整型和浮点数）、字符串常量token等。

我们需要先在yacc源文件grammar.y中声明这些token，并在lex源文件token.l中定义这些token对应的操作，即遇到identifier、数字、字符串等token就将其内容保存到一个string对象中，并返回相应的tokenid以便之后bison程序用来进行语法分析；如果遇到if、else、while或运算符等静态的token就直接返回tokenid。

语法分析

实现方式

语法分析是本项目的关键环节之一。由于源代码是以字符串即字节流的形式存在的，难以进行后续的编译解释工作，因此我们需要将源代码转化成能够反映语法规则的数据结构，即抽象语法树（Abstract Syntax Tree，AST），之后才能利用抽象语法树进行语义分析，中间代码的生成。

抽象语法树实际上就是经过简化和抽象的语法分析树。在完整的语法分析树中每个推导过程的终结符都包含在语法树内，而且每个非终结符都是不同的节点类型。实际上，如果仅仅是要做编译器的话，很多终结符（如关键字、各种标点符号）是无需出现在语法树里的
抽象语法树实现

首先我们需要针对每种类型的语法，如变量声明、变量赋值、函数定义、控制流定义等语法定义其相应的抽象语法树，以便能够将任意符合语法标准的源代码都能够转化成一棵抽象语法树。

TinyCompiler支持语言的语法主要可以分为两类，有返回值的Expression——表达式，以及没有返回值的Statement——语句，这样一来所有合法的语法语句都可以归为表达式或语句中的一种。

因此，根据OOP思想，我们只需要定义抽象语法树的根节点Node类，以及两种语法对应的NStatement以及NExpression类，作为所有语法的抽象基类。之后所有语法对应的抽象语法树结点类，如表示For循环语句的NForStatement类，二元运算表达式的NBinaryOperator类，只需要继承这两个类中的一个并实现其接口即可。

现已实现的Expression即表达式类型包括整数、浮点数、变量、二元运算式、函数调用、数组元素、结构体、赋值、字符串，基本块；实现的Statement即语句类型包括变量定义、结构体定义、函数定义、表达式语句、if语句、for语句、数组初始化语句。

为了增强程序的鲁棒性，避免出现内存泄漏，本项目使用C++11提供的shared_ptr智能指针代替所有成员的裸指针，用于维护本语法特有的成员字段。此外，每类AST节点除了要维护这些字段外，还需要实现一个codeGen函数，作为每种语法树生成相应LLVM中间代码的接口。

Node抽象基类节点的定义
```
class Node {
protected:
    const char m_DELIM = ':';
    const char* m_PREFIX = "--";
public:
    Node(){}
    virtual ~Node() {}
    virtual string getTypeName() const = 0;
    virtual void print(string prefix) const{}
    virtual llvm::Value *codeGen(CodeGenContext &context) { return (llvm::Value *)0; }
};
```
各个AST结点类的继承关系如下图所示。

bison代码实现

bison（yacc）是基于类似于BNF的语法，使用定义的好终结符和非终结符来组成我们有效的每一个语句和表达式(这些语句和表达式就代表我们之前定义的AST节点)。例如：

if_stmt : TIF expr block 
{ $$ = new NIfStatement(shared_ptr<NExpression>($2), shared_ptr<NBlock>($3)); }
| TIF expr block TELSE block
{ $$ = new NIfStatement(shared_ptr<NExpression>($2), shared_ptr<NBlock>($3), shared_ptr<NBlock>($5)); }
| TIF expr block TELSE if_stmt 
{ 
    auto blk = new NBlock(); 
    blk->statements->push_back(shared_ptr<NStatement>($5)); 
    $$ = new NIfStatement(shared_ptr<NExpression>($2), shared_ptr<NBlock>($3), shared_ptr<NBlock>(blk)); 
}

例子中涉及到的NIfStatement结点的定义：

class NIfStatement: public NStatement{
public:

    shared_ptr<NExpression>  condition;
    shared_ptr<NBlock> trueBlock;       // should not be null
    shared_ptr<NBlock> falseBlock;      // can be null

    NIfStatement(shared_ptr<NExpression>  cond, shared_ptr<NBlock> blk, shared_ptr<NBlock> blk2 = nullptr)
            : condition(cond), trueBlock(blk), falseBlock(blk2){}

    string getTypeName() const override {
        return "NIfStatement";
    }

    void print(string prefix) const override;

    llvm::Value *codeGen(CodeGenContext &context) override ;
};

在该例子中，我们定义了一个if语句，针对每个语法后都注明了相应的语义动作，这个动作将在此条语法被规约（reduce）的时候被执行。这个过程将会递归地从叶符号到根结点符号的次序执行。在这个过程中，每个非终结符最终会被合并为一棵大的语法树。

例如，遇到 TIF expr block TELSE block 类型的语法时，说明解析到一个标准的if-else语法，这时候便调用NIfStatement类的构造函数，同时将所需要的条件表达式（$2)以及true和false所要执行的两个block作为函数参数传递进去，生成一个NIfStatement结点的对象后返回给上一层级。

语义分析

实现方式所谓编程语言的语义，就是一段代码的实际含义。比如最简单的一行代码：a = 1; 它的语义是“将32位整型常量存储到变量a中”。首先我们对“1”有明确的定义，它是32位有符号整型字面量，这里“32位有符号整型”就是表达式“1”的类型。其次，这句话成为合法的编程语言，32位整型常量必须能够隐式转换为a的类型。假设a就是int型变量，那么这条语句就直接将1存储到a所在内存里。如果a是浮点数类型的，那么这句话就隐含着将整型常量转换为浮点类型V的步骤。

在语义分析中，类型检查是贯穿始终的一个步骤。类型检查通常要做到：
- 判定每一个表达式的声明类型
- 判定每一个字段、形式参数、变量声明的类型
- 判断每一次赋值、传参数时，是否存在合法的隐式类型转换
- 判断一元和二元运算符左右两侧的类型是否合法（类型相同或存在隐式转换）
- 将所有要发生的隐式类型转换明确化
在TinyCompiler中，目前暂时使用NIdentifier即标识符对AST结点来存储类型信息（之后可以专门定义表示类型的数据结构用于表达类型）。标识符除了存储其字符串值之外，还使用两个bool变量isType以及isArray来表示该标识符是否为类型标识符，是否为数组类型的标识符。通过在grammar.y文件中定义相应的语义动作，我们实现了语法分析时发现一个标识符是类型标识符而非变量名，那么其isType以及isArray字段将立即被设为true。

NIdentifier定义：
```
class NIdentifier : public NExpression {
public:
    std::string name;
    bool isType = false;
    bool isArray = false;

    shared_ptr<NInteger> arraySize;

    NIdentifier(){}

    NIdentifier(const std::string &name)
        : name(name), arraySize(nullptr) {
    }

    string getTypeName() const override {
        return "NIdentifier";
    }

    void print(string prefix) const override;

    virtual llvm::Value* codeGen(CodeGenContext& context) override ;
};
```

类型系统实现

在有了能够表达类型的数据结构后，我们便能够通过类型名（name）以及isArray字段判断在一个变量声明语法（NVaraibleDeclaration类）中，变量所使用的类型了。但为了实现判断两种类型之间是否存在可转换的关系，以及以上类型检查所需要的其他操作，我们定义并实现了一个TypeSystem类专门用于存储类型相关、上下文无关的信息，包括各种隐式类型转换关系，是否为结构体，以及结构体各个成员类型等。

TypeSystem类定义：


class TypeSystem{
private:

    LLVMContext& llvmContext;

    std::map<string, std::vector<TypeNamePair>> _structMembers;

    std::map<string, llvm::StructType*> _structTypes;

    std::map<Type*, std::map<Type*, CastInst::CastOps>> _castTable;

    void addCast(Type* from, Type* to, CastInst::CastOps op);

public:
    Type* floatTy = Type::getFloatTy(llvmContext);
    Type* intTy = Type::getInt32Ty(llvmContext);
    Type* charTy = Type::getInt8Ty(llvmContext);
    Type* doubleTy = Type::getDoubleTy(llvmContext);
    Type* stringTy = Type::getInt8PtrTy(llvmContext);
    Type* voidTy = Type::getVoidTy(llvmContext);
    Type* boolTy = Type::getInt1Ty(llvmContext);

    TypeSystem(LLVMContext& context);

    void addStructType(string structName, llvm::StructType*);

    void addStructMember(string structName, string memType, string memName);

    long getStructMemberIndex(string structName, string memberName);

    Type* getVarType(const NIdentifier& type) ;
    Type* getVar

TinyCompiler

Install / Use

README

TinyCompiler

序言

语法定义

词法分析

语法分析

语义分析