《编译原理》课程设计说明书WHILE循环语句的翻译程序设计.doc

附件1：学 号： 课 程 设 计题 目WHILE循环语句的翻译程序设计学 院计算机科学与技术学院专 业计算机科学与技术班 级计算机0702姓 名指导教师 2010年1月8日课程设计任务书学生姓名： 专业班级： 计算机0702班 指导教师： 工作单位：计算机科学与技术学院 题目: WHILE循环语句的翻译程序设计（LR方法、输出三地址表示） 初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法及属性文法。（2） 完成题目要求的中间代码三地址表示的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名： 2009年 11月 23日系主任（或责任教师）签名： 2009年 11月 23日1.系统描述 自定义while循环句型的文法及其属性文法，并用LR法为该文法设计、编制、调试一个语法及语义分析程序，并在过程中实现词法分析、语法分析，最终以三地址码的形式将形成的中间代码输出。2.文法及属性文法的描述21 文法的描述该文法的产生式如下所示：S->while(A)B;A->CDCC->a|b D-> <=|>=|<|> B->a=E B->B; E->EFE E->(E) E->a|b F->+|-|*|/ 其中while、( 、) 、 、 、；、a 、b、<=、>=、<、>、=、+、-、*、/ 均为终结符，而S、A、B、C、D、E、F这些大写字母均为非终结符。D表示比较运算符，F表示算术运算符。22 属性文法的描述对该文法的属性文法描述如下：(1) S->while(A)B; prinf(if A goto B else goto next)(2) A->CDC printf(A.val = C1.val D C2.val) (3) C->a|b C.val = a | b(4) D-> <=|>=|<|> D.val = <=|>=|<|> (5) B->a=E B.val =a.val = E.val (6) B->B; printf(B = i1.Val T i2.Val)(7) E->EFE printf(E.val = E1.val F E2.val) (8) E->(E) printf(E.place=E1.place)(9) E->a|b E.val = a | b(10)F->+|-|*|/ F.val = +|-|*|/ 3. 语法分析方法描述及语法分析表设计3.1语法分析方法的描述3.1.1 LR分析法基本概述LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。LR分析法正是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输入串的K个(K0)符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄3.1.2 LR分析器分析过程1.首先将初始状态 S0及句子的左界符#分别压入状态栈和符号栈中。2.设在分析中的某一步，分析栈及余留的输入串为如下格局： S0S1 Sm ai ai+1an #X1 Xm 则用栈顶状态Sm和当前扫描符 ai组成符号对（ Sm, ai)去查分析动作表，根据ACTIONSm, ai的指示完成相应的分析动作。表中每一表元素所规定的动作仅能是下列四种动作之一：（1） ACTIONSm, ai= Sm+1 （移进）表明句柄尚未在栈顶形成，此时正期待移进输入符号以便形成句柄。故将当前的输入符号和表元素Sm+1分别压入栈中（2） ACTIONSm, ai= Rj (归约）表明此时应按文法的第j个产生式A Xm-k+1Xm-k+2 Xm 进行归约。即栈顶符号串Xm-k+1Xm-k+2 Xm已成为当前句型的句柄。所谓按第j个产生式归约，就是将分析栈中从顶向下的k个符号退栈，然后将文法符号A压入符号栈中。然后以（ Sm-k,A)去查状态转移表，设GOTOSm-k,A= Sl ,则将此新状态压入状态栈中。（3） ACTIONSm, ai=acc （接受）表明当前的输入串已被成功地分析完毕，应停止分析器的工作。（4） ACTIONSm, ai=ERROR（空白）。 表明当前的输入串中含有错误，也应终止当前的分析工作。转出错处理3. 重复上述第2步的工作，直到分析栈顶出现“接受状态”或“出错状态“为止。3.2 LR分析表设计构造3.2.1 已定义文法的DFA如图3.2.13.2.2 文法的分析表见表3.2.2分析表注释：a代表 a|b+代表 +|-|*|/<=代表 <=|>=|<|>a|bEF（E;F)E)(a|bEFa|b>|<)a|bCDI3: S->W (·A)B;A->·CDCC->·a|bI4: C-> a|b·I6: S->W (B)·EI5: A->C·DCD->·>|<I7: A->CD·CC-> ·a|bI20: E->EF·EE->·(E)E->·EFEE->·a|bI14: B->a=·EE->·(E)E->·EFEE->·a|bI21: E->EFE·I22: E-> (E·)I13: B->a·=EI16: E->E·FEF->·+|-|*|/ I15: B->a=E·I18: E->a|b··I17: E-> (·E)E->·(E)E->·EFEE->·a|bSW(a|bB;E;（=EFCaI8: A->CDC·I0: S->·SS ->·w(A)B;I2: S->W ·(A)B;I1:S->S·I9:S->W (A·)B;I10:S->W (A) ·B;I11:S->W (A) ·B;B->·a=EB->·B;I12:S->W (A) B·B->B·I24:S->W(A)B;·B->B;·I25：S->W(A)B;·I23:E-> (E)·图3.2.1： 文法的DFA分析表的ACTION部分状态w（）；a<= +#0S21acc2S33S4R345S66R47S48R29S1010S1111S1312S2413S1414S17S1815R5R516S191718R919R102021R722S2323R824S25R625R1分析表的GOTO部分状态SABCD EF011239545767889101112121314151615162017161819202121222324254.中间代码形式的描述及中间代码序列的结构设计本系统中所采用的中间代码形式是三地址，是一种比较普遍采用的形式。三地址的组成成分是：运算结果RESULT、第一运算对象ARG1、算符op第二运算对象ARG2。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。例如a：=b*c+b*d的三地址表示如下：1）t1:=b*c2）t2:=b*d3）t3:=t1+t24）a:=t3三地址对中间结果的引用必须通过给定的名字，也就是说，三地址的联系是通过临时变量实现的。将while( B rop C )goto L写成四元式为（jrop，B，C，L）进一步写为三地址为if B rop C goto L5 编译系统的概要设计5.1 词法分析词法分析程序要做的工作是：从源程序的第一个字符开始，顺序读字符，一次读一个，根据所读进的字符识别各类单词，同时去掉源程序中的空白和注释。词法分析检查的错误主要是挑出源程序中出现的非法符号。所谓非法符号是指不是程序设计语言中允许出现的符号，就像自然语句中的错字。结束符“#”界限符开始到输入流中读下一字符ÞCharChar是什么？初始化标识符和关键字词法分析子程序字母数字运算符无符号数词法分析子程序运算符词法分析子程序界限符词法分析子程序I1: S->S·流程图如下：5.2 语法分析语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。流程图如下：输入串#cic1Sp#XiSi总 控 程 序输出ACTION表GOTO表栈结束其中SP为栈顶指针，Si为状态栈，Xi为文法符号栈。状态转换表内容按关系GOTOSi,X=Sj确定，改关系式是指当前栈顶状态为Si遇到当前文法符号为X时应转向状态Sj。X为终结符或非终结符。5.3 语法制导翻译在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译。属性文法的每个符号有属性，所以每个符号入栈时，必须连属性一起入栈，这样，栈符号就由文法符号及存放该符号属性的域所组成。由于属性类型不同，属性域存放的内容就要根据属性的类型来定。有的可能直接存放属性值，也有的存放的是指向属性值的指针。对于综合属性，其属性域不存放其属性值，而是存放一个指针，指向存贮该属性值的单元。对于继承属性，其属性域直接保存其属性值。继承属性的属性域刚入栈时为空，但是在该栈符号变成栈顶符号之前的某一时刻，它们必须接受相应的属性值，即在成为栈顶时，继承属性的属性域必须有值。6 详细的算法描述主要是词法分析与LR语法分析部分（包含主体程序干，对于调用的函数略去）词法分析主体：int cifa()ofstream fout;fout.open("词法分析.txt",ios:out);if(!fout)cout<<"词法分析文件打开失败！"<<endl;fout.close();/将词法分析文件置空ifstream fin;fin.open("源文件.txt");if(!fin)cout<<"打开源文件失败!"<<endl;/源文件打开char temp120;for(int i=0;i<20;i+)temp1i='0'/temp1用来记录非符号串且初始值均置空char temp2;i=0;while(!fin.eof()&&temp2!='')fin.get(temp2);if(Isfuhao(temp2)/当读入的是符号时，分析temp1 if(temp10!='0') analysis(temp1);fuhao(temp2);/判断是那种符号i=0; for(int i=0;i<20;i+) temp1i='0'/temp1置空elsetemp1i=temp2;i+; fin.close();cout<<"文件 词法分析 导入完成！"<<endl;cout<<"是否转化为含有双符号的词法分析文件？(yes-1,no-0)"<<endl;cin>>i;if(i)change();cout<<"文件 词法分析2 已导入完成！"<<endl;/转化为双符号 return 0; 语法分析中分析表部分：words *gotoaction(words *p)int n=top->n;zhuangtai *temp;temp=top;while(temp!=NULL)cout<<temp->n<<" "temp=temp->next;cout<<"now analysis "<<p->w<<endl;switch(n)case(0):if(strcmp(p->w,"while")=0) push(2);p=p->next;break;case(1):if(strcmp(p->w,"")=0) pop(1);push(0);break;case(2):if(strcmp(p->w,"(")=0) push(3);p=p->next;break;case(3):if(strcmp(p->d,":为标示符")=0|strcmp(p->d,":为常数")=0) push(4);p=p->next;break;case(4):pop(1);n=top->n;if(n=3) push(5);break; if(n=7) push(8);break;case(5):if(strcmp(p->d,":运算符")=0) push(6);p=p->next;break;case(6):pop(1);push(7);p=p->next;break;case(7): if(strcmp(p->w,")")=0) push(8);break;case(8):pop(3);push(9);break;case(9):if(strcmp(p->w,")")=0) push(10);p=p->next;break;case(10):if(strcmp(p->w,"")=0) push(11);p=p->next;break;case(11):/if(strcmp(p->w,"")=0) push(12);break; if(strcmp(p->d,":为标示符")=0) push(13);p=p->next;break; case(12): if(strcmp(p->w,"")=0) push(24);p=p->next;break;case(13):if(strcmp(p->w,"=")=0) push(14);p=p->next;break;case(14):if(strcmp(p->w,"(")=0) push(17);p=p->next;break;if(strcmp(p->d,":为标示符")=0|strcmp(p->d,":为常数")=0) push(18);p=p->next;break;case(15): pop(3);if(top->n=11) push(12);break;case(16):/if(strcmp(p->d,":为运算符")=0)if(strcmp(p->d,":运算符")=0)push(19);p=p->next;break;case(17):if(strcmp(p->w,"(")=0) push(17);p=p->next;break;if(strcmp(p->d,":为标示符")=0|strcmp(p->d,":为常数")=0) push(18);p=p->next;break;case(18):pop(1);n=top->n;if(strcmp(p->w,")")=0)&&(n=20) push(21);break;if(strcmp(p->w,"")=0)&&(n=20) push(21);break;if(n=14)&&(strcmp(p->d,":运算符")=0) push(16);break;if(n=14)&&(strcmp(p->d,":为标示符")=0|strcmp(p->d,":为常数")=0) push(15);break;if(strcmp(p->d,":运算符")=0)&&(n=17) push(16);break;if(strcmp(p->w,")")=0&&(n=17) push(21);break;if(strcmp(p->d,":运算符")=0)&&(n=20) push(16);break;case(19):pop(1);if(top->n=16) push(20);break;case(20):if(strcmp(p->d,":为标示符")=0|strcmp(p->d,":为常数")=0) push(18);p=p->next;break;if(strcmp(p->w,"(")=0) push(17);p=p->next;break; case(21):pop(3);n=top->n;if(strcmp(p->w,")")=0&&(n=17) push(22);break;if(strcmp(p->w,"")=0)&&(n=20) push(21);break;if(strcmp(p->d,":运算符")=0)&&(n=20) push(16);break;if(strcmp(p->w,")")=0)&&(n=20) push(21);break; if(n=14)&&(strcmp(p->w,"")=0) push(15);break;if(n=14)&&(strcmp(p->d,":运算符")=0) push(16);break;if(n=14)&&(strcmp(p->d,":为标示符")=0|strcmp(p->d,":为常数")=0) push(15);break;if(strcmp(p->d,":运算符")=0)&&(n=17) push(16);break;case(22):if(strcmp(p->w,")")=0) push(23);p=p->next;break;case(23):pop(3); n=top->n;if(strcmp(p->w,")")=0&&(n=17) push(22);break;if(strcmp(p->w,"")=0)&&(n=20) push(21);break;if(strcmp(p->d,":运算符")=0)&&(n=20) push(16);break;if(strcmp(p->w,")")=0)&&(n=20) push(21);break;if(n=14)&&(strcmp(p->d,":运算符")=0) push(16);break;if(n=14)&&(strcmp(p->d,":为标示符")=0|strcmp(p->d,":为常数")=0) push(15);break;if(strcmp(p->d,":运算符")=0)&&(n=17) push(16);break;case(24): if(strcmp(p->d,":为标示符")=0)|(strcmp(p->d,":为标示符")=0)pop(2);push(13);p=p->next;break;if(strcmp(p->w,"")=0) push(25);break;case(25):pop(8);push(1);break;return p;7 软件的测试方法和测试结果运行界面及结果显示：语法分析过程中状态栈与符号栈情况：源文件：词法分析结果：三地址输出结果：8 研制报告通过本次的编译原理的课程设计，对于LR分析方法的思想和过程，我有了更加深刻更加全面的认识与理解。我认识到，对于大多数用无二义性的上下文无关文法描述的语言都可以用相应的LR分析器进行识别，这种方法不仅具有分析速度快，而且能准确、即使地指出出错的位置。当然通过这次课设我也明显的感觉到它有一个很明显的局限性：对于一个实用的高级语言程序，文法的分析器的构造工作量是相当大的。本次课程设计，对于自己定义的文法结构来构造分析表实现“WHILE循环语句的翻译程序设计”，确实是花了很多功夫。由于时间仓促，可能会有错误产生。另外，对于程序本身，由于自身水平所限，是存在着很大不足的。例如：在项目表实现时过于死板，不能够灵活的进行变动，给程序本身带来极大的局限性，希望以后加以改进。 除此以外，在本次课程设计的过程中我又巩固了一些C+编程方面的知识点。举一个例子来说，在主函数体内，我曾出现过一个错误，引用了getch（）函数但却忘记了声明conio.h头文件 ，从而导致编译出错。当然，最基本的还是对于数据结构中栈的应用，通过这次课程设计以及前两次课程实验，我深刻的认识到栈在语法语义分析中的重要性，在以后的学习中一定要加强这方面的学习。 总而言之，本次课程设计虽然存在很多不足与缺陷，但总体上达到了课程任务书对我的要求，也对我以前的各种知识体系做了很好的检测，也让我在实践中加深了对知识的理解，对我以后的学习有着很大的帮助。9 参考文献1张素琴、吕映芝、蒋维杜、戴桂兰等编译原理（第二版）清华大学出版社2005年2月2钱能著,C程序设计教程,北京：清华大学出版社，2002.73陈火旺主编程序设计语言编译原理（第3版）2000 国防工业出版社