《编译原理》实验指导书-最终版

《编译原理》实验指导书-最终版《编译原理》实验指导书-最终版《编译原理》实验指导书-最终版《编译原理》实验指导书-最终版编制仅供参考审核批准生效日期地址：电话：传真:邮编:编译方法实验指导书柴本成赵晨编写浙江万里学院目录实验一有限自动机的构造与实现 1实验二词法分析器的设计 3实验三语法分析－递归下降分析器 5实验四LL(1)文法预测分析表的实现 6附录 9附录一实验结果的提交与检查 9附录二实验报告参考格式 9附录三VisualC++上机环境简介 10附录四参考程序 13实验一有限自动机的构造与实现实验目的正确理解正规式和正规集以及有限自动机的定义；熟练掌握用状态转换图表示有限自动机的方法。实验预习提示正规表达式就是一种形式化的表示法，它可以表示单词符号的结构，从而精确地定义单词符号集。正规表达式简称为正规式，它表示的集合即为正规集。状态转换图是一张当输入不同内容时选择不同分析路径的有向图。一个状态转换图可用于识别一定的字符串。有限自动机（FA）是更一般化的状态转换图，可用来识别正规集；分为DFA和NFA两种。实验内容构造识别如下字符串的状态转换图，并将其编程实现。识别标识符(以字母开始由字母和数字构成的字符串，要求长度不超过10)；参考程序：#include<> #include<> （2，”main”）（5，”（“）（5，”）“）（5，”{“）（1，”int（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，”}“）检查方式与评分标准在大家提交实验后，我们将对提交的程序进行测试。评分的主要标准是实验报告以及程序输出与标准输出相符合的程度。附录二实验报告参考格式 以实验二（词法分析器的设计为例），实验报告格式如下：一、实验目的与任务编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）二、实验步骤仔细阅读实验要求和书上的相关内容，写出基本保留字、标识符、常数、运算符、分隔符和要测试的程序例。（在这里写出基本保留字、标识符、常数、运算符、分隔符和要测试的程序实例）程序的功能描述。（在这里描述你的程序的功能）程序的模块描述。（在这里写出：重要的全局变量及其用途，主要函数的定义、功能、参数与返回值的含义）关键程序代码（在这里写出：实验中关键的程序代码，不用把所有代码都写上）三、实验总结（可以从以下几个方面来总结：你在编程过程中花时多少时间是怎么分配的多少时间在思考问题遇到了哪些难题你是怎么克服的你对你的程序的评价你的收获有哪些）附录三VisualC++上机环境简介 上机实验环境亦可选择MicrosoftVisualC++（以下简称VC）。VC是美国微软公司生产的基于其Windows系统的软件开发工具。它具有使用灵活，并与32位Windows内核（使用于Windows2000/WindowsXP）高度兼容的特点，从而被Windows程序员们广泛使用。同时，VC同样可以加工处理C语言程序，与标准的ANSIC语言兼容。VC提供了一种控制台操作方式，初学者使用它应该从这里开始。下面我们将对使用VC编写简单的控制台程序作一个最初步的介绍。一、控制台程序简介Win32控制台程序(Win32ConsoleApplication)是一类Windows程序，它不使用复杂的图形用户界面，程序与用户交互时通过一个标准的正文窗口，通过几个标准的输入输出流（I/OStreams）进行。它们分别是stdin（标准输入），stdout（标准输出）以及stderr（标准错误输出）。这些流都是ANSIC语言标准库提供的，通过printf(…)等函数可以访问这些流。一个最简单的控制台程序如下：/**/#include<>/*包含使用标准输入输出的头文件声明*/intmain()/*主函数*/{printf(“Hello,World!\n”);/*向标准输出stdout输出一个字符串*/return0;/*主函数返回*/}该程序的运行结果如图3-4所示。?图3-4控制台程序运行结果图中显示的黑色窗口称为控制台窗口，程序的输入、输出均在这个窗口中进行。二、使用VC编写控制台程序很简单，只需要按照下面几个步骤进行：打开MSVC集成开发环境。双击桌面或“开始”菜单中的MicrosoftVisualC++，不久将看到VC的编辑窗口，如图3-5：图3-5VC启动界面选择菜单“File|New”,在弹出的对话框中单击上方的选项卡“File”，选择“C++SourceFile”，在“Filename”一栏中填写文件名例如，在“Location”一栏中填写你想把文件存放的位置（目录）。然后按“OK”。见图3-6。注意：第3）步中一定写明扩展名“.c”（不要用“.cpp”。那样VC将按C++的方式编译，C++与C有一些的不兼容性）；第4）步中指定你自己的目录，不要使用系统的缺省目录或者随便放在根目录或者其他的目录下。图3-6应用程序向导主界面在右侧的窗口中键入程序的内容，然后点击图标存盘。进入VC编辑界面，如图3-7。图3-7VC编辑界面试编译。点击图标，或者选择菜单“Build|Build”（启动程序加工，这样系统将连续进行编译和连接操作。另一种更稳妥的方式是先做编译，检查无误后再做连接）。这时VC将弹出一个对话窗口，说明这个命令需要一个工程（Project），问：是否创建一个默认的工程点击“Yes”。如图3-8所示。图3-8是否创建一个工程编辑器中编译窗口开始显示编译的结果。如果显示“--0error(s),0warning(s)”，则表示编译已经通过！点击快捷工具栏上的红色的感叹号（或者选择菜单“Build|Execute”或按Ctrl-F5），查看运行结果（VC将自动打开一个显示结果的窗口，如上图3-4所示）。三、如何调试程序利用VC编写程序，还需要学会如何调试程序。我们都会发现，在编写较长的程序时，能够一次成功而不含有任何错误决非易事（当然，鼓励同学们以此为目标，进行长期大量的练习）。对于程序中的错误，VC提供了易用且有效的调试手段。在工具栏上单击鼠标右键，在弹出的菜单中对“Debug”项打勾，发现如图3-9所示的许多按钮。其中，较常用的工具有：单步跟踪进入子函数（StepInto），单步跟踪跳过子函数（StepOver），运行至当前函数的末尾（StepOut）以及观察变量的值（Watch）等，这些VC中常用的调试功能详见有关参考文献。图3-9VC调试工具条附录四参考程序1.词法分析器的设计-参考程序/*cifafenxichengxu*/#include<>#include""#include<>#defineN100 LL(1)文法预测分析表的实现-参考程序/************************程序说明*********************************用于输入相应的文法，第一行字母表示起始字符。****************************************************************/#include<>#include<>#include<>#defineMAX_GRAM_LEN255 n"); return; } if((testFile=fopen(testFileName,"wb"))==NULL) { printf("openfile:testFileerror.\n"); return; } readInGrammer(); Setence[0]=tmpChar; GrammerSet[tmpIndex].mSetence[1]='\0'; strcat(GrammerSet[tmpIndex].mSetence,tmpStr); tmpIndex++; for(i=0;i<vnIndex;i++) if(tmpChar==VNSet[i]) break; if(i==vnIndex) n"); return; } for(i=0;i<matrixSize;i++) for(j=0;j<matrixSize;j++) relationMatrix[i][j]=0; Setence[0]!=VNSet[vnIndex]) vnIndex++; j=1; while(GrammerSet[i].mSetence[j]!='\0') {Setence[j]>=65&&GrammerSet[i].mSetence[j]<=90) { for(k=0;k<vnSetLen;k++)Setence[j]) break; n"); return; } colIndex=k; rowIndex=vnIndex; relationMatrix[rowIndex][colIndex]=1; if(VNProduceZ[k]) Setence[j]) break; n"); return; } if(VTSet[k]=='z') { gotofir_cond1; } else { colIndex=vnSetLen+k; rowIndex=vnIndex; relationMatrix[rowIndex][colIndex]=1; gotofir_cond2; } }fir_cond1: j++; }fir_cond2:; } en=0; for(j=vnSetLen;j<matrixSize;j++) { if(VTSet[j-vnSetLen]!='z'&&relationMatrix[i][j]==1) { groupFirst[i].ele[groupFirst[i].len]=VTSet[j-vnSetLen]; groupFirst[i].len++; } } if(VNProduceZ[i]==1) { groupFirst[i].ele[groupFirst[i].len]='z'; groupFirst[i].len++; } } en;j++) { printf("%c,",groupFirst[i].ele