R0分析器自动构造程序的实现详细解.DOC

1、R(0)分析器自动构造程序的实现详细解第一章 概 述 .4第二章 基 本原理 .52.1 识别文法的 LR(0)项目集规范族的构造 .52.2 LR(0)分析表的构造 .52.3 LR(0)分析器总控程序构造 .6第三章 程序设计 .73.1 程序总体构架 .73.2 程序存储结构 .83.2.1 符号表存储结构 .83.2.2 产生式表存储结构 .83.2.3 项目集规范族表存储结构 .93.2.4 LR(0)分析表存储结构 .93.3 程序算法 .103.3.1 项目集规范族的构造 .103.3.2 LR(0)分析表构造 .11第四章 程序测试 .124.1 符号表测试 .124.2 产生

2、式表测试 .134.3 项目集规范族表测试 .134.4 LR(0)分析表测试 .144.5 LR(0)分析器测试 .14第五章 总结和展望 .15参考文献 .16附录 .172第一章 概 述本次实验要求完成以下内容：1. 实现对任意给定的文法 ，识别文法活前缀的 、 的状态转化矩阵GDFA及 项目集规范族的构造；(0)LR2. 判断该文法是否为 文法，实现了 分析表的构造，并输出到指定(0)LR(0)LR文件中；3. 实现了 分析器总控程序，对输入的表达式进行文法分析。(0)3第二章 基本原理本实验的核心算法 Error! Reference source not found.主要有三点：1

3、. 识别文法活前缀的 、 的状态转化矩阵及 项目集规范族的构造；2. 分析表DFA(0)LR(0)LR的构造；3. 分析器总控程序的构造。(0)LR2.1 识别文法的 LR(0)项目集规范族的构造采用 （闭包）的构造一个文法 的 项目规范簇。CLOSUREG(0)LR假定 是文法 的任一项目集，定义和构造 的闭包 的算法：IGI()COSUEI（1） 的任何项目都属于 ；()CLOSURE（2）若 属于 ，那么，对任何关于 的产生式 ，ABIB项目 也属于 ；B()I（3）重复执行上述两个步骤直至 不再增大。()CLOSUREI其中初始 ， 为对文法 进行拓广构造 而引进的不出现在ISEAG中

4、的非终结符。G定义状态转换函数 ， 的第一个变元 是一个项目集，第二个变元G(,)IXI是一个文法符号。函数值 定义为 。XO(,)()XCLOSUREJ其中 = 任何形如 的项目| 属于 JAAI2.2 LR(0)分析表的构造假定 。令每个项目集 的下标作为分析器的状态。特别是，令01,nCI kI那个包含项目 的集合 的下标 为分析器的初态。分析表的 子表和SAkI ACTION4子表可按如下方法构造：GOT（1）若项目 属于 且 ， 为终结符，则置AakI(,)kjGOIa为“把 移近栈” ，简记为“ ”。,ACINka(,)j jS（2）若项目 属于 ，那么对于任何终结符 （或结束符#

5、） ，置kI为“用产生式 进行规约” ，简记为“ ”（假定产生式 是,TIOkAjrA文法 的第 j 个产生式）G（3）若项目 属于 ，则置 为“接受” ，简记为“acc” 。SkI,CTIONka（4）若 ，则置 。(,)kjIAAj（5）分析表中凡不能用规则 14 填入信息的空白处均置上“报错标志” 。如果分析表中任何一项被重复填入，则说明分析表的入口不是唯一的，项目集中存在冲突项目，该文法不是 文法。(0)LR2.3 LR(0)分析器总控程序构造分析表包括两部分， “动作” 表和“状态转换” 表。(0)LRACTIONGOT规定了当状态 面临输入符号 时应采取什么动作。 规定,ACTIO

6、Nsasa,sX了状态 面对文法符号 时下一状态是什么。X每一项 所规定的动作不外乎是下述四种可能之一。,Is（1）移进 把 的下一状态 和输入符号 推进栈，下一输()a,sGOTsXa入符号变成现行输入符号。（2）归约 指用某一产生式 进行规约。假若 的长度为 ,规约的动作Ar是，去除栈顶的 个项，使状态 变成栈顶状态，然后把 的下一状态rmrs (,)mrsA推进栈。规约动作不改变现行输入符号。规约动作不改变现行输,mrsGOTsA入符号。（3）接受 宣布分析成功，停止分析器工作5（4）报错 发现源程序含有错误，调用出错处理程序。第三章 程序设计3.1 程序总体构架LR(0)分析器的实现程

7、序主要由 4 张表组成，分别为：符号表 、产生_SignLst式表 、 表 和项目集规范族表 。同时，_FormulaList(0)R_LTableClosure项目集规范族表包含一个分析栈作为 分析器总控程序。产生式表包含符号表(0)R作为子表，项目集规范族表包含产生式表、 表作为子表。程序工作流程：1. 读取含有文法规则的文件，为该文法中的每一个不同的文法符号（终结符和非终结符分配一个编号） ，记录文法符号的属性（终结符/非终结符） ，存储于一张符号表 中；_SignLst2. 再次读取文件，将产生式存储于产生式表 中；_FormulaList3. 根据产生式构建 项目集规范族，存储于表

8、中；(0)LRCe4. 根据构建的 项目集规范族构建 分析表，填写 分析表同时(0)LR(0)R检查该文法是否为 文法；()5. 对于输入的表达式， 分析器根据构建的 分析表进行文法分析，(0)LR()给出分析结果。63.2 程序存储结构3.2.1 符号表存储结构 _ArayIndex动态数组下标，同时作为符号的编号Iti标识符sV是否为非终结符3.2.2 产生式表存储结构 _FormulaN产生式标号Vne非终结符标号 （与 中的 一致）_SignLst_ArayIndexrl指示当前非终结符 的产生式VName_FomulaLegth当前非终结符 产生式的长度，用于帮助区分一个产生式的不同

9、项目，即项目个数等于 _1FormulaLength_NextVn指示下一个非终结符Siga一个产生式中的标识符名（与 中的_SignLst一致）_ArayIndex_Nextin一个产生式中的下一个标识符73.2.3 项目集规范族表存储结构1）定义二元组 ： _,_ItemNaTypeFormulaNForulaItem：产生式标号，与 中的 一致Forula ListN：一个产生式的第 个项目，可由 中的ItejrlList帮助确定 _orulaLength如：产生式 ： ， WEA1,WEA1,22） 结构：_ClosureLit_GoTSetParnt待构造的 项目的闭包的GoTPar

10、entChild待构造的 项目的闭包urett待构造状态的 arent_nil待构造状态的项目3.2.4 LR(0)分析表存储结构nSa当前状态编号 Next指示下一状态 Im指示闭包中的项目 _tea闭包中的项目名Dsino当前项目的 产生的新状态的编号，即状态转移的otSe目的地状态编号NxtIm闭包中的下一个项目80_LRTableChild指示表头的孩子结点Prnt指示表头的后继结点Opertio指示该表项的操作and指示该表项的操作数_HsBeFil指示该表项是否被填写过,用于判断文法是否为文法(0)LR3.3 程序算法3.3.1 项目集规范族的构造1. （初始化）将初始条件作为该状

11、态头结点的第一个孩子结点，并构造该孩子结点的闭包，连接其后， 指向第一个状态头结点，_GoTSetParnt指向第一个状态头结点的第一个孩子结点；_GoTSetChild2. 查看 ，若为空，停止；若不为空，转 3；Parent3. 查看 ，若为空，转 4；若不为空，构造 的oil _GoTSetChild，检查该状态与之前构造的状态有无重复，若重复，则停止构造，oTSet的 填写重复的已存在的状态的编号；若不重复，则_GChildDestina作为一个新状态，连接于 ，并构造其闭包连接其后，_urtPent指向 。转 2；oTSetilNextS4. 指向下一状态，若下一状态为空，则结束，否

12、则，_Goarn指向下一状态头结点的第一个孩子结点，转 3。etChild具体细节：设 所指项目为 ，因为要对其构造闭包，该项目一定不是_GoTSethild,ij终态，所以区分项目的圆点符号位于第 个标识符的左侧。现在构造 的闭包，,ij9分两个步骤实现：1. 构造 的 ： _GoTSetChildGoTSet查看 中编号为 的产生式，取得该产生式的长度属性FrmuaLngtilet1） 若 ，则停止构造当前闭包（已是终态） ，此时 _1jorleth的 项填 ；GTSetCidDsinao2） 否则，将 作为该闭包的第一个项目 ，此时 ,jitem_GoTSetChild的 项填该新状态的

13、状态编号。estinao2. 构造该孩子结点的闭包 ：查看 中编号为 的产生式的第 个标识符，取得该标识符的_FrmulListi1j，查看 中该标识符的类别属性SignNaeSgnt _IsVn3） 若为 1（非终结符） ，则查看 非终结符 的所有产生 FormulaLitSigName式，记这些产生式的编号为 ，将所有的_SignNe加入闭包_,SignNamei4） 否则，结束3. 检查该状态与之前构造的状态有无重复 :断言：任意两个状态，只要 不同，则即为不同状态。GoTSet3.3.2 LR(0)分析表构造对于编号为 的状态，现依据其项目 填写 分析表：i ,pq(0)LR1. 如果

14、该项目形如 ，查看该项目的 属性，XY A DestinaokDestinao1）若 为终结符，则在表的状态 对应行，对应列，填写 ，表示将把 Yi S移进栈(,)k2）若 为非终结符，则在表的状态 对应行， 对应列，填写 ，表示状态转iYk10移至 状态k2. 如果该项目形如 XYA1）若 为起始符号，则置在表的状态 对应行， 对应列，填写 ，表示接受。Yi#ac2）否则，对任何终结符或结束符 ，则在表的状态 对应行， 对应列，填写#iY，表示用产生式 进行规约。pRp第四章 程序测试以文法 G 为例：WEaAbBcd程序模块输入：含上述文法的文件，下面展示个模块的输出结果4.1 符号表测试输出结果为 与预期结果相同