《编译原理》实验指导书.doc

编译方法实验指导书柴本成 赵晨 编写浙江万里学院2010.01目 录实验一 有限自动机的构造与实现1实验二 词法分析器的设计3实验三 语法分析递归下降分析器5实验四 LL(1)文法预测分析表的实现6附 录9附录一 实验结果的提交与检查9附录二 实验报告参考格式9附录三 Visual C+上机环境简介10附录四 参考程序13I实验一 有限自动机的构造与实现一、 实验目的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、 写出从文件读入源代码，输出测试结果至文件保存。4、 书写实验报告；实验报告的格式可参见附录实验报告参考格式。实验二 词法分析器的设计一、 实验目的通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“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 2000/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;i=65&tmpStri=90)/不是大写字母(不是非终结符)for(j=0;jvtIndex;j+)if(tmpStri=VTSetj)break;if(j=vtIndex) /新的文法符号VTSetvtIndex=tmpStri;vtIndex+;i+;VTSetvtIndex=0;VNSetvnIndex=0;vtSetLen=vtIndex;vnSetLen=vnIndex;grammerNum=tmpIndex;/计算First集合void cal_first_set()int i,j,k;int* relationMatrix;int matrixSize;int vnIndex;int rowIndex,colIndex;matrixSize=vnSetLen+vtSetLen;relationMatrix=(int*)malloc(sizeof(int*)*matrixSize);for(i=0;imatrixSize;i+)relationMatrixi=(int*)malloc(sizeof(int)*matrixSize);if(relationMatrix=NULL)printf(in cal_first_set,mem apply failure.n);return;for(i=0;imatrixSize;i+)for(j=0;jmatrixSize;j+)relationMatrixij=0;/创建一个图vnIndex=0;for(i=0;iBeta , Beta是非终结符if(