C语言编写源程序建立LR(1)分析器

目录前言................................................................................................................................................2用C语言编写源程序建立LR(1)分析器........................................................................................3一，设计目的，要求，算法与设计思想.......................................................................................31.设计内容...............................................................................................................................32.设计要求...............................................................................................................................33.设计的基本原理...................................................................................................................31.CLOSURE(I)的构造.......................................................................................................32.GO(I,X)的构造.............................................................................................................33.FIRST集合的构造........................................................................................................44.LR(1)分析表的构造.....................................................................................................4二，LR（1）分析器.........................................................................................................................41.LR(1)分析器的实现图：.....................................................................................................42.LR分析器与逻辑结构及工作过程......................................................................................5三，总体方案设计...........................................................................................................................51.各模块设计..........................................................................................................................6四，程序测试...................................................................................................................................81.教科书的第142页文法的LR1分析器的构造和语法分析...............................................82.表达式文法的LR1分析器的构造和语法分析器...............................................................9五，源程序.....................................................................................................................................10六，总结.........................................................................................................................................19七，参考文献.................................................................................................................................19编译原理学年论文2前言《编译原理》是计算机专业的一门重要的专业课程，其中包含大量软件设计细想。通过课程设计，实现一些重要的算法，或设计一个完整的编译程序模型，能够进一步加深理解和掌握所学知识，对提高自己的软件设计水平具有十分重要的意义。我选的是老师给的题，并予以扩充。即对任意给定的问法G构造LR(1)项目集规范族，其中要实现CLOSURE(1)，GO(I,X)，FIRST集合符。在此基础上，构造了LR(1)分析表。然后对输入的句子进行语法分析，给出接受或出错报告。程序采用文件输入输出方式。其中包括两个输入文件：文法grammar.txt，以及输入串input.txt；两个输出文件:项目集items.txt和文法的LR(1)分析表action_table.txt。由于语法分析的结果只给出接受或错误报告，比较简单。所以直接在屏幕上输出，也便于用户查看。在具体编写程序中，对文法操作的各个功能模块独立成为一个子程序，而对具体输入穿得分析则放在main()函数中进行。各个变量奇函数的意义和用法我将在论述程序设计的通体方案中向西给出。程序的通体算法细想来自《编译原理》课程。具体实现有我独立完成。程序用C/C++语言编写。在MicrosoftVisualC++2005环境下调使通过。编译原理学年论文3用C语言编写源程序建立LR(1)分析器一，设计目的，要求，算法与设计思想1.设计内容对任意给定的上下文无关文法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)若项目[A→a.Bβ,a]属于CLOSURE(I)，B→ξ是一个产生式，那么，对于FIRSTβa中的每一个中介符b,如果[β→.ξ,b]原来不在CLOSURE(I)中，则把它加进去；(3)重复执行步骤（2），直到CLOSURE(I)不再增大为止。2.GO(I,X)的构造GO(I,X)=CLOSURE(J)其中J={任何形如[A→aX.Β,a]的项目[A→a.X.Β,a]属于I}编译原理学年论文43.FIRST集合的构造在这个程序中使用的是FIRST(βa)，这基于每一个非终结符的FRIST集合（终结符的FIRST就是它本身）。所以需要对每一个非终结符构造其FIRST集合。方法如下：连续使用下面的规则，直到每个集合FIRST不再增大为止。（1）若X属于VT，则FIRST(X)={X}。（2）若X属于VN，且有产生式X→a…，则把A加入到FIRST(X)中；若X→ξ也是一条产生式，则把ξ也加入到FIRST中。4.LR(1)分析表的构造在实现GO(I,X)时，记录下状态的转化。得到分析表中的移进部分。然后再扫描所有的项目集，找到其中包含归约项目的哪些项目集，根据其中项目，得到分析表中那些鬼月的部分。二，LR（1）分析器1.LR(1)分析器的实现图：图1LR（1）分析器的实现编译原理学年论文52.LR分析器与逻辑结构及工作过程图2LR分析器的逻辑结构三，总体方案设计在main()函数中读入文件，并堆文法进行扩展，同时记录下文法的所有终结符和非终结符，对每个非终结符计算它的FIRST集合。以备在计算CLOSURE(1)时使用。然后调用GO()函数。完成LR(1)项目集组的计算。计算的结果记录到ITEMS.TXT中。并且记录下状态之间转换关系。接下来，调用GET_ACTION()根据上面的项目集族和记录的状态转换数组获得LR(1)分析表。然后就可以对输入的句子进行语法检查。程序中主要变量以及函数的说明如下：charstr_vn[20][20];//存放输入的文法：为简单起见，设问发的产生式条数不多于20条，每个产生式不多与20个字符，用@表示，且产生式输入的时候要以S结束。intlength[20];//每条产生式的长度intnumber=0;//产生式的条数booltempofinput//记录哪些ASCII字符在文法中，以求得所有的VT和VNcharstr_vn[20];//记录所有的非终结符intsize_vn=0;//记录非终结符的个数charstr_vt[150];//记录所有的终结符intsize_vt=0;//记录终结符的个数boolfirst_vn[30][150];//记录每个非终结符的FIRST集charbuffer[50];//用来存放CLOSURE(I)时需要的FIRST_SET也用来读入用户的输入电intbsize=0//buffer的有效长度structthri{intbeg;编译原理学年论文6intnex;charch;};thritrans[200];//定义状态转换组中的元素格式intsize-trans=0;//用来在go()函数中记录状态间的转换trans数组的大小structproj{intpart;charexpc;};//定义项目集的格式projirems[100][100];//项目集数组，假设项目集的个数不超过100个，且每个项目集中的项目个数不超过100个intCCOUNT=0;//项目集的个数intsize_item[100];//每个项目集中的项目个数structaction{charch;//定义状态转换表的格式intnxt_sta;};//定义状态转换表的格式actionaction