《C语言编写源程序建立LR(1)分析器1.doc》由会员分享，可在线阅读，更多相关《C语言编写源程序建立LR(1)分析器1.doc（19页珍藏版）》请在三一办公上搜索。
1、精选优质文档-倾情为你奉上目 录前 言编译原理是计算机专业的一门重要的专业课程，其中包含大量软件设计细想。通过课程设计，实现一些重要的算法，或设计一个完整的编译程序模型，能够进一步加深理解和掌握所学知识，对提高自己的软件设计水平具有十分重要的意义。我选的是老师给的题，并予以扩充。即对任意给定的问法G构造LR(1)项目集规范族，其中要实现CLOSURE(1)，GO(I,X)，FIRST集合符。在此基础上，构造了LR(1)分析表。然后对输入的句子进行语法分析，给出接受或出错报告。程序采用文件输入输出方式。其中包括两个输入文件：文法grammar.txt，以及输入串input.txt；两个输出文件:
2、项目集items.txt和文法的LR(1)分析表action_table.txt。由于语法分析的结果只给出接受或错误报告，比较简单。所以直接在屏幕上输出，也便于用户查看。在具体编写程序中，对文法操作的各个功能模块独立成为一个子程序，而对具体输入穿得分析则放在main()函数中进行。各个变量奇函数的意义和用法我将在论述程序设计的通体方案中向西给出。程序的通体算法细想来自编译原理课程。具体实现有我独立完成。程序用C/C+语言编写。在Microsoft Visual C+2005环境下调使通过。用C语言编写源程序建立LR(1)分析器一，设计目的，要求，算法与设计思想1.设计内容 对任意给定的上下文无
3、关文法G，构造其LR(1)项目集族，并且在此基础上进一步构造其LR(1)分析表。然后分析输入的句子。2.设计要求对输入的文法G（要求是上下文无关文法），在程序终实现CLOSURE(1),GO(I,X)，FRIST等的构造，并利用这些功能函数构造出LR(1)项目集族。并且输出结果。在此基础上构造G的LR(1)分析表（这个表也输出给用户），并对输入的句子进行语法分析表，给出分析结果。3.设计的基本原理1.CLOSURE(I)的构造CLOSURE(I)表示和I中项目可以识别同样活前缀的所有项目的集合。它可以有以下方法得到：(1)I中的所有项目都属于CLOSURE(I)；(2)若项目Aa.B,a属于C
4、LOSURE(I)，B是一个产生式，那么，对于FIRST中的每一个中介符b,如果.,b原来不在CLOSURE(I)中，则把它加进去；(3)重复执行步骤（2），直到CLOSURE(I)不再增大为止。2.GO(I,X)的构造GO(I,X)=CLOSURE(J)其中J=任何形如AaX.,a的项目Aa.X.,a属于I3.FIRST集合的构造在这个程序中使用的是FIRST(a)，这基于每一个非终结符的FRIST集合（终结符的FIRST就是它本身）。所以需要对每一个非终结符构造其FIRST集合。方法如下：连续使用下面的规则，直到每个集合FIRST不再增大为止。（1） 若X属于VT，则FIRST(X)=X。
5、（2）若X属于VN，且有产生式Xa，则把A加入到FIRST(X)中；若X也是一条产生式，则把也加入到FIRST中。4.LR(1)分析表的构造在实现GO(I,X)时，记录下状态的转化。得到分析表中的移进部分。然后再扫描所有的项目集，找到其中包含归约项目的哪些项目集，根据其中项目，得到分析表中那些鬼月的部分。二，LR（1）分析器1.LR(1)分析器的实现图：图1 LR（1）分析器的实现2.LR分析器与逻辑结构及工作过程图2 LR分析器的逻辑结构三，总体方案设计在main()函数中读入文件，并堆文法进行扩展，同时记录下文法的所有终结符和非终结符，对每个非终结符计算它的FIRST集合。以备在计算CLO
6、SURE(1)时使用。然后调用GO()函数。完成LR(1)项目集组的计算。计算的结果记录到ITEMS.TXT中。并且记录下状态之间转换关系。接下来，调用GET_ACTION()根据上面的项目集族和记录的状态转换数组获得LR(1)分析表。然后就可以对输入的句子进行语法检查。程序中主要变量以及函数的说明如下：char str_vn2020; / 存放输入的文法：为简单起见，设问发的产生式条 数不多于20条，每个产生式不多与20个字符，用 表示，且产生式输入的时候要以S结束。int length 20; / 每条产生式的长度int number=0; / 产生式的条数bool tempofinput
7、 /记录哪些ASCII字符在文法中，以求得所有的VT和VNchar str_vn20; /记录所有的非终结符int size_vn=0; /记录非终结符的个数char str_vt150; /记录所有的终结符int size_vt=0; /记录终结符的个数bool first_vn30150; /记录每个非终结符的FIRST集char buffer50; /用来存放CLOSURE(I)时需要的FIRST_SET 也用来读入用户的输入电int bsize=0 / buffer的有效长度struct thri int beg; int nex; char ch; ; thri trans200;
8、/定义状态转换组中的元素格式 int size-trans=0; /用来在go()函数中记录状态间的转换trans数组 的大小 struct proj int part; char expc; ; /定义项目集的格式 proj irems100100; /项目集数组，假设项目集的个数不超过100个， 且每个项目集中的项目个数不超过100个 int CCOUNT=0; /项目集的个数 int size_item100; /每个项目集中的项目个数 struct action char ch; /定义状态转换表的格式int nxt_sta; ; /定义状态转换表的格式action action_ta
9、ble100100; /状态转换表 int size_act_table100; / 输入文法的文件指针ifstream G_ifile; / 输入句子的文件指针ofstream input_ifile; / 输出项目集族的文件指针ofstream items_ofile; / 输出转换表的文件指针void read_G() / 计算每个非终结符的FIRST集合void get_first() / 判断项目temp是否已经在项目集族 itemsT中 bool is_in(proj temp,int,T) / 计算itemTclosure(1)时用到的frst(a) void e_closure
10、(intT) / 计算itemsT的closure闭包 int is_containd() /判断新生成的项目集是否已经de 在项目集 族中 void go() /实现go(1)的功能 void get_action() /生成LR(1)表 int main() / 调用个个子模块，并在其中堆输入串进行语法分析1. 各模块设计1.读入模块：Read_G()文法要为上下无关文法。输入文件的格式为：首先输入产生式的条数：每条产生式的第一个字符为非终结符。以S结尾。输入的同时用tempofinputtemp=true来记录符temp。为统计有哪些非终结符和终结符作准备。这些都通过ASCLL码对应位是
11、否为true来判断。2.计算FIRST模块：get_first()现设计FLAG1表示本轮扫描first_vn中有没有新增加的内容。要是有，还有进行下一次扫描。每一轮扫描所有的产生式，在扫描每一个产生式的时候，设置一个下标指针t用来保证不会扫过本产生式，还设置flag表示t的位置是否式一个可以推导出的非终结符。是的话，还有进行下一个t位置的检查。如果t走到产生式的最后位置的下一个位置，则表明属于此产生式左边非终结符的first集合。3.判断项目数是否在项目集里：is_in(proj temp,int T)Scan项目集原有的每一个项目，和新生成的项目作比较。若有相同的就返回true，否则返回f
12、alse。4. 获得计算closure(I)时需要的First(a):gete_expc(proj temp)设计Flag表示是否还要进行下一轮计算，若处理的位置已经查过了产生式的长度，则直接把项目中的那个搜索字符添加进去。这个模块的返回结果放在BUFFER数据中。5.项目集的CCLUSER计算：e_closure(int T)在GO()函数中会产生itemsT的一些基本项目。对itemsT中已经有的每一个项目检查在“。”之后的是否为非终结符；若是，则计算FIRST(a)，把每一个BUFFER中的元素和相应的产生式构成一个项目，加入到项目集中。（注意，此时的项目记得大小时随着项目的不断加入而变
13、大的，所以可以用FOR循环保证项目集中不会有错误。6.检查项目集是否已经在项目族里：is_contation()把已经有的项目集和新生成的项目集进行比较，要是有相等的话则表示已经存在相同的项目集合，此时返回相同的那个项目集的编号，否则，返回0.四，程序测试。7.GO()函数地实现：第一步制作一个初始项目（即扩展文法的第一条产生式），然后用e_closure构造项目集0.在程序中Ccount制作项目集的计数从0开始到（包括n)，所以在for循环中是。即扫描每一个项目集，对每一个项目在“.”之后的终结符，向后移动一位“.”的位置生成新的项目，暂存在buf数组中。然后预生成项目集，并且求其closu
14、re，再判断新的项目集是否已经存在，若存在了，就删除这个项目集，并设置相应的trans。否则就生成的项目集，也设置相应的trans。在以上过程中，每次确定生成一个项目集的时候都把它输出到items.txt中。8. LR(1)分析表的构造get_action()Scan 每一个项目集，若其中有规约项目，则转换表增加一个归约（用负值表示）。然后，根据trans 数组中的元素，构造转换表的移进项（用正值表示）。接受项目也是一个归约项，用0表示。生成的转换表输出到action_table.txt中。9. 堆输入串的语法分析：在main()中实现用stack模拟语法分析的过程，先在stack 中放入（0
15、，#），然后，用当前栈项状态和当前输入字符查找action_table。根据action_table中的值的情况做相应处理（即执行移进和归约动作）。若遇到接受项目则给出接受提示，程序结束。若遇到出错的情况给出出错提示，页结束程序。四，程序测试本程序在Dev_C+和Microsoft Visual C+2005中调试通过。下面给出两个调试实例：1.教科书的第142页文法的LR1分析器的构造和语法分析输入文法： 3 EBBS BaBS BbS 生成的项目集族： 生成的转换表： 输入句子测试：图3 输入句子运行结果2.表达式文法的LR1分析器的构造和语法分析器 生成的项目集族：图4 生成的项目集组表
16、 生成的转换表： 输入句子测试图5 输入句子运行结果五，源程序 /* Name: LR(1)分析器的构造 Author: ELNUR Date: 08-06-07 Description: 输入文法，构造出相应的LR(1)分析器 */#includeiostreamusing namespace std;char G2020; /use a matrix to store grammar Gint length20; /length use to store each formulas lengthint number = 0;bool tempofinput150; /buffer of i
17、nputchar str_vn20; /put all vn into itint size_vn = 0; char str_vt150; /put all vt into itint size_vt = 0;bool first_vn30150;char buffer50; /用来存放生成LR（1） 项目集时需要的first_set int bsize = 0;struct thri int beg; int nex; char ch;thri trans200;int size_trans = 0;/*定义项目集的形式 */struct proj int formula_numb; in
18、t part; char expc;proj items100100;int Ccount = 0;int size_item100;void Read_G() cin number; /user should give the number of formula first for(int i = 1; i temp; while(temp != $) tempofinputtemp = true; Gij+ = temp; cin temp; lengthi = j; G00 = S; G01 = G10; length0 = 2; for(int i = 0; i 64; i+) if(
19、tempofinputi) str_vtsize_vt+ = i; for(int i = 91; i 128; i+) if(tempofinputi) str_vtsize_vt+ = i; for(int i = 65; i 91; i+) if(tempofinputi) str_vnsize_vn+ = i; /*for(int i = 0; i size_vn; i+) cout str_vni ; cout endl endl; cout size: size_vt endl; for(int i = 0; i size_vt; i+) cout str_vti ; cout e
20、ndl; */ void get_first() bool flag1; do flag1 = false; for(int i = 1; i = A & Git = Z) for(int k = 0; k 64; k+) if(first_vnGit-Ak = true & !first_vnGi0-Ak) first_vnGi0-Ak = true; flag1 = true; for(int k = 91; k 128; k+) if(first_vnGit-Ak = true & !first_vnGi0-Ak) first_vnGi0-Ak = true; flag1 = true;
21、 if(first_vnGit-A64 = true) t+; flag2 = true; else if(!first_vnGi0-A Git ) first_vnGi0-A Git = true; flag1 = true; while(flag2 & t lengthi); if(t = lengthi) first_vnGi0-A26 = true; while(flag1);/*j判断项目数否在项目集里*/bool is_in(proj temp,int T) for(int i = 0; i = lengthtemp.formula_numb) bufferbsize+ = tem
22、p.expc; return; else if(Gtemp.formula_numbtt+1 Z) bufferbsize+ = Gtemp.formula_numbtt+1; return; else if(Gtemp.formula_numbtt+1 = A & Gtemp.formula_numbtt+1 = Z) for(int i = 0; i 64; i+) if(first_vn Gtemp.formula_numbtt+1-A i) bufferbsize+ = i; for(int i = 91; i 128; i+) if(first_vn Gtemp.formula_nu
23、mbtt+1-A i) bufferbsize+ = i; if(first_vn Gtemp.formula_numbtt+1-A 64) tt+; flag = true; while(flag);void e_closure(int T) /cout T: T , size_itemT endl; for(int i = 0; i = A & GitemsTi.formula_numbitemsTi.part = Z) for(int j = 0; j 20; j+) if(Gj0 = GitemsTi.formula_numbitemsTi.part) gete_expc(itemsT
24、i); for(int k = 0; k bsize; k+) temp.formula_numb = j; temp.part = 1; temp.expc = bufferk; if(!is_in(temp,T) itemsTsize_itemT+ = temp; bsize = 0; /* for(int i = 0; i size_itemT; i+) printf(%d , %d , %cn,itemsTi.formula_numb,itemsTi.part,itemsTi.expc); cout * endl;*/ return ;int is_contained() for(in
25、t i = 0; i Ccount; i+) int s = 0; /记录有多少是匹配的 if(size_itemi = size_itemCcount) for(int j = 0; j size_itemCcount; j+) for(int k = 0; k size_itemi; k+) if(itemsCcountj.formula_numb = itemsik.formula_numb) & (itemsCcountj.part = itemsik.part) & (itemsCcountj.expc = itemsik.expc) s+; break; if(s = size_i
26、temCcount) return i; return 0;void go() proj init; init.expc = #; init.formula_numb = 0; init.part = 1; items00 = init; size_item0+; e_closure(0); cout I0: endl; for(int i = 0; i size_item0; i+) printf(%d , %d , %cn,items0i.formula_numb,items0i.part,items0i.expc); cout * endl; bool beginflag = true;
27、 for(int index = 0; (index Ccount) | beginflag ; index+) beginflag = false; for(int j = 0; j size_vt; j+) proj buf50; int buf_size = 0; proj tp; int ccc = 0; for(int p = 0; p size_itemindex; p+) if(itemsindexp.part length itemsindexp.formula_numb ) & ( G itemsindexp.formula_numb itemsindexp.part = s
28、tr_vtj) ) tp.formula_numb = itemsindexp.formula_numb; tp.expc = itemsindexp.expc; tp.part = itemsindexp.part+1; bufbuf_size+ = tp; /ccc+; printf(/I%d - %c:n,index,str_vtj); if(buf_size != 0) Ccount+; for(int t = 0; t buf_size; t+) itemsCcount size_itemCcount+ = buft; e_closure(Ccount); int next_stat
29、e = is_contained(); /看生成的项目集是否已经在项目集族中了 if(next_state != 0) size_itemCcount = 0; Ccount-; transsize_trans.beg = index; transsize_trans.nex = next_state; transsize_trans.ch = str_vtj; size_trans+; else cout I Ccount : endl; for(int i = 0; i size_itemCcount; i+) printf(%d , %d , %cn,itemsCcounti.formula_numb,itemsCcounti.part,itemsCcounti.expc); cout * endl; transsize_trans.beg = index; transsize_trans.nex = Ccount; transsize_trans.ch = str_vtj; size_trans+; /对文法的每一个终结符 for(int j = 0; j size_vn; j+) proj buf50; int buf_size = 0; proj tp;
