吉林大学编译原理课程设计满分实验报告.doc

2023级《编译原理课程设计》总结报告（组）

_2023_年_5_月_25_日
姓名
性别
班级
学号
所占比例
个人成绩

男
04

%

男
04

%

男
04

%

任务分工：（请用小四号宋体填写）
编译系统的总体分析与设计-
具体功能的设计与实现-
相应的测试与验证过程-
系统界面的设计与美工-

成绩评估：
词法分析

自底向上语法分析

中间代码生成

自顶向下语法分析

语义分析

目的代码生成

团队成绩

教师签章

备注

填写说明：
1、请将首页红色部分信息填全，其中：班级为2位数字，保存首位的0；学号为8位数字，软件学院以54开头；所占比例为百分数，精确到个位数，且所有人的所占比例之和为100%；局限性3人的分组请保存后面的多余空行，请勿修改该表的结构。
2、请根据实际情况填写任务分工部分，重要任务涉及：编译系统的总体分析与设计，4个具体功能的设计与实现，相应的测试与验证过程（报告正文需要列出若干组具体测试样例与相应结果），系统界面的设计与美工，以及辅助工具、视图和文献等。
3、成绩评估部分由指导教师填写，请勿填写和修改。

报告正文（请用小四号宋体填写，自行组织章节和段落）
目录
第一部分 实验成果登记表 …………………………………………………………1
第二部分 实验简介 …………………………………………………………………2
第三部分 词法分析 …………………………………………………………………3
第四部分 语法分析 …………………………………………………………………6
4.1 LL(1)语法分析 ……………………………………………………………7
4.2 LR语法分析 ……………………………………………………………10
第五部分 程序测试…………………………………………………………………22

第一部分 实验成果登记表
见首页

第二部分 实验简介
实验目的
分组（每组最多3人）完毕对SNL语言的以下两个程序：词法分析程序，语法分析程序（方法不限）。察并锻炼学生的团队协作能力，代码编写能力，加深同学对编译原理中SNL编译系统的理解，帮助同学理解整个编译原理的机制
实验内容
本实验中实现了SNL编译系统中的词法分析、语法分析。其中语法分析涉及LL（1）分析方法和LR分析方法
词法分析，以源程序为输入，生成单词的内部表达TOKEN序列。
语法分析，以TOKEN序列为输入进行语法分析，并生成整个源程序的语法分析树。在SNL编译程序中，采用了两种语法分析方法实现：LL（1）和LR，前者为自顶向下的，后者为自底向上的。两种语法分析的结果是同样的。
实验环节
编译系统的总体分析（算法分析，数据结构设计，优化）→代码实现，分工进行词法分析，语法分析部分→代码测试→结果反馈，修正→系统界面优化设计

第三部分 词法分析
源程序一般表现为字符串（机器语言称其为ASCII码）序列的形式，而编译程序的翻译工作应当在单词一级上进行，这与自然语言的翻译理解过程是类似的。因此要进行编译工作，一方面要把源程序的字符序列翻译成单词序列。
词法分析是编译过程的第一阶段。它的任务就是对输入的字符串形式的源程序按顺序进行扫描，根据源程序的词法规则辨认具有独立意义的单词（符号），并输出与其等价的TOKEN序列。TOKEN是单词（符号）的内部表达。完毕词法分析任务的程序称为词法分析程序，通常也称为词法分析器或扫描器（scanner）。
TOKEN是单词在编译程序解决过程中的一种内部表达，也是词法分析程序对程序中各类单词进行解决之后的输出形式。对于一种语言而言，如何对它的单词进行分类，每一类单词的TOKEN数据结构的形式如何，都没有固定的模式，可以随编译程序的不同而不同。通常TOKEN的结构可以提成两部分，单词的语法信息和语义信息。其中语法信息记录的是这个单词的种类，语义信息则记录着这个单词的具体信息。这样，就能为以后的语法分析和语义分析解决单词做好准备。
SNL语法分析对每类单词的分析结果的TOKEN结构为三元组（词法信息、语义信息以及该单词在源程序中的行号）。
实现词法分析器的注意事项：
1.保存字和标记符名字的区分
2.复合单词的解决
3.向前搜索及回退
4.数字的转换
5.输入时边界的解决
6.注释的解决
词法分析重要的类有DoToken、Data、Rule、Token
DoToken是最重要的类，它涉及identifier标记符列表、INTC常量列表、isIdentifier()标记符自动机、isINTC()数字常量自动机。
Data类涉及tokenShow显示token用StringBuffer、tokenShow2测试token用StringBuffer、token token列表、separator 分隔符列表等、以及LL（1）分析表，终极符，非终极符等。
Rule表达SNL的语法规则。
doToken（）函数是最重要的函数，它每次调用词法分析方法时要先重新初始化各列表和缓冲字符串，然后从源程序中一个字符一个字符地进行读取，并逐个分离出单词，然后构造它们的机内表达Token。假如该字符不是分隔符则直接追加到sb中，假如该字符是分隔符，则解决分离出的单词。假如是数字常量，则对数字常量进行解决，假如数字常量列表INTC中没有该数字常量则添加。若程序结束时分离出的单词长度不为零，则解决为相应的Token（尽管词法分析已失败，由于程序未能成功结束），并重新初始化用以分离单词的缓冲字符串。当整个源程序都分析完毕的时候，将TOKEN链表中各个TOKEN存入文献Tokenlist.txt中，将来输出显示TOKEN时再从Tokenlist.txt中读取。
isIdentifier（）函数被doToken（）函数调用，假如分隔出的字符串是标记符则在token和tokenShow都要追加。
isINTC（）函数被doToken（）函数调用，对数字常量列表进行判断，假如数字常量列表中没有该数字常量则添加。
Token（）函数中，i表达类型，1为分隔符，2为保存字，3为标记符，4为数字
重要函数doToken（）的流程图如下：

第四部分 语法分析
语法分析是编译程序的第二阶段，也是编译程序的核心部分。语法分析的任务是，根据语言的语法规则，对源程序进行语法检查，并辨认出相应的语法成分。按照SNL编译程序的模型，语法分析的输入时从词法分析器输出的源程序的TOKEN序列形式，然后根据语言的文法规则进行分析解决，语法分析的输出是无语法错误的语法成分，表达成语法树的形式。
语言是具有独立意义的单词根据一定的语法规则组成的句子的集合，句子的结构由语法规则给出，句子的含义由语义规则给出，而对语言的语法分析就是对语言的句子结构的分析。归于程序设计语言而言，它的句子就是程序，程序设计语言定义的是符合其语法规则的程序的集合，因此程序设计语言的语法分析的关键是辨认程序（句子）的语法结构。
完毕语法分析任务的程序成为语法分析程序，也称为语法分析器或简称分析器。
编译器的语法分析采用自顶向下的语法分析LL（1）和自底向上的语法分析。
LL（1）语法分析
LL（1）语法分析方法是一种自顶向下的语法分析方法，它是LL（k）分析方法的特例，其中k表达向前看k个符号的意思。
LL（1）分析程序工作过程一方面初始化，即把开始符压入栈中，以后的每步分析必是下面的四种情况之一：
（1）分析栈的栈顶元素是终极符，则看其是否与输入流的头符相匹配，假如匹配成功，则去掉栈顶元素并读入下一个单词；若匹配不成功，则报错。
（2）栈顶是非终极符，则用栈顶和输入流的当前单词去查当前矩阵，假如查得的值是产生式编号，则把相应的产生式右部逆序压入栈中；假如查得的值为错误信息，则报错。
（3）栈已空，输入流不空，这时输入流报错。
（4）若栈已空，输入流也空，则语法分析成功。
SNL语法程序的实现采用手工操作构造LL（1）分析表。LL（1）分析表用一个二维矩阵表达，其中每个非终极符相应一行，每个终极符相应一列，一个非终极符和一个终极符可以拟定矩阵中的一个元素。
SNL的LL（1）语法分析程序共用到四个栈，分别称为：符号栈、语法树栈、操作符栈和操作数栈。
LL（1）语法分析的重要函数有：doGrammar()、Grammar()、findRuleIndex()、getVariables()、getStartVariable()、computeFirstSets()、computeFollowSet()、getRuledByLeftVariable()、getTerminals()、getFirstSets()、getFallowSets()等等
doGrammar()函数是最重要的函数。它运用LL（1）分析表和符号栈进行语法分析，并解决终极符不匹配和文献提前结束错误。函数解决完毕后，得到整个语法树。
Grammar()函数重要进行Rule格式转换。

自底向上语法分析
LR(0)分析方法实现过程
结构如下
LR(0) --->LR0Item//在每个产生式的右部适当位置添加一个点构成项目
--->LR0Item(Rule r)//以文法规则初始化构造
--->getDotPointer()//返回点的位置
--->goTo()//判断能否移动
--->getCurrentTerminal()//得到点后终极符
---->LR0State//LR(0)状态
--->closure(Grammar grammar)//求文法闭包
---->LR0Parser//为LR（0）分析过程建立相应的表
--->createStates()//创建相关状态形成NFA
对Token的操作有如下几种
Action --->ACCEPT//接受
--->SHIFT//移入
--->REDUCE//规约
LR(1)分析方法实现过程，结构如下
LALR(1)
--->LR1Item//在每个产生式的右部适当位置添加一个点构成项目
--->LR1Item(Rule r,Lookahead l)
--->getDotPointer()//返回点的位置
--->closure(Grammar grammar)//求文法闭包
---->LR1Parser//为LR(1)分析过程建立相应的表
--->createStatesForLALR1()//创建相关状态形成NFA
--->createGoToTable()//创建goto表
--->createActionTable()//创建action表
LR分析驱动程序

第五部分 程序测试
对的情况：（1）词法分析：

（2）LL（1）语法分析：

（3）LR（0）语法分析：

（4）LALR（1）语法分析

2.错误情况（由于篇幅因素这里仅以删除冒泡排序倒数第二行endwh为例）：
（1）词法分析：

（2） LL（1）语法分析：

（3） LR（0）语法分析：

（4） LALR（1）语法分析

结论（请用小四号宋体填写）
还记得第一次编译系统实验的时候，我们在得知要设计一个SNL编译器时，有很多迷茫。理论课上的确有涉及到设计的内容，然而我们都没有真正实践过，完全不知道从何下手。但重要任务还是清楚的，词法分析和语法分析。
考虑届时间局限性，我们决定先明确每周分工，具体实行的时候就不用紧张最后赶工的情况发生了。大体是第一周—编译系统的总体分析（算法分析，数据结构设计，算法优化）。第二周—代码实现，分工进行词法分析，语法分析部分。第三周—代码测试，结果反馈，系统界面优化设计，实验报告撰写。进展有条不紊，每个人都被分到了相应的任务，在具体实现时保持沟通，分工协作，推动工作开展。编程的过程中我们小组的成员密切配合，积极讨论，共同探讨不同模块的耦合关系以及接口实现，遵循基本的软件开发过程：设计、编码、集成和测试。
整个编程过程锻炼了我们的学习和调试程序的能力，同时对于一些不完善的细节通过我们自己的努力进行重新编程和纠错，最终完毕了程序的相关功能。并达成了更高规定，完毕了自底向上的语法分析，并且对界面进行的细致的优化，使其更显美观，这也是我们有别于其他组的优势所在。
这大学三年也接触了不少项目，因此在进行这个项目的时候大家都有些胜券在握的感觉，然而实际过程中还是碰到了不少的麻烦，所幸我们都努力一一克服了。这也提醒我们对待每个项目都要拿出100%的专注度，要享受完毕项目的过程，乐在其中才是学习的意义。我也相信这一次的编译原理课程设计，不仅仅是帮助我们对编译器有了更深的了解，更多的是让我们在自己的科研道路上又看到了一个新的方向，朝着更广阔的未来前进。