编译原理实验报告

1、2014-2015学年第二学期编译原理课程设计实验报告项目组人员构成:角 色学 号姓 名担任工作占比词法分析53120416杨得成 40 %语法分析53120402刘中天 30 %语义分析53120403姚梦龙 30 %项目设计任务和目标：项目主要分为三个部分: 1.词法分析 2 .语法分析 3.语义分析 其中各部分完成的主要任务如下:词法分析:根据源语言(SNL)的词法规则，扫描源程序的字母（ASCII码）序列，并识别出一个一个具有独立意义的最小语法单位，即“单词”，同时确定该单词的种类（如标识符，界限符，常数，等等），并把每个单词的ASCII码序列替换为统一的标准形式-所谓的机内表示TOK

2、EN形式-这种形式既刻画了单词本身，又刻画了它所有的属性，同时词法分析还要完成词法错误的检查以及去掉注释等。词法分析不依赖于语言的语法分析。语法分析：语法分析的功能是：把词法分析的输出（TOKEN序列）作为输入，按照文法规则，从其中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成做准备。其实现有两种方式，递归下降法和LL（1）分析方法法。根据源语言的语法规则，逐一扫描源程序的ASCII码序列或者词法分析后的TOKEN序列（对于前者，词法分析程序将作为语法分析程序的子程序），以确定源程序的具体组成结构（语法结构）。分析时如果发现有不符合语法规则的地方，则打印出错位置和错误类型，以便程序

3、员进行修改；如果未发现语法错误，则将源程序转换成能够表示程序结构的语法树形式。很多编译程序在进行语法分析的同时还要完成其他的工作，但如果语法有错误，那么其他工作就没有意义了。语义分析：根据源语言的语义规则对语法分析得到的语法树进行语义检查(确定类型，类型和运算的合法性检查等)，并建立标识符的符号表等各种信息表。只有在没有语义错误的情况下才继续下面的编译过程，否则将不进行下面的编译工作。语义分为静态语义和动态语义，编译阶段一般只检查静态语义,而静态语义检查中重点是类型检查。SNL编译程序的功能结构框图如下：出错处理SNL目标程序词法分析语法分析语义分析目标代码生成 源 程序 表格处理SNL目标语

4、言程序解释执行示意图如下：输入数据运行结果解释执行过程SNL目标程序 关于SNL的词法：一个SNL程序是由程序头、声明部分和程序体组成的。声明部分包括类型声明、变量声明和过程声明。小组成员经过讨论，在其语法基础上对SNL语法做如下改动：去除过程的嵌套声明。在过程中只声明变量，不声明过程和类型。改进数组表示方式。原SNL语法中定义数组为a0.9这种形式，考虑到这种形式的落后以及给接下来的分析带来的不方便性。我们重新定义了数组为a9（下标默认从零开始）这种主流的形式。经过改进后的SNL语法，其对应自动机为： S入口 字母 字母，数字 标识符状态，INID 数字 数字 无符号整数 数字状态，INNU

5、M +，*，/，(，)，;，,，=，EOF 单分界符 完成状态，DONE 其他符号 ： = 双分界符 赋值状态，INASSIGN 注释状态，INCOMMENT 注释头符号 EOF 程序结束标志 . 字母 域.对象（A.a） 域状态，INYUE 其他符号 出错， 字母或数字 字符 字符标识状态，INCHAR 完成状态，DONE出口 其他 出错词法分析程序简介：词法分析程序（Scanner）源程序 Token序列 图：词法分析程序的功能词法分析程序的大体步骤： 单词分类 正则表达式 转成DNF 驱动程序在这里，主程序首先调用词法分析程序（函数getTokenlist），通过扫描源程序字符序列，按语

6、言的词法规则将一个又一个的字符组合成各类单词符号，并填写Tokenlist信息，然后将结果通过链表存入文件Tokenlist中，最后将整个源程序的字符序列转换成TOKEN序列，并将该TOKEN序列交给语法分析器。语法分析程序词法分析程序字符串表示的源程序 字符 Token序列 图：词法分析程序与语法分析程序的接口其中SNL 的Token结构如下：TOKEN域名（成分）类型 含义Lineshowint记录该单词在源程序中的行数LexLexType记录该单词的词法信息，其中LexType为该单词的枚举类型SemChar记录该单词的语义信息词法分析程序阶段用到的函数及其主要功能：Scan:阶段文件函

7、数函数功能参数参数含义词法分析阶段ScannergetNexChar取得下一个非空字符空ungetNexChar回退字符空reservedLookup查找保留字字符串s要检查的标识符getTokenlist取得所有单词空utilprintTokenlist显示词法分析结果空getToken显示一个单词TOKEN给出打印的TOKENChainToFile将链表中的TOKEN存入文件Chainhead语法分析程序简介：语法分析是编译程序的第二阶段。语法分析的任务是，根据语言的语法规则，对源程序进行语法检查，并识别出相应的语法成分。语法分析的输入是从词法分析器输出的源程序的TOKEN序列形式，然后根

8、据语言的文法规则进行分析处理，语法分析的输出是无语法错误的语法成分，表示成语法树的形式。语法分析程序的功能示意图：语义分析语法分析程序词法分析程序序源程序 Token序列 语法树 语法分析，其实现有两种方式，递归下降法和LL（1）分析方法法。其中递归下降法的主要原理是，对每个非终极符按其产生式结构构造相应的语法分析子程序，其中终极符产生匹配命令，而非终极符则产生过程调用命令。其文法递归相应子程序也递归，故称为递归下降法。递归下降法应满足的条件：当一个非终极符有多个产生式时，如何来选择唯一的产生式？如何保证被选择产生式是唯一的选择？为此引入下面两个基本动作：1） ReadToken:从输入流把下

9、一个TOKEN码读到变量token中。2） Math(a):检查token=a？若是，则执行ReadToken，否则报错并停机。其中a是终极符。LL(1)分析文法是一种自顶向下的语法分析方法，它是LL（k）分析方法的特例，其中的k表示向前看k个符号的意思。定义如下：假设A的全部产生式为A12n则有： Predict(Ai)Predict(Aj)=，当ij。有了上面的限制条件，就可以保证选择产生式的唯一性，满足上面条件的文法称为LL(1)文法。LL（1）语法分析程序由两部分组成：第一部分是语法分析表，也称为LL(1)分析矩阵；第二部分语法分析驱动程序。语法分析可概括如下： 求Predict集。

10、构造LL(1)分析表。 语法分析驱动程序。SNL的LL(1)语法分析概述：1）LL(1)分析表的构造。2）SNL语法分析的数据结构。3）语法分析树的生成。在语法分析的数据结构中共用到4个栈，分别为：符号栈、语法树栈 、操作符栈和操作数栈。其中符号栈用于进行SNL的LL(1)语法分析；其他的栈是为了在语法分析过程中同时生成与源程序结构相对应的语法树而设置的。在语法分析过程中用到的主要函数及其实现的功能：函数parseLL()。说明：LL(1)语法分析主函数，初始化符号栈，调用创建LL(1)符号表函数，生成语法树的根节点，分别指向程序体的指针child2的地址、指向声明部分的指针child1的地址

11、、指向程序头的儿子指针child0的地址压入语法树栈。利用LL(1)分析表和符号栈进行语法分析，并处理标识符不匹配错误和文件提前结束错误，函数处理完毕时，整个语法分析结束，函数返回生成的语法分析树。 函数Creat LL1Table()。说明：创建LL(1)分析表。用二维数组表示LL(1)分析表。 函数predict()。 说明：根据产生式编号选择一个要执行的函数。以及其他的产生式处理函数process()。语法分析函数parse()的算法框图：入口 出口函数返回t文件提前结束错误处理当前Token是ENDFILE?调用总程序处理分析函数，函数返回给t读入一个单词 N Y 语法分析器的输出将作

12、为语义分析的输入，因此语法分析树中不仅应该包括源程序的结构信息，还应为语义分析提供必要的信息。SNL语法树的节点（TreeNode）结构设计如下所示：childSiblingLinenonodekindkindidnumnametableattrtype-name012decstmtexp.语义分析程序简介：源程序在经过了词法分析之后，首先保证了构成它的每个单词的形式是正确的，然后再经过语法分析，保证了构成它的各个语法成分的构成是正确的。但是，源程序是要完成一定功能的，仅仅形式和结构正确并不能保证相应功能得到实现，所以源程序在经过词法分析、语法分析之后，还要进行语义分析，即检查程序的含义是否正

13、确。在整个编译过程中，词法分析和语法分析是对源程序形式上的识别和处理，而语义分析程序是对源程序的语义做相应的处理工作。SNL的语义分析程序主要完成以下两项工作：1. 构造符号表和信息表 构造标识符的符号表； 构造类型信息表，包括数组信息表和记录信息表； 构造过程信息表； 构造形参信息表；2. 进行语义错误检查，语义错误通常包括下面几类 标识符的重复定义； 无声明的标识符； 赋值语句的左、右两边类型不相容； 赋值语句的左端不是标识符变量； 过程调用中形参类型、个数不匹配； 表达式中运算符的分量的类型不相容。SNL语义分析程序以语法分析程序所生成的与源程序结构相对应的语法分析树为输入。语义分析程序

14、通过遍历语法分析树进行语义分析。在分析过程中用到以下标识符：标识符的内部表示：常量标识符的内部表示：NameKindTypeValue变量标识符的内部表示：NameKindTypeAccessLevelOffValue类型标识符的内部表示：NameKindType过程/函数标识符的内部表示：NameKindTypeClassLevelOffParamCodeSizeForward域名标识符的内部表示：NameTypeOffNext数组类型的内部表示：SizeKindUpElemtype结构类型的内部表示：SizeKindFieldList枚举类型的内部表示：SizeKindElemList入口

15、算法框图： 出口 撤销符号表处理主程序体循环处理主程序的声明部分调用类型内部表示初始化函数initialize()创建新一层的符号表图： 语义分析主函数Analyze（）的算法框图在语义分析过程中用到的主要函数及其实现的功能： 语义分析主函数void Analyze(TreeNode *currentP)。 说明：语义分析总程序，对语法树进行分析。 初始化基本类型内部表示函数void initialize()。 说明：初始化整数类型、字符类型、布尔类型的内部表示（由于这三种类型均为基本类型，内部表示固定。） 类型分析处理函数 TypeProcess(TreeNode *t,DecKind deckind)。 说明：类型分析处理。处理语法树的当前节点类型，构造当前类型的内部表示，并将其地址返回给Ptr类型内部表示的地址。 自定义类型内部结构分析函数：TypeIR *nameTy