FOR循环语句的翻译程序设计.doc

武汉理工大学编译原理课程设计报告书目录1 系统描述21.1目的21.2设计内容：21.3 翻译过程31.4初始条件：31.5 开发平台32文法及属性文法的描述33 语法分析表设计43.1 LR分析概述43.2 LR(0)分析表53.3 LR语法分析过程的设计思想及算法73.4 翻译方法84 中间代码形式的描述及中间代码序列的结构设计85简要的分析与概要设计96详细的算法描述96.1 main函数106.2词法分析106.3 语法分析127 测试方法和测试结果137.1测试过程137.2 测试结论148 研制报告148.1研制过程148.2本设计的评价158.3个人心得体会159 参考文献16本科生课程设计成绩评定表17FOR循环语句的翻译程序设计 LR方法 、输出四元式1 系统描述1.1目的通过设计、编制、调试一个FOR循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，实现词法分析程序对单词序列的词法检查和分析，并且实现对单词序列的语法分析、语义分析以及中间代码生成。1.2设计内容：本设计按照要求设计出for语句的简单文法，并使用LR分析法对用户输入的程序进行分析和翻译。对下列正确的程序输入： for(i=0;i10;i+) m=m+i; 结果程序要对该输入进行词法分析，然后利用LR分析法对词法分析后得到的单词序列进行语法分析，经过语法制导翻译显示出等价的四元式表示的中间代码。对于错误的程序输入，如：for(i=0;i10) m=m+i;结果程序要指出程序出错。1.3 翻译过程词法分析：词法分析是编制一个读单词的过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。程序语言的单词符号一般分为五种：关键字（保留字/基本字）if、while、begin；标识符：常量名、变量名；常数：34、56.78、true、a、；运算符：+、-、*、/、and、or、.、；界限符：， ； （ ） /*。语法分析：语法分析是编译程序的核心部分,其主要任务是确定语法结构,检查语法错误，报告错误的性质和位置，并进行适当的纠错工作。此次设计中语法分析中主要通过LR分析表对语法分析处理过程进行控制，使四元式翻译的工作有条不紊的进行，同时识别语法分析中的语法错误。中间代码生成：为了使编译程序有较高的目标程序质量，或要求从编译程序逻辑结构上把与机器无关和与机器有关的工作明显的分开来时，许多编译程序都采用了某种复杂性介于源程序语言和机器语言之间的中间语言。常用的几种中间语言有: 逆波兰式、四元式、三元式、树表示。本课程设计主要实现四元式的生成。1.4初始条件：理论：掌握一种计算机高级语言的使用。学完编译课程，掌握词法分析程序设计方法，LR语法分析方法，以及语法制导的翻译和中间代码生成技术。实践工具和环境：计算机实验室提供计算机及软件环境。1.5 开发平台所使用的系统：Windows XP程序开发工具：Visual C+ 6.0程序设计语言：C+。2文法及属性文法的描述按照设计要求，设计出的For语句的符合简单优先定义的文法规则及相关的语义规则如下： 产生式 语义规则S f ( E ; F ; G ) H ; goto S f ( E ; X ; Y ) H ; goto E id = c id.value=c.value; F id =c.value goto over ; G id + + id.value=id.value+1 ; X id c If id.value=c.value goto over ; Y id id.value=id.value-1; Hid 1 = id 2 + id 3 id 1.value= id 2 .value + id 3 .value H id 1 = id 2 + c id 1.value= id 2 .value + c .value H id 1 = c+ id 2 id 1 .value= c.value + id 2 .value 其中产生式规则中的符号： c 表示常数const ， f表示关键字for ， i表示一般标识符id3 语法分析表设计3.1 LR分析概述一个LR分析器由3个部分组成：总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。分析表或分析函数。不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作（ACTION）表和状态转换（GOTO）表两个部分，他们都可用二维数组表示。分析栈，包括文法符号栈和相应的状态栈。它们均是先进后出栈。分析器的动作由栈顶状态和相应的状态栈所决定（LR（0）分析器不需向前查看输入符号）。LR分析器工作过程示意图如下图所示：其中SP为栈指针,Si为状态栈，Xi为文法符号栈。状态转换表内容按关系GOTOSi,X=Sj确定，该关系式是指当栈顶状态为Si遇到当前文法符号为X时应转向状态Sj。X为终结符或非终结符。 ACTIONSi,a规定了栈顶状态为Si时遇到输入符号a应执行的动作。动作有4种可能：移进：档Sj=GOTOSi,a成立，则把Sj移入到状态栈，把a移入到文法符号栈。其中i,j表示状态号。归约：档在栈顶形成句柄为时，则用归约为相应的非终结符A，即当文法中有A的产生式，而的长度为r（即|=r），则从状态栈和文法符号栈中自栈顶向下去掉r个符号，即栈指针SP减去r。并把A一如文法符号栈内，再把满足Sj=GOTOSi,A的状态移进状态栈，其中Si为修改指针后的栈顶状态。接受acc：当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是#，则为分析成功。报错：当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入串不是该文法能接受的句子3.2 LR(0)分析表根据上述文法构造的有穷自动机和根据有穷自动机构造的LR(0)分析表有穷自动机： LR(0)分析表： ACTION GOTOf(;)id=c-#SEFGXYH0S211acc2S33S544S65S76S10897S118S129S1310S14S1511R3R3R3R3R3R3R3R3R3R3R3R3R3R312S171613S191814S2015S2116S2217S2318S2419S2520R4R4R4R4R4R4R4R4R4R4R4R4R4R421R6R6R6R6R6R6R6R6R6R6R6R6R6R622S2623S2724S2825S2926S313027R5R5R5R5R5R5R5R5R5R5R5R5R5R528S313229R7R7R7R7R7R7R7R7R7R7R7R7R7R730S3331S3432S3533S3634S37S3835S3936R1R1R1R1R1R1R1R1R1R1R1R1R1R137S4038S4139R2R2R2R2R2R2R2R2R2R2R2R2R2R240S4241S4442R8R8R8R8R8R8R8R8R8R8R8R8R8R843R9R9R9R9R9R9R9R9R9R9R9R9R9R944R10R10R10R10R10R10R10R10R10R10R10R10R10R10 其中，S表示移进且下一状态为S的下标；R表示归约，归约所用的产生式为R的下标相对应的产生式;空白表示没有相应的关系即出错。3.3 LR语法分析过程的设计思想及算法3.4 翻译方法 设计中，使用语法制导翻译方法。所谓语法制导的翻译方法是指：按照给定的语法，对单词符号串进行语法分析，并构造出语法分析树，语法分析过程中根据需要构造属性依赖图，然后遍历语法树并在语法树的各个节点处，按语义规则进行计算，并生成中间代码。所谓属性依赖图是一个有向图，用于描述分析树中的属性和属性间的相互依赖关系。4 中间代码形式的描述及中间代码序列的结构设计本次设计，使用的中间代码为四元式（即三地址码）。四元式的四个组成成分：算符op，第一和第二运算对象ARG1和ARG2，及运算结果RESULT。例如对语句：for(i=0;i=10 goto over（3）（+，temp，i，t）（4）（=，t，temp）（5）（+，i，1，i）（6）goto （2）（7）over 设计并生成的结果程序，最终需要将用户输入的程序经过词法分析和语法分析，生成如上所述的四元式表示的中间代码形式。5简要的分析与概要设计程序由词法分析和语法分析两部分构成：词法分析程序，以用户输入的字符串为输入，判断输入是否包含非法字符，若字符完全合法，分析结果是，将标识符、常量、其他合法单词的类别和值保存在输入流中，做为语法分析的输入。为了有效地编写词法分析程序，首先应构造出程序流程图，然后根据流程图编写程序。语法分析，以词法分析结果作为输入，验证，输入流中各种符号是否符合语法规则。若不符合，显示出错信息，否则，在分析过后显示与输入程序等价的中间代码。同样需要构造语法分析的程序流程图。6详细的算法描述程序包括三个文件：词法分析.cpp和for循环翻译.cpp。其中for循环语句翻译.cpp中含有main函数，作为程序的入口，在main函数中接受用户输入的程序流，并保存在一个string对象中，然后调用词法分析.cpp中的void getSym(string &s,int &i)对程序流进行词法分析分离出单词符号，再调用语法分析.cpp文件中的void gramCheck()函数对单词符号输入流进行语法分析和语义分析，并生成四元式形式的中间代码。函数void getSym(string &s,int &i)调用getchar函数获得输入流中的符号进行分析，如得到的是标识符，则调用outsym函数分别普通标识符和关键字。函数gramCheck()调用函数priCmp比较符号栈和输入流中的两个符号的优先级关系。程序中的函数调用关系如，图1： 图1 for循环语句翻译程序函数调用关系图6.1 main函数Main()函数主要代码和相关解释如下：int main()Int r;string s; /用于保存输入程序的字符串cout输入for循环语句：endl; /提示用户输入程序getline(cin,s); /接受用户输入并保存在s中getSym(s,i); /调用词法分析程序r=nodeSize;for(i=0;ir;i+) sti=nodei.type; /将此法分析的结果保存到数组中 语法分析； 中间代码生成； 6.2词法分析 在文件“词法分析.cpp”中编写词法分析程序，文件中主要包含一个结构体struct symNode，一个结构体数组symNode node100，取字符函数void getChar(string &s,int &i)ch=si;i+;，取单词函数void getSym(string &s,int &i)，程序中数据结构和各函数具体功能如下：（1）定义结构体：struct symNodeint type;string sValue;int eValue;此结构体用来保存词法分析后，各种单词的信息。Type表示单词的类别，各符号对应的类别值见表1，如果单词是常量，eValue 则保存该常量的值，如果单词是标识符，sValue则保存该标识符的值。（2）数组symNode node100，用来保存单词输入流作为语法分析的输入流；int position=0; position保存数组node中将要输入的单词的位置，初值为0。（3）函数void getSym(string &s,int &i);用来作词法分析，s存储用户的输入程序，i 用来保存当前应该取字符的位置。（4）函数 void getChar(string &s,int &i)ch=si;i+;用来取字符串s 中第i个字符。 （5）函数 void outSym(string s); 区分s是关键字还是普通标识符。词法分析程序的具体算法描述：getChar()函数从串s里面取字符，直到遇到非空字符，如果已到达串尾，词法分析结束。getSym（）判断所取的字符是字母开头，还是以数字开头，还是其他合法字符；如果以字母开头，则开始保存为标识符，继续取字符直到遇到非字母非数字字符；如果以数字开头则保存为整数常量，继续取字符直到遇到非数字字符；其他字符则保存为相应类别。所有的单词分离后保存到数组symNode node100中。 词法分析程序所输出的单词符号常常采用以下二元式表示：（单词种别，单词自身的值）。单词的种别是语法分析需要的信息，而单词自身的值则是编译其他阶段所需要的信息。词法分析的流程图，如图2：图2词法分析流程图6.3 语法分析在文件“for循环翻译.cpp”中编写语法分析程序。程序中各函数具体功能解释如下：int Initstack(stack &s)：初始化栈；int push(stack &s,char e) ：将要入栈的元素压入栈中；char pop(stack &s,char *e) ：将要出栈的元素弹出栈；int action(int m,int n,char a) ：对照LR分析表，判断输入的字符需要移进还是归约；int go(int m,int n,char a) ：对照LR分析表，判断需要归约的字符串所对应的产生式； 在main函数中利用switch()语句来实现归约。7 测试方法和测试结果7.1测试过程针对所设计的关于for循环语句的翻译程序，分别用正确的程序和有错误的程序进行测试，测试出结果程序的可用性和健壮性。测试中分别使用了两个合法程序和两个非法程序，对结果程序进行测试，具体的测试程序、测试过程和测试结果如下：for循环语句语法分析过程：合法程序1: for(i=0;i100;j -)t=t+j;非法程序： for(i=0;i+”,当前字符为，此时，分析器到底是将其分析为大于关系运算符还是大于等于关系运算符呢？又比如，+分析为正号还是加法符号，以及对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注解等。这些在程序设计初期实现都比较困难，经过努力，在后期这些问题都得到了比较有效的解决。在语法分析的设计过程中，程序相当复杂，需要利用到大量的编译原理，其中在分析表的构造时遇到了非常大的困难，对输