编译原理课程设教案.doc

黄冈师范学院 《编译原理课程设计》教案 （2011·春） 授 课 教 师： 张 瑞 红 授 课 班 级： 计科2008级 授 课 时 间： 2010-2011 二 课题一 有限自动机的运行设计题目：有限自动机的运行 设计目的：1、理解有限自动机的作用 2、利用转态图和状态表表示有限自动机 3、以程序实现有限自动机的运行过程 设计内容：（注：题目详细要求） 利用状态表和有限自动机的运行原理编制程序，使得程序能够识别一个输入串是否为一个有效的符号串，具体可以选择下面之一：无符号定点实数、自然数、整数、十六进制数或其它自己定义的符号串。 设计思想：（注：算法思想、程序流程图、不要写代码） 本程序实现对无符号定点实数的判断，正确接受，否则不接受。 本程序的关键在状态表和缓冲区的运用。首先定义了一个布尔型函数然后定义了?和实现对输入字符串的正确性判断，更改Run函数可以改变程序功能：如 ?程序流程图如下： 五、运行结果与数据分析： 六、设计体会： 通过这次课程设计，我对程序的编译和运行过程有了更进一步的了解，对程序的底层设计、代码优化也有了初步的认识，而且知道了如何从根本上来提高程序运行的速度。 附录：（完整代码） #include?stdio.h #include?string.h //状态表相关存储信息： #define?STATE_NUMBER?4????//状态数目 #define?CHAR_NUMBER?2????//输入字符的种类:?d?和?. #define?DIGIT?0????//输入数字在状态表中位于第0列 //State[][]为状态表，以整数组形式存放，0,1,2,3表示状态，-1表示没有此状态 int?State[STATE_NUMBER][CHAR_NUMBER]=????{{1,-1},{1,2},?{3,-1},?{3,-1}}; int?Q[STATE_NUMBER]?=?{0,1,0,1};????//终态标志：0非终态，1终态。 //缓冲区： //输入缓冲区：由专门函数操作（ReadALine(),GetChar()） #define?BUFFER_SIZE?1000????//表达式缓冲区大小 char?Buffer[BUFFER_SIZE];????//表达式缓冲区，以\0表示结束 int?ipBuffer?=?0;????????//表达式缓冲区当前位置序号 char?ch;????//存放取得的一个字符 //函数声明： bool?Run();????//对存储在缓冲区的一行字符串（以#结束）进行运行 void?Init();????//全局初始化 bool?ReadALine();????//从键盘读一行（没有空格），存于表达式缓冲区Buffer[]中 char?GetChar();?//从缓冲区取一个字符，返回该字符的同时将它存于全局变量ch中 //主程序： void?main() {???Init(); ????while(ReadALine())?//读一行成功，对它进行判断 ????{????????if(Run())?//对该行进行运行，看是否能被接受？ ????????????printf(接受\n\n); ????????else????????????printf(不接受\n\n); ????} } //对存储在缓冲区的一行字符串（以#结束）进行运行 //返回：如果是无符号定点实数，返回true；否则返回：false bool?Run() {??int?S=0;?//S存放运行时的当前状态，目前为初态 ????while(GetChar()!=#) ????{???if(ch?=?0ch=9)? ????????????S?=?State[S][DIGIT];?//将状态转换成输入后的状态 ????????else?//其他都为非法字符 ????????????return?false; ????????if(S?==?-1)?//处于非法状态 ????????????return?false; ????} ????//运行结束，判断S是否为终态 ????if(Q[S]?==?1)?//终态 ????????return?true; ????else?//非终态 ????????return?false; } //全局初始化 void?Init() {???//好像无需初始化 ????printf(程序功能：输入一个字符串，判断它是否是a。\n); ????printf(======================================================\n\n); } //从键盘读一行（没有空格），存于表达式缓冲区Bu