实现一个小型编译程序
- 1 程序介绍
- 1.1 小型编译程序关于高级语言的规定
- 1.2 小型编译程序关于单词的内部定义
- 1.3 小型编译程序的LR分析表
- 1.4 待分析的源程序 pas.dat
- 2 结构体
- 2.1 结构体reswords
- 2.2 结构体exp_two
- 2.3 结构体VN_semantics
- 2.4 结构体exp_four
- 另：数组
- 3 程序流程
- 3.1 词法分析阶段
- 3.2 语法分析阶段
- 3.2.1 程序语句分析
- 3.2.2 算术表达式和赋值语句分析
- 3.2.3 布尔表达式分析
- 3.3 中间代码生成阶段
- 3.4 目标代码生成（选做）阶段
- 4 程序实现流程图
- 4.1 词法分析器
- 4.2 语法语义分析程序
- 4.2.1 程序语句分析程序
- 4.2.2 算术表达式和赋值语句分析程序
- 4.2.3 布尔表达式分析程序
- 4.3 中间代码显示和保存
- 4.4 目标代码生成程序
- 4.4.1 对于操作数arg1和arg2
- 4.4.2 对于四元式结果result
- 4.4.3 汇编语句产生规则
- 5 结果展示
- 5.1 pas.dat
- 5.2 词法分析结果
- 5.3 程序语句分析
- 5.4 表达式分析
- 5.5 中间代码生成
- 5.6 目标代码生成
- 6 健壮性测试
资源下载传送门
实现一个小型编译程序。
（1） 输入：高级语言源程序；
（2） 输出：四元式程序（必做） 汇编语言程序（选做）。
小型编译程序执行分两个阶段：
（1） 第一阶段，将高级语言源程序翻译成四元式程序；
（2） 第二阶段，将四元式程序翻译成汇编语言目标程序。
- 开发环境
windows 10
visual studio 2019
1 程序介绍
1.1 小型编译程序关于高级语言的规定
- 考虑的产生式所定义的程序语句
S→if B then S else S︱while B do S︱begin L end︱A
L→S;L︱S
A→i:=E
B→B∧B︱B∨B︱┐B︱(B)︱i rop i︱i
E→E+E︱E*E︱(E)︱i
其中，各非终结符和终结符的含义如下：
| 非终结符 | 含义 |
|---|---|
| S | 语句 |
| L | 语句串 |
| A | 赋值句 |
| B | 布尔表达式 |
| E | 算术表达式 |
| 终结符 | 含义 |
|---|---|
| i | 整型变量或常数，布尔变量或常数 |
| rop | 关系运算符 |
| ; | 起语句分隔符作用 |
| := | 赋值符号 |
| ¬ | 逻辑非运算符“not” |
| ∧ | 逻辑与运算符“and” |
| ∨ | 逻辑或运算符“or” |
| + | 算术加运算符 |
| * | 算术乘运算符 |
| ( | 左括号 |
| ) | 右括号 |
- 优先级
- 表达式
由高到低的优先顺序：算术运算＞关系运算＞布尔运算，并且服从左结合原则。 - 算术运算符
由高到低的优先顺序：“()”＞“*”＞“+”。 - 关系运算符
6个关系运算符优先级相同。 - 布尔运算符
由高到低的优先顺序：“¬”＞“∧”＞“∨”。
1.2 小型编译程序关于单词的内部定义
- 词法分析输出的二元式格式：(单词种别,单词自身的值)
（1） 不单独设置保留字表，而是直接使用其种别编码来表示保留字；
（2） 不单独设置常数表，而是直接通过单词种别来标识常数，再通过单词自身的值表示常数值；
（3） 单独设置标识符表（数组），通过单词种别来标明标识符，单词自身的值为标识符在标识符表中的位置，位置通过数组下标表示。
（4） 关于6种关系运算符，单词种别都为rop，单词自身的值分别为：
| 关系运算符 | 单词自身的值 |
|---|---|
| <= | 0 |
| < | 1 |
| >= | 2 |
| > | 3 |
| 4 | |
| = | 5 |
- 关于单词的内部定义
| 符号 | 种别编码 | 说明 |
|---|---|---|
| sy_if | 0 | 保留字 if |
| sy_then | 1 | 保留字 then |
| sy_else | 2 | 保留字 else |
| sy_while | 3 | 保留字 while |
| sy_begin | 4 | 保留字 begin |
| sy_do | 5 | 保留字 do |
| sy_end | 6 | 保留字 end |
| a | 7 | 赋值语句 |
| semicolon | 8 | “；” |
| e | 9 | 布尔表达式 |
| jinghao | 10 | “#” |
| S | 11 | 语句 |
| L | 12 | 复合语句 |
| tempsy | 15 | 临时变量 |
| EA | 18 | B and(即布尔表达式中“B∧”) |
| EO | 19 | B or(即布尔表达式中“B∨”) |
| plus | 34 | “+” |
| times | 36 | “*” |
| becomes | 38 | “:=” |
| op_and | 39 | “and” |
| op_or | 40 | “or” |
| op_not | 41 | “not” |
| rop | 42 | 关系运算符 |
| lparent | 48 | “(” |
| rparent | 49 | “)” |
| ident | 56 | 变量 |
| intconst | 57 | 整常量 |
1.3 小型编译程序的LR分析表
算术表达式的SLR(1)分析表：
布尔表达式的SLR分析表如下:
程序语句的 SLR 分析表:
1.4 待分析的源程序 pas.dat
【注意】测试用例文档规范要求：
（1） 程序由一条语句或由 begin-end 嵌套起来的复合语句组成；
（2） 语句末必须加上“#~”表示程序结束。
while (a>b) dobeginif m>=n then a:=a+1elsewhile k=h do x:=x+2;m:=n+x*(m+y)end#~2 结构体
2.1 结构体reswords
结构体reswords存放保留字、逻辑运算符单词名称及对应的种别编码。
设置table_reswords存放系统保留字和逻辑运算符，是为了词法分析时的查表操作。因为无论是保留字还是逻辑运算符，它们的单词构造都与标识符相同，但却不能将其视为变量。因此，在分析出单词为标识符后，通过查table_reswords，判断这个单词是变量还是保留字还是逻辑运算符与或非。
当查表成功后，返回保留字或逻辑运算符的种别编码；当查表失败，返回-1，从而对标识符进行后续操作。
2.2 结构体exp_two
结构体exp_two即为词法分析所规定输出的单词符号格式——二元式：(单词种别,单词自身的值)
设置exp_two类型的数组exp_two_table，顺序存放词法分析后的二元式结果。其中，变量的单词自身的值为其在变量名表中的位置，rop的单词自身的值用来区分是哪种关系运算符。因此，单词自身的值设置为int类型。同时，设置int类型的变量count_exp_two_table，统计产生的二元式个数，便于后续操作。
设置exp_two类型的数组production，记录一条表达式所包含的二元式。因为在进行程序语句的翻译时，对表达式是进行单独分析的，将production作为参数传递给算术表达式和赋值语句或布尔表达式的函数进行表达式翻译。同时，设置int类型的变量count_pro记录表达式中包含的二元式个数。
为了方便之后调用emit函数产生四元式，设置exp_two类型变量underline表示操作数缺省时的情况，表示缺省状态下的下划线。underline初始为(-1,-1)，即代表此条二元式为空。
2.3 结构体VN_semantics
结构体VN_semantics存放非终结符语义值，用于表达式分析。
其中，非终结符E对应算术表达式和赋值语句的分析，非终结符B、A、O对应布尔表达式的分析。
结构体中变量tc和fc仅用于布尔表达式分析过程中，地址合并和回填的需要。
2.4 结构体exp_four
结构体exp_four即最终需要的四元式数据结构：(op,arg1,arg2,result)
其中，op用于存储运算符和转移指令标识，由于转移指令标识例如“j”、“j＞”等没有对应的种别编码，因此直接将其定义为char类型，便于显示。定义操作数arg1和arg2为exp_two类型的变量是考虑到区分变量、常数和临时变量。定义result为int类型的变量是基于如下考虑：
result只可能是三种情况之一：地址量；临时变量；变量。
可基于对op位的考虑，当op位为转移指令标识时，result为必为地址量，因此可以有效区分地址量和其他两者。
关于临时变量和变量的区分，也是基于对运算符的考虑，当op为“:=”进行赋值操作时，result位必为变量；而当op为算术运算符时，result位必为产生的临时变量保存运算的中间结果。
另：数组
（1） char类型的字符数组token，用来暂存读取到的一个单词。
（2） char类型的字符串数组table_ident，用来存放读取到的变量，即为变量名表。
3 程序流程
小型编译程序主要分为四个阶段：
（1） 词法分析（二元式）；
（2） 语法分析；
（3） 中间代码生成（四元式）；
（4） 目标代码生成（汇编程序）。
没有进行代码优化。语法分析过程中包含对程序的语义分析。下面对词法分析和语法分析进行详细说明。
3.1 词法分析阶段
词法分析阶段的任务是输入源程序识别出程序中的单词符号，形成二元式，以便后续语法分析阶段等的操作。
逐个读取文件中的字符，保存在char类型的变量character中，以‘~’为分析结束符号，滤除空白符。当首字母characterer为字母时，表明为标识符，将连续的字母和数字字符链接成串，保存在token中，进而判断是变量还是保留字还是逻辑运算符。当首字母character为数字时，表明为常数，将连续的数字链接成串，保存在token中，进而将token中的字符串转换成常数。当首字母非字母且非数字时，判断运算符种类，否则提示出错信息。
将二元式登记入表。
3.2 语法分析阶段
在进行语法分析的同时进行语义分析。
根据已有的SLR分析表进行相应的分析程序构造。根据当前状态和输出串的当前分析字符决定分析过程，主要执行两个动作：
（1） 移进s。将当前状态移入状态栈，当前分析字符移入符号栈。
（2） 归约r。根据对应的产生式进行归约。若产生式右部有n个字符，状态栈和符号栈就出栈n个字符，并将符号栈的这n个归约为产生式左部的非终结符入符号栈。根据当前状态栈的栈顶状态和符号栈栈顶的非终结符，决定下一个状态是什么，并将这个状态移入状态栈。
对高级语言源程序进行程序语句分析，当遇到表达式时，进行表达式的SLR分析。
3.2.1 程序语句分析
- 每次归约为语句S时，为了回填四元式的跳转地址，需要判断归约后的S的前一个单词是do还是then。
- 如果是do，说明此时S为循环结构中的循环体且循环体S已经执行完，即将执行无条件转移指令，要跳转到此循环结构的while布尔表达式e处，并且知道了循环结构的出口。因此，此时需要创建一条无条件转移的四元式，同时e的假出口确定了可以回填。
- 如果是then，说明此时S为if-else条件语句中布尔表达式e为真的程序块，那么此时就知道了e为假时的出口（因为如果从e为真的程序块开始，顺序往下执行的话就是e为假的程序块），同时为了跳过else后的程序块，需要一条无条件转移指令。因此，此时需要创建一条无条件转移的四元式，但由于此时并不知道if-else程序块执行结束后的下一条四元式的地址，所以这条无条件转移的四元式的跳转地址是未知的，将这条四元式的地址予以保存在stack_nxq栈中，以便回填；同时，布尔表达式e的假出口可以回填，即当前nxq的值（假出口的第一条四元式地址）。
- 当用产生式S->if e then S else S进行归约时，此时知道了if-else程序块结束后，下一条四元式所在的地址nxq，因此，stack_nxq栈顶（if-else遵循就近匹配原则）所保存的地址指向的四元式的跳转地址就知道了，予以回填。
3.2.2 算术表达式和赋值语句分析
在对表达式进行算术表达式和赋值语句的分析时，最需要注意的是中间变量的产生。不单独设置中间变量数组进行中间变量的保存，而是通过单词自身的值来反映这是第几个中间变量，通过种别编码来标明其中间变量的身份。
为了使上述假设成立，规定不重复使用同一个编号的临时变量，即每一个临时变量仅在赋值语句的算术表达式中有效。除非是直接变量之间赋值，否则必然产生中间变量。
对表达式分析结束之后，返回程序语句分析，整个表达式设为a。
3.2.3 布尔表达式分析
在对表达式进行布尔表达式分析时，最需要注意的是真假出口的地址。详细的产生式翻译程序说明见编程。
为了防止逻辑运算符对真假口的更新从而干扰条件转移指令的判断，因此在进入布尔表达式分析之前，需要保存此条产生式最开始的真口地址，例如对x and y分析时，需要对x的真出口进行保存，否则这整条表达式的真出口将更新为y的真出口。
由于程序的顺序执行，当布尔表达式分析完成后，真口肯定是当前nxq所指向的四元式地址，而假口需要在程序语句分析过程中才能知道它需要跳转到的地址所在，因此在程序语句分析过程中需要对假口所在的四元式地址进行保存，以便后续回填。
3.3 中间代码生成阶段
在语义分析时，已生成中间代码——四元式了。因此，这个阶段对语义分析所产生四元式进行显示和保存，将四元式结果保存在pas.med中。
3.4 目标代码生成（选做）阶段
将四元式结果变换成汇编程序，保存在pas.asm中。
由于对目标代码生成算法还是一知半解，因此在本次课设中，牺牲了过多的寄存器去完成数据的存取等操作。
其中，temp_arg1和temp_arg2存放当前分析的四元式的操作数，temp_result存放当前分析的四元式的非转移地址结果，count_T记录每条四元式中产生的临时变量个数，temp_jump存放当前分析的四元式的转移地址结果。
由于四元式结构中使用char类型的op，这在进行目标代码生成时略麻烦，因此考虑在exp_four结构体中添加exp_two类型的op_asm数组变量，以期记录op的类型。op主要分为转移指令标识、算术运算符标识和赋值符号标识。对于后两者，op_asm存储对应的二元式，而针对转移指令标识，又分为如下类型：
（1） 无条件转移“j”，此时将op_asm置为(-1,-1)；
（2） “jnz”，此时将op_asm置为(-1,0);
（3） 条件转移“jrop”，此时op_asm保存关系运算符对应的二元式。
4 程序实现流程图
4.1 词法分析器
4.2 语法语义分析程序
4.2.1 程序语句分析程序
4.2.2 算术表达式和赋值语句分析程序
4.2.3 布尔表达式分析程序
4.3 中间代码显示和保存
中间代码的显示和保存这两个函数的唯一区别在于，一个是直接通过printf在命令行显示四元式，一个是通过fprintf将四元式结果保存到pas.med文件中。
4.4 目标代码生成程序
遍历四元式数组exp_four_table，每次循环都初始化count_T=0，顺序分析arg1、arg2和result。对于临时变量，采用寄存器方式暂存并进行值传递，分配的寄存器依次为“BX”、“CX”、“DX”。
4.4.1 对于操作数arg1和arg2
对于操作数arg1和arg2，根据它们的种别编码进行对应操作，种别编码分为4种情况：
- 变量
当操作数为变量时，根据对应的单词自身的值去变量名表种找到相应的变量，将变量放在temp_argx中暂存。 - 常数
当操作数为常数时，将对应的单词自身的值转换成字符串并链接后缀D形成新的字符串，放在temp_argx中暂存。 - 临时变量
当操作数为临时变量时，count_T增1，将寄存器“BX”送入temp_argx中暂存。对于操作数2，如果arg1为临时变量的话，需要将寄存器“CX”送入temp_arg2。 - -1
说明此位缺省，不做任何处理。
4.4.2 对于四元式结果result
对于四元式结果result，根据op位进行对应操作，result的值分为3种情况：
- 地址值
当op位的第一个字符为“j”时，说明这是一条转移指令，那么result存放的就是地址值，将地址值存放在temp_jump中。 - 变量值
当op位为赋值符号时，说明此时result中存放的肯定时变量值，将该变量值存放中temp_result中。 - 临时变量值
当op为不是转移指令标识，也不是赋值符号时，说明这是一条赋值语句右部算术表达式的四元式，先将count_T增1代表此时又有一个临时变量，同时检测count_T的值，由于在一条四元式中临时变量的个数最多3个（arg1、arg2和result都为临时变量的情况），因此根据此条四元式中临时变量的个数分为3种情况：
count_T=1：此条四元式中只有一个临时变量，用到寄存器“BX”送入temp_result；
count_T=2：此条四元式中有两个临时变量，且因为先分析的arg1和arg2，所以在result中的肯定是第2个临时变量，即代表寄存器“BX”已用，此时分配寄存器“CX”送入temp_result；
count_T=3：此条四元式中有三个临时变量，在result中得肯定是第3个临时变量，即代表寄存器“BX”、“CX”已用，此时分配寄存器“DX”送入temp_result。
4.4.3 汇编语句产生规则
根据四元式op位的种别编码（op_asm.id），进行汇编语句的产生，分为5种情况:
5 结果展示
5.1 pas.dat
5.2 词法分析结果
5.3 程序语句分析
5.4 表达式分析
按照程序运行时对表达式的分析顺序，进行分析过程输出，结果保存在testout.txt中。
对表达式(a>b)分析：
对表达式m>=n分析
对表达式a:=a+1分析
对表达式k=h分析
对表达式x:=x+2分析
对m:=n+x*(m+y)分析
5.5 中间代码生成
- 中间代码保存（pas.med）
5.6 目标代码生成
存放在pas.asm中。
6 健壮性测试
不想贴图了，感兴趣你们可以试试对这个代码进行分析
参考文献：胡元义.编译原理教程（第四版）[M].西安电子科技大学出版社:西安,2015.