编译原理试验参考指导书最终版.doc

编译办法实验指引书柴本成 赵晨 编写浙江万里学院.01目 录实验一 有限自动机构造与实现1实验二 词法分析器设计3实验三 语法分析递归下降分析器5实验四 LL(1)文法预测分析表实现6附 录9附录一 实验成果提交与检查9附录二 实验报告参照格式9附录三 Visual C+上机环境简介10附录四 参照程序13实验一 有限自动机构造与实现一、 实验目1、 对的理解正规式和正规集以及有限自动机定义；2、 纯熟掌握用状态转换图表达有限自动机办法。二、 实验预习提示1、 正规表达式就是一种形式化表达法，它可以表达单词符号构造，从而精准地定义单词符号集。正规表达式简称为正规式，它表达集合即为正规集。2、 状态转换图是一张当输入不同内容时选取不同分析途径有向图。一种状态转换图可用于辨认一定字符串。3、 有限自动机（FA）是更普通化状态转换图，可用来辨认正规集；分为DFA和NFA两种。三、 实验内容构造辨认如下字符串状态转换图，并将其编程实现。1、 辨认标记符(以字母开始由字母和数字构成字符串，规定长度不超过10)；参照程序：#include #include /字符串解决头文献/判断一种字符是不是字母bool Isletter(char ch)if(ch=a & ch=A & ch=0 & ch=9)return true;return false;/判断一种字符串是不是标记符bool IsId(char *str)if(!Isletter(str0)return false;int l=strlen(str);/计算字符串长度for(int i=1;il;i+)if(Isletter(stri) | IsDigit(stri)continue;/如果是字母或数字就继续循环elsereturn false;/否则，返回不是字符串return true;void main()char *str=1abc;/初始化字符串，也可键盘输入if(IsId(str)coutaccept!endl;else cout not accept!endl;2、 辨认实数(规定正负号可有可无，长度不超过20，不规定辨认用科学记数法表达实数)。3、 （选做）辨认实数（包括科学计数法）。四、 实验规定1、 编程语言可用C/C+中任意一种；2、 自行设计测试数据对程序进行测试，对输入字符串（以#作为结束符）如果能辨认，则显示“接受”，否则，显示“不接受”；3、 书写实验报告；实验报告格式可参见附录实验报告参照格式。实验二 词法分析器设计一、 实验目通过设计编制调试一种详细词法分析程序，加深对词法分析原理理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词词法分析办法。编制一种读单词过程，从输入源程序中，辨认出各个具备独立意义单词，即基本保存字、标记符、常数、运算符、分隔符五大类。并依次输出各个单词内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误某些继续显示）二、实验预习提示1. 词法分析器功能和输出格式词法分析器功能是输入源程序，输出单词符号。词法分析器单词符号经常表达到如下二元式(单词种别码，单词符号属性值)。本实验中，采用是一类符号一种别码方式。2. 单词BNF表达- -|- - |- +- - - =3. “超前搜索”办法词法分析时，经常会用到超前搜索办法。如当前待分析字符串为“a+”,当前字符为，此时，分析器究竟是将其分析为不不大于关系运算符还是不不大于等于关系运算符呢？显然，只有懂得下一种字符是什么才干下结论。于是分析器读入下一种字符+，这时可知应将解释为不不大于运算符。但此时，超前读了一种字符+，因此要回退一种字符，词法分析器才干正常运营。在分析标记符，无符号整数等时也有类似状况。三、实验过程和指引 （一）准备：1. 阅读课本关于章节，花一周时间明确语言语法，写出基本保存字、标记符、常数、运算符、分隔符和程序例。2. 初步编制好程序。3. 准备好多组测试数据。（二）上课上机：将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。（2，”main”）（5，”（“）（5，”）“）（5，”“）（1，”int”）（2，”a”）（5，”,”）（2，”b”）（5，”;”）（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;规定输出如右图。详细规定如下：1. 辨认保存字：if、int、for、while、do、return、break、continue等2. 其她都辨以为标记符；3. 常数为无符号整形数；4. 运算符涉及：+、-、*、/、=、=、TAA-+TAA-eT-FBB-*FBB-eF-(E)F-i2. 依照预测分析表，判断该文法与否为LL(1)文法。三、实验过程和指引对给定无左递归和无回溯上下文无关文法，按如下环节执行：1. 构造First集合对文法中每一种非终结符X构造FIRST(X)，其办法是持续使用下述规则，直到每个集合FIRST不再增大为止。(注：对终结符a而言，FIRST(a)=a，因而无需构造。)1) 若有产生式Xa，且aVT ，则把a加入到FIRST(X)中；若存在X，则将也加入到FIRST(X)中。2) 若有XY，且YVN，则将FIRST(Y)中所有非元素(记为“”)都加入到FIRST(X)中；若有XY1Y2Yk，且Y1Yi1都是非终结符，而Y1Yi1候选式均有存在，则把FIRST(Yj)所有非元素都加入到FIRST(X)中(j=1,2,i)；特别是当Y1Yk均具有产生式时，应把也加到FIRST(X)中。2. 构造FOLLOW集合对文法GS每个非终结符A构造FOLLOW(A)办法是持续使用下述规则，直到每个FOLLOW不再增大为止。1) 对文法开始符号S，置#于FOLLOW(S)中(由语句括号“#S#”中S#得到)。2) 若有AB(可为空)，则将FIRST()加入到FOLLOW(B)中。3) 若有AB或AB，且(即FIRST()，则把FOLLOW(A)加到FOLLOW(B)中(此处也可为空)。 3. 构造预测分析表M1) 对文法GS每个产生式A执行如下2)、3)步。2) 对每个终结符aFIRST(A)，把A加入到MA,a中，其中为具有首字符a候选式或为惟一候选式。3) 若FIRST(A),则对任何属于FOLLOW(A)终结符b，将A加入到MA,b中。4) 把所有无定义MA,a标记为“出错”。 4. 判断该文法与否为LL(1)文法若预测分析表M无多重定义，则该文法为LL(1)文法；否则，该文法不是LL(1)文法。四、实验提示1. 为了简化实验过程，咱们这里假定要分析文法都是无左递归；即咱们编程序时无需考虑文法与否左递归了。下面给出文法构造体和文法符号集合程序定义#define MAX_GRAM_LEN 255/文法符号最大长度#define MAX_ELE_NUM 40/文法符号最大个数#define MAX_GRAM_ELE_NUM 300/所有文法符号个数/-定义文法构造体 -typedef structchar mSetenceMAX_GRAM_LEN;grammerElement;grammerElement GrammerSetMAX_GRAM_ELE_NUM;/定义文法符号构造体typedef structint len;char eleMAX_ELE_NUM;simpleGroup;simpleGroup groupFirstMAX_ELE_NUM;/ First集simpleGroup groupFollowMAX_ELE_NUM;/ Follow集int grammerNum;/文法符号个数char VTSetMAX_ELE_NUM;/ 终结符char VNSetMAX_ELE_NUM;/ 非终结符int VNProduceZMAX_ELE_NUM;/ 产生式int vtSetLen;/终结符个数int vnSetLen;/非终结符个数char startedSign;/开始符号2. 为了便于分析程序，在实验中规定把分析文法保存在一种文本文献中，同步输出成果也保存在一种文本文献中。3. 在附录中，咱们给出了求First集参照程序。人们可以参照该程序，并在此基本上写出求Follow集以及构造分析表程序。附 录附录一 实验成果提交与检查1. 提交实验成果每个实验成果涉及两项：实验报告和程序源代码。实验报告中请写明姓名、班号、学号、Email等个人信息，以便遇到问题时教师可以及时与你联系。实验报告格式可参见实验报告参照格式，也可自行拟定报告格式，但规定实验报告中至少包括如下内容：实验题目及内容，所用状态转换图，重要数据构造设计，重要算法流程，核心代码段及注释，所用测试数据及测试成果，以及实验中遇到问题和解决办法。请把实验成果放入一种目录中，并将上述所有文献打包成rar文献，文献名为“自己学号.rar”，例如“01001.zip”，通过ftp或Email提交。2. 检查方式与评分原则在人们提交实验后，咱们将对提交程序进行测试。评分重要原则是实验报告以及程序输出与原则输出相符合限度。附录二 实验报告参照格式以实验二（词法分析器设计为例），实验报告格式如下：一、实验目与任务编制一种读单词过程，从输入源程序中，辨认出各个具备独立意义单词，即基本保存字、标记符、常数、运算符、分隔符五大类。并依次输出各个单词内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误某些继续显示）二、实验环节1. 仔细阅读实验规定和书上有关内容，写出基本保存字、标记符、常数、运算符、分隔符和要测试程序例。（在这里写出基本保存字、标记符、常数、运算符、分隔符和要测试程序实例）2. 程序功能描述。（在这里描述你程序功能）3. 程序模块描述。（在这里写出：重要全局变量及其用途，重要函数定义、功能、参数与返回值含义）4. 核心程序代码（在这里写出：实验中核心程序代码，不用把所有代码都写上）三、实验总结（可以从如下几种方面来总结：你在编程过程中花时多少？时间是怎么分派？多少时间在思考问题？遇到了哪些难题？你是怎么克服？你对你程序评价？你收获有哪些？）附录三 Visual C+上机环境简介上机实验环境亦可选取Microsoft Visual C+（如下简称VC）。VC是美国微软公司生产基于其Windows系统软件开发工具。它具备使用灵活，并与32位Windows内核（使用于Windows /Windows XP）高度兼容特点，从而被Windows程序员们广泛使用。同步，VC同样可以加工解决C语言程序，与原则ANSI C语言兼容。VC提供了一种控制台操作方式，初学者使用它应当从这里开始。下面咱们将对使用VC编写简朴控制台程序作一种最初步简介。一、控制台程序简介Win32控制台程序(Win32 Console Application)是一类Windows程序，它不使用复杂图形顾客界面，程序与顾客交互时通过一种原则正文窗口，通过几种原则输入输出流（I/O Streams）进行。它们分别是stdin（原则输入），stdout（原则输出）以及stderr（原则错误输出）。这些流都是ANSI C语言原则库提供，通过printf()等函数可以访问这些流。一种最简朴控制台程序如下：/* hello.c */#include/* 包括使用原则输入输出头文献声明 */int main()/* 主函数 */ printf(“Hello，World!n”);/* 向原则输出stdout输出一种字符串 */ return 0;/* 主函数返回 */该程序运营成果如图3-4所示。 图3-4 控制台程序运营成果图中显示黑色窗口称为控制台窗口，程序输入、输出均在这个窗口中进行。二、使用VC编写控制台程序很简朴，只需要按照下面几种环节进行：1. 打开MSVC集成开发环境。双击桌面或“开始”菜单中Microsoft Visual C+6.0，不久将看到VC编辑窗口，如图3-5：图3-5 VC启动界面2. 选取菜单“File | New”,在弹出对话框中 1) 单击上方选项卡“File”，2) 选取“C+ Source File”， 3) 在“File name”一栏中填写文献名例如hello.c，4) 在“Location”一栏中填写你想把文献存储位置（目录）。然后按“OK”。见图3-6。 注意： 第3）步中一定写明扩展名“.c”（不要用“.cpp”。那样VC将按C+方式编译，C+与C有某些不兼容性）； 第4）步中指定你自己目录，不要使用系统缺省目录或者随便放在根目录或者其她目录下。 图3-6 应用程序向导主界面3. 在右侧窗口中键入程序内容，然后点击图标存盘。进入VC编辑界面，如图3-7。图3-7 VC编辑界面4. 试编译。点击图标，或者选取菜单“Build | Build”（启动程序加工，这样系统将持续进行编译和连接操作。另一种更稳妥方式是先做编译，检查无误后再做连接）。这时VC将弹出一种对话窗口，阐明这个命令需要一种工程（Project），问：与否创立一种默认工程？点击“Yes”。如图3-8所示。 图3-8 与否创立一种工程5. 编辑器中编译窗口开始显示编译成果。如果显示“hello.exe - 0 error(s)，0 warning(s)”， 则表达编译已经通过！ 6. 点击快捷工具栏上红色感叹号（或者选取菜单“Build | Execute”或按Ctrl-F5），查看运营成果（VC将自动打开一种显示成果窗口，如上图3-4所示）。 三、如何调试程序运用VC编写程序，还需要学会如何调试程序。咱们都会发现，在编写较长程序时，可以一次成功而不具有任何错误决非易事（固然，勉励同窗们以此为目的，进行长期大量练习）。对于程序中错误，VC提供了易用且有效调试手段。在工具栏上单击鼠标右键，在弹出菜单中对“Debug”项打勾，发现如图3-9所示许多按钮。其中，较惯用工具备：单步跟踪进入子函数（Step Into），单步跟踪跳过子函数（Step Over），运营至当前函数末尾（Step Out）以及观测变量值（Watch）等，这些VC中惯用调试功能详见关于参照文献。图3-9 VC调试工具条附录四 参照程序1.词法分析器设计-参照程序/*cifa fenxi chengxu*/#include #include stdlib.h#include #define N 100/定义要分析标记符或常数最大个数#define M 20/标记符长度char *sourceFile=1.txt;/定义进行词法分析源文献char *key8=if,else,for,while,do,return,break,continue;/核心字char *border6=,;,(,);/界符定义char *arithmetic4=+,-,*,/;/算术运算符定义char *relation6=,=,；/关系运算符定义char *constsN;/常数定义char *labelN;/标记符int constnum=0,labelnum=0;/constnum-常数个数;labelnum-标记符个数/判断一种字符是不是字母int Isletter(char ch)if(ch=a & ch=A & ch=0 & ch=9)return 1;return 0;/判断单词符号类型int search(char searchchar,int wordtype)int i=0;switch (wordtype) 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)=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;ilabelnum;i+) if(labeli!=NULL) if (strcmp(labeli,searchchar)=0)/返回标记符 return(i+1); labeli-1=(char *)malloc(sizeof(searchchar);strcpy(labeli-1,searchchar);labelnum+;return(i); return -1;/标记符或核心字char alphaprocess(char buffer,FILE* fp)int atype;int i=-1;char alphatpM;while (Isletter(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);elseatype=search(alphatp,6);/输出标记符printf(%s (6,%d)n,alphatp,atype-1);return(buffer);/常数解决char digitprocess(char buffer,FILE* fp)int i=-1;char digittpM;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 otherprocess(char buffer,FILE* fp)int i=-1;char othertpM;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)printf(%s (4,%d)n,othertp,otypetp-1);goto out;elseothertp1=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 (buffer!=n)&(buffer!= ) printf(%c error,not a wordn,buffer); buffer=fgetc(fp);out： return(buffer);void main()int i;FILE *fp;/文献指针,指向要分析源程序char cbuffer;/保存最新读入字符for (i=0;i=N;i+)labeli=NULL;/初始化标记符constsi=NULL;/初始化常数;if (fp=fopen(sourceFile,rb)=NULL)/判断源文献与否存在printf(文献%s不存在,sourceFile);elsecbuffer = fgetc(fp);/读入字符while (cbuffer!=EOF)/如果文献没有结束,就始终循环if (Isletter(cbuffer)/若为字母cbuffer=alphaprocess(cbuffer,fp);else if (IsDigit(cbuffer)/若为数字cbuffer=digitprocess(cbuffer,fp);else cbuffer=otherprocess(cbuffer,fp);printf(overn);getchar();2. LL(1)文法预测分析表实现-参照程序/*程序阐明*grammer.txt用于输入相应文法，第一行字母表达起始字符。*/#include #include #include #define MAX_GRAM_LEN 255/文法符号最大长度#define MAX_ELE_NUM 40/文法符号最大个数#define MAX_GRAM_ELE_NUM 300/所有文法符号个数/-文献指针-FILE* grammerFile;char* grammerFileName=grammer.txt;/输入文法文献FILE* testFile;char* testFileName=outputData.txt;/输出文献/-文法构造体 -typedef structchar mSetenceMAX_GRAM_LEN;grammerElement;grammerElement GrammerSetMAX_GRAM_ELE_NUM;typedef structint len;char eleMAX_ELE_NUM;simpleGroup;simpleGroup groupFirstMAX_ELE_NUM;/ First集simpleGroup groupFollowMAX_ELE_NUM;/ Follow集int grammerNum;/文法符号个数char VTSetMAX_ELE_NUM;/ 终结符char VNSetMAX_ELE_NUM;/ 非终结符int VNProduceZMAX_ELE_NUM;/ 产生式int vtSetLen;int vnSetLen;char startedSign;/开始符号voidreadInGrammer();void cal_first_set();/计算First集void main()/一方面读入文法文献if(grammerFile=fopen(grammerFileName,rb)=NULL)printf(open file:grammerFile error.n);return;if(testFile=fopen(testFileName,wb)=NULL)printf(open file:testFile error.n);return;readInGrammer();/计算First集,Follow集cal_first_set();/GrammerSetcal_follow_set();/GrammerSetfclose(grammerFile);fclose(testFile);getchar();/从文献中读入文法void readInGrammer()char tmpChar;char tmpStrMAX_GRAM_LEN;int tmpIndex;int vtIndex,vnIndex;int i,j;tmpIndex=0;vtIndex=0;vnIndex=0;fscanf(grammerFile,%crn,&startedSign);while(!feof(grammerFile)if(fscanf(grammerFile,%c-%srn,&tmpChar,&tmpStr)!=2)break;GrammerSettmpIndex.mSetence0=tmpChar;GrammerSettmpIndex.mSetence1=0;strcat(GrammerSettmpIndex.mSetence,tmpStr);tmpIndex+;for(i=0;ivnIndex;i+)if(tmpChar=VNS