学习Kaleidoscope:Kaleidoscope Introduction and the Lexer（万花筒语言的简介和词法）

万花筒语言简介和词法

万花筒语言

万花筒语言中唯一的数据类型是64位浮点类型（也就是C语言中的double），并且该语言不需要类型声明，例如下面的计算斐波那契数列的代码：

1
2
3
4
5
6
7
8
9
10
# 计算第x个斐波那契数.
# def：定义
def fib(x)
  if x < 3 then
    1
  else
    fib(x-1)+fib(x-2)

# 这个表达式会输出第40个斐波那契数
fib(40)

允许Kaleidoscope调用标准库函数（LLVM JIT使这完全无关紧要）。这意味着您可以在使用之前使用’extern’关键字来定义函数（这对于相互递归函数也很有用）。例如：

1
2
3
4
extern sin(arg);
extern cos(arg);
extern atan2(arg1 arg2);
atan2(sin(.4), cos(42))

词法分析器 / gettok

使用词法分析器分析万花筒语言

1
2
3
4
5
6
7
8
9
10
11
12
13
//如果token是未知字符，词法分析器返回对应的0~255，否则词法分析器将返回其中一个已知的token
enum Token {
  tok_eof = -1,
  // commands
  tok_def = -2,
  tok_extern = -3,
  // primary
  tok_identifier = -4,
  tok_number = -5,
};

static std::string IdentifierStr; // Filled in if tok_identifier
static double NumVal;             // Filled in if tok_number

词法分析器返回的每个标记将会是token的枚举值之一，或者它会是一个“未知”的字符，比如“+”，那么它将会作为ASCII值返回。

如果当前token是标识符，则string类型的全局变量IdentifierStr将会保存标识符的名称。

如果当前token是数字（如3.14），则NumVal保存其值。（为了简单起见，这里使用了全局变量，实际上这并不是最佳选择）。

词法分析器的实际实现是一个名为gettok的函数，gettok函数。

gettok函数通过调用C语言的getchar函数从标准输入每次读取一个字符，在识别他们时会“吃掉”他们，并在LastChar中保存最后一个未处理的字符。

gettok函数要做的第一件事就是忽略token之间的空格，通过下面的循环实现这一点：

1
2
3
4
5
6
7
8
///gettok——从标准输入返回下一个token
static int gettok()
{
    static int LastChar=''; //static类型，只初始化一次
    
    //跳过空白符
    while(isspace(LastChar))
        LastChar=getchar();

接下来gettok需要做的是识别标识符和特定的关键字比如“def”，通过下面的循环实现这一点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if(isalpha(LastChar)) //isalpha函数用于判断是不是字母(包含大小写)
{
    IdentifierStr=LastChar;
    while(isalnum((LastChar=getchar()))) //isalnum函数用于判断是数字或字母
        IdentifierStr+=LastChar;

    //检测到关键字
    if(IdentifierStr == "def")
        return tok_def;
    if(IdentifierStr == "extern")
        return tok_extern;
    //其他关键字
    return tok_identifier;
}

接下来处理数字相关：

1
2
3
4
5
6
7
8
9
10
11
12
13
if(isdigit(LastChar) || LastChar=='.') //isdigit函数用于判断是不是十进制数字
{
    //用于存放数字串
    std::string NumStr;
    do
    {
        NumStr += LastChar;
        LastChar = getChar();
    }while(isdigit(LastChar) || LastChar=='.');

    Numval = strtod(NumStr.c_str(),0); //将string转化为double
    return tok_number;
}

以上都是处理输入的非常简单的代码。从输入读取数值时，我们可以使用C语言的strtod函数将string类型转化为double类型，若要提高健壮性，则要进行数字检查（如1.23.456.7并不能和1.23一样处理），接下来是处理注释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    if(LastChar=='#')  //出现这个表示之后的一整行都是注释
    {
        do
        {
            LastChar=getchar();
        }while(LastChar!=EOF && LastChar!='\n' && LastChar!='\r');
    
        //通过一路跳到行尾来处理注释，然后返回下一个token
        if(LastChar!=EOF)
        {
            return gettok();
        }
    }

    if(LastChar==EOF)  //到达文件的末尾
        return tok_eof;

    //否则，就返回这个字符的ASCII
    int ThisChar=LastChar;
    LastChar=getChar();
    return ThisChar;
}

至此，就已经有了万花筒语言的完整词法分析器。

抽象语法树（AST）

表达式
表达式 / ExprAST / NumberExprAST
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//所有表达式节点的基类
class ExprAST
{
public:
    virtual ~ExprAST(){}
};

//数字抽象语法树——用于数字文字“1.0”的表达式类
class NumberExprAST: public ExprAST
{
    double Val;
public:
    NumberExprAST(double val) :val(Val){}
    
};

上面的代码显示了ExprAST基类的定义以及用于数字文本的一个子类的定义。

此代码的重要注意事项是NumberExprAST子类将数字文本的数值捕获为实例变量，便于编译器后续能够知道存储的数值是什么。

变量表达式AST / VariableExprAST

现在仅创建AST，因此现在没有写访问的方法（函数），以下是在万花筒语言的基本形式中使用的其他表达式的AST节点的定义：

1
2
3
4
5
6
7
8
9
//变量表达式抽象语法树——用于引用一个变量的表达式类，如“a”
class VariableExprAST: public ExprAST
{//用于存储变量名
    std::string Name;
public:
    //使用const保证传入的Name不被修改
    VariableExprAST(const std::string &Name): Name(Name){}
}

二元运算符表达式AST / BinaryExprAST
1
2
3
4
5
6
7
8
9
10
11
12
//二元运算符表达式抽象语法树——用于一个二元运算符的表达式类
class BinaryExprAST: public ExprAST
{
    char Op;
    //智能指针——一个仅能移动的类型，也可以自动释放内存。使用std::move函数将指针的所有权从一个unique_ptr转移到另一个unique_ptr
    std::unique_ptr<ExprAST> LHS,RHS;  //左被运算符，右被运算符
    
public:
    //将输入的Op给类内Op，将传入的智能指针转移到类内的智能指针
    BinaryExprAST(char op,std::unique_ptr<ExprAST> LHS,std::unique_ptr<ExprAST> RHS): Op(op),LHS(std::move(LHS)),RHS(std::move(RHS)){}
    
};
函数调用表达式AST / CallExprAST
1
2
3
4
5
6
7
8
9
10
//函数调用表达式抽象语法树
class CallExprAST: public ExprAST
{
    std::string Callee;
    std::vector<std::unique_ptr<ExprAST>> Args; //用于存储函数参数列表的数组
    
public:
    CallExprAST(const std::string &Callee,std::vector<std::unique_ptr<ExprAST>> Args): Callee(Callee),Args(std::move(Args)){}

};

变量捕获变量名称，二元运算符捕获它们的操作符（如“+”），函数调用捕获函数名称和它的参数表达式的列表。这里没有讨论二元运算符的优先级和词法结构。

函数声明AST / PrototypeAST

对于我们的基本语言，以上这些就是我们定义的所有表达式的节点。因为它没有条件控制流程，所以它不是图灵完备的。接下来需要解决的是讨论函数接口的方法以及讨论函数本身的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//这个类表示函数的声明，捕获函数名及其参数列表（因此隐式表示函数接受的参数）
class PrototypeAST
{
    std::string Name;
    std::vector<std::string> Args;
    
public:
    PrototypeAST(const std::string &name,std::vector<std::string> Args): Name(name),Args(std::move(Args)){}
    
    const std::string &getName() const
    {
        return Name;
    }
};
函数定义AST / FunctionAST
1
2
3
4
5
6
7
8
9
10
//这个类用于表示函数定义
class FunctionAST
{  
    std::unique_ptr<PrototypeAST> Proto; //上方类的智能指针，存储函数【声明】
    std::unique_ptr<ExprAST> Body; //存储函数体
    
public: 
    FunctionAST(std::unique_ptr<Prototype> Proto,std::unique_ptr<ExprAST> Body): Proto(std::move(Proto)),Body(std::move(Body)){}

};
解析基础

现在需要构建一个AST，需要定义解析器代码来构建它。这里的想法是我们要解析类似“x+y”（由词法分析器返回三个token）到AST中，可以通过这样的调用生成：

1
2
3
auto LHS = llvm::make_unique<VariableExprAST>("x");  //使用智能指针创建节点
auto RHS = llvm::make_unique<VariableExprAST>("y");  //使用智能指针创建节点
auto Result = std::make_unique<BinaryExprAST>("+",std::move(LHS),std::move(RHS));  //使用智能指针创建节点

首先需要定义一些基本的帮助程序：

缓冲区 / getNextToken
1
2
3
4
5
6
7
//提供一个简单的token缓冲区，CurTok是解析器正在查看的当前token
//getNextToken是从词法分析器读取下一个token，并用其来更新CurTok
static int CurTok;
static int getNextToken()
{
    return CurTok=gettok(); //在上方【词法分析器】章节中定义的函数
}

这样就在词法分析器周围实现了一个简单的token缓冲区，这允许我们在词法分析器返回时提前查看一个token，我们的解析器中的每个函数都假定CurTok是需要解析的当前标记。

错误帮助 / LogError
1
2
3
4
5
6
7
8
9
10
11
12
13
///这是用于错误处理的帮助函数
std::unique_ptr<ExprAST> LogError(const char*Str)
{
    fprint(stderr,"LogError: %s\n", Str); //stderr：标准错误
    return nullptr;
}

//函数“原型”
std::unique_ptr<PrototypeAST> LogErrorP(const char* Str)
{
    LogError(Str);
    return nullptr;
}

LogError程序是我们的解析器用来处理错误的简单的辅助程序。

基本表达式的解析
数字表达式的解析 / ParseNumberExpr

接下来从数字文本开始，对于数字文本，有：

1
2
3
4
5
6
7
//numberexpr::=number
static std::unique_ptr<ExprAST> ParseNumberExpr()
{ //可见上方对数字语法树的描述
    auto Result = llvm::make_unique<NumberExprAST>(NumVal); //使用智能指针创建节点
    getNextToken();  //消耗掉数字
	return std::move(Result);
}

这个程序希望在当前token是tok_number时被调用，它会获取当前数字的值，创建NumberExprAST子类的节点，然后将词法分析器前进到下一个token，最后返回。

括号运算符的解析 / ParseParenExpr

对于括号运算符，有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/// parenexpr ::= '(' expression ')'
static std::unique_ptr<ExprAST> ParseParenExpr()
{
    getNextToken();  //“吃掉”左括号“（”
    auto V = ParseExpression(); //解析表达式
    if(!V)
        return nullptr; //如果解析表达式为空
    if(CurTok != ')')
    {
        return LogError("expected ')'");
    }
    
    getNextToken();  //“吃掉”右括号“）”
    return V;
}

这个函数通过递归使用PareExpression来完成【详见下方的解析表达式】。

括号不会导致AST节点本身的构造，括号最重要的作用是引导解析器并提供分组，解析器构造AST后，不需要括号。

标识符表达式的解析 / ParseIdentifierExpr

下面是用于处理变量引用和函数调用的程序：

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
/// identifierexpr
/// 	::= identifier
/// 	::= identifier '(' expression* ')'
static std::unique_ptr<ExprAST> PraseIdentifierExpr()
{
    std::string IdName = IdentifierStr;
    
    getNextToken();  //“吃掉”标识符
    if(CurTok != '(') 
        return llvm::make_unique<VariableExprAST>(IdName);
    
    //函数调用
    getNextToken();  //吃掉左括号
    std::vector<std::unique_ptr<ExprAST>> Args;
    if(CurTok!=')')
    {
        while(1)
        {
            if(auto Arg = ParseExpression())
                Args.push_back(std::move(Arg));//依次将解析表达式加入数组中
            else
                return nullptr;
            
            if(CurTok==')')
                break;
            
            if(CurTok!=',')
                return LogError("Expected ')' or ',' in argument list");
            getNextToken();
        }
    }
    
    //吃掉右括号
    getNextToken();
    
    return llvm::make_unique<CallExprAST>(IdName,std::move(Args));
}

如果当前的token是tok_identifier，则希望调用这个函数。

主表达式的解析 / ParsePrimary

现在已经有了所有简答表达式的解析逻辑，可以定义一个辅助函数将它们组合成一个入口，称这类表达式为主要表达式。为了解析任意的主表达式，则需要确定它是什么类型的表达式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/// primary
///  ::= identifier
///  ::= numberexpr
///  ::= parenexpr
static std::unique_ptr<ExprAST> ParsePrimary()
{
    switch(CurTok)
    {
        default:
            return LogError("unknown token when expecting an expression");
        case tok_identifier:
            return ParseIdentifierExpr();
        case tok_number:
            return ParseNumberExpr();
        case '(':
            return ParseParenExpr();
    }
    
}

使用这段程序就能通过预测来确定正在检查哪种表达式，然后使用函数调用对其进行解析。

二元表达式的解析

二进制表达式很难解析，因为它们通常是模糊的。例如，当给定字符串“x + y z”时，解析器可以选择将其解析为“（x + y） z”或“x +（y *z）”。对于数学中的常见定义，我们期望后面的解析，因为乘法具有比加法更高的优先级。

优先级表 / GetTokPrecedence

有很多方法可以解决这个问题，但优雅而有效的方法是使用Operator-Precedence Parsing。此解析技术使用二元运算符的优先级来指导递归。首先，我们需要一个优先级表：

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
///它保留已定义的每个二元运算符的优先级
static std::map<char,int> BinopPrecedence;

//获取挂起的二元运算符token的优先级
static int GetTokPrecedence()
{
    if(!isascii(CurTok))
        return -1;
    
    //要确保它是一个已经声明的二元运算符
    int TokPrec = BinopPrecedence[CurTok];
    
    if(TokPrec<=0) return -1;
    
    return TokPrece;
}


int main()
{
    //规定标准的二元运算符
    //最低的优先级是1
    BinopPrecedence['<'] = 10;
    BinopPrecedence['+'] = 20;
    BinopPrecedence['-'] = 20;
    BinopPrecedence['*'] = 40;  //最高优先级
   
    ......
}

目前对于万花筒的基本形式，只写了四个二元运算符。使用GetTokPrecedence函数返回当前token的优先级，如果token不是二元运算符，则返回-1。使用map可以随意添加二元运算符。

通过上面定义的程序，现在可以开始解析二元表达式，因为括号是主表达式，所以二元表达式解析器不需要担心嵌套的子表达式。

解析表达式 / ParseExpression

运算符优先级解析的基本思想是将具有可能不明确的二元运算符的表达式分解为多个部分。

例如，考虑表达式“a + b +（c + d） *e* f + g”。

它将首先解析主要的主要表达式“a”，然后它将看到对**[+，b] [+，（c + d）] [*，e] [*，f]和 [+，g]** 。请注意，因为括号是主表达式，所以二进制表达式解析器根本不需要担心嵌套的子表达式，如（c + d）。

首先，表达式是一个主表达式，可能后面跟一系列【binop，primaryepxr】对：

1
2
3
4
5
6
7
8
9
10
11
/// expression
/// 	::= primary binoprhs
///
static std::unique_ptr<ExprAST> ParseExpression()
{
    auto LHS = ParsePrimary(); //分析二元表达式左部的主表达式，见上方【主表达式的解析】
    if(!LHS)
        return nullptr;
    
    return ParseBinOpRHS(0,std::move(LHS));
}

ParseBinOpRHS是解析对序列的函数，它需要一个优先级和一个指向目前已解析的部分的表达式的指针。

解析二元表达式的右部 / ParseBinOpRHS

传入的优先级的值表示允许该函数吃掉的最小的运算符优先级。例如，如果当前的对是【+，x】，并且ParseBinOpRHS传入的是40的优先级，则该函数不会吃掉任何token（因为加号的优先级仅为20），考虑到这一点，则有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/// binoprhs
/// 	::= ('+' primary)*
static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,std::unique_ptr<ExprAST> LHS)
{
    //如果这是一个二元运算符，就需要它的优先级
    while(1)
    {
        int TokPrec = GetTokPrecedence();
        
        //这个（下一个）运算符的优先级大于当前的运算符，就消耗掉它，否则就结束程序
        if(TokPrec < ExprPrec)
            return LHS;
        
        //现在我们知道这是一个二元运算符了
        int BinOp = CurTok;
        getNextToken();  //吃掉这个运算符,将其包含在表达式中
        
        //分析二元运算符之后的主表达式
        auto RHS = ParsePrimary();
        if(!RHS)
            return nullptr;

此代码获取当前token的优先级，并检查它是否过低，因为我们将无效的即除了运算符以外的字符的优先级定义为-1，所以此检查知道标记流消耗掉二元运算符时，就停止对流，

这样一来，此程序吃掉并记住二元运算符，然后解析其右部的主表达式。

现在我们解析了运算符左部的表达式和一对RHS序列，接下来必须决定表达式关联的方式。特别是可能有“**（a+b） binop unparsed **” 或者“a+（b binop unparsed） ” 两种形式，为了确定这一点，我们预观测binop并确定其优先级，并将其与BinOp（当前是指a后面的加号）的优先级进行比较，显然binop是“+”，优先级小于等于BinOp，故选择第一种形式。

1
2
3
4
5
// 如果预测运算符的优先级小于等于当前运算符，就把当前处理的对的右部与左侧关联，即 (a+b) binop unparsed
// 如果预测运算符的优先级大于当前运算符，就把当前处理的对的右部与右侧关联，即 a+(b binop unparsed)
int NextPrec= GetTokPrecedence();
if(TokPrec < NextPrec)
{

  • 考虑表达式“a + b +（c + d） *e* f + g”：

    它将首先解析主要的主要表达式“a”，然后它将看到对**[+，b] [+，（c + d）] [*，e] [*，f]和 [+，g]** 。

如果binop在RHS右边的优先级小于等于当前运算符的优先级，那么就是**（a+b）binop**。当前运算符为**+，下一个运算符为+，他们有相同的优先级，在这种情况下，将为a+b**创建AST节点，然后继续解析：

1
2
3
4
5
6
7
8
			...省略if体...
	}

	//合并 LHS/RHS
	LHS = llvm::make_unique<Binary<ExprAST>(BinOp,std::move(LHS),std::move(RHS));

	 	} //跳转回顶部，继续执行while循环
}

上面的例子中，会把a+b+变成(a+b)进行下一次的循环，其中第二个+作为当前token，将上面代码消耗，存储并解析(c+d)作为主表达式，就使得当前的对变成了**[+,(c+d)]，然后它将使用下一个***作为主要右侧的二元运算符来进行上方if条件的判断，这种情况下，***的优先级大于+**的优先级，因此执行if体中的代码。

接下来的关键问题就是：如何在if里完全解析右部。特别是，要构建正确的AST，它需要将所有的**(c+d)*e*f**作为RHS表达式变量，执行此操作的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 如果预测运算符的优先级小于等于当前运算符，就把当前处理的对的右部与左侧关联，即 (a+b) binop unparsed
		// 如果预测运算符的优先级大于当前运算符，就把当前处理的对的右部与右侧关联，即 a+(b binop unparsed)
		int NextPrec= GetTokPrecedence();
		if(TokPrec < NextPrec)
		{
            RHS = ParseBinOpRHS(TokPrec+1,std::move(RHS));
            if(!RHS)
                return nullptr;
        }

		//合并 LHS/RHS
		LHS = llvm::make_unique<Binary<ExprAST>(BinOp,std::move(LHS),std::move(RHS));

 	 	} //跳转回顶部，继续执行while循环
	}

此时，我们知道我们主要RHS的二元运算符的优先级高于当前的二元运算符，因此我们知道任何优先于**+的对的序列应该被一起解析并被返回为RHS**。为此，就要用递归方式调用ParseBinOpRHS，指定TokPrec+1作为其继续执行的最小优先级。在上面的例子中，这会导致它将**(c+d)*e*f的AST节点作为RHS返回，最后将其设置为第二个+**的RHS。

最后，在下一次的while循环中，解析**+g**并将其添加到AST。

此时，已经可以将解析器指向任意token流并从中构建表达式，并且会停止在不属于表达式的第一个token处。

解析函数声明 / ParsePrototype

目前缺少功能原型的处理，在万花筒语言中，这些用于extren函数声明以及函数体定义。

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
/// prototype
///  ::= id '(' id* ')'
static std::unique_ptr<PrototypeAST> ParsePrototype()
{
    //需要输入函数名（标识符）
    if(CurTok!=tok_identifier)
        return LogErrorP("Expected function name in prototype");
    
    //使用全局变量IdentifierStr保存函数名
    std::string FnName = IdentifierStr;
    getNextToken();
    
    //函数需要输入括号
    if(CurTok!='(')
        return LogErrorP("Expected '(' in prototype");
    //读取参数名列表
    std::vector<std::string> ArgNames;
    //如果下一个token是
    while(getNextToken() == tok_idenifier)
        ArgNames.push_back(IdentifierStr);
    //函数需要定义
    if(CurTok!='(')
    	return LogErrorP("Expected ')' in prototype");
    
    //完成 
    getNextToken();  //吃掉右括号
    
    //构建函数AST
    return llvm::make_unique<PrototypeAST>(FnName,std::move(ArgsNames));
}
解析函数定义 / ParseDefinition
1
2
3
4
5
6
7
8
9
10
11
12
/// definition ::= 'def' prototype expression
static std::unique_ptr<FunctionAST> ParseDeFinition()
{
    getNextToken();  //吃掉def
    auto Proto = ParsePrototype();
    if(!Proto) return nullptr;  //如果函数声明是空
    
    if(auto E = ParseExpression())
        return llvm::make_unique<FunctionAST>(std::move(Proto),std::move(E));
    
    return nullptr;
}

另外，支持extern来声明sin和cos之类的函数，以及支持用户函数的向前声明，这些extern只是没有代码体的声明：

1
2
3
4
5
6
/// external ::= 'extern' prototype
static std::unique_ptr<PrototypeAST> ParseExtern()
{
    getNextToken(); //吃掉extern
    return ParsePrototype();
}

最后，还让用户输入任意顶级表达式并动态评估它们，将通过为它们定义匿名的nullary（零参数）函数来处理这个问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
/// toplevelexpr ::=expression
static std::unique_ptr<FunctionAST> ParseTopLevelExpr()
{
    if(auto E = ParseExpression())
    {
        //创造一个匿名函数声明
        auto Proto = llvm::make_unique<PrototypeAST>("",std::vector<std::string>());
        
        return llvm::make_unique<FunctionAST>(std::move(Proto),std::move(E));
    }
    
    return nullptr;
}

到现在，已经完成了所有部分。

驱动程序

下面的程序只是通过顶级调度循环调用所有解析的程序：

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
/// top ::= definition | external | expression | ';'
static void MainLoop()
{
    while(1)
    {
        fprint(stderr,"ready>");
        switch(CurTok)
        {
            case tok_eof:
                return;
            case ';':  //忽略顶级分号
                getNextToken();
                break;
            case tok_def:
                HandleDefinition();
                break;
            case tok_extern:
                HandleExtern();
                break;
            default:
                HandleTopLevelExpression();
                break;
        }
    }
}

  • 忽略顶级分号：

    如果在命令行中输入4+5，解析器不能确定是不是已经结尾，第一种情况，在下一行可以继续输入def foo，在这种情况下，4+5是顶级表达式的结尾；或者可以继续输入***6**，这将继续表达式的输入。使用顶级分号将允许输入4+5，这样解析器就会知道已经输入完成。

代码生成LLVM IR

代码生成设置

为了生成LLVM IR，需要一些简单的设置才能开始。

首先，要在每个AST类中定义虚拟方法codegen

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 原代码见【表达式】
class ExprAST 
{
    
public:
  virtual ~ExprAST() {}
  virtual Value *codegen() = 0;
    
};



class NumberExprAST : public ExprAST 
{
  double Val;
    
public:
  NumberExprAST(double Val) : Val(Val) {}
  virtual Value *codegen();
    
};

codegen方法表示为该AST节点发出IR及其依赖的所有内容，并且它们都返回一个LLVM Value对象，Value是用于表示LLVM中的静态单一分配（SSA）寄存器或SSA值。

SSA值得最独特之处在于它们的值是在相关指令执行时计算的，并在指令重新执行之前不会获得新值。也就是说，没有办法改变SSA值。

接下来要完成像之前用于解析器的LogError的方法，它将用于报告在代码生成期间发现的错误：

1
2
3
4
5
6
7
8
9
10
static LLVMContext TheContext;
static IRBuilder<> Builder(TheContext);
static std::unique_ptr<Module> TheModule;
static std::map<std::string,Value *> NameValues;

Value *LogErrorV(const char *Str)
{
    LogError(Str);
    return nullptr;
}

以上的静态变量将在代码生成期间使用。

TheContext是一个不透明的对象，拥有许多核心LLVM数据结构。

Builder对象是一个辅助对象，可以生成LLVM指令。IRBuilder类模板的实例可以跟踪插入指令的当前位置，并具有创建新指令的方法。

TheModule是一个包含函数和全局变量的LLVM构造。

NameValues图跟踪哪些值在当前范围内，是代码的符号表。在这种形式的万花筒语言中，唯一可以引用的是功能参数。

表达式代码生成

为表达式节点生成LLVM代码

数字文本

首先编写数字文本

1
2
3
4
Value *NumberExprAST::codegen()
{
  return ConstantFP::get(TheContext, APFloat(Val));
}

在LLVM IR中，数字常量用ConstantFP类表示，它在APFloat内部保存数值（APFloat能够保持任意精度的浮点常量）。这段代码基本上只是创建并返回一个ConstantFP。

在LLVM IR中，常量都是唯一的并且共享，出于这个原因，API使用foo::get (…) 而不是new foo (…)或foo::Create (…)。（即不用再次创建）

变量
1
2
3
4
5
6
7
8
9
10
Value *VariableExprAST::codegen() 
{
  // 在函数中查找此变量
  Value *V = NamedValues[Name];
    
  if (!V)
    LogErrorV("Unknown variable name");
    
  return V;
}

在简单版的万花筒语言中，假设变量已经在某处发出并且其值可用。

实际上，NamedValues映射中唯一的值是函数参数，此程序只是检查指定的名称是否在映射中（如果没有，就引用未知变量）并返回其值。

二元运算符
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
Value *BinaryExprAST::codegen() 
{
  Value *L = LHS->codegen();
  Value *R = RHS->codegen();
    
  if (!L || !R)
    return nullptr;
    
  switch (Op) 
  {
  case '+':
    return Builder.CreateFAdd(L, R, "addtmp");
  case '-':
    return Builder.CreateFSub(L, R, "subtmp");
  case '*':
    return Builder.CreateFMul(L, R, "multmp");
  case '<':
    L = Builder.CreateFCmpULT(L, R, "cmptmp");
          
    //将布尔值0/1转化为双精度值0.0/1.0
    return Builder.CreateUIToFP(L, Type::getDoubleTy(TheContext),
                                "booltmp");
  default:
    return LogErrorV("invalid binary operator");
  }
    
}
函数调用
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 *CallExprAST::codegen() 
{
  
  //在全局模块表中查找名称
  Function *CalleeF = TheModule->getFunction(Callee);
    
  if (!CalleeF)
    return LogErrorV("Unknown function referenced");
    
  // If argument mismatch error.
  if (CalleeF->arg_size() != Args.size())
    return LogErrorV("Incorrect # arguments passed");
    
  std::vector<Value *> ArgsV;
    
  for (unsigned i = 0, e = Args.size(); i != e; ++i)
  {
    ArgsV.push_back(Args[i]->codegen());
      
    if (!ArgsV.back())
      return nullptr;
  }
    
  return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
}
功能代码生成
声明代码的生成
1
2
3
4
5
6
7
8
9
10
11
Function *PrototypeAST::codegen() 
{
  // 创建函数类型:  double(double,double) etc.
  std::vector<Type*> Doubles(Args.size(),
                             Type::getDoubleTy(TheContext));
    
  FunctionType *FT =
    FunctionType::get(Type::getDoubleTy(TheContext), Doubles, false);
    
  Function *F =
    Function::Create(FT, Function::ExternalLinkage, Name, TheModule);

FunctionType::get创建FunctionType，它的调用应该用于给定的Prototype。由于Kaleidoscope中的所有函数参数都是double类型，因此第一行创建了一个“N”LLVM double类型的向量。然后它使用该Functiontype::get方法创建一个函数类型，该函数类型将“N”双精度作为参数，结果返回一个double，而不是vararg（false参数表示这一点）。请注意，LLVM中的类型与常量一样是唯一的，所以你不要new一个类型，你get它。

上面的最后一行实际上创建了与Prototype相对应的IR功能。这表示要使用的类型，链接和名称，以及要插入的模块。外部链接意味着该功能可以在当前模块外部定义,可以由模块外部的功能调用。传入的名称是用户指定的名称：由于指定了TheModule，因此该名称在TheModule符号表中注册。

1
2
3
4
5
6
7
// 设置所有参数的名称
unsigned Idx = 0;

for (auto &Arg : F->args())
  Arg.setName(Args[Idx++]);

return F;

我只能说，再往后我就不会了

就写到这里了，以后看情况可能会再写一点