LR实验报告册资料

1、实验三 LR分析实验名称LR语法分析实验要求(1)输入任意文法(2)输出LR分析表(3)输入任意测试语句(4)输出分析过程，判定结果要求提供：(1)数据结构描述(2)算法说明(3)测试截图数据结构描述主要列举了如下几个：1 产生式存储结构s文法开始符号line产生式的个数Gi0产生式的标号Gi1Vt终结符Vn非终结符2 项目集存储结构prjset结构：id项目集编号 Prjt *next指示下一个项目集 Prjt存储项目的编号 ，prjt0项目编号的个数 Pointafter圆点后的字符， pointafter0为字符个数Prjset*actorgo存储出度pointbefore圆点前面的字符

2、3 LR(0)分析表存储结构form动态数组下标，同时作为符号的编号Vn非终结符序列Vt终结符序列（3）存放LR分析表的数据结构实现方法一：用一个二维整数数组表示数组元素为表示动作的整数。数组的行下标为状态号，列下标用来表示终结符与非终结符的整数表示。数组元素可作如下约定： 正整数：表示移进动作，如S6用数6表示； 负整数：表示归约动作，如R5用数-5表示；：表示接受，通常为按产生式0归约；状态号也用整数表示；用不可能是状态号的较大的整数表示错误转移。 请将上述LALR(1)分析表用这种表示方法，完成LR分析器的程序设计，并添加输出状态栈内容的功能。用上述表达式文法G的一个句子作为输入，进行测

3、试。实现方法二：采用压缩表示法动作Action表的每一行用一个数组表示，数组的第一个元素是本数组中存放的数偶个数，第二个元素到最后一个元素都以终结符，动作的数偶的形式存放。再用一个以状态号为下标的下标数组，每个元素含一个指向数偶数组的指针。若数组元素的值为NULL，则表示从此状态无转移弧发出。若分析表有几行相同，则只需保存一行，其它元素则都指向存放这一行表的数组即可。转移Goto表也按同样方式组织，只是这个行数组的数偶为非终结符，下一状态号。 每个行数组Yyan表示动作表Yy_action的一行，每个行数组Yygn表示转移表Yy_goto的一行。假定上述表达式文法G中终结符及非终结符的整数值为

4、： 终结符： # ID + * ( ) 非终结符： S E T F 整数值： 0 1 2 3 4 5 整数值： 0 1 2 3 Yy_action数组是以状态号为下标的下标数组，每个元素含有指向数组Yyan的指针；下标数组Yy_goto的每个元素含有指向数组Yygn的指针。表达式文法G的LALR(1)分析表的具体压缩表示如下：24,2 1,1Yya000Yy_action. 045,-63,-62,-60,-6Yya001 1Yya003 220,02,7 345,-22,-20,-23,8Yya004 4Yya005 45,-43,-42,-40,-4 525,92,7Yya006 6 7Y

5、ya009 845,-53,-52,-50,-5 945,-12,-10,-13,8Yya010 10 Yya011 45,-35,-32,-30,-3 11Yyg000 Yy_goto.NULL.NULLNULL NULLNULL.NULLNULLNULL33,52,41,3 0Yyg002 133,52,41,6 2 3 4 5Yyg007 623,52,10 713,11Yyg008 8 9 10 11 实验原理及算法描述LR分析器由三个部分组成：(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR

6、分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。2. LR分析器的结构为：其中:SP为栈指针，Si为状态栈，Xi为文法符号栈。状态转换表用GOTOi，X=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。1 识别文法的LR(0)项目集规范族的构造采用（闭包）的构造一个文法的项目规范簇。假定是文法的任一项目集，定义和构造的闭包的算法：（1）的任何项目都属于；（2）若属于，那么

7、，对任何关于的产生式，项目也属于；（3）重复执行上述两个步骤直至不再增大。其中初始 ，为对文法进行拓广构造而引进的不出现在中的非终结符。定义状态转换函数，的第一个变元是一个项目集，第二个变元是一个文法符号。函数值定义为。其中 = 任何形如的项目| 属于2 LR(0)分析表的构造 假定。令每个项目集的下标作为分析器的状态。特别是，令那个包含项目的集合的下标为分析器的初态。分析表的子表和子表可按如下方法构造： （1）若项目属于且，为终结符，则置为“把移近栈”，简记为“”。 （2）若项目属于，那么对于任何终结符（或结束符#），置为“用产生式进行规约”，简记为“”（假定产生式是文法的第j个产生式） （3）若项目属于，则置为“接受”，简记为“acc”。 （4）若，则置。 （5）分析表中凡不能用规则14填入信息的空白处均置上“报错标志”。如果分析表中任何一项被重复填入，则说明分析表的入口不是唯一的，项目集中存在冲突项目，该文法不是文法。3 LR(0)分析器总控程序构造分析表包括量部分，“动作”表和“状态转换”表。规定了当状态面临输入符号时应采取什么动作。规定了状态面对文法符号时下一状态是什么。每一项所规定的动作不外乎是下述四种可能之一。（1）移进 把的下一状态和输入符号推进栈，下一输入符号变成现行输入符号。（2）归约 指用某一产生式进行规约