# fajal

**Repository Path**: cp-is-delicious/fajal

## Basic Information

- **Project Name**: fajal
- **Description**: 编程语言 Fajal

追求优雅和高性能！
- **Primary Language**: C++
- **License**: Apache-2.0
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2021-05-26
- **Last Updated**: 2022-06-13

## Categories & Tags

**Categories**: Uncategorized

**Tags**: 编译器

## README

## 0	分工与框架

揭海亮：词法分析，语法分析

邓子烽：语义分析，IR至Object File生成

### 开发框架

主要使用CMake管理所有的源文件和选项开关，按照需求生成Fajal编译器。

![开发框架](./assets/编译Fajal架构.png)

### 运行框架

在运行时，Fajal最多生成x64平台下的Object File，后续依赖gcc或其他工具进行链接。

![运行框架](./assets/Fajal编译架构.png)

## 1	词法分析

	借助flex工具完成词法分析工作，代码位于主目录下token.l文件中

### 	1.1	特点

- 支持单行/多行注释
- 支持转义字符读取
- 区分字符与字符串，字符使用**''**，字符串使用**""**
- 支持数据类型：布尔型、字符型、整型、单浮点型、双浮点型、字符串型及它们各自的引用类型
- 支持运算：算术运算、逻辑运算与简单的单目运算

###     1.2    定义关键字

```
if	else	return	for	while	break	continue	struct	class	fun	Void
Bool&	Bool	Char&	Char	Int&	Int	Float&	Float	Double&	Double
String&	String	val	var	true	false
```

### 	1.3	变量名、数值与字符内容的获取

```json
[a-zA-Z_][a-zA-Z0-9_]*	//匹配变量名
[0-9]+\.[0-9]*	//匹配浮点值
[0-9]+	//匹配整型
\'(\\.|[^"]|\\0|\\t|\\n|\\r)\'	//匹配单字符
\"(\\.|[^"])*\"	//匹配字符串
```

###     1.4	其他

```json
//其他字符获取
"="	"=="	"!="	"<"	"<="	">"	">="
"("	")"	"{"	"}"	"["	"]"
"."	","	":"	";"
"+"	"-"	"*"	"/"	"%"
"++"	"--"
"&&"	"||"	"!"
"^"	">>"	"<<"	//画饼部分
```

### 	1.5	关于YYSTYPE定义

```C++
struct ASTNode {
    OpType op;
    llvm::Type *type = nullptr;

    llvm::SmallVector<Expr *> initArgs;
    llvm::SmallVector<llvm::Type *> funParaTypes;
    llvm::SmallVector<std::string> funParaNames;
    llvm::SmallVector<bool> funParaIsRefs;
    llvm::SmallVector<uint64_t, 2> arraySizes;

    bool isFunParaRef = false;
    int iValue = 0;
    double dValue = 0.0;
    char c = '\0';
    std::string content;
    Expr *node = nullptr;
    ASTNode() { }

    ASTNode& operator=(const ASTNode&) = default;
    ASTNode& operator=(ASTNode&& o);
};

typedef struct ASTNode YYType;

#define YYSTYPE YYType

//token.l中使用到的成员
OpType op;	llvm::Type* type;	isFunParaRef;	iValue;	dValue;
char c;	std::string content;
```



## 2	语法分析

### 	2.1	语法树粗览

```mermaid
flowchart TD
	A([program]) -.*.-> B([decl])
	B --> C([func_decl])
	B --> D([struct_decl])
	B --todo--> E([class_decl])
	C --> FUN_HEAD([func_head])
	FUN_HEAD --> F([func_name])
	FUN_HEAD --> ARG([func_args])
	FUN_HEAD --> RETURN([return type])
	C --> FUN_BODY([func_body])
	FUN_BODY --> BLOCK([block])
	FUN_BODY --> G([eq decl])
	D --> H([struct_name])
	D -.*.-> VAR([var_decl])
	D -.*.-> C
	BLOCK -.*.-> if_stmt([if_stmt])
	BLOCK -.*.-> for_stmt([for_stmt])
	BLOCK -.*.-> while_stmt([while_stmt])
	BLOCK -.*.-> VAR([var_decl])
	BLOCK -.*.-> expr([expr])
	BLOCK -.*.-> other([other])
```

### 	2.2	代码例子

<a id="22"></a>

1. hello, world输出

![hello,world例子](./assets/hello_world.png)

![AST:hello,world](./assets/helloworld.svg)

1. 数组的声明与使用

![数组声明与使用](./assets/arrRef.png)


![AST:数组使用](./assets/arrayRef.svg)


1. for循环的使用


![for语句使用](./assets/for.png)

![AST:for循环使用](./assets/for.svg)

1. 函数调用



![函数调用例子](./assets/if.png)

![AST:函数调用](./assets/if.svg)

## 3 语义分析

Fajal编译器使用Expr基类及其派生类来表示抽象语法树AST的节点。在语法分析阶段，我们利用Yacc完成了AST节点的构建和连接，我们将在完整的AST上进行语义分析。

### 3.1 类型系统

我们在语法层面上提供了多个内建基础类型，在此基础上允许数组和结构体的任意嵌套。在语义分析中，Fajal编译器将语法层面的类型映射到llvm::Type中。实际上在AST构建完成后，语法层面的类型已经被完全“遗忘”。

![类型映射举例](./assets/type.png)

对于数组类型，我们用元素类型和长度的组合来表示。类似地映射到llvm::ArrayType。


![数组类型映射举例](./assets/ArrayType.png)

 对于结构体类型，我们用成员名字和类型的vector来表示。由于LLVM的结构体类型不能记忆成员名字，我们需要额外地使用符号表来储存和引索每个成员对应的结构体内下标。

![结构体类型映射举例](./assets/StructType.png)

### 3.2 符号表栈

由于作用域是以栈的形式嵌套，所以符号表的顶层设计也自然按照栈的形式排布。符号表栈的每一层对应作用域栈的每一层。在每个作用域中，我们动态维护以下信息：新建的符号（变量），被当前作用域隐藏的外层作用域符号（变量），分支信息（break锚点，continue锚点）。在全局，我们动态维护以下信息：当前可见的符号（变量，函数，结构体定义），当前可见的分支信息（break锚点，continue锚点）。

我们用Scope类的单例模式来维护以上信息，此外，我们使用ScopeGuard类以RAII的模式来保证作用域的创建和删除的配对安全。


![维护符号表栈的结构](./assets/Scope.png)


### 3.3 AST类层次组织

我们将语句和表达式都抽象为Expr基类（对于语句，其返回值类型为Void），并按照功能分类，派生出子类。如下类图所示：


![AST类层次组织](./assets/Hierarchy.svg)

在开发后期我们向Fajal添加AST可视化功能，需要使用访问者(Visitor)模式，因此我们向Expr类添加了父类Acceptor。

在Fajal编译器中Expr类和子类起到承上启下的作用：它面向Yacc暴露构造函数接口，使Yacc具有构造AST的能力。它基于LLVM实现了codegen（IR代码生成）接口，开启了编译器后端流程。我们将在下一章分析中间代码生成。

 

## 4	中间代码生成

Fajal基于LLVM，将AST转化为LLVM IR作为中间代码。负责IR生成工作的是Expr类的纯虚函数codegen。下面我们分类列举不同AST节点的codegen任务。

### 4.1	字面量的IR生成

对于字面量（literal的子类），codegen通常只要返回一个常量的缓存。例如Int::codegen()如下

![Int的主要功能](./assets/Int.png)


对于字符串常量则有些特殊，因为它需要在数据段申请一段空间，来存放字符串。我们将申请空间的操作提前到构造函数中，避免重复codegen浪费空间。返回值则是字符串所在地址。


![StringPtr的主要功能](./assets/StringPtr.png)


### 4.2	运算符的IR生成

对于二元运算符（BinaryOp），它的codegen任务比较繁重，所以我们切分出多个子函数，分类讨论逐个处理。

首先，最频繁的运算符可能是分号。为了支持“最后一条表达式是作用域的返回值”的语法糖，我们令分号的返回值是右手边的操作数。


![BinaryOp：分号](./assets/semi.png)


其次可能是赋值运算符。我们要检查等号左边是不是一个已定义的变量，然后在符号表中找到变量的地址，然后计算等号右边的表达式结果，检查两边的类型相符合后，将右边的值写入变量的所在地址中。由于LLVM SSA的优雅性，可以认为赋值运算的返回值就是等号右边的值。


![BinaryOp：赋值](./assets/assign.png)


接下来是算术运算和逻辑运算。Fajal运算算术运算中的隐式类型转换，规则是“小类型向大类型”转换。在保证两操作符正确转换类型后，依据操作数类型来添加算术或逻辑指令。

![BinaryOp：算术（逻辑）运算](./assets/Binary.png)


以上是BinaryOp类的主要功能，再底层的运算符生成只是简单的分类讨论和创建IR运算语句，非常基础而不须赘述。


### 4.3	变量的IR生成

下面是比较重要的Var类。Var类代表一个变量的定义或者引用，还要注意Var类的向后兼容性（Array类和Struct类）。在codegen中，首先根据定义或引用来分类讨论。如果是定义，则需要申请栈空间，计算、检查和储存初始值，还要添加变量到符号表。如果是引用，还要分类讨论按值引用和按地址引用，来决定查询符号表后的返回值。


![IR生成：定义变量](./assets/valdef.png)


![IR生成：按值引用变量](./assets/valval.png)


![IR生成：按地址引用变量](./assets/valref.png)



### 4.4	分支控制的IR生成

下面是分支控制的IR代码生成，我们选取比较全面的For循环来介绍。For循环包含init, condition, step 和 body四个部分，Fajal将它们组织成LLVM的BasicBlock，并加以连接。在For类的codegen中，Fajal首先创建一个作用域；接着生成init的IR，然后创建三个llvm::BasicBlock作为分支控制的锚点，分别对应condition, body 和循环结束。然后分别分别生成condition, body和step的IR。在condition BasicBlock的末尾，创建CondBr语句。在body的末尾，要判别最新的BasicBlock中有没有跳转指令（由于AST的递归，最新的BasicBlock可能不再是body的入口所在），如果已有跳转指令，说明有break或continue或return抢先进行了跳转；如果没有跳转指令，则要跳转到condition BasicBlock中。

![IR生成：For循环：初始化和设置锚点](./assets/forStart.png)

![IR生成：For循环：body结束和循环结束](./assets/forEnd.png)



注意到我们在作用域中设置了break和continue的锚点，如果在body内碰见对应的语句，只要跳转到设定的锚点即可。


## 5	优化以及进阶主题


### 5.1	结构体和任意维数组

在Fajal中实现结构体有以下难点：一是编译器在遇见形如”a.b.c”的结构成员访问时，通常不直接知道”a”的类型，需要查询符号表，查到”a”是某一个struct。二是不知道”b”是结构体内的第几个成员（而LLVM需要知道），又需要查询符号表，查到”b”的引索。三是”b”的类型可能还是一个结构体，编译器需要具有递归解析的能力。四是在使用LLVM的`getElementPointer`时很容易迷惑，这也是任意维数组的难点。

Fajal为结构体提供了全局符号表，并针对结构体和数组提供可递归的解析能力。

以按值引用一个任意维数组中的元素为例。如果当前维度不是最高维，那么在Yacc中我们获得了对高维数组的解引用，现在需要进行低维解引用；否则当前维度是最高维，我们需要先查找符号表，然后进行第一次解引用。然后对现有值解两次引用（这是由于LLVM GEP的特性）。对结构体的操作也是类似，只不过要依赖符号表进行引索。


![任意维数组：分类讨论是否最高维](./assets/arrStart.png)


![任意维数组：令LLVM解两次引用](./assets/arrEnd.png)


![结构体：在构造函数将结构体定义插入到符号表](./assets/StructStart.png)

### 5.2	AST可视化

我们使用Graphviz工具进行AST的可视化，效果如[2.2代码例子](#22)所示。为了能遍历整个AST而尽量减少对已有代码的改动，我们采用Visitor模式，令Expr基类继承自Acceptor，然后对每一个子类实现accept方法，将数据的访问权赋给我们的图生成器，生成Dot Lang。由Graphviz解析 Dot Lang 然后生成svg格式的AST图。

令Expr的具体子类调用accept函数，令控制权转移到visitor（即GraphGenerator）中，调用相应的visit函数。下面以针对For循环生成子图为例：


![针对For循环的图生成](./assets/forGraph.png)


![在处理子节点后添加父子单向边](./assets/handleChild.png)


## 测试结果

在递归、结构体和任意维数组的支撑下，三个测试题均完全通过。


![auto-advisor测试](./assets/image-20210628235111825.png)


![matrix-multiplication测试](./assets/image-20210628235137927.png)

![quicksort测试](./assets/image-20210628235157457.png)