HNUSTC 编译器14天速通后记

发表于 2022-05-25 更新于 2023-01-28 分类于项目本文字数： 48k 阅读时长 ≈ 43 分钟

前情提要

对我校编译原理没有实验课，没有课程设计，就是纯纯的理论很不爽，在与老师沟通后开始尝试写一个用于教学目的的编译器，在此之前我已经实现了正则表达式的解析和LL文法的分析，对于实现一个编译器很有兴趣。本着跟计算机打交道这么多年，连一个编译器都没摸透过的遗憾心理开始了编译器速通计划。

先花了一个星期确定技术栈上，最终我们敲定了先使用lex+yacc，然后借助llvm的框架快速搭建一个以llvm ir为目标代码的编译器。语言选定为C98的一个子集，去除了一些无关紧要的特性，保留了结构体等比较重要的特性。

然后是漫长的看各种手册实现的过程，在不断的思考-实现-碰壁循环中最终花费大约两个星期实现了一个最简单的编译器，但是相比原计划还是削减了一些重要的特性，比如结构体和函数指针。最终代码量总和在1k行左右，编译中的各个阶段均能独立运行输出调试结果。拿libreoj上的两道题跑了两个简单的测试，能过应该就没问题了。

开源以后再说吧。

简介

HNUSTC语言是C语言的一个相差极小的子集（），去除了C语言一些对于学习编译原理无关紧要的特性。本参考手册提供了HNUSTC的语言文法定义以便同学们能够更轻松的实现HNUSTC编译器。以下是HNUSTC语言相比C语言（C98）特性差别的一个快速概览。

只考虑单文件（单编译单元）编译
自动引入标准库
没有预处理器（意味着不能使用assert等依赖宏的组件）
没有结构体和函数指针
没有inline、register、goto、extern、case、union、static、const、goto、volatile、default、do、typedef
没有内嵌汇编
没有函数指针
简化的字面量形式，简化的变量初始化形式
以ixx表示xx位有符号整数
没有函数声明，函数定义顺序不影响编译执行结果
局部变量定义只允许出现在函数定义之后
没有显式类型转换和泛化的隐式转换

词法分析

以下用正则表达式描述了HNUSTC的单词定义。;开头的行为注释。

在词法分析阶段进行简单的字面量翻译。

注释

HNUSTC支持单行和多行注释，词法分析器遇到时将会忽略。

关键字

;流程控制
while
for
if
else
return
;基本类型
i8 i16 i32 i64 i128
f32 f64
void
;特殊字面量
NULL
;类型操作
sizeof

为了实现方便放弃实现无符号整形。删除了C中令人困惑的类型long int，使用ixx表示xx位有符号整形，f32表示float，f64表示double。

运算符

按优先级排序，越前面优先级越高。

第一列描述了结合性，如果没有则顺延上一个描述了结合性的行的结合性。[a-z]描述了其他表达式。

以{...}为注释

从左到右 a(b){函数调用} a[b]{数组}
从右到左 +a{单元加} -a{单元减} !a ~a *a &a sizeof a
从左到右 a*b a/b a%b
		a+b a-b
		a<<b a>>b
		a<b a<=b a>b a>=b
		a==b a!=b
		a&b
		a^b
		a|b	
		a&&b
		a||b
从右到左 a=b
从左到右 a,b

为了实现方便，我们去除了++,--以及如+=各种组合赋值运算符，还有三元运算符?:。

运算符优先级不等于求值顺序。

标识符

以下定义了一个标识符。

1	[a-zA-Z_][a-zA-Z_0-9]*

标识符不能与现有关键字相同。

字面量

;字符串字面量
".*?[^\\]"
;字符字面量
'.*?[^\\]'
;整形字面量(十进制)
[0-9]+
;整形字面量(十六进制)
0x[0-9A-Fa-f]+
;浮点字面量(十进制)
[0-9]+\.?[0-9]*[Ee][\+-]?[0-9]+|\.[0-9]+([Ee][\+-]?[0-9]+)?
;NULL字面量
NULL

相比C，为了实现方便，HNUSTC去除了八进制字面量并简化了浮点字面量的定义。

整形字面量均为i32，如果不能完整表示则提升至最少能表示的整形，浮点字面量均为f64。

在C中，NULL由宏定义，因为HNUSTC没有宏所以将NULL提升为字面量，等价与0。

语法分析

在词法分析完成后，ply生成了一个由单词token组成的串，每一个token还附带一个额外的的值，可以通过定义函数直接处理字面量，接下来语法分析阶段将这些token归约为对应的文法，并利用这个额外的值构建语法分析树。

这里给出了HNUSTC语法的顶层设计

程序 program
           |
定义 declare/函数定义 declare_func
                               |
语句 statement |               |
               | - 复合语句 compound_statements-----------|
               | - 选择语句 selection_statements----------|
               | - 表达式语句 expression_statements-------|
               | - 循环语句 iterator_statements-----------|
               | - 跳转语句 jump_statements---------------|
                                                          |
                                                          |
表达式 expression-----------------------------------------|

程序由定义或者函数定义组成，函数定义引入复合语句。

1
2
3

program : declare program  
        | declare_func program
        | empty

empty表示空token。

定义 declare

HNUSTC使用定义引入变量：

declare : specifiers declarators_and_initializers ";"

specifiers : TYPENAME

declarators_and_initializers : declarator_and_initializer COMMA declarators_and_initializers 
                            | declarator_and_initializer

declarator_and_initializer : declarator initializer 
                            | declarator

initializer : ASSIGN nocomma_expression

declarator : STAR declarator %prec dec_ptr

declarator :  "(" declarator ")"

declarator : declarator "[" INTEGERINSTANT "]" %prec dec_array

declarator : IDENT

其中specifiers和declarator共同确定了标识符的类型。

其中declarator使用dec_ptr和dec_array并指明优先级是为了防止诸如int *a[3];的歧义发生，此时优先使用dec_array，那么从里至外为a,长度为3的数组,指针,int。a的含义为包含三个指针int的数组。

HNUSTC这么做的动机是对着a反向进行declarator的操作，最终类型会变成specifiers。比如*(a[0])是int类型。

背后原理跟编译原理有关，如果按照这种文法直接生成语法分析树的话，一边遍历树一边push节点进栈，最终栈顶就是顶层的类型，要对这种值运算的话就可以很方便的进行类型计算。

函数定义 declare_func

declare_func : parameter "(" parameters ")" "{" function_body "}"

parameters : parameter COMMA parameters 
            | parameter

parameter : type_name

type_name : specifiers declarator

initializer : ASSIGN nocomma_expression

function_body : compound_statements

函数定义不是语句，只能在程序顶层使用。

语句 statement

共五种语句：复合语句、选择语句、表达式语句、循环语句、跳转语句。

statements : "{" compound_statements "}" 
            | expression_statements   
            | selection_statements    
            | iterator_statements     
            | jump_statements

compound_statements : statements_or_declare compound_statements 
                    | statements_or_declare

statements_or_declare : statements 
                        | declare

expression_statements : expression ";" 
                        | ";"

selection_statements : IF "(" expression ")" statements %prec THEN
                        | IF "(" expression ")" statements ELSE statements

iterator_statements : WHILE "(" expression ")" statements

iterator_statements : FOR "(" expression ";" expression ";" expression ")" statements

jump_statements : BREAK ";" 
                | CONTINUE ";" 
                | RETURN expression ";" 
                | RETURN ";"

为了解决if-if-else二义性问题，这里介绍一种方法。使用yacc的%prec语法将if和if-else看成两个运算符THEN和ELSE的文法。接下来就是解决二义性

if-if-else二义性：if(if else) 还是 (if if) else

表达式 expression

nocomma_expression : IDENT "(" expression ")" %prec CALL

expression : nocomma_expression COMMA expression
        | nocomma_expression

nocomma_expression : "(" expression ")"

nocomma_expression : nocomma_expression "[" nocomma_expression "]"

nocomma_expression : nocomma_expression STAR nocomma_expression
        | nocomma_expression DIV nocomma_expression
        | nocomma_expression MOD nocomma_expression
        | nocomma_expression PLUS nocomma_expression
        | nocomma_expression MINUS nocomma_expression
        | nocomma_expression LSHIFT nocomma_expression
        | nocomma_expression RSHIFT nocomma_expression
        | nocomma_expression LESS nocomma_expression
        | nocomma_expression LESSEQ nocomma_expression
        | nocomma_expression GREATER nocomma_expression
        | nocomma_expression GREATEREQ nocomma_expression
        | nocomma_expression EQ nocomma_expression
        | nocomma_expression NEQ nocomma_expression
        | nocomma_expression AMPERSAND nocomma_expression
        | nocomma_expression BITOR nocomma_expression
        | nocomma_expression BITXOR nocomma_expression
        | nocomma_expression LOGICOR nocomma_expression
        | nocomma_expression LOGICAND nocomma_expression

nocomma_expression : nocomma_expression ASSIGN nocomma_expression
        | nocomma_expression PLUSASSIGN nocomma_expression
        | nocomma_expression MINUSASSIGN nocomma_expression
        | nocomma_expression MULTIASSIGN nocomma_expression
        | nocomma_expression DIVIASSIGN nocomma_expression
        | nocomma_expression MODASSIGN nocomma_expression
        | nocomma_expression RSHIFTASSIGN nocomma_expression
        | nocomma_expression LSHIFTASSIGN nocomma_expression
        | nocomma_expression BITANDASSIGN nocomma_expression
        | nocomma_expression BITXORASSIGN nocomma_expression
        | nocomma_expression BITORASSIGN nocomma_expression

nocomma_expression : nocomma_expression QUES nocomma_expression COLON nocomma_expression %prec QUESTION

nocomma_expression :  PLUS nocomma_expression %prec UPLUS
        | MINUS nocomma_expression %prec UMINUS
        | LOGICNOT nocomma_expression
        | BITNOT nocomma_expression
        | STAR nocomma_expression %prec DEREF
        | AMPERSAND nocomma_expression %prec ADDRESS
        | SIZEOF nocomma_expression

nocomma_expression : instant_value
                | IDENT

instant_value : STRINGINSTANT
        | CHARINSTANT
        | INTEGERINSTANT
        | FLOATINSTANT
        | NULL

因为逗号表达式在函数调用中被认为是传参，为了防止其造成的二义性，所以表达式分为两类，不是逗号表达式的表达式nocomma_expression和包含逗号表达式的表达式expression，在需要使用表达式时按情况使用这两类。

解决二义性

LR语法分析器遇到无法解决的二义性被称为移入-规约冲突。

对于这个文法

1
2
3

表达式 : 表达式 + 表达式
      | 表达式 * 表达式
      | 数字

下面描述了LR语法分析器分析3*4+5时遇到移入规约冲突的情景

步数  符号栈                  输入Token               步骤
---- ---------------------  ---------------------   -------------------------------
1    $                                3 * 4 + 5$    移入 3
2    $ 3                                * 4 + 5$    归约 表达式 : 数字
3    $ 表达式                             * 4 + 5$    移入 *
4    $ 表达式 *                             4 + 5$    移入 4
5    $ 表达式 * 4                             + 5$    归约: 表达式 : 数字
6    $ 表达式 * 表达式                          + 5$    移入规约冲突

此时归约最终会变成(3*4)+5，此时移入最终就会变成3*(4+5)。yacc通过引入规则的优先级解决了这个问题。

如果表达式 + 表达式的优先级比表达式 * 表达式低，那么在遇到移入归约冲突时，有两种情况：

符号栈中已经可以归约表达式 * 表达式，移入+可以继续构造表达式 + 表达式。

此时优先进行归约
符号栈中已经可以归约表达式 + 表达式，移入*可以继续构造表达式 * 表达式。

此时优先进行移入

如你所见，一个规则的优先级其实就是与冲突的规则的第一个不同终结符的优先级，在遇到这种表达式规则时退化为运算符的优先级。也可以通过%prec指定一个规则的优先级等于优先级表上的哪个token的优先级。

除了优先级还有结合性之分，左结合优先进行符号栈中栈底方向的归约，右结合优先进行符号栈中栈顶方向的归约。

yacc优先级

排在越上面的优先级越低，同行是相同优先级，第一列表明了操作符的结合性。

right PLUSASSIGN MINUSASSIGN MULTIASSIGN DIVIASSIGN MODASSIGN RSHIFTASSIGN LSHIFTASSIGN BITANDASSIGN BITXORASSIGN BITORASSIGN ASSIGN 
right QUESTION 
left LOGICOR 
left LOGICAND 
left BITOR 
left BITXOR 
left AMPERSAND 
left EQ NEQ 
left LESS LESSEQ GREATER GREATEREQ 
left LSHIFT RSHIFT 
left PLUS MINUS 
left STAR DIV MOD 
right UPLUS UMINUS LOGICNOT BITNOT DEREF ADDRESS SIZEOF 
left CALL [ 
right THEN ELSE 
right dec_ptr 
left dec_array

python-yacc的缺陷

在语法分析中，如果一个需要进行优先级分析的规则的优先级token没有裸露到优先级表上就会导致预期外的错误。

1
2
3

exp : exp * exp %prec TIMES
....
	| * exp %prec DEREF

需要去掉任意一个$prec才能正常处理。

1
2
3

exp : exp * exp
....
	| * exp %prec DEREF

语法分析树的生成

不能简单的根据语法分析的结果生成语法分析树，诸如int a,b;的结构完全可以分解成int a;int b;方便后续的实现。基于同样的理由，我们把表达式转换为逆波兰式，在之后的语义分析就能借助栈很轻松的处理，而不是编写递归函数。

借助python的tuple和namedtuple，我们可以很轻松的实现这一过程。

from collections import namedtuple
declare = namedtuple('declare',['type','ini'])
array_type = namedtuple('array_type',['size'])
pointer_type = namedtuple('pointer_type',[])
function_type = namedtuple('function_type',['paras'])
#compound_statements = (statement...)
whileStatement = namedtuple('whileStatement',['exp','state'])
forStatement = namedtuple('forStatement',['iniexp','condexp','iterexp','state'])
ifStatement = namedtuple('ifStatement',['exp','then_state','else_state'])
expStatement = namedtuple('expStatement',['exp'])
breakStatement = namedtuple('breakStatement',[])
returnStatement = namedtuple('returnStatement',['exp'])
continueStatement = namedtuple('continueStatement',[])
instantvalue=namedtuple('instantvalue',['value'])
variable=namedtuple('variable',['name','type','value'])

具体实现细节此时忽略，只谈类型的表示，也就是上述代码的type字段。

类型 type 的表示

在HNUSTC中，任何一个标识符和字面量都具有类型信息和名字信息。每一个type都是这样的一个tuple。

1	(名字,类型修饰,...,类型修饰,基本类型)

类型修饰是上文定义的array_type、pointer_type由function_type的一个类型。以下是一个典型的函数type。

1	('test', function_type(paras=(('a', 'i32'), ('b', 'i32'))), 'i32')

中间代码生成

LLVM项目介绍

LLVM项目是模块化和可复用的编译器和工具链技术的集合。尽管它的名字叫LLVM，但它与传统的虚拟机没有什么关系。“LLVM”本身不是首字母缩略词；这是项目的全称。

LLVM IR介绍

LLVM 中间代码表示被设计为以三种不同的形式使用：作为内存上的编译器中间表示、作为磁盘上的字节码表示（适合JIT编译器快速加载）以及作为人类可读的汇编语言表示。这允许LLVM为高效的编译器转换和分析提供强大的中间表示，同时提供一种自然的方式来调试和可视化转换。三种不同形式的LLVM代码都是等价的。

LLVM 笔记

LLVM抽象机

为LLVM IR设计的LLVM抽象机是一层更贴近计算机硬件并进行合理抽象的概念上的机器，理解LLVM IR抽象机有助于我们理解LLVM IR的执行过程。

LLVM IR抽象机相比C语言抽象机有以下不同：

LLVM IR抽象机是对现实世界机器的抽象
一个LLVM IR程序由(模块-函数/全局变量-块-指令)组成
变量存放在寄存器上，寄存器的数量是无限的
可以使用load和store系列指令进行寄存器和内存间的数据传送，无法直接操作内存的一切对象
对寄存器的操作满足静态单赋值形式
寄存器均有类型属性，一般指令所要求的操作数类型必须相同

以LLVM IR为目标代码相比汇编的目标代码简化了什么

完整静态类型检查

LLVM自带了一套类型系统，如果使用LLVM库构建LLVM IR，那么会静态检查类型。而汇编的类型系统是隐含的，直到运行时才能发现类型错误。
一些由LLVM后端维护的算法

比如寄存器分配，后端优化等

对于本科生，这两点弊端均可以接受，而这换来的是对编译器前端工作的完全认识。

使用LLVM IR的优点

LLVM IR保留了大部分汇编语言的性质，一是不至于和之后学的汇编语言产生内容上的重叠，二是能为汇编语言做出一个良好的铺垫
让学生能接触到一线编译器的中间代码
能让学生体会到后端优化和前端优化的必要性

具体实现简记

因为使用了python的llvmlite库，不考虑额外优化的话可以很快的搭出编译器。

隐式转换

为了方便我们直接借用LLVM IR的类型系统作为我们的类型表示。在要使用标识符表示的左值时load进寄存器，这个过程被称为load。指定一个目标类型进行类型转换称为cast。

在HNUSTC中类型存在三种隐式转换

传递函数参数以及赋值时的转换
进行表达式计算时的转换
在if和while和for等语句中出现的条件表达式的转换

对于1，在load之外还需要进行数组的指针退化操作。对于2，除了进行1的操作外还需要进行类型提升的操作。对于3，除了进行1的操作外还需要进行!=0的判断。

因为HNUST没有强制转换，所有指针都能互相进行隐式转换。

表达式到ir转换递归函数

因为在语法分析后得到的是一个逆波兰式，我们使用栈就能很轻松的实现从表达式到ir的转换。

为了避免&a时load a，我们使用rvalue属性标记存放在寄存器上的指针是不是一个需要load的值。因为增加了属性，所以在栈上需要浅拷贝一下。

语句到ir转换递归函数

因为语句会创建新的块，所以语句需要一点复杂的操作，得益于python是引用传递，这一部分得以轻松完成。

在进入一个转换函数的时候，需要额外进行栈指针的保存，在退出一个转换函数时如果没有return掉就恢复栈指针。如果遇到了break和continue等语句提前结束块或者正常结束块时就恢复栈指针。

使用printf和scanf

直接全局声明printf和scanf就行，llc出来中间文件之后由clang链接进C库，printf和scanf自然就导入进来了。

其他工具

使用opt+dot工具可以生成控制块流程图

1 2	opt -dot-cfg foo.ll -disable-output -enable-new-pm=0 dot -Tpng -o test_main.png <dotfile>