编译原理课程设计-LL文法的判定

《编译原理课程设计-LL文法的判定》由会员分享，可在线阅读，更多相关《编译原理课程设计-LL文法的判定（37页珍藏版）》请在金锄头文库上搜索。

1、课程设计报告编译原理课程设计课程 学号 姓名 班级 教师 时间计算机科学与技术系设计名称：LL (1)文法的判定(假设文法符合的First和Follow集未知)设计内容、目的与要求：1、设计内容(1) LL(1)文法的判定(假设文法符合的First和Follow集未知)根据LL(1) 分析法编写一个语法分析程序，可根据自己实际情况，选择以下一项作为分 析算法的输入：a. 直接输入根据已知文法构造的分析表M;b. 输入文法的FIRST(a)和FOLLOW(U)集合，由程序自动生成文法的分析表M；c. 输入已知文法，由程序自动构造文法的分析表M。(2) 所开发的程序可适用于不同的文法和任意输入串，

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日：根

3、据上一步的各个函数，编写对应的代码；6月3日一6月4日：对各个函数进行编译和检查；6月5日一6月6日：编写程序执行的入口函数main ()函数，通过调用各个 函数，实现整个程序的基本功能；6月7日一6月8日：编写程序执行的入口函数main ()函数，通过调用各个 函数，实现整个程序的基本功能；6月9日一6月10日：编译整个程序，并根据调试信息进行相应的修改，同时设计相关的文法进行测试，检查程序是否满足设计要求;6月11日一6月12日:6月13日一6月17日:使用不同的实例进行测试,完成设计并答辩。同时修改并完善设计;设计过程、步骤(可加页)：1、数据结构设计数据结构设计的合理性直接关系着系统功

4、能的实现方便与否。本系统的数据结构包含全局变量的定义和一位数组以及二维数组的定义。int count=0;/*分解的产生式的个数*/int number;/*所有终结符和非终结符的总数*/char start;/*开始符号*/char termin50;/*终结符号*/char non_ter50;/*非终结符号*/char v50;/*所有付号*/char left50;/*左部*/char righ t 5050;/*右部*/char first5050,follow5050;/*各产生式右部的 FIRST 和左部的FOLLOW 集合*/char firs t1 5050;/*所有单个符号

5、的FIRST集合*/char selec t 5050;/*各单个产生式的SELECT集合*/char f50,F50;/*记录各符号的FIRST和FOLLOW是否已求过*/char empty20;/*记录可直接推出的付号*/char TEMP50;/*求FOLLOW时存放某 符号串的FIRST集合*/int validity=1;/*表示输入文法是否有效*/int ll=1;/*表示输入文法是否为LL(1)文法*/int M2020;/*分析表*/char choose;/*用户输入时使用*/char empt20;/*求_emp()时使用*/char fo20;/*求FOLLOW集合时使

6、用*/int dg=0;/*标志输入文法是否是由有递归的文法哈成的LL()*/2、函数设计及其说明(1) int in(char c,char *p)功能：判断个字符是否在指定字符串中说明：若该字符在指定字符串中，函数返回1；否则返回0。(2)void MM()功能：构造预测分析表M。说明：在该函数中，把预测分析表设计成二维数组，构造预测分析表时，文法 用其序号代替。(3) void menu()功能：设置用户界面。说明：该函数将设计一个人机交互界面，从而选择实现各种功能。(4) void Ch()功能：得到一个不是非终结符的符号。说明：该函数通过调用in(char c,char *p)函数，

7、返回一个不是非终结符的 符号。(5) void merge(char *d,char *s,int type) 功能：将单个符号或符号串并入另一符号串说明：d指向目标符号串，s指向源串，type = l，源串中的 一并并入 目串；type = 2，源串中的不并入目串。(6) void recur(char *point) 功能：分解含有左递归的产生式。 说明：完整的产生式在point中。(7) void non_re(char *point)功能：分解不含有左递归的产生式，即将形如P-*Qa|F的产生式分解为P f*Qa 和 PF。说明：完整的产生式在point中。(8) int judge(

8、)功能：判断读入的文法是否正确 说明：若读入的文法不正确则返回0,否则返回1。(9) void syntax()功能：检查输入串是否满足，通过分析表判断。 说明：通过分析表判断，检查输入的字符串是否满足。(10) char grammer(char *t,char *n,char *left,char right5050) 功能：读入一个文法。说明：char *七指向终结符号的集合；char *n指向非终结符号的集合；char * left指向文法产生式的左部；charrigh t5050 传递的参数是文法产生式的右部。(11) void FOLLOW(int i) 功能：求各产生式左部的FO

9、LLOW集。说明：i为分解后的产生式的序号。(12) void first2(int i)功能：求单个符号的FIRST集。说明：i为符号在所有输入符号中的序号。(13) void FIRST(int i,char *p)功能：求各产生式右部的FIRST集。说明：i为分解后的产生式的序号；char *p指向产生式的右部。(14) int lll()功能：判断读入文法是否为一个LL(1)文法。说明：若输入的文法是LL(1)文法，返回1,否则报错，返回0。(15) void emp(char c)功能：求所有能直接推出的符号，这里利用Y弋替。说明：char c是需要判断的符号。(16) int _e

10、mp(char c)功能：求某一符号能否推出说明：char c是需要判断的符号，若能推出，则返回1,否则返回0。3、总控算法及流程(1) 推导出非终结符首先进行第一次扫描，把能够直接推出$的非终结符号记录到空串表，把不 能直接推出$的符号依次记录下来，然后单个扫描每一个不能直接推出$的符号。 扫描这个符号能够直接推出的第一个非终结符记录到一个队列，接下来依次检查 队列中每一个元素，把二次能够推出$的符号记录到空串表，把二次也推不出空 串的继续送入到队列，然后再从队列取元素扫描，直到队列为空没能找到能够星 推导出$的终结符，那么可以确定这个非终结符推导不出$,接下去扫描下一个非 终结符。(2)

11、确定FIRST集FIRST集使用以下四个步骤判定：1) 、若 XeVTT，则 FIRST(X)二X2) 、若XGVN，且有产生式X-a，aeVT则把a加入到FIRST(X)中，即aeFIRST(X)3) 、若XeVN,且有产生式X-$，则把$也加到FIRST(X)中，P$GFIRST(X)4) 、若 XeVN, Y1，Y2，Yi 都eVN，且有产生式 XY1Y2-Yno当 Y1，.Yi-1二$ (1WiWn)，贝 UFIRST(Y1)-$,，FIRST(Yi-1)- $， FIRST(Yi)都包含在 FIRST(X)中，即：FIRST(Yi-1)-$ eFIRST(X)所有Y1,Yn *= $

12、，则把$加到FIRST(X)中，即：FIRST(Yi) eFIRST(X)其中第1-3个方法都很好处理，关键是第四个方法判断时首先判断第一个字 符为非终结符，设定一个布尔型扫描标志FLAG，赋初值TRUE，接下去依次扫描 产生式右部每一个字符Yi，假如第i个字符可以推出空，那么就把这个字符的 FIRST集去除$加入到产生式左部字符的FIRST集中，即 FIRST(Yi)-$iFIRST(X)，假如Yi是终结符或者不可以推出$，那么就把这个字 符的FIRST集直接加入到FIRST(X)中，即FIRST(Yi)IFIRST(X)同时置FLAG为 FALSE不再向下扫描，假如Yi恰好是最后一个字符，

13、那么不管它能不能星推导 出空都直接把它的FIRST集加入到FIRST(X)中。同时要设置一个队列和一组布 尔型变量记录FIRST集是否完成，队列用来记录FIRST(X)用到了哪些其它非终 结符的FIRST集。第一遍扫描完成后就扫描队列，把FIRST集完成的非终结符的FIRST集加入 到那些没有完成的非终结符的FIRST集中去，没有完成的非终结符再送回到队 列，这时候可能出现死循环，比如F IRST(S)用到了 FIRST(A),而FIRST(A)用到 了 FIRST(B)，FIRST(B)又用到了 FIRST(S),这时候 S,A,B 的 FIRST 标志均为 FALSE，无限循环下去。这时候

14、可以记录一下，比如循环了 100次，强行设置 FIRST(S)的标志为TRUE，那么FIRST(A),FIRST(B)也就依次可以求出了。我们在 实际计算时也是这样处理的，只是没有把标志写出来而是记录在心里的。(3) 确定FOLLOW集FOLLOW集使用以下三个步骤判定：1) 、如果X是开始符那么把#加入到FOLLOW(X)2) 、若A=aBB是一个产生式，则把FIRST(B) $加至FOLLOW(B)中3) 、若A=aB是一个产生式，或A二aBB是一个产生式而B*二$(即$ FIRST(B),则把 FOLLOW(A)加至 FOLLOW(B)中。FOLLOW集的求法与FIRST集类似，但有不同

15、的地方。FOLLOW集需要扫描每 一个产生式。而FIRST集扫描的是产生式左部不同的产生式，然后扫描左部相同 的产生式的每一个右部。FOLLOW集第一次扫描可以确定哪些FIRST集或FOLLOW 集属于所求的FOLLOW集，由于FIRST集已经求出，所以第一次扫描就可以把相 应的FIRST集加入到FOLLOW集中，设置FOLLOW集完成标记位，设置队列，把未 完成的非终结符送入队列，依次取出队列元素，把求出FOLLOW集的非终结符的 FOLLOW集加入到相应的FOLLOW集中，把未求出的送回队列。如果碰到死循环使 用FIRST集一样的方法处理就可以。(4) 确定 SELLECT 集FIRST集&FOLLOW集都已经求出来后SELLECT集就很好求了，扫描每一个 产生式，使用以下三个步骤确定：Aa AeVN，aEV *，1) 、