华南理工大学
《编译原理》课程实验报告
实验题目： 实现TINY+编译器
源代码及报告书： （为了大家的学习着想，此处就不放github的地址了 可以在我的个人上传资源中找到这份文档）。
（此处图片未显示，可以在github中下载报告书观看。报告书即为如下内容）
【实验目的】
构造一个将TINY+高级程序设计语言转换为TINY+虚拟机上的中间代码的编译器。
整个实验包括两个部分：实验一完成TINY+编译器的词法分析器部分；实验二完成TINY+编译器的语法分析器部分、语义分析器部分及中间代码生成器部分。
【实验环境】
Microsoft Visual Studio 2015
C++语言实现
分为实验一、二。实验一、 实现TINY+编译器的词法分析器
【实验目的及要求】
学生在该实验中构造TINY+语言的词法分析程序。具体要求如下：
1 词法分析器的输入是源程序文件，输出是单词（token）流。
2 构造的词法分析器必须遵循最长子串原则，例如字符串‘:=’ 应该被识别为一个代表赋值符号的单词，而不是识别为两个单词‘:’和 ‘=’。
3 词法分析器识别出的单词应该被表示成二元组的形式（Kind, Value），其中Kind表示单词的种类，Value表示单词的实际值。要求用如下符号表示不同种类的单词：
l KEY 表示关键字；
l SYM 表示特殊符号；
l ID 表示标识符；
l NUM 表述数字常量
l STR 表示字符串常量
4 词法分析器的任务除了完成对单词的识别之外，还要检查程序中的词法错误，给出错误的信息以及错误在源程序中出现的位置（所在的行号）。词法错误的种类包括：
l Ø 非法符号，词法分析器可能识别到一个TINY+程序的字母表中不允许的符号，例如，词法分析器在一个源程序中识别到$，应报告一个词法错误，发现了一个非法符号；
l Ø 字符串类型的单词STRING，单引号不匹配。例如，源程序中出现' scanner，词法分析分析器应报告错误“字符串缺少右引号”；
l 注释的括号不匹配。例如源程序中出现{this is an example，词法分析器应报告错误“注释缺少右括号”。
- 在main函数中将NO_ANALYZE、NO_CODE、PARSE设置为TRUE，使程序只进行词法分析过程。
- 由于增加了关键字(keyword)，TINY语言关键字如下：
Tiny关键字 |
if，then，else，end ，repeat，until，read，write |
Tiny+新增关键字 |
Or，and ，int，bool，char，while，do |
其中所有的关键字是程序设计语言保留使用的，并且用小写字母表示，用户自己定义的标识符不能和关键字重复。
- 特殊符号定义：
Tiny符号 |
{ } ; := + - * / ( ) < = |
Tiny+新增符号 |
> <= >= , ' |
- 词法分析器中识别的单词用二元组形式表示（Kind,Value），其中Kind表示单词的种类，Value表示单词的实际值。要求用如下符号表示不同种类的单词：
KEY |
关键字 |
SYM |
特殊符号 |
ID |
标识符 |
NUM |
数字常量 |
STR |
字符串常量 |
- 词法分析器的任务除了完成对单词的识别之外，还要检查程序中的词法错误，给出错误的信息以及错误在源程序中出现的位置（所在的行号）。词法错误的种类包括：
- 非法符号，词法分析器可能识别到一个TINY+程序的字母表中不允许的符号，例如，词法分析器在一个源程序中识别到$，应报告一个词法错误，发现了一个非法符号；
- 字符串类型的单词STRING，单引号不匹配。例如，源程序中出现' scanner，词法分析分析器应报告错误“字符串缺少右引号”；
注释的括号不匹配。例如源程序中出现{this is an example，词法分析器应报告错误“注释缺少右括号”。
实验过程：
- 在GLOBALS.h中的TokenType枚举中增加相应的类型：
关键词 |
特殊符号 |
||
新增枚举定义 |
对应的关键词 |
新增枚举定义 |
对应特殊符号 |
OR |
or |
RT |
> |
AND |
and |
LTEQ |
<= |
INT |
Int |
RTEQ |
>= |
BOOL |
bool |
COMMA |
, |
CHAR |
char |
CO |
‘ |
WHILE |
while |
|
|
DO |
do |
|
|
- 在SCAN.C的getToken()函数中进行相应修改，让程序能够正确识别新添加的关键词以及特殊符号，并且对程序出错进行相应提示）
词法分析测试结果
测试一：
|
输入 |
输入右边所示文件，运行程序后，结果如下图： (下面两张图为同一输出结果) |
|
输出 |
|
|
测试二：
输入 |
输入右边所示文件，运行程序后，结果如下图： (下面两张图为同一输出结果) |
|
输出 |
|
|
测试三：（测试错误提示）
输入 |
输入右边所示文件，运行程序后，结果如下图： 其中有两处错误：
|
|
输出 |
|
|
实验二、实现TINY+的语法分析器、语义分析器以及中间代码生成器
【实验目的及要求】
学生在该实验中构造TINY+语言的语法分析器、语义分析器以及中间代码生成器，具体要求如下：
- 为TINY+构造一个递归下降语法分析器。该语法分析器对词法分析器生成的单词序列进行语法分析，产生一颗抽象语法树作为语法分析器的输出。
- 构造TINY+的语义分析器，该语义分析器构建符号表，然后检查程序中的语义错误。
- 构造TINY+的中间代码生成系，该中间代码生成器将TINY+程序翻译为三地址中间代码。
- 要求能检查程序中语法和语义错误，具体包括：
-
语法错误：
- 语法结构的开始符号以及跟随符号错误；
- 标识符错误，例如在程序的变量声明中，关键字int 后没有跟随标识符；
- 括号不匹配的错误，例如左括号(和右括号 )不匹配。
- 符号错误，例如赋值语句中要求使用的正确符号是‘:=’，而在关系比较表达式要求使用的正确符号是‘=’。
- 语义错误：
- 一个标识符没有声明就使用，以及一个标识符被声明不止一次。
- 一个条件表达式的类型不是布尔类型bool。
- 一个二元操作符的两个操作数的类型不相等。
- 赋值语句左右部的类型不相等。
语法分析实验过程：
- 在main函数中将NO_ANALYZE、NO_CODE 设置为TRUE，使程序只进行PARSE（语法分析）过程。
- Tiny+的语法EBNF定义如下（其中红色是指Tiny+在Tiny上新增的语法）：
20 bool-exp -> bterm { or bterm } 21 bterm -> bfactor { and bfactor} 22 bfactor -> comparison-exp 23 comparison-exp -> arithmetic-exp comparison-op arithmetic-exp 24 comparison-op -> < | = | > | >= | <=
|
- 根据EBNF的定义，修改PARSE.C文件，构造递归下降语法分析器，产生一棵语法树。
- 基本语法树木的结构如下：
语句系列 |
|
语句间通过链表相连，除了第一条语句，其他语句均可通过前一个语句的->slibing查找到。 |
If语句 |
|
test位于If语句的child[0], then-part为child[1], else-part为child[2] |
Repeat |
|
Body位于repeat语句中的child[0], test位于chlid[1] |
Assign |
|
Expression 位于assign语句child[0] |
write |
|
Expression位于write的child[0] |
|
Op 逻辑运算 |
|
Left-operand 位于op语句的child[0], Right-opreand位于语句的child[1]; |
while |
|
Test位于while语句的child[0] Do-part位于child[1] |
|
Define 如： int A，B |
|
B位于A的slibing中， 其中A、B的子节点均未赋值（此处留给将来拓展用） |
- 新建一个define的结点类型，用来识别定义语句.
- 重写tiny中不适合的语法分析树枝，按照新的ENBF定义写出合适的分析函数，从而构建出正确语法树。
语法分析测试结果：
测试一：
输入 |
输入右边所示文件，运行程序后，结果如下图： |
|
输出 |
|
|
语义分析实验过程：
1在main函数中将 NO_CODE 设置为TRUE，使程序进行语义分析过程。
2一个用TINY+语言编写的程序包括变量的声明和语句序列两个部分。变量声明部分可以为空，但一个TINY+程序至少要包含一条语句。
- 所有的变量在使用之前必须声明，并且每个变量只能被声明一次。
- 变量以及表达式的类型可以是整型int，布尔类型bool或者字符串类型char，必须对变量的使用和表达式进行类型检查。
3构建语义分析器主要包括
- 符号表的设计以及符号表的相应操作
- 符号表保存信息：变量的地址信息、变量被访问的行号
- 变量以其变量名ID，通过链式hash储存查找到相应数据。
- 语义分析程序本身的操作，包括符号表的构建以及类型检查。
- 符号表的创建：
- 前序遍历语法树:
当遇到定义的语法结点时候，将其变量新增到哈希表中，并存储其行号位置；
遇到含有变量的非定义语句的结点时，查找该变量位于哈希表中的位置，将该行号储存到哈希相应表项的next位置。
- 类型检查:
- 后续遍历语法树，对每一个结点进行语义判断:
1. if语句结点中，if-test(child[0])的类型必定为boolean，
2. while语句结点中，while-test(child[0])的类型必定为boolean，
3. op算术运算结点中，child[0]、child[1]必须为integer类型
4. op逻辑运算结点中，child[0]、child[1]必须为boolean
5. 赋值运算结点中，child[0]、child[1]的类型必须一致
6. ……
- 在后续遍历语法树中，查看变量是否非法使用：
- 当结点为ID结点时候，在哈希表中查看是否已经定义。
- 如果该结点为定义语句结点，则判断此变量是否重复定义。
- 如果该变量已经定义，则将变量的type（类型）赋于定义时候的类型
- 进入上一层遍历，当其类型不符合上一层所需类型时候提示错误。（即如在赋值语句中，该变量的类型与赋值语句另一个子节点的类型不一致，提示语义错误）。
词法分析测试结果
测试一：
输入 |
输入右边所示文件，运行程序后，结果如下图：
|
|
输出 |
|
|
测试二：
输入 |
输入右边所示文件，运行程序后，结果如下图：
|
|
输出 |
|
|
测试三：（测试错误提示）
输入 |
输入右边所示文件，运行程序后，结果如下图： 代码中有三处错误：
|
|
输出 |
|
|
中间代码生成实验过程：
1 在main函数中将 NO_PARSE、NO_ANALYZE、NO_CODE 设置为FALSE，使程序进行中间代码生成过程。
2 构造TINY+的中间代码生成系，该中间代码生成器将TINY+程序翻译为三地址中间代码。
3在原tiny中间代码生成器的实现位于cgen.c和cgen.h中。其接口为codeGen(TreeNode* syntaxTree,char* codefile).
主要功能为：
- 函数的开始，产生一些注释以及建立运行时环境的指令。
- 对语法树调用cGen函数，对每一个语法树结点生成相应指令
- 最后生成HALT指令，结束目标代码生成。
注释以及指令均写在某指定.tm文件上，供TM程序调用并且运行。
- Tiny+在tiny的基础上进行修改。其中codeGen函数将保持不变，修改其cGen函数即可。
- 修改cGen函数调用的getExp()函数。
- 增加OpK的类型，即在原有功能代码基础上，增加新增符号其操作的中间代码生成步骤。即新增符号RT,EQ,LTEQ,RTEQ.
如增加“>”的中间代码生成过程
- 增加LogicOpK的处理（即增加AND、OR的中间代码的生成）
此处中间代码生成比算术运算的中间代码复杂得多，根据TM程序的指令以及其操作原理，写出AND和OR中间生成代码功能：
- 修改cGen函数调用的getStmt()函数。增加语句while的中间代码生成。
此处通过Tiny+文法规则产生对于的三地址中间代码属性，完成while生成中间代码功能。
中间代码测试结果
测试一：
输入 |
输入右边所示sample.tny文件到TINY+，运行程序后，获得example.tm文件。
将example.tm文件输入TM程序中，运行结果如图： 输入x=5，输出120（正确） 输入x=101，跳出if（正确） 输入x=4，输出24（正确） 输入x=-1，跳出if（正确） |
|
输出 |
Example.TM文件如下截图：
输入上述文件到TM程序中运行，结果如下：
|
|
- 在TINY+编译器的设计编写中，将书上学到的知识运用到实践中，从而完成TINY编译器的拓展。
- 加深对文法的理解、词法分析中的无穷自动机（NFA）转为有穷自动机（DFA）再转成最间DFA的过程以及原理有了新的认识。
- 语法分析是耗费我最多时间的地方。TINY+语法定义稍有不准确，将为后期代码调试带来很大的麻烦。并且语法的定义在精简压缩方面需要下很大功夫。从给定的EBNF定义，到真正可运行的程序代码，期间需要大量的测试调试。
- 在构建语法生成树中，曾多次修改之前写的词法分析器，并且重写了之前写的质量不高的语法分析器，将代码结构进行解耦，方便了后续的调试以及改进。
- 在中间代码生成中，深入了解生成三地址的中间代码方式。其中就if语句的中间代码生成进行了大量的测试，最终将原先不太了解的汇编代码看懂，并且写出了逻辑表达式AND、OR、以及While的中间代码生成功能。
- 在TM程序中，通过一步步调试程序代码，学会执行汇编语言，其中学会自定义寄存器、内存缓冲区、指令缓冲区来执行汇编语言。也在此过程中，改正了中间代码生成中的许多bug。
- 该TINY+编译器存在着许多不足，仍需要进行改造进化。但完成该编译器后，已经向编译原理世界迈进一大步了。