编译原理_上机指导.doc

《编译原理_上机指导.doc》由会员分享，可在线阅读，更多相关《编译原理_上机指导.doc（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验指导书 编译原理上机指导 前 言编译原理是计算机专业的重要专业课之一，主要介绍程序设计语言编译构造的基本原理和基本实现方法。由于这门课程相对抽象且内容复杂，一直是最难学的一门课程。编译原理是一门理论性和实践性较强的课程，在学习过程中，实验非常重要，只有通过上机实验，才能使学生对比较抽象的课程内容产生一个具体的感性认识。但是，目前国内市场上很少有较详细且比较适合我校实际的实验指导书。为此，我们特编了这份指导书，希望能对我校的编译原理教学工作有所帮助。由于这门课实验难度较大，所以希望任课教师在实验前安排好学生的预习工作。在上机前要求学生写好实验预习报告。本书中c程序均在Turbo c 下调试通

2、过。由于编者水平有限，本书中必然存在着不少缺点，在此恳请大家给予批评和指正，我们将尽力纠正。如对本书有批评指正，请Email至houhf72163 。在此特对关心支持编写本书的院系领导表示感谢。目 录实验一 源程序的输入和扫描 -1实验二词法分析 -2实验三递归下降分析法-8实验四LL（1）分析法-14实验五算符优先法处理算术表达式与赋值语句-19实验六逆波兰式的产生及计算-31实验七LR（1）分析法-36附录一 实验报告样例-41附录二 词法分析器生成工具FLEX简介-45附录三 语法分析器生成工具YACC简介-513实验指导书 实验一 源程序的输入和扫描一、实验目的：编制一个源程序的输入过

3、程，从键盘、文件或文本框输入若干行语句，依次存入输入缓冲区（字符型数据）；并编制一个扫描子程序，该子程序中每次调用能依次从存放源程序的输入缓冲区中读出一个有效字符。二、估计实验时间：1.课余准备2小时以上；2.上机一次2小时；3.完成实验报告2小时。三、实验过程和指导：（一）准备：确定开发工具，如TC、VC、VC+、Delphi等；花一周时间熟悉开发工具。花一周时间确定被处理的语言的语法特点（初步确定，也可使用现成语言如Pascal、C等）。写好实验报告，编好程序。（二）上机：安装所需的开发工具，输入或拷贝程序，调试。1.主程序的部分伪代码：从输入设备接收所有输入到缓冲区While 读入一字符

4、成功显示该字符end while2.读入一字符的部分伪代码：if 缓冲区非空 then读出该字符改变缓冲区指针返回该字符else返回结束标记end if（三）程序要求：如源程序为C语言。输入如下一段：main()int a,b ,c;a = 10; b=20; c=a+b;要求输出与输入相同。要点：读字符的子程序作为单独一个过程（函数），每调用它一次只返回缓冲区里的一个字符，主程序连续调用它就得到完整的输出。（见右图）（四）练习该实验的目的和思路：1.程序非常简单，但要明白该程序的作用，为什么要设计成独立的子函数？要将它和在以后的实验中进行比较，可得出这样处理的目的。2.通过练习，掌握字符处理

5、的方法。四、实验报告要求：1.写出编程思路、源代码；2.写出上机调试时发现的问题，以及解决的过程；3.写出你所使用的测试数据；4.谈谈你的体会。五、上交：1.实验报告；2.程序源文件（通过网络提交）。实验二 词法分析一、实验目的：通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）二、

6、实验预习提示1、 词法分析器的功能和输出格式词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码，单词符号的属性值)。本实验中，采用的是一类符号一种别码的方式。2、 单词的BNF表示- -|- - |- +- - - =3、“超前搜索”方法词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a+”,当前字符为，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符+，这时可知应将解释为大于运算符。但此时，超前读了一个字符+，所以要回退一个字符，词法分析器才能正常运

7、行。在分析标识符，无符号整数等时也有类似情况。4、模块结构缓冲区扫描一个字符主函数main()N输入文件名，判断能否打开文件Y缓冲区中是否还有字符Y结束取单词扫描一个字符调用返回输出N三、实验过程和指导：（一）准备：1.阅读课本有关章节，明确语言的语法，写出基本保留字、标识符、常数、运算符、分隔符和程序例。2.初步编制好程序。3.准备好多组测试数据。（二）上课上机：将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。（三）程序要求：程序输入/输出示例：（2，”main”）（5，”（“）（5，”）“）（5，”“）（1，”int”）（2，”a”）（5，”,”）（2，”b”）（5，”;

8、”）（2，”a”）（4，”=”）（3，”10”）（5，”;”）（2，”b”）（4，”=”）（2，”a”）（4，”+”）（3，”20”）（5，”;”）（5，”“）如源程序为C语言。输入如下一段：main()int a,b;a = 10; b = a + 20;要求输出如右图。要求：识别保留字：if、int、for、while、do、return、break、continue；单词种别码为1。其他的都识别为标识符；单词种别码为2。常数为无符号整形数；单词种别码为3。运算符包括：+、-、*、/、=、=、=、!= ；单词种别码为4。分隔符包括：,、;、(、)； 单词种别码为5。以上为参考，具体可自行增

9、删。（四）程序思路（仅供参考）：这里以开始定义的C语言子集的源程序作为词法分析程序的输入数据。在词法分析中，自文件头开始扫描源程序字符，一旦发现符合“单词”定义的源程序字符串时，将它翻译成固定长度的单词内部表示，并查填适当的信息表。经过词法分析后，源程序字符串（源程序的外部表示）被翻译成具有等长信息的单词串（源程序的内部表示），并产生两个表格：常数表和标识符表，它们分别包含了源程序中的所有常数和所有标识符。0.定义部分：定义常量、变量、数据结构。1.初始化：从文件将源程序全部输入到字符缓冲区中。2.取单词前：去掉多余空白。3.取单词后：去掉多余空白（可选，看着办）。4.取单词：利用实验一的成果

10、读出单词的每一个字符，组成单词，分析类型。（关键是如何判断取单词结束？取到的单词是什么类型的单词？）5.显示结果。（五）练习该实验的目的和思路：程序开始变得复杂起来，可能是大家目前编过的程序中最复杂的，但相对于以后的程序来说还是简单的。因此要认真把握这个过渡期的练习。本实验和以后的实验相关。通过练习，掌握对字符进行灵活处理的方法。（六）为了能设计好程序，注意以下事情：1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。四、上交：1.程序源代码

11、（上交软盘）；2.已经测试通过的测试数据3组；3.实验报告：实验名称实验目的和要求（一）实验内容（1）功能描述：该程序具有什么功能？（2）程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数之间的调用关系图。（3）程序总体执行流程图（二）实验过程记录：出错次数、出错严重程度、解决办法摘要。（三）实验总结：你在编程过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的程序的评价？你的收获有哪些？五、参考源程序：实验一（词法分析）源代码如下：/*cifa fenxi chengxu*/#include #include

12、#include #include #include #define NULL 0FILE *fp;char cbuffer;char *key8=if,else,for,while,do,return,break,continue;char *border6=,;,(,);char *arithmetic4=+,-,*,/;char *relation6=,=,;char *consts20;char *label20;int constnum=0,labelnum=0;int search(char searchchar,int wordtype) int i=0; switch (wor

13、dtype) case 1:for (i=0;i=7;i+) if (strcmp(keyi,searchchar)=0) return(i+1); case 2:for (i=0;i=5;i+) if (strcmp(borderi,searchchar)=0) return(i+1); return(0); case 3:for (i=0;i=3;i+) if (strcmp(arithmetici,searchchar)=0) return(i+1); return(0); case 4:for (i=0;i=5;i+) if (strcmp(relationi,searchchar)=

14、0) return(i+1); return(0); case 5:for (i=0;i=constnum;i+) if (strcmp(constsi,searchchar)=0) return(i+1); constsi-1=(char *)malloc(sizeof(searchchar); strcpy(constsi-1,searchchar); constnum+; return(i); case 6:for (i=0;i=labelnum;i+) if (strcmp(labeli,searchchar)=0) return(i+1); labeli-1=(char *)mall

15、oc(sizeof(searchchar); strcpy(labeli-1,searchchar); labelnum+; return(i); char alphaprocess(char buffer) int atype; int i=-1; char alphatp20; while (isalpha(buffer)|(isdigit(buffer) alphatp+i=buffer; buffer=fgetc(fp); alphatpi+1=0; if (atype=search(alphatp,1) printf(%s (1,%d)n,alphatp,atype-1); else

16、 atype=search(alphatp,6); printf(%s (6,%d)n,alphatp,atype-1); return(buffer);char digitprocess(char buffer) int i=-1; char digittp20; int dtype; while (isdigit(buffer) digittp+i=buffer; buffer=fgetc(fp); digittpi+1=0; dtype=search(digittp,5); printf(%s (5,%d)n,digittp,dtype-1); return(buffer);char o

17、therprocess(char buffer) int i=-1; char othertp20; int otype,otypetp; othertp0=buffer; othertp1=0; if (otype=search(othertp,3) printf(%s (3,%d)n,othertp,otype-1); buffer=fgetc(fp); goto out; if (otype=search(othertp,4) buffer=fgetc(fp); othertp1=buffer; othertp2=0; if (otypetp=search(othertp,4) prin

18、tf(%s (4,%d)n,othertp,otypetp-1); goto out; else othertp1=0; printf(%s (4,%d)n,othertp,otype-1); goto out; if (buffer=:) buffer=fgetc(fp); if (buffer=) printf(:= (2,2)n); buffer=fgetc(fp); goto out; else if (otype=search(othertp,2) printf(%s (2,%d)n,othertp,otype-1); buffer=fgetc(fp); goto out; if (

19、buffer!=n)&(buffer!= ) printf(%c error,not a wordn,buffer); buffer=fgetc(fp);out: return(buffer);void main() int i; for (i=0;iu1|u2|un处理的方法如下：U( )ch=当前符号;if(ch可能是u1字的开头) 处理u1的程序部分;else if(ch可能是u2字的开头)处理u2的程序部分;else error() （2）对于每个右部u1-x1x2xn的处理架构如下：处理x1的程序；处理x2的程序； 处理xn的程序；（3）如果右部为空，则不处理。（4）对于右部中的每个

20、符号xi如果xi为终结符号：if(xi= = 当前的符号) NextChar()； return; else出错处理如果xi为非终结符号，直接调用相应的过程xi()说明： NextChar为前进一个字符函数。四、实验过程和指导：（一）准备：1.阅读课本有关章节，2.考虑好设计方案；3.设计出模块结构、测试数据，初步编制好程序。（二）上课上机：将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。（三）程序要求：程序输入/输出示例：对下列文法，用递归下降分析法对任意输入的符号串进行分析：（1）E-TG（2）G-+TG|TG （3）G-（4）T-FS（5）S-*FS|/FS（6）S-（

21、7）F-(E)（8）F-i输出的格式如下：(1)递归下降分析程序，编制人：姓名，学号，班级(2)输入一以#结束的符号串(包括+*/（）i#)：在此位置输入符号串例如：i+i*i#(3)输出结果：i+i*i#为合法符号串备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。引用也要改变）。注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符I，结束符#；2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；3.对学有余力的同学，可以详细的输出推导的过程，即详细列出每一步使用的产生式。（四）程序思路（仅供参考）：0.定义部分：定义常量、变量、数据结构。1.初始化：从

22、文件将输入符号串输入到字符缓冲区中。2.利用递归下降分析法分析，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。（五）练习该实验的目的和思路：程序开始变得复杂起来，需要利用到程序设计语言的知识和大量编程技巧，递归下降分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调用的方法。（六）为了能设计好程序，注意以下事情：1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。五、上交：1.程序源代码（上交

23、软盘）；2.已经测试通过的测试数据3组；3.实验报告：实验名称实验目的和要求（一）实验内容（1）功能描述：该程序具有什么功能？（2）程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数之间的调用关系图。（3）程序总体执行流程图（二）实验过程记录：出错次数、出错严重程度、解决办法摘要。（三）实验总结：你在编程过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的程序的评价？你的收获有哪些？六、参考源程序：#include #include#include#includechar a50 ,b50,d200,e10;ch

24、ar ch;int n1,i1=0,flag=1,n=5;int E();int E1();int T();int G();int S();int F();void input();void input1();void output();void main() /*递归分析*/int f,p,j=0;char x; d0=E; d1=; d2=; d3=T; d4=G; d5=#;printf(请输入字符串(长度TGt); flag=1;input();input1();f=T();if (f=0) return(0);t=G();if (t=0) return(0);else return(

25、1);int E() int f,t;printf(E-TGt); e0=E;e1=;e2=;e3=T;e4=G;e5=#;output();flag=1;input();input1();f=T();if (f=0) return(0);t=G();if (t=0) return(0);else return(1);int T() int f,t;printf(T-FSt);e0=T;e1=;e2=;e3=F;e4=S;e5=#; output();flag=1;input();input1();f=F();if (f=0) return(0);t=S(); if (t=0) return(

26、0);else return(1);int G() int f;if(ch=+) bi1=ch;printf(G-+TGt); e0=G;e1=;e2=;e3=+;e4=T;e5=G;e6=#;output(); flag=0;input();input1();ch=a+i1;f=T();if (f=0) return(0);G();return(1);printf(G-t);e0=G;e1=;e2=;e3=;e4=#;output();flag=1; input();input1();return(1);int S()int f,t;if(ch=*) bi1=ch;printf(S-*FSt

27、); e0=S;e1=;e2=;e3=*;e4=F;e5=S;e6=#;output();flag=0;input();input1();ch=a+i1;f=F();if (f=0) return(0);t=S();if (t=0) return(0);else return(1);printf(S-t);e0=S;e1=;e2=;e3=;e4=#;output();flag=1; ai1=ch;input();input1();return(1);int F() int f;if(ch=() bi1=ch;printf(F-(E)t);e0=F;e1=;e2=;e3=(;e4=E;e5=);

28、e6=#;output();flag=0;input();input1();ch=a+i1;f=E();if (f=0) return(0);if(ch=) bi1=ch;printf(F-(E)t); flag=0;input();input1(); ch=a+i1; else printf(errorn); return(0); else if(ch=i) bi1=ch;printf(F-it);e0=F;e1=;e2=;e3=i;e4=#;output();flag=0;input();input1();ch=a+i1; else printf(errorn);return(0); re

29、turn(1);void input() int j=0; for (;j=i1-flag;j+) printf(%c,bj); /*输出分析串*/ printf(tt); printf(%ctt,ch); /*输出分析字符*/ void input1() int j; for (j=i1+1-flag;j;dn+2=#;n=n+2;i=n;i=i-2;while(di!=&i!=0) i=i-1;i=i+1;while(di!=e0) i=i+1;q=i;m=q;k=q;while(dm!=) m=m-1;m=m+1;while(m!=q) dn=dm;m=m+1;n=n+1;dn=#; f

30、or(j=3;ej!=#;j+)dn=ej;n=n+1;k=k+1;while(dk!=) dn=dk;n=n+1;k=k+1;dn=#;实验四 LL(1)分析法一、实验目的：根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。二、实验预习提示1、LL（1）分析法的功能LL（1）分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程。2、LL（1）分析法的前提改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法，XVN#S进栈，当前输入

31、符送a上托栈顶符号放入X若产生式为X X1X2Xn按逆序即XnX2X1入栈出错X=#XVTX=aMX,a是产生式吗出错X=a读入下一个符号结束是是是是否否否否否是3、LL（1）分析法实验设计思想及算法三、实验过程和指导：（一）准备：1.阅读课本有关章节，2.考虑好设计方案；3.设计出模块结构、测试数据，初步编制好程序。（二）上课上机：将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。（三）程序要求：程序输入/输出示例：对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E-TG（2）G-+TG|TG （3）G-（4）T-FS（5）S-*FS|/FS（6）S-（7）F-(E)（8）F-i输出的格式如下：(1)LL（1）分析程序，编制人：姓名，学号，班级(2)输入一以#结束的符号串(包括+*/（）i#)：在此位置输入符号串(3)输出过程如下：步骤分析栈剩余输入串所用产生式1Ei+i*i#E-TG(4)输入符号串为非法符号串(或者为合法符号串)备注：(1)在“所用产生式”一列中如果对应有推导则写出所用产生式；如果为匹配终结符则写明匹配的终结符；如分析异常出错则写为“分析出错”；若成功结束则写为“分析成功”。(2) 在此位置输入符