编译原理课程设计(if-else条件语句翻译三地址简单优先法).doc

课程设计任务书题目: IF-ELSE条件语句的翻译程序设计（简单优先法、输出三地址表示）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法及属性文法。（2） 完成题目要求的中间代码三地址表示的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名： 2013年 月 日系主任（或责任教师）签名： 2013年 月 日 IF-ELSE条件语句的翻译程序设计（简单优先法、输出三地址表示）1 系统描述 1.1题目IF-ELSE条件语句的翻译程序设计（简单优先法、输出三地址表示）1.2目的通过设计、编制、调试一个条件语句的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。1.3设计内容及步骤对条件语句： IF 布尔表达式 THEN 赋值语句 ELSE 赋值语句（1） 按给定的题目写出符合语法分析方法要求的文法和属性文法描述。（2） 按给定的题目给出语法分析方法的思想及分析表设计。（3） 按给定的题目给出中间代码序列的结构设计。（4） 完成相应的词法分析、语法分析和语义分析程序设计。（5） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。2 文法及属性文法的描述2.1文法文法是用于描述语言的语法结构的形式规则（即语法规则）。这些规则必须是准确的、易于理解的以及有相当强的描述能力。由这种规则所产生的程序语言应有利于句子分析和翻译，而且，最好能通过这些规则自动产生有效的语法分析程序。IF-ELSE条件语句的文法GS如下所示：(1) S - CM(2) S - TM(3) M - begin L end(4) C - if B then(5) T - C M else其中非终结符B为布尔表达式，其文法GB如下：(1) B - B1 or B2(2) B - B1 and B2(3) B - not B1(4) B - ( B1 )(5) B - id1 rop id2(6) B - true(7) B - false而在文法GS中非终结符L表示赋值语句块，其文法GL如下：(1) L - L1 A ;(2) L - A;(3) A - id = M(4) M - E(5) E - E1 + E2(6) E - E1 * E2(7) E - -E1(8) E - ( E1 )(9) E - id 2.2属性文法属性文法是在上下文无关文法的基础上，为每个文法符号（终结符或者非终结符）配备若干相关的“值”（与文法符号相关的属性）。 在一个属性文法中，对应于每个产生式Aa都有一套与之相关联的语义规则，每规则的形式为：b:=f(c1,c2,，ck)其中f是一个函数，而且或者b是A的一个综合属性并且c1,c2,，ck是产生式右边文法符号的属性或者非终结符既可有综合属性也可有继属性，文法开始符号的所有继承属性作为属性计算前的初始值1。2.2.1 语义变量和语义动作说明 对于文法GL,首先对id表示的单词定义一属性，用做语义变量，用Lookup（）语义函数审查是否出现在符号表中，如在，则返回一指向该登陆项的指针，否则返回nil。语义过程emit表示输出四元是到输出文件上。语义过程newtmp表示生产一临时变量，每调用一次，生成一新的临时变量。语义变量E.place，表示存放E值的变量名在符号表的登陆项或一整数码（若此变量时一个临时变量）2，2.2.1 给出了翻译赋值语句块到三地址的语义描述。 2.2.1 GS的属性文法为：(1) S - CM S.chain := merge(C.chain,M.chain) (2) S - TM S.chain := merge(T.chain,M.chain) (3) M - begin L end M.chain := L.chain(4) C - if B then bakpatch(B.true,nextstat) C.chain := B.false(5) T - C M else q := nextstat emit(GOTO-) backpatch(C.chain,nextstat) T.chain := merge(M.chain,q)2.2.2 GB的属性文法为：(1) B - B1 or B2 backpatch(B1.false,B2.codebgin); B.codebegin := B1.codebegin; B.true := merge(B1.true,B2.true); B.false := B2.false(2) B - B1 and B2 backpatch(B1.true,B2.codebegin); B.codebegin := B1.codebegin; B.true := B2.true; B.false := merge(B1.false,B2.false);(3) B - not B1 B.true := B1.false; B.codebegin := B1.codebegin; B.false := B1.true;(4) B - ( B1 ) B.true := B1.true; B.codebegin := B1.codebegin; B.false := B1.false;(5) B - id1 rop id2 B.true := nextstat; B.codebegin := nextstat; B.false := nextstat+1; emit(ifid1.placeropid2.placegoto-); emit(goto-) (6) B - true B.true := nextstat; B.codebegin := nextstat; emit(goto-)(7) B - false B.false := nextstat; B.codebegin := nextstat; emit(goto-) 其中nextstat给出在输出序列中下一三地址式子的序号。emit过程没调用一次，nextstat增加12.2.3 GL的属性文法为：(1) L - L1 A ; L.chain := A.chain(2) L - A; L.chain := A.chain(3) A - id := M p := lookup(); if p nil then emit(p := E.place); else error(4) M - E (5) E - E1 + E2 E.place := newtemp； emit(E.place :=E1.place + E2.place)(6) E - E1 * E2 E.place := newtemp; emit(E.place := E1.place * E2.palce)(7) E - -E1 E.palce := newtemp; emit(E.place := minusE1.place)(8) E - ( E1 ) E.place := E1.place (9) E - id (6)A-num p := lookup(); if p nil then E.palce := p else error3 语法分析方法描述及语法分析表设计3.1简单优先法的定义构造及优缺点3.1.1简单优先法定义构造一个文法G，若它不含e产生式，也不含任何右部相同的不同产生式，并且它的任何符号对(X,Y)，或者没有关系，或者存在下述三种关系：=、之一，则称该文法是一个简单优先文法。 A)X=Y当且仅当G中含有形如PXY的产生式 B)XY当且仅当Y为G的终结符，G中含有形如PQR的产生式，其中Q，R为非终结符，且Q X，YFirst(R)D)对任何X，若文法开始符号SX，则#。33.1.2简单优先法的优缺点优点：准确、规范，技术简单。缺点：适用的范围小，构造的分析表太大，分析效率较低。3.2语法分析为实现简单优先算法,可以使用工作栈.用以寄存操作数或运算结果.算法的基本思想是: (1) 置初始状态：S(1):=#, i:=1, j:=1(2) 若 S(i)与T(j)无任何关系，则出错停机(3) 若 S(i)= T(j)或S(i)T(j)，则把T(j)送入S栈中，读下一符，转（2）。(4) 若S(i)T(j)，则从S栈顶开始往前栈串Sj1 ,Sj1+1,Si其中 Sj1为第一个使 Sj1-1Sj1 ,然后用Sj1,Sj1+1,Si去查生产式表，若查到有相同右部的产生式即USj1,Sj1+1,Si，则从栈中退掉子串Sj1,Sj1+1,Si，并把U进栈；然后转(2)。若查不到转出错处理。(5) 若T(j)=#,并且S栈的内容为# Z(Z为文法开始符号)则正确停机。否则，出错停机。3.3语法分析表设计3.3.1 GS的优先关系表如表1：表 1 GS 的优先关系矩阵SCTM beginLendifB thenelse#SC=T=beginif=B=thenelse#orandnot()id=rop=truefalse#注：表中id代表标识符，rop代表关系运算符,下同。3.3.2 GL的优先关系表如表3：表 3 GL 的优先关系矩阵LA ; := ( ) id + - M E * # L = A = ; := = ( = + = - E = # b and c b goto 3002: goto -003: if c ,等。常数 如13，34，67等。界符 如“，”“；”“（”“）”“”“”等。词法分析流程图如图4：图4 词法分析流程图6.2语法分析 语法分析的任务是识别单词符号序列是否符合给定的语法规则，并在规约时调用相应的语义函数，执行中间代码的翻译。语法分析过程还包含简单的错误处理机制。语法分析流程图如下：开始初始化词法分析 器及符号栈规约后的符号进栈 当前输入单词进栈 出错处理规约成开始符号？ 结束栈顶元素优先级大于或等于出栈元素？ 栈顶元素优先级 大于输入单词？ 无关系？查优先关系表，得栈顶元素与输入单词优先关系为文件结束符？从词法分析器取下一个单词 栈顶元素出栈用所有弹栈的元素作为产生式右部规约 图5 语法分析7 软件的测试方法和测试结果7.1.1 测试用例1 测试用源文件如下：if ab or c f then begin x = y*z*a; d= -h; p= q+r+s; c =w; end#$其中“#”为文法结束标志，“$”为文件结束标志，下同。运行结果如下图6，图6 用例1运行结果文件输出结果为：001: if a b goto 7002: goto 3003: if c f goto 7006: goto -007: T1:= a * z008: T2:= T1 * y009: x:= T2010: T3:= - h011: d:= T3012: T4:= s + r013: T5:= T4 + q014: p:= T5015: c:= w 图中的“goto -,表示布尔表达式的假出口，下同。7.1.2 测试用例2 测试用源文件如下：if ab and cd then begin x = y*z*a; d= -h; p= q+r+s; c =w; endelse begin x = y*z*a; d= -h; p= q+r+s; c =w; end#$运行结果如下图7，图7 用例2运行结果7.1.3 测试用例3测试用源文件如下：if ab or c f then begin x = y*z*a; d= -h; p= q+r+s; c =w; end#if ab and cb and cd then begin x = y*z*a; d= -h; p= q+r+s; c =w; endelse begin x = y*z*a; d= -h; p= q+r+s; c =w; end#$运行结果如下图9图9 用例4运行结果8研制报告8.1研制过程 选择符合条件的文法，然后对满足文法的if then else语句进行翻译。首先进行词法分析，对输入的符号串进行分析，判断出关键字，数字，终结符和非终结符。然后进行语法分析，首先要构造出文法的简单优先关系矩阵，然后再将输入的符号串根据简单优先关系矩阵放入栈中，如果栈中的栈顶符号比输入串队列的队头符号优先关系为则要将栈中的符号进行归约，这时要找到栈中的句柄归约，若找不到句柄进行归约则输入的符号串不是该文法的句子。找到句柄归约完之后再重复上面的步骤，最后得到接受acc，完成分析过程。8.2本设计的评价、特点、不足、收获与体会等该程序能够对输入的单词符号串进行词法分析，语法分析，并能产生三地址形式的中间代码，完成了所要求的内容。但由于时间关系以及自身的编程能力的关系，该程序中还存在着很多的不足。比如该程序的容错能力不强，对有些输入串不能正确分析，以及并未严格的完成语法制导翻译等。在完成了整个程序后的确有很多的收获和体会。在这次课程设计中我最大的收获就是对简单优先法的整个过程有了非常深刻的认识，也更加深了我对该分析法的理解，也对我的编程能力有一定的提高，同时也培养了自己严密的逻辑思维能力。基础知识方面，由于授课学时的限制和自己学习中的疏忽，遗漏了一些比较细小的知识点，例如：数组下标的问题，和栈使用的时候的栈顶指针指向问题，问题虽然小，但是在运行程序时，这种错误的确是比较具有隐蔽性的，也比较烦人。在上机实验方面，在平时的学习中，学习的是理论知识，所以在进行课程设计的时候，发现一定的难度。由于语句相对比较多，很多函数的组合没有处理好，经常会出现函数类型不匹配的错误。由于程序比较长，语句的包含关系的搞错和匹配问题也在编译时经常碰到。总之，在这次课程设计后我的理论知识，动手动脑能力，和心理素质都有了一定的提高，经过这次实验，我基本明白了自己做一个课题的实验过程，从中也学到很多东西，这是以前按教科书上照搬照套的实验得不到的。在这里，我也要感谢我的同学和老师，正是他们帮助我解决了课程设计中遇到的一个又一个难题。9参考文献1蒋宗礼、姜守旭编译原理（第1版）高等教育出版社2010年2月2张素琴、吕映芝、蒋维杜、戴桂兰编译原理（第2版）清华大学出版社2005年2月 3陈意云等编译原理（第2版）高等教育出版社2008年6月附录1 源代码 / 主函数#include Lexical.h#include SStack.h/ Global variables declarationconst int TAB_DIM0 = 12;const int TAB_DIM1 = 13;const int TAB_DIM2 = 13;/ Data structure definitionint preMat0TAB_DIM0TAB_DIM0; int preMat1TAB_DIM1TAB_DIM1;int preMat2TAB_DIM2TAB_DIM2;/* Define the precedence relationships NO: not relativeEQ: equalLT: less than GT: greater than*/enum Relation NO=-1,EQ,LT,GT;/ Function declarationToken* processBoolean(Lexical &lex);Token* processAssignmentBlock(Lexical &lex);Chain* merge(Chain* head,Chain* append);Chain* merge(Chain* head,int label); int main() / Initializingint i,j;for(i=0;iTAB_DIM0;i+)for(j=0;jTAB_DIM0;j+) preMat0ij = -1;for(i=0;iTAB_DIM1;i+)for(j=0;jTAB_DIM1;j+) preMat1ij = -1;for(i=0;iTAB_DIM2;i+)for(j=0;j CM(2) S - TM(3) M - begin L end(4) C - if B then(5) T - C M else-Grammer GB:(1) B - B1 or B2(2) B - B1 and B2(3) B - not B1(4) B - ( B1 )(5) B - id1 rop id2(6) B - true(7) B - false-Grammer GL:(1) L - L1 A ;(2) L - A;(3) A - id = M(4) M - E(5) E - E1 + E2(6) E - E1 * E2(7) E - -E1(8) E - ( E1 )(9) E - id- Precedencd matrixs for Grammer GS*/preMat013=preMat023=preMat045=0;preMat056=preMat0310=preMat078=0;preMat089=0;preMat024=preMat0112=preMat014=1; preMat0117=preMat01111=preMat034=1; preMat0111=preMat0104=preMat0103=1;preMat0011=preMat0610=preMat093=2;preMat094=2; preMat0611=preMat0311=preMat0104=2;/ */ * / Precedencd matrixs for Grammer G1 preMat101=preMat102=preMat110=0;preMat120=preMat130=preMat105=0;preMat140=preMat167=preMat176=0; preMat113=preMat114=preMat116=1;preMat123=preMat134=preMat148=1;preMat149=preMat1106=preMat1108=1;preMat11