C语言编写源程序建立LR分析器.docVIP

目 录 前 言 1 用C语言编写源程序建立LR(1)分析器 2 一，设计目的，要求，算法与设计思想 2 1.设计内容 2 2.设计要求 2 3.设计的基本原理 3 1.CLOSURE(I)的构造 3 2.GO(I,X)的构造 3 3.FIRST集合的构造 3 4.LR(1)分析表的构造 3 二，LR（1）分析器 4 1.LR(1)分析器的实现图： 4 2.LR分析器与逻辑结构及工作过程 4 三，总体方案设计 5 1. 各模块设计 6 四，程序测试 7 1.教科书的第142页文法的LR1分析器的构造和语法分析 7 2.表达式文法的LR1分析器的构造和语法分析器 8 五，源程序 10 六，总结 19 七，参考文献 19 前 言 《编译原理》是计算机专业的一门重要的专业课程，其中包含大量软件设计细想。通过课程设计，实现一些重要的算法，或设计一个完整的编译程序模型，能够进一步加深理解和掌握所学知识，对提高自己的软件设计水平具有十分重要的意义。 我选的是老师给的题，并予以扩充。即对任意给定的问法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++语言编写。在Microsoft Visual C++2005环境下调使通过。 用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} 3.FIRST集合的构造 在这个程序中使用的是FIRST(βa)，这基于每一个非终结符的FRIST集合（终结符的FIRST就是它本身）。所以需要对每一个非终结符构造其FIRST集合。 方法如下： 连续使用下面的规则，直到每个集合FIRST不再增大为止。 若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)分析器的实现图： 图1 LR（1）分析器的实现 2.LR分析器与逻辑结构及工作过程 图2 LR分析器的逻辑结构 三，总体方案设计 在main()函数中读入文件，并堆文法进行扩展，同时记录下文法的所有终结符和非终结符，对每个非终结符计算它的FIRST集合。以备在计算CLOSURE(1)时使用。然后调用GO()函数。完成LR(1)项目集组的计算。计算的结果记录到ITEMS.TXT中。并且记录下状态之间转换关系。接下来，调用GET_ACTION()根据上面的项目集族和记录的状态转换数组获得LR(1)分析表。然后就可以对输入的句子进行语法检查