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

1、目录1系统描述 .21.1目的 .21.2设计内容： .21.3翻译过程 .21.4初始条件： .31.5开发平台 .32文法及属性文法的描述 .33语法分析表设计 .43.1 LR 分析概述 .43.2 LR(0) 分析表 .53.3LR 语法分析过程的设计思想及算法 .743.4翻译方法 .8中间代码形式的描述及中间代码序列的结构设计.85简要的分析与概要设计 .96详细的算法描述 .96.1main 函数 .106.2词法分析 .1076.3语法分析 .12测试方法和测试结果 .137.1测试过程 .137.2测试结论 .148研制报告 .148.1研制过程 .148.2本设计的评价 .

2、1598.3个人心得体会 .15参考文献 .16本科生课程设计成绩评定表 .17FOR循环语句的翻译程序设计 LR 方法 、输出四元式1 系统描述1.1 目的通过设计、编制、调试一个FOR 循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解， 实现词法分析程序对单词序列的词法检查和分析，并且实现对单词序列的语法分析、语义分析以及中间代码生成。1.2 设计内容：本设计按照要求设计出for 语句的简单文法， 并使用 LR 分析法对用户输入的程序进行分析和翻译。对下列正确的程序输入：for(i=0;i<10;i+)m=m+i;结果程序要对该输入进行词法分析，然后利用LR 分析法对词法

3、分析后得到的单词序列进行语法分析，经过语法制导翻译显示出等价的四元式表示的中间代码。对于错误的程序输入，如：for(i=0;i<10)m=m+i;结果程序要指出程序出错。1.3 翻译过程词法分析：词法分析是编制一个读单词的过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。程序语言的单词符号一般分为五种：关键字（保留字/基本字） if 、while 、begin ；标识符：常量名、变量名 ；常数： 34、56.78、true、a、；运算符： +、-、* 、/、and、or、.、；界限符：，

4、； （）/* 。语法分析：语法分析是编译程序的核心部分 ,其主要任务是确定语法结构 , 检查语法错误，报告错误的性质和位置，并进行适当的纠错工作。此次设计中语法分析中主要通过 LR 分析表对语法分析处理过程进行控制，使四元式翻译的工作有条不紊的进行，同时识别语法分析中的语法错误。中间代码生成：为了使编译程序有较高的目标程序质量，或要求从编译程序逻辑结构上把与机器无关和与机器有关的工作明显的分开来时，许多编译程序都采用了某种复杂性介于源程序语言和机器语言之间的中间语言。常用的几种中间语言有: 逆波兰式、四元式、三元式、树表示。本课程设计主要实现四元式的生成。1.4 初始条件：理论：掌握一种计算机

5、高级语言的使用。学完编译课程，掌握词法分析程序设计方法， LR 语法分析方法，以及语法制导的翻译和中间代码生成技术。实践工具和环境：计算机实验室提供计算机及软件环境。1. 5 开发平台所使用的系统： Windows XP程序开发工具： Visual C+ 6.0程序设计语言：C+ 。2 文法及属性文法的描述按照设计要求，设计出的For 语句的符合简单优先定义的文法规则及相关的语义规则如下：产生式语义规则S f ( E ; F ; G ) H ;gotoS f ( E ; X ; Y ) H ;gotoEid= cid.value=c.value;Fid<cIf id.value>=

6、c.valuegoto over ;Gid + +id.value=id.value+1 ;Xid> cIf id.value<=c.valuegoto over ;Yid id.value=id.value-1;H123123id= id+ idid .value= id .value + id.valueHid 1 = id 2 + cid 1.value= id 2 .value + c .valueHid 1 = c+ id 2id 1 .value= c.value + id2 .value其中产生式规则中的符号：c 表示常数 const， f 表示关键字 for， i

7、表示一般标识符id3 语法分析表设计3.1 LR 分析概述一个 LR 分析器由 3 个部分组成：总控程序，也可以称为驱动程序。对所有的LR 分析器总控程序都是相同的。分析表或分析函数。不同的文法分析表将不同，同一个文法采用的LR 分析器不同时，分析表也不同，分析表又可分为动作（ACTION ）表和状态转换（ GOTO）表两个部分，他们都可用二维数组表示。分析栈，包括文法符号栈和相应的状态栈。它们均是先进后出栈。分析器的动作由栈顶状态和相应的状态栈所决定（ LR （0）分析器不需向前查看输入符号）。LR 分析器工作过程示意图如下图所示：输入串 XXX .#SnXn.SP.总控程序输出.S1X1S

8、0X0ACTIONGOTO 表表其中 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），则从状态

9、栈和文法符号栈中自栈顶向下去掉 r 个符号，即栈指针 SP 减去 r。并把 A 一如文法符号栈内，再把满足 Sj=GOTOSi,A 的状态移进状态栈，其中Si 为修改指针后的栈顶状态。接受 acc：当归约到文法符号栈中只剩文法的开始符号S 时，并且输入符号串已结束即当前输入符是 #，则为分析成功。报错：当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入串不是该文法能接受的句子3.2 LR(0) 分析表根据上述文法构造的有穷自动机和根据有穷自动机构造的LR(0)分析表有穷自动机：>15c21id10<14c20H0S1F8;12G16)222630;3336c43f

10、idid37+40id422( 3E 4; 6X9id17+23+ 27id;1331=34c38+41id445= 7c11idY18)242832;3539idH19_25_29 LR(0)分析表：ACTIONGOTOf(;)id=c<+>-#SEFGXYH0S211acc2S33S544S65S76S10897S118S129S1310S14S1511R3R3R3R3R3R3R3R3R3R3R3R3R3R312S171613S191814S2015S2116S2217S2318S2419S2520R4R4R4R4R4R4R4R4R4R4R4R4R4R421R6R6R6R6R6

11、R6R6R6R6R6R6R6R6R622S2623S2724S2825S2926S313027R5R5R5R5R5R5R5R5R5R5R5R5R5R528S313229R7R7R7R7R7R7R7R7R7R7R7R7R7R730S3331S3432S3533S3634S37S3835S3936R1R1R1R1R1R1R1R1R1R1R1R1R1R137S4038S4139R2R2R2R2R2R2R2R2R2R2R2R2R2R240S4241S4442R8R8R8R8R8R8R8R8R8R8R8R8R8R843R9R9R9R9R9R9R9R9R9R9R9R9R9R944R10R10R10R10R

12、10R10R10R10R10R10R10R10R10R10其中， S 表示移进且下一状态为S 的下标； R 表示归约，归约所用的产生式为 R 的下标相对应的产生式;空白表示没有相应的关系即出错。3.3 LR语法分析过程的设计思想及算法3.4翻译方法设计中，使用语法制导翻译方法。所谓语法制导的翻译方法是指：按照给定的语法，对单词符号串进行语法分析，并构造出语法分析树，语法分析过程中根据需要构造属性依赖图，然后遍历语法树并在语法树的各个节点处，按语义规则进行计算，并生成中间代码。所谓属性依赖图是一个有向图，用于描述分析树中的属性和属性间的相互依赖关系。4 中间代码形式的描述及中间代码序列的结构设计

13、本次设计，使用的中间代码为四元式（即三地址码） 。四元式的四个组成成分：算符 op，第一和第二运算对象ARG1 和 ARG2，及运算结果RESULT。例如对语句：for(i=0;i<10;i+)emp=temp+i;等价的四元式表示如下：（1）(=,0,， i)（2）if i>=10 goto over（3）（ +，temp， i ， t）（4）（ =，t， temp）（5）（ +，i， 1， i）（6）goto （2）（7）over设计并生成的结果程序，最终需要将用户输入的程序经过词法分析和语法分析，生成如上所述的四元式表示的中间代码形式。5 简要的分析与概要设计程序由词法分析和

14、语法分析两部分构成：词法分析程序， 以用户输入的字符串为输入，判断输入是否包含非法字符，若字符完全合法，分析结果是，将标识符、常量、其他合法单词的类别和值保存在输入流中，做为语法分析的输入。为了有效地编写词法分析程序，首先应构造出程序流程图，然后根据流程图编写程序。语法分析，以词法分析结果作为输入，验证，输入流中各种符号是否符合语法规则。若不符合，显示出错信息，否则，在分析过后显示与输入程序等价的中间代码。同样需要构造语法分析的程序流程图。6 详细的算法描述程序包括三个文件：词法分析.cpp 和 for 循环翻译 .cpp。其中 for 循环语句翻译 .cpp 中含有 main 函数，作为程序

15、的入口，在main 函数中接受用户输入的程序流，并保存在一个string 对象中，然后调用词法分析.cpp 中的voidgetSym(string &s,int &i) 对程序流进行词法分析分离出单词符号，再调用语法分析 .cpp 文件中的 void gramCheck()函数对单词符号输入流进行语法分析和语义分析，并生成四元式形式的中间代码。函数 void getSym(string &s,int &i) 调用 getchar 函数获得输入流中的符号进行分析，如得到的是标识符，则调用 outsym 函数分别普通标识符和关键字。函数 gramCheck()调用函

16、数 priCmp 比较符号栈和输入流中的两个符号的优先级关系。程序中的函数调用关系如，图1：图 1 for 循环语句翻译程序函数调用关系图Maingetlinegetsymactiongotopoppushgetcharoutsym6.1main函数Main() 函数主要代码和相关解释如下：int main()Int r;string s;/用于保存输入程序的字符串cout<<" 输入for循环语句："<<endl;/ 提示用户输入程序getline(cin,s);/接受用户输入并保存在s 中getSym(s,i);r=nodeSize;for(i=

17、0;i<r;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;str

18、ing 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 用来保存当前应该取字符的位置

19、。（4）函数void getChar(string &s,int &i)ch=si;i+;用来取字符串 s 中第 i 个字符。（5）函数 void outSym(string s); 区分 s 是关键字还是普通标识符。词法分析程序的具体算法描述： getChar()函数从串 s 里面取字符，直到遇到非空字符，如果已到达串尾，词法分析结束。 getSym（）判断所取的字符是字母开头，还是以数字开头，还是其他合法字符；如果以字母开头，则开始保存为标识符，继续取字符直到遇到非字母非数字字符；如果以数字开头则保存为整数常量，继续取字符直到遇到非数字字符；其他字符则保存为相应类别。所有的

20、单词分离后保存到数组symNode node100中。词法分析程序所输出的单词符号常常采用以下二元式表示：（单词种别，单词自身的值）。单词的种别是语法分析需要的信息，而单词自身的值则是编译其他阶段所需要的信息。词法分析的流程图，如图2：图 2 词法分析流程图开始输入串末尾NYYgetcharCh=空YN结束Ch=string sCh=保存 s 的类型Ys=s+chA-Z orNA-Z和值getchar0-9NYCh=Yint temp保存 temp 的类Temp=temp*10+Ch=0-9Nint(ch)-480-9型和值Ngetchar其他合法Y保存其他符号字符？的类型和值N出错6.3语法

21、分析在文件“ 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()

22、语句来实现归约。7 测试方法和测试结果7.1 测试过程针对所设计的关于for 循环语句的翻译程序，分别用正确的程序和有错误的程序进行测试，测试出结果程序的可用性和健壮性。测试中分别使用了两个合法程序和两个非法程序，对结果程序进行测试，具体的测试程序、测试过程和测试结果如下： for 循环语句语法分析过程：合法程序 1:for(i=0;i<10;i+) m=m+i;合法程序 2：for(j=1000;j >100;j -)t=t+j;非法程序：for(i=0;i<20) m=m+i;7.2测试结论经过测试，可以得知，结果程序能达到预计的要求：对合法程序进行词法分析和简单优先的语

23、法分析，并生成四元式表示的中间代码；对于错误的程序输入，结果程序能够判断其出错。存在问题：对于错误的程序输入，结果程序不能给出错误的位置。对于含有非法输入符号的程序，结果程序没有很好地处理，程序健壮性不强。8 研制报告8.1 研制过程在课程设计期间，通过阅读大量相关书籍，利用网络查找各种资料，根据相关知识，写出了符合简单优先语法规则的关于for 语句的属性文法。获得语法规则的属性文法后，对程序进行了概要设计，将程序大致分为词法分析和语法分析两个模块，并且设计出文法对应的符号优先关系表。词法分析负责对输入串进行单词识别，并保存单词各信息，作为语法分析和翻译的输入。语法分析负责对输入流中的单词进行

24、分析，检验是否符合所写的语法规则，并对其进行初步翻译。概要设计后，对两个模块分别进行了详细设计，并利用词法分析流程图和语法分析流程图，设计程序的大致流程，并具体到各函数的设计。通过对程序进行了详细设计，得到了程序大致流程， 并根据流程进行编码，编码过程中，出现了一些语法和语义上错误，通过调试和修改，使得程序成功运行。设计测试方法和测试用程序，并对程序进行了测试。8.2 本设计的评价此次设计对for 语句进行了全面词法分析和语法分析，并得到了用于分析for 语句的结果程序。结果程序能对用户输入的程序代码进行分析，判断是否存在词法错误和语法错误，如果出现错误，向用户给出提示，如果没有错误，则生成于

25、输入程序等价的中间代码，方便后续编译过程工作。但是结果程序也存在很多不足：对于非法的输入，无法给出错误的位置。对非法输入考虑不全面，对某些非法输入无法给出错误信息，另外属性文法不完善，程序中的使用的某些判断方法，只适合于本次设计使用的文法，实用性不强。8.3 个人心得体会本课程设计是for循环语句的翻译程序，包括词法分析部分、语法分析部分和中间代码生成部分。词法分析阶段是编译过程的第一个阶段，是编译的基础。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词( 也称单词符号或符号 )。 语法分析部分采用 LR 分析方法进行语法分析，判断给出的符号串是否为该文法识别的句子。中间代码生成器部分主要实现四元式的生成，将用中缀式表示的算术表达式转换为用四元式表示的算术表达式。在整个编译器设计过程中，遇到了很多意想不到的困难，其主要原因是对各个部分要实现的功能考虑不够周全，典型的如在词法分析的设计中，当前待分析字符串为“ a>+” , 当前字符为 >，此时，分析器到底是将其分析为大于关系运算符还是大于等