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

1、附件1：学 号： 课 程 设 计题 目while循环语句的翻译程序设计学 院计算机科学与技术学院专 业计算机科学与技术班 级计算机0702姓 名指导教师 2010年1月8日课程设计任务书学生姓名： 专业班级： 计算机0702班 指导教师： 工作单位：计算机科学与技术学院 题目: while循环语句的翻译程序设计（lr方法、输出三地址表示） 初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法

2、及属性文法。（2） 完成题目要求的中间代码三地址表示的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按

3、公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名： 2009年 11月 23日系主任（或责任教师）签名： 2009年 11月 23日1.系统描述 自定义while循环句型的文法及其属性文法，并用lr法为该文法设计、编制、调试一个语法及语义分析程序，并在过程中实现词法分析、语法分析，最终以三地址码的形式将形成的中间代码输出。2.文法及属性文法的描述21 文法的描述该文法的产生式如下所示：s

4、-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-

5、 =| 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分析法

6、正是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输入串的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=

7、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 （接受）表明当前的输入串已被成功地分析完毕，应停止分

8、析器的工作。（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|w (a)b;a-cdcc-a|bi4: c- a|bi6: s-w (b)ei5: a-cdcd-|cdcc- a|bi20: e-efee-(e)e-efee-a|bi14: b

9、-a=ee-(e)e-efee-a|bi21: e-efei22: e- (e)i13: b-a=ei16: e-efef-+|-|*|/ i15: b-a=ei18: e-a|bi17: e- (e)e-(e)e-efee-a|bsw(a|bb;e;（=efcai8: a-cdci0: s-ss -w(a)b;i2: s-w (a)b;i1:s-si9: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分析表的a

10、ction部分状态w（）；as流程图如下：5.2 语法分析语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。流程图如下：输入串#cic1sp#xisi总 控 程 序输出action表goto表栈结束其中sp为栈顶指针，si为状态栈，xi为文法符号栈。状态转换表内容按关系gotosi,x=sj确定，改关系式是指当前栈顶状态为si遇到当前文法符号为x时应转向状态sj。x为终结符或非终结符。5.3 语法制导翻译在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译。属性文法的每个符

11、号有属性，所以每个符号入栈时，必须连属性一起入栈，这样，栈符号就由文法符号及存放该符号属性的域所组成。由于属性类型不同，属性域存放的内容就要根据属性的类型来定。有的可能直接存放属性值，也有的存放的是指向属性值的指针。对于综合属性，其属性域不存放其属性值，而是存放一个指针，指向存贮该属性值的单元。对于继承属性，其属性域直接保存其属性值。继承属性的属性域刚入栈时为空，但是在该栈符号变成栈顶符号之前的某一时刻，它们必须接受相应的属性值，即在成为栈顶时，继承属性的属性域必须有值。6 详细的算法描述主要是词法分析与lr语法分析部分（包含主体程序干，对于调用的函数略去）词法分析主体：int cifa()o

12、fstream 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;i20;i+)temp1i=0;/temp1用来记录非符号串且初始值均置空char temp2;i=0;while(!fin.eof()&temp2!=)fin.get(temp2);if(isfuhao(temp2)/当读入的是符号时，分

13、析temp1 if(temp10!=0) analysis(temp1);fuhao(temp2);/判断是那种符号i=0; for(int i=0;i20;i+) temp1i=0;/temp1置空elsetemp1i=temp2;i+; fin.close();cout文件 词法分析 导入完成！endl;cout是否转化为含有双符号的词法分析文件？(yes-1,no-0)i;if(i)change();cout文件 词法分析2 已导入完成！n;zhuangtai *temp;temp=top;while(temp!=null)coutnnext;coutnow analysis ww,wh

14、ile)=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,:运算符)=

15、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,:为

16、标示符)=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);b

17、reak;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

18、(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(

19、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

20、);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

21、&(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 软件的测试方法和测试结果运行界面及结果显示：语法分析过程中状态栈与符号栈情况：源文件：词法分析结果：三地址输出