编译原理课程设计教案

黄冈师范学院《编译原理课程设计》教案（2011·春）授课教师：张瑞红授课班级：计科2008级授课时间：2010-2011二课题一有限自动机的运行一、设计题目：有限自动机的运行二、设计目的：1、理解有限自动机的作用2、利用转态图和状态表表示有限自动机3、以程序实现有限自动机的运行过程三、设计内容：（注：题目详细要求）利用状态表和有限自动机的运行原理编制程序，使得程序能够识别一个输入串是否为一个有效的符号串，具体可以选择下面之一：无符号定点实数、自然数、整数、十六进制数或其它自己定义的符号串。四、设计思想：（注：算法思想、程序流程图、不要写代码）本程序实现对无符号定点实数的判断，正确接受，否则不接受。本程序的关键在状态表和缓冲区的运用。首先定义了一个布尔型函数ReadALine把输入的字符串送到缓冲区中；然后定义了布尔型函数Run和Getchar实现对输入字符串的正确性判断，更改Run函数可以改变程序功能：如可将状态表改变成识别“偶数”的有限自动机的状态表。程序流程图如下：（学生自己画）五、运行结果与数据分析：六、设计总结体会：（学生自己写，此处可参考）通过这次课程设计，我对程序的编译和运行过程有了更进一步的了解，对程序的底层设计、代码优化也有了初步的认识，而且知道了如何从根本上来提高程序运行的速度。附录：（完整代码）#includestdio.h#includestring.h//状态表相关存储信息：#defineSTATE_NUMBER4//状态数目#defineCHAR_NUMBER2//输入字符的种类:d和.#defineDIGIT0//输入数字在状态表中位于第0列//State[][]为状态表，以整数组形式存放，0,1,2,3表示状态，-1表示没有此状态intState[STATE_NUMBER][CHAR_NUMBER]={{1,-1},{1,2},{3,-1},{3,-1}};intQ[STATE_NUMBER]={0,1,0,1};//终态标志：0非终态，1终态。//缓冲区：//输入缓冲区：由专门函数操作（ReadALine(),GetChar()）#defineBUFFER_SIZE1000//表达式缓冲区大小charBuffer[BUFFER_SIZE];//表达式缓冲区，以'\0'表示结束intipBuffer=0;//表达式缓冲区当前位置序号charch;//存放取得的一个字符//函数声明：boolRun();//对存储在缓冲区的一行字符串（以'#'结束）进行运行voidInit();//全局初始化boolReadALine();//从键盘读一行（没有空格），存于表达式缓冲区Buffer[]中charGetChar();//从缓冲区取一个字符，返回该字符的同时将它存于全局变量ch中//主程序：voidmain(){Init();while(ReadALine())//读一行成功，对它进行判断{if(Run())//对该行进行运行，看是否能被接受？printf(接受\n\n);elseprintf(不接受\n\n);}}//对存储在缓冲区的一行字符串（以'#'结束）进行运行//返回：如果是无符号定点实数，返回true；否则返回：falseboolRun(){intS=0;//S存放运行时的当前状态，目前为初态while(GetChar()!='#'){if(ch='0'&&ch='9')S=State[S][DIGIT];//将状态转换成输入后的状态else//其他都为非法字符returnfalse;if(S==-1)//处于非法状态returnfalse;}//运行结束，判断S是否为终态if(Q[S]==1)//终态returntrue;else//非终态returnfalse;}//全局初始化voidInit(){//好像无需初始化printf(程序功能：输入一个字符串，判断它是否是a。\n);printf(======================================================\n\n);}//从键盘读一行（没有空格），存于表达式缓冲区Buffer[]中，以'#'结束，并置ipBuffer=0；//读到非空字符串：返回true；读到单独的“#”：返回falseboolReadALine(){intl;printf(请输入以\#\号结束的无空格字符串：);scanf(%s,Buffer);l=strlen(Buffer);//读入的字符串的长度if(l==0)returnReadALine();//输入了空字符串，重新输入if(Buffer[0]=='#')returnfalse;//输入单独的'#'表示不再输入Buffer[l]='#';//最后一个字符用结束标记'#'代替（本来是'\0'）ipBuffer=0;//初始化缓冲区指针returntrue;}//从缓冲区取一个字符，返回该字符的同时将它存于全局变量ch中//成功：返回字符；不成功：返回'#'charGetChar(){if((ch=Buffer[ipBuffer])!='#')ipBuffer++;returnch;}五、运行结果与数据分析：六、设计总结体会：课题二：简单词法分析器设计（C或C++）一、设计题目：简单词法分析器设计（C或C++）二、设计目的要求：1、目的：通过设计、编程、调试出一个具体词法分析程序，加深对词法分析原理的理解，掌握其设计方法。2、要求：1）整理出所有单词符号及内部表示分类：各关键字、标识符、运算符、分界符、常数2）画出状态转换图3）编程。要求用自动机的方法进行编程。①预处理，去除注释、多余空格、回车换行符等。②词法分析程序能通过实例数据的测试。备注：设计词法分析程序时，应考虑能为语法分析程序调用。4）写出设计报告，内容为：状态转换图、单词符号及内部表示、符号表、出错处理、编程方法等。三、实验内容：选择一个词法分析方法，编写一个的词法分析器，对下面的实例进行测试。测试用例：programtestexample;{读入一组整数，统计并输出：其中非负整数之和，整组数的10倍平均值}vark,sum1,sum2,x:int;constnum=20,times=10;beginsum1:=0;sum2:=0;k:=num;whilek=1dobeginread(x);ifx=0thensum1:=sum1+x;sum2:=sum2+x;k:=k-1;end;write(sum1,times*sum2/num);end.四、设计思想：（注：算法思想、程序流程图、不要写代码）利用单词的构成规则，对输入的字符串进行分析再归类即可。（流程图学生自己画）五、运行结果与数据分析：六、设计总结体会：课题三：语法分析器的设计一、设计题目：语法分析器的设计二、设计目的要求：通过设计、编程、调试出一个具体语法分析程序，能调用词法分析程序为其提供单词符号串，进行语法分析，掌握语法分析方法和程序设计方法。三、设计内容：任选一种语法分析方法进行程序设计，语法分析程序能通过实例数据的测试。写出设计报告，内容为：所选的语法分析方法、算法、改写的文法、符号表、出错处理、编程方法等。SPL语言的文法程序::=程序首部说明部分程序主体程序首部::=program标识符;标识符*::=字母┃字母字母数字串字母*::=a┃b┃┅┃y┃z字母数字串*::=字母┃数字┃字母字母数字串┃数字字母数字串数字*::=0┃非0数字非0数字*::=1┃┅┃8┃9说明部分::=var变量组:int;┃const常量组;┃var变量组:int;const常量组;变量组::=标识符┃标识符,变量组常量组::=标识符=整数┃标识符=整数,常量组整数*::=数字┃非0数字数字串数字串*::=数字┃数字数字串程序主体::=begin执行语句end.执行语句::=语句┃语句;执行语句语句::=赋值语句┃条件语句┃循环语句┃读语句┃写语句┃复合语句赋值语句::=标识符:=表达式表达式::=表达式+项┃表达式-项┃项项::=项*因子┃项/因子┃因子因子::=(表达式)┃标识符┃整数条件语句::=if表达式关系符表达式then语句关系符*::==┃┃┃=┃=┃循环语句::=while表达式关系符表达式do语句读语句::=read(变量组)写语句::=write(表达式组)表达式组::=表达式┃表达式,表达式组复合语句::=begin执行语句end【备注】1.SPL语言源程序格式自由；2.SPL语言源程序中可以插入注解，用“{”、“}”括起来。测试用例同课题二四、设计思想：（注：算法思想、程序流程图、不要写代码）根据自己选择语法分析方法（LL（1）、LR（0）、OPG），先设计分析表再设计主控程序。（LL（1））主要算法:构造算符优先分析表的算法以下几个步骤：（1）构造文法G中非终结符号的FIRSTVT集合FIRSTVT集合用一个整型二维数组F[q][f]表示，其值为0或1。F是一个q*f的二维数组（q=文法G中非终结符号个数，f=文法G中终结符号个数）。对于文法G的所有终结符，构造数组F[q][f]的算法（该算法使用一个STACK栈，用于存放含有一个非终结符和一个终结符对的结构体X。）如下：BEGINfor任何非终结符P和终结符a对（P，a）确定P在非终结符数组VN[]中的位置q1和a在终结符数组VT[]中的位置f1F[q1][f1]=0；for任何形如P-》a…或P-》Qa…的产生式BEGINIFNOTF[q1][f1]F[q1][f1]=0；将（P，a）放入结构体x；X进STACK栈；ENDWHILESTACK栈非空BEGIN将STACK栈的栈顶元素出栈FOR每个形如Q-》P…的产生式BEGIN确定Q在非终结符数组VN[]中的位置q2IFNOTF[q2][f1]BEGINF[q2][f1]=1；将（Q，a）放入结构体X；X进STACK栈；ENDENDEND.（2）构造文法G中非终结符号的LASTVT集合类似于构造FIRSTVT集合，LASTVT集合用一个整型数组L[P，a]表示，其值为0或1。L是一个q*f的二维数组（q=文法G中非终结符号个数，f=文法G中终结符号个数）。对于文法G的所有终结符，构造数组L[q][f]的算法（该算法法使用一个STACK栈，用于存放含有一个非终结符和一个终结符对的结构体D。）如下：BEGINfor任何非终结符P和终结符a对（P，a）确定P在非终结符数组VN[]中的位置q1和a在终结符数组VT[]中的位置f1L[q1][f1]=0；for任何形如P-》…a或P-》…Qa的产生式BEGINIFNOTL[q1][f1]L[q1][f1]=0；将（P，a）放入结构体d；D进STACK栈；ENDWHILESTACK栈非空BEGIN将STACK栈的栈顶元素出栈FOR每个形如Q-》…P的产生式BEGIN确定Q在非终结符数组VN[]中的位置q2IFNOTL[q2][f1]BEGINL[q2][f1]=1；将（Q，a）放入结构体D；D进STACK栈；ENDENDEND.（3）构造文法G的优先关系表使用文法G中任何非终结符号的FIRSTVT集合和LASTVT集合，可以构造文法G的优先关系表。优先关系表用一个二维字符数组Z[][]表示，Z是一个f*f的数组（f=文法G中终结符号个数）。Z表的值为‘0’、‘》’、‘《’或‘=’。构造优先关系表Z[][]的算法如下：{FOR每个形如产生式P-》Qa…或P-》…Qa{在las