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

《FOR循环语句的翻译程序设计》由会员分享，可在线阅读，更多相关《FOR循环语句的翻译程序设计（18页珍藏版）》请在装配图网上搜索。

1、目录1 系统描述（问题域描述）21.1 目的21.2 设计步骤21.3 系统体系结构描述22 文法及属性文法的描述32.1 文法32.2 属性文法33 语法分析方法描述及语法分析表设计53.1 语法分析方法53.2 语法分析表设计64 中间代码形式的描述及中间代码序列的结构设计64.1 中间代码形式描述64.2 中间代码序列的结构设计75 编译系统的概要设计75.1 系统分析75.1.1 词法分析75.1.2 语法分析85.1.3 中间代码生成85.2 概要设计95.2.1 系统总体设计图95.2.2 数据结构96 详细的算法描述（流程图或伪代码）106.1 词法分析 106.2 语法分析 1

2、17 软件的测试方法和测试结果127.1 软件测试方法127.2 测试结果12721简单for循环语句（无嵌套）12722 for循环嵌套语句148 研制报告168.1 研制过程168.2 对本设计特点和不足的评价168.3 收获与体会179 参考文献（按公开发表的规范书写） 17FOR 循环语句的翻译程序设计（递归下降法、输出四元式）1 系统描述（问题域描述）1.1目的通过设计、编辑、调试和运行一个 对 for 循环语句进行词法分析、语法及语义分析的编 译程序，并通过对实验用例的测试来更加深刻的理解语言编译的过程和原理。从而达到在理 论学习的基础上，对本课程有一个更深的掌握。1.2设计步骤对

3、循环语句：for表达式；循环条件；表达式赋值语句（赋值语句中可以嵌套更多的 for 循环语句）（1）设计符合自身语法分析方法要求的文法和属性文法。（2）设计对for循环语句进行词法分析的函数，输出单词序列。（ 3） 设计递归下降法对文法进行语法分析。（ 4） 对源文件进行语法分析同时对源文件进行语义处理。（5）设计中间代码格式并输出四地址中间代码到文件中保存。（6）对源文件中的错误进行输出。1.3 系统体系结构描述文件管理本系统包括两大部分：词法分析和语法分析；系统中还包含了一个文件管理的连接件 实现对词法分析结果和中间代码的输出保存功能。2 文法及属性文法的描述2.1 文法文法是用于描述语言

4、的语法结构的形式规则(即语法规则)。这些规则必须是准确的、易 于理解的以及有相当强的描述能力。由这种规则所产生的程序语言应有利于句子分析和翻译， 而且，最好能通过这些规则自动产生有效的语法分析程序。for循环语句的文法如下所示：1) S-for(W)Sx2) W-A;W13) W1-B;W24) W2-A5) Sx-Ax6) Sx-Am7) Am-AmAx8) Am-Ax2.2 属性文法递归下降法的属性文法是在上下文无关文法的基础上，为每个文法符号(终结符或者非终结 符)配备若干相关的“值”(与文法符号相关的属性)。在一个属性文法中，对应于每个产生式A-a都有一套与之相关联的语义规则，每规则的

5、形 式为：b:=f (cl, c2,，ck)。其中f是一个函数，b和cl, c2,，ck是该产生式的文法 符号的属性。并有如下规则：(1) 如果b是A的一个属性，cl，c2，ck是产生式右边文法符号的属性或A的其他属 性，则称b是A的综合属性。(2) 如果b是产生式右部某文法符号X的一个属性，并且cl，c2，ck是A或产生式右边 任何文法符号的属性，则称b是文法符号X的继承属性。for 循环语句的属性文法为：产生式属性文法S-for(W)Sxemit(l);/生成最后一个jump backpatch(nextstat,LastGotoAddress); 回填最后 jump; backpatch

6、(W.FalseOrEnd ,nextstat);/B 为假跳到最后一个语 句W1-B;W2backpatch(B.TrueOrChain,W2.True0rChain);backpatch(W2.FalseOrEnd , B.codeBegin );W2-Aemit(4);输出跳转W2.True0rChain = nextstat;W2.FalseOrEnd = nextstat-1;Sx-Am去掉B-B1IILbackpatch(B.FalseOrEnd, L.codeBegin );/ 回填 B.codeBegin =B1.codeBegin ;B.TrueOrChain=chainMe

7、rge(B 1.TrueOrChain,L.TrueOrChain);B.FalseOrEnd = L.FalseOrEnd ;LastGotoAddress=nextstat;记录最后 jump 回填地址B-LLastGotoAddress=nextstat;记录最后 jump 回填地址L-L&Mbackpatch(L.TrueOrChain , M.codeBegin );/ 回填L.codeBegin =L1.codeBegin ;L.TrueOrChain =M.TrueOrChain ;L. FalseOrEnd=chainMerge(L1 .FalseOrEnd,M.FalseOr

8、End );M-!M1M.TrueOrChain =M1.FalseOrEnd;M. FalseOrEnd =M1 TrueOrChainM.codeBegin =M1.codeBegin ;K-idScidK.TrueOrChain =nextstat;K.codeBegin =nextstat;K.FalseOrEnd = nextstat+1;emit(J+Sc,id,id, );/ 输出跳转语句emit(jump,-,-,);A-id=Eemit(E,-，- ,id);/输出赋值语句E-EoperT(oper 为+-*/)emit(oper , E , T , temp);/ 输出表达

9、式3 语法分析方法描述及语法分析表设计3.1语法分析方法递归下降分析方法是一种自顶向下语法分析方法，其目的是从文法的开始符号开始，根 据输入字符串进行最左推导，试图推导出给定的字符串。或者说，从根节点(文法开始符号) 开始，自上而下，从左到右地为输入字符串建立一棵语法树，并以预先确定的顺序创建语法 树的节点。递归下降分析法可能需要回溯，即需要重复地扫描输入。递归子程序法的实现思想是对应每个非终结符编写一个递归过程，每个过程的功能是识 别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，能够按照LL (1)形式 唯一地确定选择某个候选式进行推导，因此首先要消除左递归。由于递归下降法对每个

10、过程 可能存在直接或间接的递归调用，所以对某个过程在退出之前可能又要被调用，因此有些信 息需要保留，通常在入口时需保留某些信息，出口时需恢复。由于递归过程是遵循先进后出 规律，通常开辟栈来处理。递归调用的语法调用关系图如下图所示：递归调用的语法调用关系图3.2语法分析表设计在对 for 循环语句进行翻译时，涉及到对赋值表达式和布尔表达式语句的翻译。在文法 的描述中给出了算术运算符、关系运算符和逻辑运算符之间的优先级关系，其结合性由下表 所示：优先级操作符类型操作对象的个数结合性1()逻辑运算符左 右2!逻辑非运算符单目运算符右一 左3*,/算术运算符双目运算符左 右4+,算术运算符双目运算符左

11、 右5,=关系运算符双目运算符左 右6二二丨二，关系运算符双目运算符左 右7&逻辑与运算符双目运算符左 右8|逻辑或运算符双目运算符左 右9=赋值运算符双目运算符右一 左4中间代码形式的描述及中间代码序列的结构设计4.1 中间代码形式描述常见的中间代码形式有逆波兰记号，三元式，四元式和树形表示。本课程设计输出的中 间代码的表示方法是四元式。 四元式是一种更接近目标代码的中间代码形式。由于这种形 式的中间代码便于优化处理，因此，在目前许多编译程序中得到了广泛的应用。四元式实际上是一种“三地址语句”的等价表示。它的一般形式为： (op,argl,arg2,result)其中，op为一个二元(也可是

12、一元或零元)运算符；argl,arg2分别为它的 两个运算 (或操作)对象，它们可以是变量、常数或系统定义的临时变量名；运算的结果将放 入 result 中。需要指出的是，每个四元式只能有一个运算符，所以，一个复杂的表达式须由多个四元 式构成的序列来表示。例如，表达式A+B*C可写为序列T1 : =B*C T2 : =A+T1其中，Tl, T2是编译系统所产生的临时变量名。当op为一元、零元运算符(如无条件转移) 时， arg2 甚至 arg1 应缺省，即 result: =op arg1 或 op result ；对应的一般形式为： (op,arg1,result) 或 (op,result

13、)4.2中间代码序列的结构设计对于循环语句：for （语句1；语句2；语句3） 表达式，的中间代码序列的结构为:5 编译系统的概要设计5.1 系统分析5.1.1 词法分析对源程序流进行扫描，每识别出一个单词，若是标识符，则到符号表中查找，如果符号 表中没有此标识符的记录，那么将此标识符插入符号表。最后按照单词其所属的类别，把类 标识返回，作为语法分析阶段的输入。5.1.2语法分析由文法开始符号对应的子程序控制 for 循环语句各个模块的执行顺序，并由文法开始符 号对应的子程序递归调用其他的子程序，对各个模块采用自顶向下，自左至右的推导方法完 成对输入字符进行匹配的工作，试图推导出与输入符号串一

14、致的文法的句子。5.1.3 中间代码生成控制代码的输出形式，以四元式形式输出中间代码5.2 概要设计5.2.1系统总体设计图5.2.2数据结构这次课程设计中，在词法分析阶段，用一个 KeyWord.txt 文件存放所有的关键字，用一 个结构体数组tableword table_word100来存放词法分析所输出的单词序列，并将单词序列输 出到文件 word.txt 中。在语法分析过程中，同样使用一个结构体数组item siyuanshi100来存放语法分析输 出的中间代码四元式，并将结果输出到 siyuanshi.txt 中。数组 tablewordlexptrtokenEOSEOShEOSE

15、OSoowayouEoSKEYIDIDIDID字符串数组 table_word定义字符表的数据结构如下：struct tablewordstring word;int type;/l表示ID, 2表示数值常量，3表示字符常量，0表示其它 ;/*为符号表分配一个存储空间*/tableword table_wordl00;int tableword_length=0;int word_now=0;/*保存将要输出的四元式信息*/struct itemstring text;/四元式内容 ;item siyuanshil00;6 详细的算法描述（流程图或伪代码）6.1 词法分析/词法分析相关函数（l

16、 ）bool Keyword（char c,string *KEYWORD,int KNLength,ifstream &infile）;/*对字符进行关键词的判断，将字符与关键词一个一个进行比较，如果比较成功，则返回真 如果比较到文件末尾，还未成功，则返回假。*/（2）bool Identify（char c,ifstream &infile,string &strtemp）;/对字符进行标示符的判断(3)bool ConstChar(char c,ifstream &infile); /对字符进行字符串常量的判断()bool ConstNum(char c,ifstream &infile

17、); /对字符进行常数的判断() bool Operator(char c,ifstream &infile); /对字符进行运算符的判断()bool Delimiter(char c ); /对字符进行界符的判断()int classfify(char c);/对字符进行类型判断，相应返回类型号 () int classify_num(char c);/对读入的数字字符进行分类6.2 语法分析/语法语义函数，每个函数对应产生式的一个非终结符，从上到下进行递归调用，直到推出相 应的终结符串。receive ()函数是对字符进行相应入栈出栈操作。emit()函数则是将产生的四 元式中间代码输入到

18、数组中。void S(tableword &word);void A(tableword &word);void E(tableword &word);void D(tableword &word);void O(tableword &word); void P(tableword &word); void G(tableword &word); void B(tableword &word); void S1(tableword &word); void X(tableword &word); void E1(tableword &word); void T(tableword &word)

19、; void T1(tableword &word); void F(tableword &word);void receive(tableword &word,string temp,int type); void emit(int row,string strtemp);7 软件的测试方法和测试结果7.1 软件测试方法由于本程序在设计上考虑到 for 循环语句的多种表现形式，如 for 嵌套的方式，条件语句 的表述等，所以在理论上能完成的功能很全，因此为了测试程序在实际应用中能否完成这些 功能，我设计了两种测试途径：(1)输入最简单的 for 循环语句(无嵌套)(2)实现简单for嵌套，可

20、包括多个赋值语句7.2 测试结果721简单for循环语句(无嵌套)简单for循环语句的输入文件如下图所示:MLXMJCJOCMKXJtJCMMMKWXMJCMKJOCMJCMLKMXXMLJCMKJCMLXMJCJOtMKXKJCMXMKFOR循环语句的翻译程序设计(递归下隆法、输岀四元式)X JHJCJJCJO KHJC KH KICKy 0?渤于 旳 彳子彳二 JCJHJCJJCJOJ1CJCJJJOChhX学号.S12Q910340905:mhx 输出 1 wo rd - txt :姻址码形式输出到siyuanshi.t xt鑑卿勰辦出到Press any key to continue

21、输出词法分析的单词序列：ordtxl -迅言広文昨旧 痹载E；l梧式QJ堂者卩：1辛助HlJ-crjr bp Lp LJr bp Lp LJr bp hr LJr 0.1234567B90 O1234S678911111111112 JI JL1 JrLl Ji In JrLI JL1 JL1 JL1 J1 JL1 Jrl Ji JL JrLl Ji JiH Jul Ji Ju JL1输出语法语义分析之后的四元式中间代码：ADDRE55 5ianshi 0(= -i|1 (jump-3)2 (* 1 i )3 (jli 100 3)4-(jump-8)5 (i-m 1 tO6 (=tO - m

22、)1jump-2|7.2.2 for循环嵌套语句for 循环嵌套语句的测试用例输入文件：|-far(i=2;ilM;i+)c=i/k+2*3; a=jk+c+6/2;for(k=2;5：k+)外丽精旧梧式Q(V)祂氐(巴te&t2 txt -亍事玉词法分析后输出的单词序列文件：玄肛旧 3&H*C=J 拾式而 *(7 宓flti而ADDRES&01234563 121 )(29)：=130): i31)： /阳:k(33); +(M)： 2： k:+(44) ： c(45) : +(46) : 6阿:/阳:2：；(50): ：输出语法语义分析之后的四元式中间代码:m yuansl-i.txt -

23、另文牛無辑E） ms（o）童夏（V）祸吐（HSiyua nii(=2 - i(jump -j 十 i 1 ii jl i 100(jump - (=2 -10(/i k tO )11 w2 3 tl )12（亠10 tl t2 )13（二t2 - c )14(si k tB jIS十t3 t t4 )16 /6 2 tS )17 +t4 15 恬)18（二t6 - a 19(jump - - 7 20(jump - - 2. 21(jump-8 (+ k1k)(jl k58)(jump-20 )8 研制报告8.1 研制过程作为一名计算机科学与技术专业大三的学生，我觉得能做类似的课程设计是十分有

24、意义。 它对我们的能力的提升很有好处。在已度过的大三的时间里我们大多数接触的是专业基础课 我们在课堂上掌握的仅仅是专业基础课的理论面，如何把我们所学到的专业基础理论运用到 实践中？课程设计为我们提供了良好的平台。课程设计是培养学生综合运用所学知识发现提 出分析和解决实际问题锻炼实践能力的重要环节是对学生实际工作能力的具体训练和考察过 程. 回顾起此次 for 循环课程设计，我感慨颇多，的确，从考察到定稿，从理论到实践，在 这一个多星期的日子里，可以说是苦多于甜，但是我学到了很多很多的的东西，不仅巩固了 以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。在本次课程设计中，我 先是具体了

25、解了各种文法，然后进行了自己的文法的设计，将二者结合起来，作出一个自己 的文法，然后我开始设计一些基本的构件并描述出它们的具体接口功能，接口设计好之后， 下一步便是进行类接口的实现了，最关键的一步是总控程序的设计，对其他构件类的调用。 在以上功能完成之后，我们便开始遍程了。最后，进行调试。至此，我的 for 语法分析及翻 译系统出炉了，余下的工作便是进一步的完善系统功能。8.2对本设计特点和不足的评价本程序实现的功能有：简单for循环，for循环嵌套，赋值语句，多个赋值语句（用分号隔 开成语句），能完成的计算功能有布尔表达式，基本的四则运算，能将各个功能结合起来形成 for循环，赋值语句，布尔

26、表达式，空语句的复合出现。for语句的实现上，通过将之分解成三个表达式来分别调用，直接对应接口，使得代码冗 余大大减小。for语句的分隔符是采用来代替了小括号，避免了回溯所带来的算法效 率低问题。在词法分析阶段，区分一元和二元操作符的方法是：当取得的第一个字符为一元操作符 时，继续取下一个字符，若仍为操作符，则返回宏定义的标号，若不是操作符则将其放回， 返回一元操作符的标号。在词法分析阶段在每一个类型判断中都需要进行放回操作。 对语法分析，词法分析，四元式输出分离设计，同步控制，使得代码更灵活，结构更紧凑， 不必要对中间结果进行大量重复的存储后，然后逐一检索后使用。由于没有对中间结果进行存储，

27、造成语法上的某些错误处理不是很方便等缺点。不过这 个缺点并非先天性的，可以通过冗余的存储中间结果来克服。同时，这个功能可以作为编译 是的一个开关选项，当编译过程中为了追求效率时，不打开冗余存储开关（相当于gcc中的-On 型开关），当为了检测更多的错误时，打开冗余存储开关（相当于gcc中的-Wall）。 词法分析的功能做得比较简单，主要是考虑到本程序的要求比较局限，只在 for 和赋值语句 上做了要求，不过程序采用switch-case语句和if-else语句的配合使得词法分析有比较大的扩 展空间。8.3 收获与体会此次的课程设计我一共用了整整一周才全部完成，之前在学理论的时候，感觉和实际的

28、编程联系不是很大，也不知道所学的理论如何在实际中发挥作用，如何应用，而通过这次的 课程设计，才真正的体会到了平时所学的每一步在实际的程序中实现的，实践是检验知识的 最好工具。在整个编程过程中，在词法分析和语法分析的实现过程中遇到了一些困难，比如在参数 变量定义时出现错误，或者在设计循环和堆栈操作时也出现了一些错误，虽然通过同学的帮 忙和自己的认真思考，都得到了解决。但是还是深深感觉到自己在实际编程的能力上需要进 一步的更深的学习和实践，努力做到真正的把理论与实际相结合。9 参考文献（按公开发表的规范书写）1 何炎祥编译原理（第二版）武汉：华中科技大学出版社2005年8月2 陈火旺等程序设计语言编译原理（第3版）国防工业出版社2003年2 月3AlfredV.Aho,Ravi Sethijeffrey D.Ullman. Compilers:Principles,Techniques,and Tools.人民邮电出版 社 2002 年 2 月4 胡伦骏编译原理（第2 版）电子工业出版社2005年2月5 陈意云编译原理与技术（第二版）中国科学技术大学出版社2002年1 月6 胡元义等编译原理实践教程西安电子科技大学出版社2002年1月7 王雷等编译原理课程设计机械工业出版社2005年3月8 张素琴、吕映芝、蒋维杜、戴桂兰等编译原理（第2版）清华大学出版社2005年2月