搜索
编译原理课程设计实验报告-2-目录第一部分实验成果统计表…………………………………………………………1第二部分实验简介…………………………………………………………………2第三部分词法分析…………………………………………………………………3第四部分语法分析…………………………………………………………………64.1LL(1)法语法分析…………………………………………………………74.2递归下降法语法分析……………………………………………………10第五部分语义分析…………………………………………………………………19第六部分程序测试…………………………………………………………………22第七部分实验总结与体会…………………………………………………………28第一部分实验成果统计表姓名性别班级学号所占比例个人成绩任务分工：（请用小四号宋体填写）词法分析部分程序的调试与实现；LL(1)语法分析部分程序的调试与实现；递归下降语法分析部分程序的调试与实现；语义分析部分程序的调试与实现；成绩评定：词法分析递归下降LL(1)语义分析团队成绩教师签章备注填写说明：1、请将首页红色部分信息填全，其中：班级为2位数字，保留首位的0；学号为8位数字，计算机科学与技术学院以53开头；所占比例为百分数，精确到个位数，且所有人的所占比例之和为100%；不足四人的分组请保留后面的多余空行，请勿修改该表的结构。2、请根据实际情况填写任务分工部分，主要任务包括：编译系统的总体分析与设计，四个具体功能的设计与实现，对应的测试与验证过程（报告正文需要列出若干组具体测试样例与对应结果），系统界面的设计与美工，以及辅助工具、视图和文件等。3、成绩评定部分由指导教师填写，请勿填写和修改。第二部分实验简介本实验中实现了SNL编译系统中的词法分析、语法分析和语义分析。其中语法分析包括递归下降分析方法和LL（1）分析方法。词法分析，以源程序为输入，生成单词的内部表示TOKEN序列。语法分析，以TOKEN序列为输入进行语法分析，并生成整个源程序的语法分析树。在SNL编译程序中，采用了两种语法分析方法实现：LL（1）和递归下降法。两种语法分析的结果是一样的。语义分析，以语法树为输入生成标识符的属性符号表以及相关的各类信息表，如数组信息表，并进行相关的语义检查。它们三者的关系如下：LL（1）语法分析递归下降语法分析词法分析语义分析第三部分词法分析源程序一般表现为字符串（机器语言称其为ASCII码）序列的形式，而编译程序的翻译工作应该在单词一级上进行，这与自然语言的翻译理解过程是类似的。因此要进行编译工作，首先要把源程序的字符序列翻译成单词序列。词法分析是编译过程的第一阶段。它的任务就是对输入的字符串形式的源程序按顺序进行扫描，根据源程序的词法规则识别具有独立意义的单词（符号），并输出与其等价的TOKEN序列。TOKEN是单词（符号）的内部表示。完成词法分析任务的程序称为词法分析程序，通常也称为词法分析器或扫描器（scanner）。TOKEN是单词在编译程序处理过程中的一种内部表示，也是词法分析程序对程序中各类单词进行处理之后的输出形式。对于一种语言而言，如何对它的单词进行分类，每一类单词的TOKEN数据结构的形式如何，都没有固定的模式，可以随编译程序的不同而不同。通常TOKEN的结构可以分成两部分，单词的语法信息和语义信息。其中语法信息记录的是这个单词的种类，语义信息则记录着这个单词的具体信息。这样，就能为以后的语法分析和语义分析处理单词做好准备。SNL语法分析对每类单词的分析结果的TOKEN结构为三元组（词法信息、语义信息以及该单词在源程序中的行号）。本SNL编译器单词的内部表示如下：SNL语言的单词分类如下：（1）：保留字保留字一般是由语言系统自身定义的，SNL语言中的保留字有program，while，if，fi等等。（2）：标识符用来标识程序中各个对象的名称。由用户自己定义用来表示变量名，数组名或者过程名等。SNL语言中标识符由字母开头，字母、数字的任意组合组成的。（3）：常量用来表示各类常数。如字符型常量，实行常量，布尔常量等。（4）：运算符表示程序中算术运算、逻辑运算、字符运算的确定字符或字符串。SNL语言中的运算符有+，—，*，/，和:=六种运算符。（5）：界限符包括逗号分号等。SNL语言中的‘；’表示一条语句结束，‘.’表示程序结束等等。语义信息及其字符串表示行号（便于出错处理）语法信息及其字符串表示TOKEN的内部表示-6-实现词法分析器的注意事项：1.保留字和标识符名字的区分2.复合单词的处理3.向前搜索及回退4.数字的转换5.输入时边界的处理6.注释的处理词法分析主要的函数有：getTokenlist（）、getNextChar（）、ungetNextChar（）、reservedLookup（）、ChainToFile（）、printTokenlist（）。getTokenlist（）函数是最主要的函数，它每次从输入缓冲区lineBuf字符串序列中超前读一个（有时是两个）字符，使用确定有限自动机DFA的直接转向处理方法。超前读的字符如不匹配的话，还需要回退。如果得到的TOKEN是标识符的话，还需要查询保留字表以判断该标识符是否是保留字。产生词法错误的时候，仅仅略过产生错误的字符，不加改正。然后将得到的TOKEN存入链表，当整个源程序都分析完成的时候，将TOKEN链表中各个TOKEN存入文件Tokenlist.txt中，将来输出显示TOKEN时再从Tokenlist.txt中读取。getNextChar（）函数被getTokenlist（）函数调用，每次从输入缓冲区lineBuf中返回一个字符，如果lineBuf中的字符全部读完后，再从TOKEN文件中读取下一批。如此重复下去，直到源程序字符全部读完为止。ungetNextChar（）函数被getTokenlist（）函数调用，当文件结束标志FileEnd没有置位的时候，将lineBuf缓冲区中的读取指针回退一个字符。reservedLookup（）函数用在当前TOKEN是标识符的时候，需要查保留字表来判断该TOKEN是保留字还是普通标识符。ChainToFile（）函数用在源文件处理完毕后，将TOKEN链表中的TOKEN一个一个地存入文本文件Tokenlist.txt中。将来可以直接在文本文件中查看tokenlist，也可以在需要输出显示的时候从该文件中读取TOKEN。printTokenlist（）函数用在需要在命令行输出显示Tokenlist的时候，从Tokenlist.txt中读取TOKEN，然后显示出来。-7-主要函数getTokenlist（）的流程图如下：入口state=DONE？N从lineBuf中超前读入下一个字符，根据state状态进行处理Y将curToken的信息存入链表curToken.Lex=ENDFILE？N调用ChainToFile将链表信息存入文件结束Y第四部分语法分析语法分析是编译程序的第二阶段，也是编译程序的核心部分。语法分析的任务是，根据语言的语法规则，对源程序进行语法检查，并识别出相应的语法成分。按照SNL编译程序的模型，语法分析的输入时从词法分析器输出的源程序的TOKEN序列形式，然后根据语言的文法规则进行分析处理，语法分析的输出是无语法错误的语法成分，表示成语法树的形式。语言是具有独立意义的单词根据一定的语法规则组成的句子的集合，句子的结构由语法规则给出，句子的含义由语义规则给出，而对语言的语法分析就是对语言的句子结构的分析。归于程序设计语言而言，它的句子就是程序，程序设计语言定义的是符合其语法规则的程序的集合，因此程序设计语言的语法分析的关键是识别程序（句子）的语法结构。完成语法分析任务的程序成为语法分析程序，也称为语法分析器或简称分析器。本编译器的语法分析采用自顶向下的语法分析。自顶向下分析是从文法的开始符号出发，试图为输入串建立一个最左推导，或为输入串构造一个语法树。这种分析是通过对当前句型的最左非终极符，反复使用他的不同的规则进行替换和展开，以匹配输入串来实现的。语法分析检查的错误有：程序的开始单词错，表达式的开始单词错，语句的卡是单词错，表达式的后记单词错，语句的后记单词错等。标识符和常量单词错。如域名不是标识符等。括号类错误。如begin_end不匹配，（-）不配对，[-]不配对，case-end不配对，if-then-end不配对等。分隔符错。如赋值语句后面不是赋值号，标识符表或表达式的分隔符（或后继符）错。-9-4.1LL（1）语法分析LL（1）语法分析方法是一种自顶向下的语法分析方法，它是LL（k）分析方法的特例，其中k表示向前看k个符号的意思。LL（1）语法分析程序由两部分组成的：第一部分是语法分析表，也称为LL（1）分析矩阵；第二部分是语法分析驱动程序。LL（1）矩阵的作用是帮助当前非终极符和当前输入符确定应该选择的语法规则，它的行对应非终极符，列对应终极符，矩阵的值有两种：一种是产生式编号。另外一种是错误编号。LL（1）分析程序工作过程首先初始化，即把开始符压入栈中，以后的每步分析必是下面的四种情况之一：（1）分析栈的栈顶元素是终极符，则看其是否与输入流的头符相匹配，如果匹配成功，则去掉栈顶元素并读入下一个单词；若匹配不成功，则报错。（2）栈顶是非终极符，则用栈顶和输入流的当前单词去查当前矩阵，如果查得的值是产生式编号，则把对应的产生式右部逆序压入栈中；如果查得的值为错误信息，则报错。（3）栈已空，输入流不空，这时输入流报错。（4）若栈已空，输入流也空，则语法分析成功。LL（1）工作原理如下图：SNL语法程序的实现采用手工操作构造LL（1）分析表。LL（1）分析表用一个二维矩阵表示，其中每个非终极符对应一行，每个终极符对应一列，一个非终极符和一个终极符可以确定矩阵中的一个元素，元素的值表示该非终极符和该终极符对应的产生式。SNL的LL（1）语法分析程序共用到四个栈，分别称为：符号栈、语法树栈、操作符栈和操作数栈。其中，符号栈用于进行SNL的LL(1)语法分析；其他的栈-10-是为了在语法分析过程中同时生成与源程序结构对应的语法树而设置的。语法树栈用于声明部分和语句部分的语法树；操作符栈和操作数栈用于生成表达式部分的语法树。处理声明部分和语句部分的语法树生成时，设置一个语法树栈，存放语法树节点中指向儿子或者兄弟节点的指针的地址。在生成当前语法树节点时，如果以后需要对其儿子节点或者兄弟节点赋值，则按照处理顺序的逆序将这些儿子节点或者兄弟节点的指针的地址压入语法树栈，后面生成它的儿子节点或者兄弟节点时，只需弹栈，并对相应的指针进行赋值，就可以完成所需的语法树节点的链接。处理表达式时，需要另外设置两个栈，操作数栈和操作符栈，遇到操作数压入操作数栈，遇到操作符，则进行判断，如果当前操作符的优先级高于操作符栈的栈顶操作符，直接压入操作符栈；否则，弹出栈顶操作符，并弹出操作数栈顶的两个操作数，生成相应的子树，并对新生成的子树的父节点（操作符节点）进行循环判断。LL（1）语法分析的主要函数有：parseLL1（）、CreatLL1Table（）、gettoken（）、priosity（）、predict（）、newnode（）、TreeToFile（）、printTree（）、StrToEnum（）、PushSym（）、PopSym（）、PushSynTree（）、PopSynTree（）、PushOp（）、PopOp（）、ReadOpStack（）、PushNum（）、PopNum（）等等parseLL1（）函数是最主要的函数。它利用LL（1）分析表和符号栈进行语法分析，并处理终极符不匹配和文件提前结束错误。函数处理完成后，得到整个语法树。CreatLL1Table（）用于创建LL（1）分析表。用二维数组表示LL（1）分析表，初始化二维数组所有元素为0，根据给定的LL（1）文法，对产生式编号。对于每个产生式，左部的非终极符作为行号，其Predic