搜索
1编译原理课程设计设计题目：有限自动机的运行年级：计062姓名：黄思铭学号：200600401062日期：2010-5-18指导教师:陈望明广西工学院计算机工程系2设计目的：1、理解有限自动机的作用2、利用转态图和状态表表示有限自动机3、以程序实现有限自动机的运行过程设计内容：（注：题目详细要求）利用状态表和有限自动机的运行原理编制程序，使得程序能够识别一个输入串是否为一个有效的符号串，具体可以选择下面之一：无符号定点实数、自然数、整数、十六进制数或其它自己定义的符号串。一、分析原理词法分析：就是从左至右逐个字符地对源程序进行扫描，产生单词序列，用以语法分析。在这里，我们先把文法转换成有穷自动机，然后构造出状态表，再由状态表构造出程序。二、分析的算法将G[无符号数]文法转换成有穷自动机：构造状态矩阵；将有穷自动机的状S1S2……Sn及输入的字a1a2……am构成一个n*m的矩阵。输入状态d.eε+/-01241124Z23334Z34655666ZZ再写一个程序，把状态矩阵用二维数组表示。程序通过输入的字符转换状态，从而可以识别出单词。本程序的关键在状态表和缓冲区的运用。首先定义了一个布尔型函数ReadALine把输入的字符串送到缓冲区中；然后定义了布尔型函数Run和Getchar实现对输入字符串的正确性判断，更改Run函数可以改变程序功能：如可将状态表改变成识别“偶数”的有限自动机的状态表。三、程序流程图开始初始化输入句子判断是否退出标志判断是否被接受？接受不接受输出错误位置NYNY结束4四、课程设计出现的问题及解决的方法刚开始写该程序时，虽然感觉个人的编程能力不错，但由于对编译原理的自动机的实现掌握不足，难以入手。但经过对问题的更深入了解和分析，再通过网上和书本的资料的细读，最后终于把程序编写出来了。程序中，碰到的最大的问题就是状态表的构造和如何把它转变为一个程序的实现过程。解决的方法当然是看书。五、课程设计的体会首先，题目给出的文法是有小毛病的。我个人认为无符号数不可能推出.十进制数或者e指数部分的。在写这个程序是只要对编译原理书本词法分析分析很熟悉就可以比较容易地写出该程序。通过这次课程设计，我对程序的编译和运行有了更进一步的了解，更好地掌握了编译原理的词法分析过程。六、程序清单#includestdio.h//引入基本的库函数#includestring.h//引入字符串的库函数//状态表相关存储信息：#defineSTATE_NUMBER7//状态数目#defineCHAR_NUMBER4//输入字符的种类:.;d;e/E;+/-#defineDOT0//输入数字在状态表中位于第0列#defineDIGIT1//小数点位于状态表的第1列#defineE2//E位于状态表的第2列#defineAD3//+/-运算符位于状态表的第3列//State[][]为状态表，以整数组形式存放，0,1,2,3,4,5,6表示状态，-1表示没有此状态intState[STATE_NUMBER][CHAR_NUMBER]={{1,2,3,-1},{-1,4,-1,-1},{1,2,3,-1},{-1,5,-1,6},{-1,4,3,-1},{-1,5,-1,-1},{-1,5,-1,-1}};intQ[STATE_NUMBER]={0,0,1,0,1,1,0};//终态标志：0非终态，1终态。5intindex=0;//错误坐标//缓冲区：//输入缓冲区：由专门函数操作（ReadALine(),GetChar()）#defineBUFFER_SIZE1000//表达式缓冲区大小charBuffer[BUFFER_SIZE];//表达式缓冲区，以'\0'表示结束intipBuffer=0;//表达式缓冲区当前位置序号charch;//存放取得的一个字符//函数声明：intRun();//对存储在缓冲区的一行字符串（以'#'结束）进行运行voidInit();//全局初始化intReadALine();//从键盘读一行（没有空格），存于表达式缓冲区Buffer[]中charGetChar();//从缓冲区取一个字符，返回该字符的同时将它存于全局变量ch中//主程序：voidmain(){Init();while(ReadALine())//读一行成功，对它进行判断{if(Run())//对该行进行运行，看是否能被接受？printf(接受\n\n);else{printf(不接受\n);printf(错误位置在第%d个字符！\n\n,index);//显示错误位置}}}//对存储在缓冲区的一行字符串（以'#'结束）进行运行//返回：如果是无符号定点实数，返回true；否则返回：falseintRun(){intS=0;//S存放运行时的当前状态，目前为初态index=0;while(GetChar()!='#'){index++;if(ch='0'&&ch='9')//数字S=State[S][DIGIT];//将状态转换成输入数字后的状态elseif(ch=='.')//小数点S=State[S][DOT];//将状态转换成输入小数点后的状态elseif(ch=='e'||ch=='E')//eS=State[S][E];//将状态转换成输入e后的状态6elseif(ch=='+'||ch=='-')//+或-符号S=State[S][AD];//将状态转换成输入+或-后的状态elseif(ch==NULL)return0;else//其他都为非法字符return0;if(S==-1)//处于非法状态return0;}//运行结束，判断S是否为终态if(Q[S]==1)//终态return1;else//非终态return0;}//全局初始化voidInit(){printf(程序功能：输入一个字符串，判断它是否是无符号定点实数。\n);printf(注意：若要退出，请输入“exit”或“#”!\n);printf(======================================================\n\n);}//从键盘读一行（没有空格），存于表达式缓冲区Buffer[]中，以'#'结束，并置ipBuffer=0；//读到非空字符串：返回true；读到单独的#：返回falseintReadALine(){intl;char*ex=exit;printf(请输入以“#”号结束的无符号定点实数，\n);printf(或直接输入无符号定点实数：\n);scanf(%s,Buffer);if(!strcmp(Buffer,ex))exit(0);//判断是否退出l=strlen(Buffer);//读入的字符串的长度if(l==0)returnReadALine();//输入了空字符串，重新输入if(Buffer[0]=='#')return0;//输入单独的'#'表示不再输入Buffer[l]='#';//最后一个字符用结束标记'#'代替（本来是'\0'）ipBuffer=0;//初始化缓冲区指针return1;}//从缓冲区取一个字符，返回该字符的同时将它存于全局变量ch中//成功：返回字符；不成功：返回'#'charGetChar(){if((ch=Buffer[ipBuffer])!='#')7ipBuffer++;//位置序号加1returnch;}七、测试的结果该程序在MicrosoftVisualC++6.0中调试通过，并且能够识别出一个输入串是否为一个有效的无符号数，测试结果符合题目要求。具体结果如下图：