欧拉回路-数据结构与算法课程设计报告及编译课程设计报告

华北电力大学（北京）华北电力大学（北京）PAGE20PAGE21华北电力大学（北京）XXX合肥学院计算机科学与技术系课程设计报告20～20学年第2学期课程数据结构与算法设计课程设计课程设计名称欧拉回路学生姓名学号专业班级计算机科学与技术指导教师20年3月题目：欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？一．问题分析和任务定义：题目要求判断一个给定的图中是否存在欧拉回路。由欧拉图的定义，当一个图存在欧拉回路时，该图称为欧拉图。题目问是否存在欧拉回路即等价于问给定的图是否为欧拉图。所以，证明给定图是欧拉图就说明该图存在欧拉回路，否则不存在欧拉回路。根据高等教育出版社出版屈婉玲、耿素云、张立昂主编的《离散数学》P.296定理15.1可知：无向图G是欧拉图当且仅当G是连通图且没有奇度顶点。要证明一个给定的图是否为欧拉图，证明给定的图是连通图且没有奇度顶点即可。所以，解决题目中的问题就转化为证明给定图是否是连通图且没有奇度顶点。首先要确定一给定的图是否为连通图。这里我们可以通过图的深度优先搜索遍历确定。从任意顶点出发，如果能深度优先遍历到所有的顶点就说明图中所有的顶点都是连图的即为连通图。然后再确定给定的图是否没有奇度顶点。我们可以以邻接矩阵的形式存储给定的图，对邻接矩阵的每行分别行进行扫描，记录每个顶点的度数，当每行扫描完后判断该顶点的度数是否为奇数，存在奇度顶点直接结束扫描，说明存在奇度顶点，给定图不是欧拉图。即不存在欧拉回路。否则继续扫描，当扫描完所有的行没有发现奇度顶点，即说明给定图没有奇度顶点。当上述两个问题都确定以后根据定理，当且仅当给定图为连通图且没有奇度顶点时给定的图为欧拉图。由此可确定，给定的图是否存在欧拉回路。二．数据结构的选择与概要设计：数据结构的选择：图在我们所学的数据结构与算法课程中有四种存储方式：邻接矩阵、邻接表、十字链表和邻接多重表。本问题比较简单，选用邻接矩阵或邻接矩阵就足够了。在本课程设计中需要判断是否有奇度顶点和是否为连通图，用用邻接表和邻接矩阵在时间繁杂度没有什么大的差别，在空间复杂度上，因为本题是无向图，如果如果用邻接表，储存一条边要储存两次，存储指针比int型的空间消耗大，在图不是很大的情况下，邻接矩阵的空间复杂度要小。同时选用邻接矩阵很容易得到图中个顶点的度数。因为顶点只要求编号这一信息，所以就没有用结构体存储顶点信息，图用邻接矩阵要用结构体存储。结构体定义如下：typedefstruct{ intn;//顶点个数 inte;//边的条数 intvexs[MAX_VERTEX_NUM];//一维数组储存顶点 intedges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二维数组储存边}MGraph;//图2.概要设计首先将图转换为邻接矩阵存储起来，然后邻接矩阵的每一行进行搜索得图中到每个顶点的度数，如果有奇度顶点，输出：不存在欧拉回路，即可结束程序。否则继续判断给定的图是否为连通图，如果是连通图输出：存在欧拉回路；否则输出：不存在欧拉回路。结束程序。三．详细设计和编码：1.将图转化为邻接矩阵存储：先输入图中顶点个个数和边的条数，对所有可能存在的边初始化为0，再依次输入边的信息，即如果顶点1,2存在相连的边，输入12（1,2为自动给顶点分配的编码）。将边1,2的信息改为1。用函数MGraph*creat_MGraph();完成，返回邻接矩阵的首地址即可。MGraph*creat_MGraph()//建立邻接矩阵{ inti,j,k,n,e; MGraph*mg=malloc(sizeof(MGraph)); printf("请输入顶点的个数："); scanf("%d",&n); printf("请输入边的条数："); scanf("%d",&e); mg->n=n; mg->e=e; getchar(); for(i=1;i<=n;i++) for(j=1;j<=n;j++) mg->edges[i][j]=0;//初始化邻接矩阵表示的所有边 printf("请输入边的信息:\n"); for(i=1;i<=e;i++) { scanf("%d%d",&j,&k); mg->edges[j][k]=1;mg->edges[k][j]=1;//标记存在的边 } returnmg;//返回邻接矩阵的首地址}2.搜索有没有奇度顶点：对邻接矩阵的每一行进行搜索，用num记录顶点的度数（每次对新的顶点记录前都将num置为0）。为了排除顶点自身环对判断的影响，当遇到边的两顶点相同，忽略不计，这样不会对结果产生影响。如果搜索到奇度顶点则结束intEuleriancycle(MGraph*mg);函数，返回0，搜索完成且没有发现奇度顶点则返回1.intEuleriancycle(MGraph*mg)//判断是否存在欧拉回路{ inti,j,num; for(i=1;i<=mg->n;i++)//从第一个顶点开始，判断顶点的度数 { num=0;//初始化每个顶点的度数为0 for(j=1;j<=mg->n;j++) { if((mg->edges[i][j]!=0)&&(i!=j))//如果顶点i到j的边存在度数加1 num=num+1; } if(num%2==1)//如果有哪个顶点的度数为奇数，直接退出循环，返回0 return0; } return1;//当所有的顶点都判断完成还没有退出本函数说明所有顶点度数均为偶数，返回1}3.判断给定的图是否为连通图：本程序的深度优先遍历是一个递归的过程。其中visited[MAX_VERTEX_NUM]是一个辅助的全局变量，初始值均为0.表示该顶点没有被访问。访问后用1表示。在深度优先搜索时。我们需要调用dfs_trave()函数。在dfs_trave()中，针对每个没有被访问过的顶点调用dfs()函数，它是一个递归函数，完成从该顶点开始的深度优先搜索。如果图是一个连通图，那么完成对visited数组的初始化后，在dfs_trave()中只需调用dfs()函数一次即可完成对图的遍历。当图不是一个连通图时，则在dfs_trave()中需要针对每个连通分量分别调用dfs()函数。根据dfs()函数被调用的次数就可以判断给定的图是否为连通图。如果dfs()函数被调用一次则给定的图是连通图，否则不是连通图。intdfs_trave(MGraph*mg)//深度优先搜索遍历{ inti,m=0; for(i=1;i<=mg->n;i++)//将辅助变量全部初始化为0，表明顶点没有被访问过 visited[i]=0; for(i=1;i<=mg->n;i++) if(visited[i]==0)//对没有访问过的顶点，调用深度优先搜索函数 { dfs(mg,i);//深度优先搜索 m=m+1;//如果是非连通图，要调用1次以上，m用来记录调用dfs函数的次数 } returnm;//返回调用dfs函数的次数}voiddfs(MGraph*mg,inti)//深度优先搜索{ intj; visited[i]=1;//访问该顶点 for(j=1;j<=mg->n;j++) if((visited[j]==0)&&(mg->edges[i][j]==1))//当顶点没有被访问过并且两顶点存在边 dfs(mg,j);//对该顶点深度优先搜索}4.根据上述2,3可知，必须为连通图且没有奇度顶点才是欧拉图即存在欧拉回路。5.流程图如下（图：1）：开始判断是否存在奇度顶点将图转化为邻接矩阵顶点数、边数、边信息搜索图中所有顶点的度数开始判断是否存在奇度顶点将图转化为邻接矩阵顶点数、边数、边信息搜索图中所有顶点的度数 Y N对图进行深度优先搜索遍历对图进行深度优先搜索遍历对图进行深度优先搜索遍历对图进行深度优先搜索遍历判断图是否为连通图 判断图是否为连通图 N Y存在欧拉回路不存在欧拉回路结束存在欧拉回路不存在欧拉回路结束图：1流程图四．上机调试过程：本次实验中也遇到了一些小问题，通过在适当的位置加一些printf语句即可确定出现问题的语句大概的位置。加以分析、修改即可。在本次课程设计的第三组数据的测试时出现了不存在欧拉图的错误结果，仔细分析可知，在（2,2）邻接矩阵的对角线上，所以该点的度数在计算的时候就少1度。所以，在if((mg->edges[i][j]!=0)&&(i!=j))//如果顶点i到j的边存在度数加1的判断中增加了一个判断，当该点存在环，则在度数的计数时忽略不计，这样不会印象该点度数奇偶性的变化。这样就很好的解决了，存在环对判断结果的印象的问题。通过本次课程设计让我更加深刻的体会到调试程序需要平心静气，仔细分析、研究。要有一个严谨的态度，这样才能高效率的写出优质的代码。五．测试结果与分析：测试数据的选择：在测试中考虑到多种情况使用了多组数据，分别根据是否为连通图、是否没有奇度顶点设计了一下四组数据。第一组数据为连通图且没有奇度顶点，第二组数据为连通图且有奇度顶点，第三组数据为连通图、没有奇度顶点且有环，第四组数据为非连通图且有奇度顶点，第五组数据为非连通图且没有奇度顶点。每组数据进行多次测试。测试数据1：33121323测试结果：结果分析：测试数据表示一个3个顶点，3条边的图，顶点两两相连。如下:2-1所示：123123 图：2-1测试1存在欧拉回路。测试结果正确。测试数据2：33321223测试结果： 结果分析：测试数据表示一个3个顶点，3条边的图，1,、2相连，2、3相连。如下图2-2所示：1 12323图：2-2测试2不存在欧拉回路。测试结果正确。测试数据:3：451213243422测试结果：结果分析：测试数据表示一个4个顶点，5条边的图，1、2相连，1、3相连,2、4相连,3、4相连，2、2相连。如下图2-3所示：12341234 图：2-3测试3存在欧拉回路。测试结果正确。测试数据4：5412344535测试结果：结果分析：测试数据表示一个5个顶点，4条边的图，1、2相连，3、4相连,4、5相连,3、5相连。如下:图2-4所示：1234512345不存在欧拉回路。测试结果正确。 图：2-4测试4测试数据5：66121323454656测试结果：结果分析：测试数据表示一个6个顶点，6条边的图，1、2相连，1、3相连,2、3相连,4、5相连，4、6相连，5、6相连。如下图2-5所示：456123456123 图：2-5不存在欧拉回路。测试结果正确。测试结果总结：通过对多种情况设计了多组数据多次测试如上，结果都得到了真确的结论。说明程序符合题目的要求，达到了实验的目的。六．用户使用说明：首先本程序中的所有顶点编号为1-N的整数。(0<N<1000)先输入图顶点的个数要求为一个正整数n，然后输入图所有边的条数要求为正整数e，再图边数行整形数，每行两个数（用空格相隔）表示一条边所连接的两个顶点编号。输出结果即为题目的解。七．参考文献：[1]王昆仑，李红.数据结构与算法.北京：高等教育出版社，2007年6月第1版[2]屈婉玲，耿素云，张立昂.离散数学.北京：高等教育出版社，2008年3月第1版八．附录：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineMAX_VERTEX_NUM1000//顶点的最大个数typedefstruct{ intn;//顶点个数 inte;//边的条数 intvexs[MAX_VERTEX_NUM];//一维数组储存顶点 intedges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二维数组储存边}MGraph;//图intvisited[MAX_VERTEX_NUM];//全局变量。在对顶点进行深度优先搜索遍历时的辅助变量数组intEuleriancycle(MGraph*mg);//判断顶点的度数是否全为偶数，有奇数时输出0，全为偶数时输出1MGraph*creat_MGraph();//将图转化为邻接矩阵储存起来，返回邻接矩阵的首地址intdfs_trave(MGraph*mg);//深度优先搜索遍历voiddfs(MGraph*mg,inti);//深度优先搜索voidmain(){ intnum,m;//num用来接收顶点度数判断的结果，m用来接收图是否为连通图的结果 MGraph*mg; mg=creat_MGraph();//建立邻接矩阵 num=Euleriancycle(mg);//判断顶点的度数是否全为偶数。全为偶数时num=1；否则num=0 if(num!=1) { printf("不存在欧拉图！\n"); getchar(); exit(0); } m=dfs_trave(mg);//判断图是否为连通图 if(m!=1) printf("不存在欧拉图！\n"); else printf("存在欧拉图！\n"); getch();}MGraph*creat_MGraph()//建立邻接矩阵{ inti,j,k,n,e; MGraph*mg=malloc(sizeof(MGraph)); printf("请输入顶点的个数："); scanf("%d",&n); printf("请输入边的条数："); scanf("%d",&e); mg->n=n; mg->e=e; getchar(); for(i=1;i<=n;i++) for(j=1;j<=n;j++) mg->edges[i][j]=0;//初始化邻接矩阵表示的所有边 printf("请输入边的信息:\n"); for(i=1;i<=e;i++) { scanf("%d%d",&j,&k); mg->edges[j][k]=1;mg->edges[k][j]=1;//标记存在的边 } returnmg;//返回邻接矩阵的首地址}intEuleriancycle(MGraph*mg)//判断是否存在欧拉回路{ inti,j,num; for(i=1;i<=mg->n;i++)//从第一个顶点开始，判断顶点的度数 { num=0;//初始化每个顶点的度数为0 for(j=1;j<=mg->n;j++) { If((mg->edges[i][j]!=0)&&(i!=j))//如果顶点i到j的边存在度数加1 num=num+1; } if(num%2==1)//如果有哪个顶点的度数为奇数，直接退出循环，返回0 return0; } return1;//当所有的顶点都判断完成还没有退出本函数说明所有顶点度数均为偶数，返回1}intdfs_trave(MGraph*mg)//深度优先搜索遍历{ inti,m=0; for(i=1;i<=mg->n;i++)//将辅助变量全部初始化为0，表明顶点没有被访问过 visited[i]=0; for(i=1;i<=mg->n;i++) if(visited[i]==0)//对没有访问过的顶点，调用深度优先搜索函数 { dfs(mg,i);//深度优先搜索 m=m+1;//如果是非连通图，要调用1次以上，m用来记录调用dfs函数的次数 } returnm;//返回调用dfs函数的次数}voiddfs(MGraph*mg,inti)//深度优先搜索{ intj; visited[i]=1;//访问该顶点 for(j=1;j<=mg->n;j++) if((visited[j]==0)&&(mg->edges[i][j]==1))//当顶点没有被访问过并且两顶点存在边 dfs(mg,j);//对该顶点深度优先搜索}编译原理课程设计LL(1)文法判定c语言实现专业班号____计算机_学生姓名________指导教师___________目录第一章前言 11.1LL(1)文法概述 11.2设计思想概述 1第二章语言文法规则 12.1语言的词法规则 12.2语言的语法规则 2第三章程序设计 23.1词法分析程序的实现 23.1.1文法输入规则 23.1.2数据结构 23.1.3程序流程 43.2求解FIRST集、FOLLOW集和SELECT集的实现 53.2.1求出能推出的非终结符ε 53.2.2求解产生式的右部的FIRST集 63.2.3求解非终结符的FOLLOW集 73.2.4求解产生式的SELECT集 73.3判定是否是LL(1)文法的实现 73.4预测分析表的生成实现 73.5判定给定符号串是否是文法中的句子的实现 8第四章系统运行及测试 94.1运行和安装环境 94.2系统运行 94.2系统测试 94.2.1测试一 94.2.2测试二 10第五章结论 115.1系统结论 115.2存在的不足 12参考文献 12附录 13源程序 13PAGE1第一章前言 本设计使用C语言实现了对简单方法描述的LL(1)文法的判定。该设计程序实现了：⑴分别求出每一产生式的右部的FIRST集、每一个非终结符的FOLLOW集和每一产生式的SELECT集；⑵判定是否是LL(1)文法；⑶画出预测分析表；⑷对给定的符号串判定是否是文法中的句子，分析过程用计算机打印出来。1.1LL(1)文法概述LL(1)文法是一种2型文法 ，由它所描述的语言可以使用自顶向下语法分析方法进行语法分析。LL(1)文法的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第二个L表明分析过程中将用最左推导，1表明只需向右看一个符号便可决定如何推导即选择哪一个产生式（规则）进行推导。一个上下文无关文法（即2型文法）是LL（1）文法的充分必要条件是，对每个非终结符A的两个不同产生式，A→α，A→β，满足SELECT（A→α）∩SELECT（A→β）=ø其中α、β不同时能ε[1]。1.2设计思想概述首先对输入的文法进行词法分析，识别出所有的文法符号（终结符和非终结符）并对其编码生成相应ID，同时用单链表型数据结构存储单个产生式，产生式的文法符号在单链表中以其相应ID表示，即所有的产生式以规定形式存储在一个单链表集中。第二步，针对单链表型数据结构，设计相应算法计算出每一个表达式右部的FIRST集、每一非终结符的FOLLOW集和每一产生式的SELECT集，其结果均以单链表集的形式存储。最后，由求出的SELECT集经由相应算法判定出该输入文法是否为LL(1)文法，若是，则在屏幕上输出预测分析表，并对给定的符号串判定是否是文法中的句子，分析过程用计算机打印出来。第二章语言文法规则2.1语言的词法规则为简单起见，本设计规定非终结符集VN为所有大写字母的集合，终结符集VT为所有小写字母、数字和四则运算符号的集合，取所有文法符号均为单个字符。2.2语言的语法规则由2型文法的定义，定义如下：设G=（VN，VT，P，S），若P中的每一个产生式α→β满足：α是一非终结符，β∈(VN∪VT)*则此文法称为2型的或上下文无关的[1]。规定产生式的左部必须为非终结符。第三章程序设计3.1词法分析程序的实现3.1.1文法输入规则源文法的输入采用文件输入的方式，每读入一个字符就进行文法符号的判定、记录和编码，同时对产生式以特定格式存储。文件中源产生式的书写格式规定如下：格式为“左部>右部”，左部为一非终结符，右部的文法符号之间不允许有空格，右部结束后直接回车或文件结束，规定文件的第一个字符为文法的开始符号；格式中使用“>”而非“->”的原因在于简化词法分析，可以避免在读入字符“-”时的分情况处理（因为“-”也是一个终结符）。举例如下：/*file:e:\demo1.dat参考文献1例5.5*/S>ABS>bCA>&A>bB>&B>aDC>ADC>bD>aSD>c3.1.2数据结构对非终结符和终结符分别采用以下的数据结构存储：typedefstructVn_stru{ unsignedintID; charNch; unsignedintifgetnull; }Vn_type;Vn_typeVn[100]; intVn_ID_next;以上为非终结符的存储结构，对非终结符采用结构体数组存储。结构体中ID存储非终结符的编码（关于编码，程序中规定非终结符的编码从200开始，第一个被“发现”的非终结符被编码为200，按照被“发现”顺序依次编码为201,202,…,程序最多允许100个非终结符，即编码范围在200~299之间。对于终结符，采用同样的规则对其编码，编码范围在300~399之间），Nch存储其字符，ifgetnull指示该终结符能否推出ε，用于对三个集合的求解过程中。Vn[]存储所有的非终结符。Vn_ID_next指示下一个可用的非终结符的编码值，初始为200。typedefstructVt_stru{ unsignedintID; charTch;}Vt_type;Vt_typeVt[100]; intVt_ID_next; 以上为终结符的存储结构，在结构体中，ID存储其编码，Tch存储其字符。所有终结符存储在Vt[]中。Vt_ID_next提示下一个可用的终结符的编码值。需要指出的是，出于降低程序复杂度的考虑，‘ε’（程序中以‘&’指代）和‘#’均被以终结符的身份处理。如前所述，分析所得的文法存储在单链表集中。链表的结点结构如下：typedefstructIDNode{ unsignedintID; structIDNode*next;}IDNode;结点中存储文法符号的编码和指向下一结点的指针。单链表集用IDNode*指针数组表示，即：IDNode*ppro[100]; 词法分析的结果，即第i个产生式转存为单链表的规则如下：左部作为第一个结点，该结点的地址存储在ppro[i]中，即第i个产生式的首结点地址存储在ppro[]的第i个元素中,右部第一个符号作为第二个结点，向右依次将右部所有文法符号对应的结点加入到单链表的尾部。例如：S>ABS>bC存储方法为如图3-1所示ppro[0]ppro[1]ppro[0]ppro[1]ppro[2]200201202NULL200300300NULL100200103图3-1（假定S、A、B、C、b的编码分别为100、101、102、103、200）3.1.3程序流程 词法分析由函数File_Input(FILE*fp)实现，具体实现见附录源程序。以下是程序的流程图：否否从文件中读入一个字符否否是检查Vn[]中是否存在此符号,若无,填之是准备在ppro[i+1]中填入结点若字符不是>判定为终结符检查Vt[]中是否存在此符号,若无,填之在ppro[i]中填入代表该字符的结点读入下一个字符是结束是否为非终结符是否为EOF文件结束符是否为回车换行图3-23.2求解FIRST集、FOLLOW集和SELECT集的实现存储FIRST集、FOLLOW集和SELECT集的数据结构采用如图3-1的单链表集，分别命名为FirstRight[]、Follow[]和Select[]，在这里，每个结点的ID必然大于等于300，因为这些集合的元素都必然是终结符。每个单链表中的结点将按其ID的大小顺序由小到大排列。需要指出的是，对三个集合的求解在算法上是对单链表集ppro[]进行若干种链表操作的组合，故具体过程（分别由getFirstVn()、getFirstRight()、etFollow()和getSelect()实现）不再给出，下面给出的是逻辑算法。3.2.1求出能推出的非终结符ε算法如下：将结构体数组Vn[]中对应每一非终结符的能否推出ε的标记ifgetnull（如前所述，ifgetnull为结构体变量Vn_type的成员变量，见3.1.2）置初值“未定”即2。扫描方法中的产生式（程序中的扫描对象为ppro[]的拷贝pprotemp[]）。删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为“否”，说明该非终结符不能推出ε。（在程序中的操作为：删除含有ID大于或等于300的结点的单链表，若这使得表示某一非终结符为左部的产生式的所有单链表都被删除，则将Vn[]中对应的ifgetfull置为0）若某一非终结符的某一产生式右部为ε,则将数组中对应该非终结符的标志置为“是”，并从文法中删除该非终结符的所有产生式。（程序中的操作为：删除含有对应ε的ID的结点的单链表，置该单链表的第一个结点所表示的非终结符对应的Vn[]中元素的ifgetnull为1，并从pprotemp[]删除所有以该非终结符对应的结点为第一结点的单链表。）扫描产生式右部的每一符号若所扫描到的非终结符号在数组中对应的标志是“是”，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改为“是”，并删除该非终结符为左部的所有产生式。（程序中的操作为：若所扫描到的结点所表示的非终结符号的ifgetnull被标记为1,则删去该结点，若这使该单链表只剩一个结点，则标记该产生式左部的非终结符的ifgetnull为1，并删除pprotemp[]中所有以该非终结符对应的结点为第一结点的单链表）若所扫描到的非终结符号在数组中对应的标志是“否”，则删去该产生式，若这使产生式左部非终结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改为“否”。（程序中的操作为：删除含有对应的ifgetnull==0的结点的单链表，若这使表示产生式左部非终结符的有关产生式的单链表都被删去，则把左部非终结符对应的ifgetnull置为0。）重复3），直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变为止。（程序中设置了标志变量ifVnChanged用以标识非终结符对应的特征有没有改变。）[1]该过程由函数getNULLVn()实现，由于对存储文法的链表有删除操作，为保护数据，函数开始时先从ppro[]拷贝了一个临时单链表集pprotemp[],所有删除操作均在后者中进行，并在程序结束时释放了pprotemp[]的地址空间。函数的结果存储在Vn[]中。3.2.2求解产生式的右部的FIRST集首先，计算每个文法符号的FIRST集。由定义：FIRST（α）={a|aαβ,a∈VT，a、β∈V*}，若αε，则规定ε∈FIRST（α）对每一文法符号X∈V计算FIRST（X）。若X∈VT，则FIRST（X）={X}若X∈VN，且有产生式X→a…，a∈VT则a∈FIRST（X）若X∈VN，X→ε，则ε∈FIRST（X）若X∈VN，Y1，Y2，…，Yi都∈VN，而有产生式X→Y1Y2…Yn。当Y1，Y2，…，Yi-1都ε时，（其中1≤i≤n），则FIRST（Y1）-{ε}，FIRST（Y2）-{ε}，…，FIRST（Yi-1）-{ε}，FIRST（Yi）都包含在FIRST（X）中。当d)中所有Yiε，（i=1，2，…n）则FIRST（X）=FIRST（Y1）∪FIRST（Y2）…∪FIRST（Yn）∪{ε}。反复使用上述(b)~(e)步直到每个符号的FIRST集合不再增大为止。求出每个文法符号的FIRST集合后也就不难求出一个符号串的FIRST集合。若符号串α∈V*，α=X1X2…Xn，当X1不能ε，则置FIRST（α）=FIRST（X1）。若对任何j( 1≤j≤i-1,2≤i≤n)，ε∈FIRST（Xj）则FIRST（α）=（FIRST（Xj）-{ε}）∪FIRST（Xi）当所有FIRST（Xj）( 1≤j≤n)都含有ε时，则FIRST（α）=（FIRST（Xj））∪{ε}[1]。由此算法可计算出各文法符号的FIRST集和各产生式的右部的FIRST集，分别存储在FirstVn[]和FirstRight[]中。定义如下：/*LL(1).h*/IDNode*FirstVn[100];IDNode*FirstRight[100]; 该过程分别由函数getFirstVn()和getFirstRight()实现，两者又调用了两个链表操作函数insert2link()和add2link()以及一个辅助函数getFirstExp()来实现具体功能，后三都的功能分别为插入结点到单链表、拷贝单链表到另一单链表、得到任意字符串的FIRST集。详见附录源程序。3.2.3求解非终结符的FOLLOW集算法如下：对文法中每一A∈VN计算FOLLOW(A)设S为文法中开始符号，把{#}加入FOLLOW（S）中。若A→αBβ是一个产生式，则把FIRST（β）的非空元素加入FOLLOW（B）中。如果βε则把FOLLOW（A）也加入FOLLOW（B）中。反复使用（b）直到每个非终结符的FOLLOW集不再增大为止[1]。由此算法可计算出非终结符号的FOLLOW集，存储在Follow[]中。定义如下：/*LL(1).h*/IDNode*Follow[100];该过程由函数getFollow()实现。函数中调用getFirstExp()取得“FIRST（β）的非空元素”；调用add2link()“把FOLLOW（A）也加入FOLLOW（B）中”。详见附录源程序。3.2.4求解产生式的SELECT集计算SELECT集的算法如下：对于任一产生式，若其左部的非终结符号不能推出ε，则其SELECT集等于右部的FIRST集；反之，SELECT集等于右部的FIRST集的非空元素与左部的非终结符的FOLLOW集的所有元素组成的集合。该过程由函数getSelect()实现。计算出的表达式的SELECT集存储在Select[]中。定义如下：/*LL(1).h*/IDNode*Select[100];3.3判定是否是LL(1)文法的实现如“1.1LL(1)文法概述”中所述，一个上下文无关文法是否是LL(1)文法关键在于每个非终结符的两个不同产生式的SELECT集是否存在交集，若存在则不是LL(1)文法，反之则可以判定该输入文法是LL(1)文法。该过程由函数judgeLL1()实现。3.4预测分析表的生成实现预测分析表可用一个矩阵M(或称二维数组)表示。矩阵的元素M[A,a]中的下标A表示非终结符,a为终结符或句子括号“#”,矩阵元素M[A,a]中的内容为一条关于A的产生式,表明当用非终结符A向下推导时,面临输入符a时,所应采取的候选产生式,当元素内容无产生式时,则表明用A为左部向下推导时遇到了不该出现的符号,因此元素内容为转身出错处理的信息[1]。算法如下：对每个终结符或“#”号用a表示。a∈SELECT(A→α),则把α的头指针放入M[A,a]中。把无定义的M[A,a]置为NULL空指针。该过程由函数getpa_table()实现，该函数以Select[]为输入数据，计算所得分析表存储在结构体pa_table的变量中。pa_table的定义如下：/*LL(1).h*/typedefstructpa_table{ IDNode**ptb; int*row_info,*col_info; introw_num,col_num;}pa_table; 3.5判定给定符号串是否是文法中的句子的实现预测分析程序的工作过程用示意图3-3表示图3-3第四章系统运行及测试4.1运行和安装环境WindowsXPProfessional+TurboC2.04.2系统运行首先将所需判定的文法按“3.1.1文法输入规则”中的要求写入自定义的文件中，该文件称作文法文件。运行程序LL1.exe,按照屏幕提示，输入文法文件的路径和文件名。程序将一步步进行LL(1)文法的判定。若判定为LL(1)文法，则输出预测分析表，并提示输入符号串进行语法分析。4.2系统测试4.2.1测试一测试文法一的测试数据如下:S->ABS->bCA->εA->bB->εB->aDC->ADC->bD->aSD->c图4-1、图4-2、图4-3分别是程序计算FIRST集、FOLLOW集和SELECT集的运行截图（符号“ε“由“&”代替）。图4-1图4-1图4-2图4-3图4-4是程序根据得到的SELECT集判定输入文法是否为LL(1)文法的运行截图。 图4-4如图4-4所示，经程序判定，该输入文法不是LL(1)文法。4.2.2测试二测试文法二的测试数据如下:E->TDD->+TDD->εT->FSS->*FSS->εF->iF->(E)图4-5、图4-6、图4-7分别是程序计算FIRST集、FOLLOW集和SELECT集的运行截图（符号“ε“由“&”代替）。图4-5图4-6图4-7图4-8是程序根据得到的SELECT集判定输入文法是否为LL(1)文法的运行截图。图4-8如图4-8所示，经程序判定，该输入文法是LL(1)文法。根据屏幕提示，输入符号串i+i*i#，由程序判定是否是文法中的句子，分析过程在打印在屏幕上，如图4-9所示。图4-9如图中最后一行所示，i+i*i#是该文法的句子。测试完毕。第五章结论5.1系统结论本设计用C语言成功实现了对LL(1)文法的判定，达到了课程设计题目中的所有要求，并且操作简单、易上手，输出结果清晰明了，可以作为《编译原理》初学者的学习工具，也可以作为《编译原理》课上的演示程序。本设计的设计亮点在于使用单链表集存储关键数据，实现了判定过程的高效率；同时针对链表操作的复杂和易出错的特点，设计者设计出了几个基本却功能强大的链表操作函数，如insert2link()、add2link()，提供给各主要函数调用。这样的做法，既提高的程序的开发效率和运行效率，又增强了程序运行的稳定性，此外，还大大提高了程序的可重用性。除了高标准的完成了设计要求，在这次课程设计中，设计者对编程技术也有了更进一步的理解和体会，并借此机会大大提高了对C语言的驾驭能力，可谓受益匪浅。希望以后能有更多的机会得以锻炼和施展才能。5.2存在的不足当然，由于能力所限，本设计也有一些不足：其一，没有实现实时输入文法，只采用了文件输入；其二，对于文法的要求过于苛刻，文法符号只能由一位字符构成；其三，程序中过多地采用了全局变量，模块化的程度太低；其四，程序几乎处理错误能力很低，遇非规则输入则死机。总的来说，虽然这些不足不影响程序对LL(1)文法判定的演示和教学效果，但是其判定功能却因为这些不足而被大大削弱。有时间的话，设计者会对该程序做进一步的改进。参考文献1吕映芝,张素琴,蒋维杜.编译原理.第1版.北京:清华大学出版社,1998附录源程序#include"stdlib.h"#include"stdio.h"#include<string.h>#include"e:\ll1.h"#include"dir.h"/*#defineDEBUG*/voidinitiate(){ inti; Line_Num=-1; /*specialusedininput*/ Vn_ID_next=100;/*Vn100...199*/ Vt_ID_next=200;/*Vt200...299*/ for(i=0;i<100;i++){ ppro[i]=NULL; Vn[i].ifgetnull=UNCERTAIN; FirstVn[i]=NULL; FirstRight[i]=NULL; Follow[i]=NULL; Select[i]=NULL; }}intgetVnID(charch){/*gettheIDofVnaccordingtoitselt*/ inti=0; for(;i<Vn_ID_next-100;i++){ if(Vn[i].Nch==ch)returnVn[i].ID; } return0;}intgetVtID(charch){/*gettheIDofVtaccordingtoitselt*/ inti=0; for(;i<Vt_ID_next-200;i++){ if(Vt[i].Tch==ch)returnVt[i].ID; } return0;}intgetID(charch){/*gettheIDofV*/ inti; i=getVnID(ch); if(i==0)i=getVtID(ch); returni;}intSeekoverVn(charch){/*scanvn,ifchin,thenreturnitsid,elsereturnVn_ID_next*/ inti=0,r=Vn_ID_next; for(;i<Vn_ID_next-100;i++){ if(ch==Vn[i].Nch){ r=Vn[i].ID; break; } } returnr;}intSeekoverVt(charch){/*scanvt,ifchin,thenreturnitsid,elsereturnVt_ID_next*/ inti=0,r=Vt_ID_next; for(;i<Vt_ID_next-100;i++){ if(ch==Vt[i].Tch){ r=Vt[i].ID; break; } } returnr;}StatusFile_Input(FILE*fp){/*readfilefppointsto,getallfags,andtransformtheorientalwordstotheformthatthesyntaxanalysercanreadwhichisstoredinppro[]*/ charch;intidcurrent; intifavailable; /*noteswhethertobetransformed*/ IDNode*pnewnode=NULL;/*pointertothelastnode*/ IDNode*pt; /*temppointer*/ Line_Num=-1; ch=fgetc(fp); while(ch!=EOF){ ifavailable=0; /*togetready*/ if(ch=='|'){ /*forexampleS->AB|bC,'|'meansanewexpression*/ ifavailable=1; /*notestobetransformed*/ idcurrent=ppro[Line_Num]->ID;/*leftpart*/ pnewnode=NULL; /*anewexpression*/ } elseif((ch>='A')&&(ch<='Z')){ idcurrent=SeekoverVn(ch);/*gettheidofch*/ if(idcurrent==Vn_ID_next){ Vn[Vn_ID_next-100].ID=Vn_ID_next; /*additinVn*/ Vn[Vn_ID_next-100].Nch=ch; Vn_ID_next++; } ifavailable=1; /*notestobetransformed*/ } elseif(ch=='\n'){/*carriagereturn*/ pnewnode=NULL; } elseif(ch!='>'){ idcurrent=SeekoverVt(ch);/*gettheidofch*/ if(idcurrent==Vt_ID_next){ Vt[Vt_ID_next-200].ID=Vt_ID_next; /*additinVt*/ Vt[Vt_ID_next-200].Tch=ch; Vt_ID_next++; } ifavailable=1; } if(ifavailable){/*tobetransformed*/ pt=CreateNewIDNode; pt->ID=idcurrent;pt->next=NULL; if(pnewnode==NULL){/*notesCR*/ Line_Num++; ppro[Line_Num]=pnewnode=pt; } else{ pnewnode->next=pt; pnewnode=pt; } } ch=fgetc(fp); } returnOK;}StatusFile_Print(FILE*fp){/*printthefileontothescreen*/ charch; printf("FileContent:(Pressanykeytocontinue...)\n"); getch(); ch=fgetc(fp); while(ch!=EOF){ printf("%c",ch); ch=fgetc(fp); } printf("\nPressanykeytocontinue...\n"); getch();}#ifdefDEBUGvoiddebugprint(){ inti; IDNode*pt; for(i=0;i<Vn_ID_next-100;i++){ printf("%c",Vn[i].Nch); } printf("\n"); for(i=0;i<Vn_ID_next-100;i++){ printf("%d",Vn[i].ID); } printf("\n"); for(i=0;i<Vt_ID_next-200;i++){ printf("%c",Vt[i].Tch); } printf("\n"); for(i=0;i<Vt_ID_next-200;i++){ printf("%d",Vt[i].ID); } printf("\n"); for(i=0;i<=Line_Num;i++){ pt=ppro[i]; printf("%d.",i); while(pt){ printf("%d-",pt->ID); pt=pt->next; } printf("END\n"); }}#endifintinsert2link(IDNode**pdes,IDNode*pNode,intiffreeit){ /*insertpNodeto*pdes,withtheordersmalltolarge*/ /*nosame2,ifcan'tinsert,accordingtoiffreeit,freepNodeornot,andreturn0,elsereturn1*/ IDNode*ptd1,*ptd2,*pt=pNode;intcID; if(!iffreeit){ /*ififfreeit==0,itmeansthisnodeisinanotherlink,ican'tchangeit,socopyanewone*/ pt=CreateNewIDNode; pt->ID=pNode->ID; } pt->next=NULL; /*toavoiderror*/ if(*pdes==NULL){/*insertdirectly*/ *pdes=pt; return1;} elseif(pt->ID<=(*pdes)->ID){/*atthehead*/ if(pt->ID!=(*pdes)->ID){ pt->next=*pdes; *pdes=pt; return1; } else{ if(iffreeit)free(pt); return0; } } else{ ptd1=*pdes;ptd2=ptd1->next; if(ptd2)cID=ptd2->ID; elsecID=-1;/*ifatthetail*/ while(ptd2&&(pt->ID>cID)){ ptd1=ptd2;ptd2=ptd2->next; if(ptd2)cID=ptd2->ID; elsecID=-1; } if(pt->ID!=cID){ pt->next=ptd2;ptd1->next=pt; return1; } else{ if(iffreeit)free(pt); return0; } }}intadd2link(IDNode**pdes,IDNode*psrc,intifdelsrc,intifcopyNULL){ /*thereturnvaluenotesifthe*pdesischanged*/ intmark=0,NULLID=getVtID('&');/*returnvalue*/ IDNode*ps=psrc,*pt; while(ps){ if(ifcopyNULL||(ps->ID!=NULLID)){/*about'&'*/ if(ifdelsrc)pt=ps; else{ pt=CreateNewIDNode; pt->ID=ps->ID; } ps=ps->next; pt->next=NULL; mark=insert2link(pdes,pt,1)||mark;/*makesuremarkisintheright*/ } elseps=ps->next; } returnmark;}voidDeleteLink(IDNode*p){/*deletethelinkthatppointsto*/ IDNode*pt; while(p){ pt=p; p=p->next; free(pt); }}voidDeleteAllVnExp(IDNode**pprotemp,intVnID){/*deletallVn'sexpression*/ IDNode*pt; inti; for(i=0;i<=Line_Num;i++){ pt=*(pprotemp+i); if(pt&&(pt->ID==VnID)){ DeleteLink(pt); *(pprotemp+i)=NULL; } }}voidPrintLink(IDNode*pt,charins){/*printLink,useinstodivideeachcharacter,ifins==0,theresultwillbeconsistant*/ intnum; charch; while(pt){ num=pt->ID; if(num>=200) ch=Vt[num-200].Tch; elsech=Vn[num-100].Nch; printf("%c",ch); if(ins&&pt->next)printf("%c",ins); pt=pt->next; }}intCheckVnNoExist(IDNode**pprotemp,intVnID){/*checkwhetherVn'sexpressionexists.ifno,markitNO*/ IDNode*pt; inti; for(i=0;i<=Line_Num;i++){ pt=*(pprotemp+i); if(pt&&(pt->ID==VnID)) return0; } return1;}IDNode*getFirstExp(IDNode*pExp,int*ifgetnull){/*getFirstsetofoneexpressionthatpExppointsto,withno'&'inthereturnlink*//*ifgetnullreturnswhethertheexpcan=>&*/ IDNode*phead=NULL;/*pointtothenewcreatedlink*/ IDNode*pt; while(1){ if(!pExp){/*gettothetail*/ *ifgetnull=1; returnphead; } elseif(pExp->ID>=200){ pt=CreateNewIDNode; pt->ID=pExp->ID;pt->next=NULL; insert2link(&phead,pt,1); *ifgetnull=0; if(pExp->ID==getVtID('&'))*ifgetnull=1;/*incasethatS->&*/ returnphead; } else{/*Vn*/ add2link(&phead,FirstVn[pExp->ID-100],0,0); if(Vn[pExp->ID-100].ifgetnull){ pExp=pExp->next; } else{ *ifgetnull=0; returnphead; } } }/*while*/}intifCross(IDNode*p1,IDNode*p2){/*judgeifp1p2hasthesamenode,ifhasthenprintoutintheformof{.,.,.}*/ IDNode*pt1=p1,*pt2=p2; intID1,ID2,mark=0,r=0; /*marknotesifit'sthefirstsamecharacter,usedtocontrolifprintout','*/ while(pt1){ ID1=pt1->ID; while(pt2){ ID2=pt2->ID; if(ID1==ID2){ if(mark)printf(","); /*ifnotthefirst,print','*/ elseprintf("{"); printf("%c",Vt[ID1-200].Tch); mark=1; r=r||1; /*rstorestheresult*/ } pt2=pt2->next; } pt1=pt1->next; } if(r)printf("}"); /*ifnotLL(1),printtheremaining'}'*/ returnr;}voidgetNULLVn(){/*todecidetheVnthatcandeduct,theresultisstoredinVn[]&*/ inti,j,LeftID; IDNode**pprotemp=(IDNode**)malloc(sizeof(IDNode*)*(Line_Num+1)); IDNode*pt1,*pt2;/*temppointers*/ intifVnChanged;/*markwhethertheifgetnullchangesinstage3*/ charch;/*forprinting*/ for(i=0;i<=Line_Num;i++){ *(pprotemp+i)=NULL; } /*CopyPProArray*/ for(i=0;i<=Line_Num;i++){ pt1=ppro[i]; *(pprotemp+i)=pt2=CreateNewIDNode; pt2->ID=pt1->ID; pt2->next=NULL; while(pt1->next!=NULL){ pt1=pt1->next; pt2->next=CreateNewIDNode; pt2=pt2->next; pt2->ID=pt1->ID; pt2->next=NULL; } }/*#ifdefDEBUG for(i=0;i<=Line_Num;i++){ pt1=pprotemp[i]; printf("%d.",i); while(pt1){ printf("%d-",pt1->ID); pt1=pt1->next; } printf("END\n"); }#endif*/ /*Thesecondstage*/ for(i=0;i<=Line_Num;i++){ pt1=*(pprotemp+i); if(pt1){/*incasethatthislinkwasdeleted*/ LeftID=pt1->ID; pt2=pt1->next;/*pointtotherightpart*/ if(pt2->ID==getVtID('&')){ Vn[LeftID-100].ifgetnull=YES; DeleteAllVnExp(pprotemp,LeftID);/*deletallVn'sexpression*/ } elsewhile(pt2){ if(pt2->ID>=200){/*Vt*/ DeleteLink(pt1);/*Freeallnodes*/ *(pprotemp+i)=NULL; if(CheckVnNoExist(pprotemp,LeftID))/*checkwhetherVn'sexpressionexistsifno,markitNO*/ Vn[LeftID-100].ifgetnull=NO; break; /*stopwhile*/ } pt2=pt2->next; } }/*#ifdefDEBUG for(j=0;j<=Line_Num;j++){ pt1=pprotemp[j]; printf("%d.",j); while(pt1){ printf("%d-",pt1->ID); pt1=pt1->next; } printf("END\n"); } printf("%d\n",i);#endif*/ } /*The3rdStage*/ ifVnChanged=YES; while(ifVnChanged==YES){ ifVnChanged=NO; for(i=0;i<=Line_Num;i++){ pt1=*(pprotemp+i); if(pt1){/*notNULL*/ LeftID=pt1->ID; pt2=pt1->next;/*pointtotherightpart*/ while(pt2){/*notreachthetail*/ if((pt2->ID>=100)&&(pt2->ID<200)){/*Vn*/ switch(Vn[pt2->ID-100].ifgetnull){ caseYES:pt1->next=pt2->next;/*DeleteVn(&)*/ free(pt2); pt2=pt1->next; if((*(pprotemp+i))->next==NULL){/*therightNULL*/ Vn[(*(pprotemp+i))->ID-100].ifgetnull=YES; ifVnChanged=YES; DeleteAllVnExp(pprotemp,LeftID); pt2=NULL;/*forcetoendwhile*/ } break; caseNO:DeleteLink(*(pprotemp+i)); *(pprotemp+i)=NULL; if(CheckVnNoExist(pprotemp,LeftID)){ Vn[LeftID-100].ifgetnull=NO; ifVnChanged=YES; } pt2=NULL;/*forcetoendwhile*/ break; default:pt1=pt2; pt2=pt2->next; } } else{ pt1=pt2;pt2=pt2->next; } } } } } free(pprotemp); /*printout*/#ifdefDEBUG for(i=0;i<Vn_ID_next-100;i++) printf("%c",Vn[i].Nch); printf("\n"); for(i=0;i<Vn_ID_next-100;i++){ switch(Vn[i].ifgetnull){ caseYES:ch='Y';break; caseNO:ch='N';break; default:ch='?'; } printf("%c",ch); } printf("\n");#endif}voidgetFirstVn(){ intifChanged,ifgetnull,i,j,LeftID; IDNode*pt1,*pt2,*pt3; ifChanged=1; while(ifChanged){ ifChanged=0; for(i=0;i<=Line_Num;i++){ pt1=*(ppro+i);pt2=pt1->next; LeftID=pt1->ID; if(pt2->ID>=200){/*x->aORx->&*/ ifChanged=insert2link(FirstVn+LeftID-100,pt2,0)||ifChanged; } else{ pt3=getFirstExp(pt2,&ifgetnull); ifChanged=add2link(FirstVn+LeftID-100,pt3,1,0)||ifChanged; if(ifgetnull){ /*getFirstExp()returnsno'&',butusesifgetnultomarkifitshouldcontain'&'*/ pt2=CreateNewIDNode; pt2->ID=getVtID('&');pt2->next=NULL; ifChanged=insert2link(FirstVn+LeftID-100,pt2,1)||ifChanged; } } }/*for*/ }/*#ifdefDEBUG for(j=0;j<Vn_ID_next-100;j++){ pt1=FirstVn[j]; printf("%d.",j); while(pt1){ printf("%c-",Vt[pt1->ID-200].Tch); pt1=pt1->next; } printf("END\n"); }#endif*/}voidgetFirstRight(){/*getthefirstsetoftherightpartoftheexpression*/ inti,ifgetnull;#ifdefDEBUG intj;#endif IDNode*pt; for(i=0;i<=Line_Num;i++){ pt=ppro[i]->next; pt=getFirstExp(pt,&ifgetnull); if(pt)add2link(FirstRight+i,pt,1,1); if(ifgetnull){ /*getFirstExp()returnsno'&',butusesifgetnultomarkifitshouldcontain'&'*/ pt=CreateNewIDNode; pt->ID=getVtID('&');pt->next=NULL; insert2link(FirstRight+i,pt,1); } }#ifdefDEBUG for(j=0;j<=Line_Num;j++){ pt=FirstRight[j]; printf("%d.",j); while(pt){ printf("%c-",Vt[pt->ID-200].Tch); pt=pt->next; } printf("END\n"); }#endif}voidgetFollow(){/*getfollowset*/ IDNode*pt1,*pt2; inti,LeftID,ifgetnull;/*markifcan=>&*/ intmark;/*notswhetherchange*/ /*add'#'toVt&Follow(S)*/ Vt[Vt_ID_next-200].ID=Vt_ID_next; Vt[Vt_ID_next-200].Tch='#'; Vt_ID_next++; pt1=CreateNewIDNode; pt1->ID=getVtID('#');pt1->next=NULL; Follow[0]=pt1; /*stage2*/ mark=1; while(mark){/*changed*/ mark=0; for(i=0;i<=Line_Num;i++){ pt1=ppro[i]->next; LeftID=ppro[i]->ID; while(pt1){/*pt1!=NULL,toscanfromtheheadtothetailinonelink*/ if((pt1->ID>=100)&&(pt1->ID<200)){/*Vn*/ pt2=