您好,欢迎访问三七文档
当前位置:首页 > 临时分类 > 编译原理课程设计-LL(1)文法的判定
课程设计报告课程:编译原理课程设计学号:姓名:班级:教师:时间:计算机科学与技术系1设计名称:LL(1)文法的判定(假设文法符合的First和Follow集未知)设计内容、目的与要求:1、设计内容(1)LL(1)文法的判定(假设文法符合的First和Follow集未知)根据LL(1)分析法编写一个语法分析程序,可根据自己实际情况,选择以下一项作为分析算法的输入:a.直接输入根据已知文法构造的分析表M;b.输入文法的FIRST(α)和FOLLOW(U)集合,由程序自动生成文法的分析表M;c.输入已知文法,由程序自动构造文法的分析表M。(2)所开发的程序可适用于不同的文法和任意输入串,且能判断该文法是否为LL(1)文法。(3)如完成前两项,可增加运行实例,对于输入的文法和符号串,所编制的语法分析程序应能正确判断此串是否为文法的句子,并要求输出分析过程。2、要求:输入文法,输出判定该文法是否是LL(1)的。计划与进度安排:5月20日—5月23日:查阅资料,进一步掌握LL(1)文法的定义,掌握LL(1)分析法及其原理;5月24日—5月26日:分析题目,画出系统的流程图;5月27日—5月29日:根据流程图,将系统功能划分成各个不同的模块;5月30日—5月31日:根据不同的模块,设计与其相对应的函数,并依据分析函数的功能设置函数的参数和返回值;6月1日—6月2日:根据上一步的各个函数,编写对应的代码;6月3日—6月4日:对各个函数进行编译和检查;6月5日—6月6日:编写程序执行的入口函数main()函数,通过调用各个函数,实现整个程序的基本功能;6月7日—6月8日:编写程序执行的入口函数main()函数,通过调用各个函数,实现整个程序的基本功能;6月9日—6月10日:编译整个程序,并根据调试信息进行相应的修改,同时2设计相关的文法进行测试,检查程序是否满足设计要求;6月11日—6月12日:使用不同的实例进行测试,同时修改并完善设计;6月13日—6月17日:完成设计并答辩。设计过程、步骤(可加页):1、数据结构设计数据结构设计的合理性直接关系着系统功能的实现方便与否。本系统的数据结构包含全局变量的定义和一位数组以及二维数组的定义。intcount=0;/*分解的产生式的个数*/intnumber;/*所有终结符和非终结符的总数*/charstart;/*开始符号*/chartermin[50];/*终结符号*/charnon_ter[50];/*非终结符号*/charv[50];/*所有符号*/charleft[50];/*左部*/charright[50][50];/*右部*/charfirst[50][50],follow[50][50];/*各产生式右部的FIRST和左部的FOLLOW集合*/charfirst1[50][50];/*所有单个符号的FIRST集合*/charselect[50][50];/*各单个产生式的SELECT集合*/charf[50],F[50];/*记录各符号的FIRST和FOLLOW是否已求过*/charempty[20];/*记录可直接推出^的符号*/charTEMP[50];/*求FOLLOW时存放某一符号串的FIRST集合*/intvalidity=1;/*表示输入文法是否有效*/intll=1;/*表示输入文法是否为LL(1)文法*/intM[20][20];/*分析表*/charchoose;/*用户输入时使用*/charempt[20];/*求_emp()时使用*/charfo[20];/*求FOLLOW集合时使用*/intdg=0;/*标志输入文法是否是由有递归的文法哈成的LL()*/2、函数设计及其说明(1)intin(charc,char*p)功能:判断一个字符是否在指定字符串中说明:若该字符在指定字符串中,函数返回1;否则返回0。(2)voidMM()功能:构造预测分析表M。3说明:在该函数中,把预测分析表设计成二维数组,构造预测分析表时,文法用其序号代替。(3)voidmenu()功能:设置用户界面。说明:该函数将设计一个人机交互界面,从而选择实现各种功能。(4)voidCh()功能:得到一个不是非终结符的符号。说明:该函数通过调用in(charc,char*p)函数,返回一个不是非终结符的符号。(5)voidmerge(char*d,char*s,inttype)功能:将单个符号或符号串并入另一符号串说明:d指向目标符号串,s指向源串,type=1,源串中的‘ε’一并并入目串;type=2,源串中的‘ε’不并入目串。(6)voidrecur(char*point)功能:分解含有左递归的产生式。说明:完整的产生式在point[]中。(7)voidnon_re(char*point)功能:分解不含有左递归的产生式,即将形如P→*Qa|F的产生式分解为P→*Qa和P→F。说明:完整的产生式在point[]中。(8)intjudge()功能:判断读入的文法是否正确说明:若读入的文法不正确则返回0,否则返回1。(9)voidsyntax()功能:检查输入串是否满足,通过分析表判断。说明:通过分析表判断,检查输入的字符串是否满足。(10)chargrammer(char*t,char*n,char*left,charright[50][50])功能:读入一个文法。说明:char*t指向终结符号的集合;char*n指向非终结符号的集合;char*left指向文法产生式的左部;charright[50][50]传递的参数是文法产生式的右部。(11)voidFOLLOW(inti)4功能:求各产生式左部的FOLLOW集。说明:i为分解后的产生式的序号。(12)voidfirst2(inti)功能:求单个符号的FIRST集。说明:i为符号在所有输入符号中的序号。(13)voidFIRST(inti,char*p)功能:求各产生式右部的FIRST集。说明:i为分解后的产生式的序号;char*p指向产生式的右部。(14)intll1()功能:判断读入文法是否为一个LL(1)文法。说明:若输入的文法是LL(1)文法,返回1,否则报错,返回0。(15)voidemp(charc)功能:求所有能直接推出ε的符号,这里利用^代替ε。说明:charc是需要判断的符号。(16)int_emp(charc)功能:求某一符号能否推出‘ε’说明:charc是需要判断的符号,若能推出,则返回1,否则返回0。3、总控算法及流程(1)推导出非终结符首先进行第一次扫描,把能够直接推出$的非终结符号记录到空串表,把不能直接推出$的符号依次记录下来,然后单个扫描每一个不能直接推出$的符号。扫描这个符号能够直接推出的第一个非终结符记录到一个队列,接下来依次检查队列中每一个元素,把二次能够推出$的符号记录到空串表,把二次也推不出空串的继续送入到队列,然后再从队列取元素扫描,直到队列为空没能找到能够星推导出$的终结符,那么可以确定这个非终结符推导不出$,接下去扫描下一个非终结符。(2)确定FIRST集FIRST集使用以下四个步骤判定:1)、若X∈VTT,则FIRST(X)={X}2)、若X∈VN,且有产生式X→a…,a∈VT则把a加入到FIRST(X)中,即a∈FIRST(X)3)、若X∈VN,且有产生式X→$,则把$也加到FIRST(X)中,即$∈FIRST(X)4)、若X∈VN,Y1,Y2,…,Yi都∈VN,且有产生式X→Y1Y2…Yn。当Y1,..Yi-1=$(1≤i≤n),则FIRST(Y1)-{$},…,FIRST(Yi-1)-{$},FIRST(Yi)都包含在FIRST(X)中,即:FIRST(Yi-1)-{$}∈FIRST(X)所有Y1,…Yn*=$,则把$加到FIRST(X)中,即:FIRST(Yi)∈FIRST(X)5其中第1-3个方法都很好处理,关键是第四个方法判断时首先判断第一个字符为非终结符,设定一个布尔型扫描标志FLAG,赋初值TRUE,接下去依次扫描产生式右部每一个字符Yi,假如第i个字符可以推出空,那么就把这个字符的FIRST集去除$加入到产生式左部字符的FIRST集中,即FIRST(Yi)-{$}ÌFIRST(X),假如Yi是终结符或者不可以推出$,那么就把这个字符的FIRST集直接加入到FIRST(X)中,即FIRST(Yi)ÌFIRST(X)同时置FLAG为FALSE不再向下扫描,假如Yi恰好是最后一个字符,那么不管它能不能星推导出空都直接把它的FIRST集加入到FIRST(X)中。同时要设置一个队列和一组布尔型变量记录FIRST集是否完成,队列用来记录FIRST(X)用到了哪些其它非终结符的FIRST集。第一遍扫描完成后就扫描队列,把FIRST集完成的非终结符的FIRST集加入到那些没有完成的非终结符的FIRST集中去,没有完成的非终结符再送回到队列,这时候可能出现死循环,比如FIRST(S)用到了FIRST(A),而FIRST(A)用到了FIRST(B),FIRST(B)又用到了FIRST(S),这时候S,A,B的FIRST标志均为FALSE,无限循环下去。这时候可以记录一下,比如循环了100次,强行设置FIRST(S)的标志为TRUE,那么FIRST(A),FIRST(B)也就依次可以求出了。我们在实际计算时也是这样处理的,只是没有把标志写出来而是记录在心里的。(3)确定FOLLOW集FOLLOW集使用以下三个步骤判定:1)、如果X是开始符那么把#加入到FOLLOW(X)2)、若A=αBβ是一个产生式,则把FIRST(β)-{$}加至FOLLOW(B)中3)、若A=αB是一个产生式,或A=αBβ是一个产生式而β*=$(即$∈FIRST(β)),则把FOLLOW(A)加至FOLLOW(B)中。FOLLOW集的求法与FIRST集类似,但有不同的地方。FOLLOW集需要扫描每一个产生式。而FIRST集扫描的是产生式左部不同的产生式,然后扫描左部相同的产生式的每一个右部。FOLLOW集第一次扫描可以确定哪些FIRST集或FOLLOW集属于所求的FOLLOW集,由于FIRST集已经求出,所以第一次扫描就可以把相应的FIRST集加入到FOLLOW集中,设置FOLLOW集完成标记位,设置队列,把未完成的非终结符送入队列,依次取出队列元素,把求出FOLLOW集的非终结符的FOLLOW集加入到相应的FOLLOW集中,把未求出的送回队列。如果碰到死循环使用FIRST集一样的方法处理就可以。(4)确定SELLECT集FIRST集&FOLLOW集都已经求出来后SELLECT集就很好求了,扫描每一个产生式,使用以下三个步骤确定:A→αA∈VN,α∈V*,1)、若α是终结符,那么SELLECT(A→α)={α};2)、若α是$,则SELECT(A→α)=FOLLOW(A);3)、若α是非终结符,那么若α*=$,则SELECT(A→α)=(FIRST(α)-$)∪FOLLOW(A);若α┐*=$则SELECT(A→α)=FIRST(α)。(5)LL(1)文法的判定当SELLECT集求出来后就可以判断是不是一个文法是不是LL(1)文法了,扫描产生式左部相同的SELLCET集是否含有相同元素,一旦发现相同元素立刻返回0,扫描结束没有发现相同元素则返回1。6(6)句子的判定当一个文法确定是LL(1)文法时就可以对输入的语句进行判定了。首先要安装SELLECT集生成LL(1)预测分析表,最简单的方法是使用哈希表来表示,把每一个产生式左部依次和这个产生式SELLECT集中的每一个终结符组成关键字,其值即为这个产生式,送入哈希表。这样在进行句子的分析时就可以很容易判断是否使用某一个产生式来进行规约。在实际分析时设置两个栈,把#压入分析栈和剩余栈,把开始符压入分析栈,把输入串从右向左送入剩余栈,然后只要两个栈元素个数同时大于1,那么依次从两个栈中取出两个元素进行比较,假如一样就匹配,假如可以规约就规约,否则就不
本文标题:编译原理课程设计-LL(1)文法的判定
链接地址:https://www.777doc.com/doc-1865615 .html