《LR分析法》PPT课件.ppt

第七章LR分析法 1965年 D knuth首先提出了LR K 文法及LR K 分析技术 LR K 分析是指自左向右扫描和自底向上的语法分析 且在分析的每一步 只须根据分析栈中当前已移进和归约出的全部文法符号 并至多再向前查看K个输入符号 就能确定相当于某一产生式右部符号的句柄是否已在分析栈的顶部形成 从而也就可以确定所应采取的分析动作 是移进输入符号还是按某产生式进行归约 当前扫描到Xn 1 向前查看k个符号 来确定是把Xn 1移进栈 还是把Xi Xn作为句柄进行归约 1 要归约时 则根据某产生式U XiXi 1 Xn进行归约 X1X2 Xi 1UXn 1Xn 2 Xn k 续页 LR 0 表示在每一步分析时都不用向前输入符号LR 1 表示在每一步分析时都向前看一个输入符号来决定当前的动作 SLR 1 表示简单的LR 1 即只在动作不唯一的地方向前看一个符号 在动作唯一时则不向前看输入符号 7 1LR分析概论 一 LR分析器的逻辑结构及工作过程从逻辑上来说 一个LR分析器如图7 1所示 图7 1LR分析器的逻辑结构 即一个LR k 分析器主要由 总控程序 分析栈 状态栈和符号栈 输入队列和分析表组成 一般来说所有LR分析器的总控程序基本上是大同小异 只有分析表各不相同 一般主要讨论三种不同的分析表的构造方法 第一种称为规范LR分析表构造法 用此法构造的分析表功能最强而且也适合于很多文法 但实现代价比较高 第二种称为简单LR 即SLR 分析表构造法 这是一种比较容易实现的方法 但SLR分析表的功能太弱 而且对某些文法可能根本就构造不出相应的SLR分析表 第三种称为向前LR 即LALR 分析表构造法 这种方法构造的分析表功能介于规范LR分析表SLR分析表之间 这种表适用于绝大多数程序语言的文法 而且也可以设法有效的实现 二 LR分析器的分析过程如下 1 首先将初始状态S0及句子的左界限 分别压入状态栈和符号栈中 则用栈顶状态Sm和当前扫描符ai组成符号对 Sm ai 去查分析动作表 根据ACTION Sm ai 的指示完成相应的分析动作 表中每一表元素所规定的动作仅能是下列四种动作之一 2 设在分析中的某一步 分析栈及余留的输入串为如下格局 S0S1 Smaiai 1 an X1 Xm 1 ACTION Sm ai Sm 1 移进 表明句柄尚未在栈顶形成 此时正期待移进输入符号以便形成句柄 故将当前的输入符号和表元素Sm 1分别压入栈中 有 2 ACTION Sm ai Rj 归约 表明此时应按文法的第j个产生式A Xm k 1Xm k 2 Xm进行归约 即栈顶符号串Xm k 1Xm k 2 Xm已成为当前句型的句柄 所谓按第j个产生式归约 就是将分析栈中从顶向下的k个符号退栈 然后将文法符号A压入符号栈中 此时分析的格局为 S0S1 Sm kaiai 1 an X1 Xm kA 然后以 Sm k A 去查状态转移表 设GOTO Sm k A Sl 则将此新状态压入状态栈中 则有如下格局 S0S1 Sm kSlaiai 1 an X1 Xm kA 3 ACTION Sm ai acc 接受 表明当前的输入串已被成功地分析完毕 应停止分析器的工作 其中Z为文法开始符号S 为使ACTION S acc的唯一状态 接受状态 4 ACTION Sm ai ERROR 空白 表明当前的输入串中含有错误 也应终止当前的分析工作 转出错处理 3 重复上述第2步的工作 直到分析栈顶出现 接受状态 或 出错状态 为止 对接受状态 分析栈的格局为 S0S Z 例 有文法G S 1 S aAcBe2 A b3 A Ab4 B d其ACTION表和GOTO表为 考察对输入串abbcde 的分析过程 图7 2abbcde 的语法树 对输入串abbcde 的分析过程为 图7 3abbcde 的分析过程 LR分析过程中的性质与特点 栈中的文法符号串并上剩余的输入串构成一个右句型 规范句型 当该右句型的句柄出现在栈顶时 归约 否则 移进 栈中的文法符号串是当前句型的前缀 该前缀不包含句型句柄后面的符号 称之为活前缀 ViablePrefixes 7 2LR 0 分析表的构造 为了给出构造LR 0 分析表的算法 引出一些术语 1 规范句型的活前缀前缀 一个符号串的前缀是指该串的任意首部 包括 例如abc的前缀有 a ab abcabcd的前缀有 a ab abc abcd由此可知 对于符号串 而言 其前缀的数量为 1 例 有文法G S S aAcBe 1 A b 2 这里在每条产生式后加上了产A Ab 3 生式的序号 i 当进行推导时把B d 4 序号带上 以便说明问题 对输入串abbcde进行推导如下 最右推导 S aAcBe 1 aAcd 4 e 1 aAb 3 cd 4 e 1 ab 2 b 3 cd 4 e 1 由此可知 abbcde是该文法的句子 由于LR方法是自底向上的分析 故应采用归约 最左归约为 ab 2 b 3 cd 4 e 1 用 2 式归约 aAb 3 cd 4 e 1 3 aAcd 4 e 1 4 aAcBe 1 1 S 其中 表示归约符 从归约的过程可看出 每次归约时 归约前和归约后的被归约部分与剩余部分合起来仅构成文法的规范句型 而用哪个产生式归约仅取决于当前句型的前面部分 X1X2 Xn p 其中Xi为文法的符号 p 为第p个产生式序号 如上例中每次归约前句型的前面部分为 ab 2 aAb 3 aAcd 4 aAcBe 1 我们把规范句型的这种前端部分的串称为可归前缀 实际上 它们恰好是符号栈栈顶形成句柄时符号栈中的内容 S aAcBe 1 A b 2 A Ab 3 B d 4 这是因为一旦句型的句柄在符号栈顶形成 将会立即被归约之故 所以我们将把规范句型具有上述性质 即不含句柄之后的任何符号 的前缀称之为可归前缀 对各规范句型有前缀 ab 2 b 3 cd 4 e 1 a abaAb 3 cd 4 e 1 a aA aAbaAcd 4 e 1 a aA aAc aAcdaAcBe 1 a aA aAc aAcB aAcBe 可以发现前缀a ab aA aAc是多个规范句型的前缀 因此我们可进一步把形成可归前缀前和形成可归前缀时的所有规范句型的前缀都称为活前缀 可归前缀 是指规范句型的一个前缀 这种前缀包含句柄且不含句柄之后的任何符号 活前缀 可归前缀的任意首部 特指在分析过程中对于在栈顶形成句柄之前和恰好形成句柄时 每一步中符号栈中的那些符号组成的符号串 活前缀定义 在前面例中对输入串abbcde的归约分析过程中 在规范归约过程中的任何时候只要已分析过的部分即在符号栈中的符号串均为规范句型的活前缀 它表明输入串的已被分析过的部分是该文法某规范句型的一个正确部分 LR分析 分析过程可以看作是识别文法规范句型活前缀的过程 只要每一时刻栈中的文法符号串是某规范句型的活前缀 则说明已分析的部分是正确的 一个文法的规范句型的所有活前缀构成一个语言 而且是正规语言 可以用一个DFA来识别 例子 文法G S 1 S aAcBe 2 A b 3 A Ab 4 B d 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 每个状态都是活前缀的识别态 双圈状态是可归前缀 句柄 识别态 标识了 的状态是句子识别态 分析句子的过程可以看作在上面这个DFA上运行的过程 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 1 S aAcBe 2 A b 3 A Ab 4 B d 例子 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 例子 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 例子 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 例子 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 例子 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 例子 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 例子 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 例子 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 例子 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 例子 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 例子 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 2 LR 0 项目 由上述分析和定义可知 活前缀与句柄间的关系不外乎下述三种情况 1 活前缀中已含有句柄的全部符号 句柄的最后符号就是活前缀的最后符号 2 活前缀中只含有句柄的前部分符号 句柄的最左子串为活前缀的最右子串 3 活前缀中全然不包含句柄的任何符号 第一种情况表明 此时某一产生式A 的右部 已出现在符号栈顶 因此此时相应的分析动作应当是用此产生式进行归约 第二种情况表明 形如A 1 2的产生式的右部子串已在符号栈栈顶 如 1 正期待着从余留的输入串中看到能由 推出的符号串 即期待 2进栈以便能进行归约 故此时分析动作是 移进 当前输入符号 第三种情况则意味着 期望从余留输入串中能看到由某产生式A 的右部 即 所代表的符号串 即句柄 所以此时分析的动作也是读输入符进符号栈 为了刻画在分析过程中 文法的一个产生式右部符号串有多大部分已被识别 我们可在该产生式的右部相应位置上加一个圆点 来指示位置 标明在 前的部分已被识别 如上述三种情况 可分别标注为 A A 1 2 A 我们把右部某位置上标有圆点的产生式称为相应文法的一个LR 0 项目 特别地 对形如A 的产生式 相应的LR 0 项目表示为A 显然不同的LR 0 项目 反映了分析过程中符号栈顶的不同情况 例如 产生式S aAcBe对应有六个项目 0 S aAcBe 1 S a AcBe 2 S aA cBe 3 S aAc Be 4 S aAcB e 5 S aAcBe 例如 产生式S aAcBe对应有六个项目 0 S aAcBe 1 S a AcBe 2 S aA cBe 3 S aAc Be 4 S aAcB e 5 S aAcBe 一个产生式可对应的项目的数量为它的右部符号串长度加1 值得注意的是对空产生式 即A 仅有项目A 每个项目的含义与圆点的位置有关 概括地说 圆点左边的子串表示在分析过程的某一时刻用该产生式归约时句柄中已识别过的部分 圆点右边的子串表示待识别的部分 文法的全部LR 0 项目将是构造识别它的所有活前缀的有穷自动机的基础 3 LR 0 项目的分类 例 考虑文法G S S A B a b c d P S 构造其分析表 其中P 1 S A 2 S B 3 A aAb 4 A c 5 B aBd 6 B d 解 求该文法的项目集规范族C 为了方便起见 我们在上述文法中引起一个新的开始符号S 且将S S作为第0个产生式添加到文法G中 从而得到了所谓G的拓广文法G 显然L G L G 则对于文法G 其LR 0 项目为 1 S S2 S S 3 S A4 S A 5 S B6 S B 7 A aAb8 A a Ab9 A aA b10 A aAb 11 A c12 A c 13 B aBd14 B a Bd15 B aB d16 B aBd 17 B d18 B d G 0 S S 1 S A 2 S B 3 A aAb 4 A c 5 B aBd 6 B d 如前所述 由于不同的项目反映了分析过程中栈顶的不同情况 因此 我们可根据它们不同的作用 将一个文法的全部LR 0 项目进行分类 移进项目 A a 待约项目 A B 归约项目 A 接受项目 S S 圆点的左部表示分析过程中的某时刻用该产生式归约时句柄已识别过的部分 圆点右部表示待识别部分 4 构造识别活前缀的DFA 在LR方法实际过程中 并不是去直接分析符号栈中的符号是否已形成句柄 但它给我们一个启示 我们可以把终结符和非终结符都可看成一个有限自动机的输入符号 每把一个符号进栈时看成已识别过该符号 而状态进行转换 到下一状态 当识别到可归前缀时相当于栈顶已形成了句柄 则认为到达了识别句柄的终态 在作出文法的全部LR 0 项目之后 现在将用它们来构造识别全部活前缀的DFA 这种DFA中的中每一个状态由若干个LR 0 项目所组成的集合 称为项目集 来表示 下面以上例中的文法为例来说明构造DFA的方法 G 0 S S 1 S A 2 S B 3 A aAb 4 A c 5 B aBd 6 B d 首先我们用I0表示这个DFA的初态 它预示着整个分析过程的开始 并且期待着将给定的输入串逐步归约为文法的开始符号S 或者反过来说 我们所期待的是 从使用产生式S S开始 能够逐渐推导出所给定的输入串 因此 我们应将项目S S列入项目集I0之中 换言之 也就是我们正期待将要扫描的输入串正好就是能由S 推导出的任何终结符串 然而 我们不能从输入串中直接读出非终结符号S 因此我们也应将项目S A和S B加入I0中 由于A和B同样是非终结符 所以也应将A aAb和A c和B aBb B d加入I0中 G 0 S S 1 S A 2 S B 3 A aAb 4 A c 5 B aBd 6 B d 由于最后加入I0的项目在圆点之后已都是终结符了 故I0已经 封闭 宣告项目集I0构造结束 这样 表示初态的项目集I0将由如下项目组成 I0 S S S A S B A aAb A c B aBd B d I0 S S S A S B A aAb A c B aBd B d我们将LR 0 项目S S称为项目集I0的基本项目 上述从S S出发构造项目集I0的过程 可用一个对其基本项目集 S S 的闭包运算 即closure S S 来表示 一般地 设I为项目集 I的闭包closure I 的定义为 Closure I I A A G K A closure I V V 故构造closure I 的算法为 1 I中的每一个项目都属于closure I 2 若形如K A 的项目属于I 且A 是文法的一个产生式 则关于产生式A的任何形如A 的项目也应加到closure I 中 若它们不在closure I 中 3 重复上述过程 直至不再有新的项目加入到closure I 中为止 有了初态项目集I0之后 我们来说明如何确定从I0可能转移到的下一状态 设A为一文法符号 A V 若I0中有圆点位于A左边的项目K A 其中 可能为 则当分析器从输入串识别出 即移进或归约出 文法符号A后 分析器将进入它的下一状态 设此状态为Ii 显然Ii中必含有全部形如K A 的项目 我们将这样的项目称为K A 的后继项目 对于每一个文法符号A 如果存在这样的后继项目 则可能不只一个 设其组成集合J 则J中的每个项目都是项目集Ii的基本项目 因此 按照与上面构造项目集I0相类试的讨论 我们有 Ii closure J 为了指明Ii是 I0关于文法符号A的后继状态 这一事实 我们可定义一个状态转移函数 GO I0 A closure J Ii其中 I是当前状态 A为文法符号 J是I中所有形如K A 的项目之后继项目K A 所组成的集合 而closure J 就是项目集I 即状态I 关于符号A的后继项目集 即后继状态 状态转移函数 GO I0 A closure J Ii其中 I是当前状态 A为文法符号 J是I中所有形如K A 的项目之后继项目K A 所组成的集合 而closure J 就是项目集I 即状态I 关于符号A的后继项目集 即后继状态 即 GO I A closure 所有形如 K A 的项目 K A I 对于上例 我们有 I1 GO I0 S closure S S I1 S S I2 GO I0 A closure S A I2 S A I3 GO I0 B closure S B I3 S B I4 GO I0 a closure A a Ab B a Bd G 0 S S 1 S A 2 S B 3 A aAb 4 A c 5 B aBd 6 B d I4 A a AbB a BdA aAbB aBdA cB dI5 GO I0 c closure A c I5 A c I6 GO I0 d closure B d I6 B d 此时 我们求出了I0的全部后继项目集I1 I2 I3 I4 I5 I6 而I1 I2 I3 I5 I6均无后继项目集 仅I4有后继项目集 I7 GO I4 A closure A aA b A aA b I9 GO I4 B closure B aB d B aB d 此外 还有 GO I4 a closure A a Ab B a Bd I4GO I4 c closure A c I5GO I4 d closure B d I6这些项目集均不产生新的项目集 另外还有 G 0 S S 1 S A 2 S B 3 A aAb 4 A c 5 B aBd 6 B d I8 GO I7 b closure A aAb A aAb I10 GO I9 b closure B aBd B aBd 此时I8 I10也已无后继项目集 故我们已求出文法G S 的全部项目集I0 I10 通常我们将这些项目集的全体称为文法G S 的LR 0 项目集规范族 并记为C I0 I1 I10 于是 我们所要构成的识别文法G S 的全部活前缀的DFA为M C V GO I0 Z 其中C M的状态集 即文法G S 的LR 0 项目集规范族 C I0 I1 I10 V M的字母表 即V S S A B a b c d GO M的映射函数 即上面定义的状态转移函数GO I0 M的唯一初态 Z M的终态集 Z C 为规范族中所有含有归约项目的那些项目集 DFA G 0 S S 1 S A 2 S B 3 A aAb 4 A c 5 B aBd 6 B d 图7 4文法G S 项目集规范族 DFA 即 G 0 S S 1 S A 2 S B 3 A aAb 4 A c 5 B aBd 6 B d a 图7 5识别文法G S 活前缀的DFA 5 LR 0 分析表的构造 对于一个文法G的拓广文法G 当识别它的全部活前缀的DFA作出之后 我们可以据此构造相应的LR 0 分析表了 然而 要注意的是 用前述方法所构造的每一个LR 0 项目集实质上表征了在分析过程中可能出现的一种分析状态 再根据前面对LR 0 项目的分类 项目集中的每一个项目又与某一种分析动作相关联 因此 就要求每一个项目集中的的诸项目应当是相容的 所谓相容 是指在一个项目集中不出现下列的情况 1 移进项目和归约项目并存 即存在移进 归约冲突 2 多个归约项目并存 即存在归约 归约冲突 如果一个文法G满足上述条件 也就是它的每个LR 0 项目集中都不含有冲突的项目 则称G为LR 0 文法 显然 只有当一个文法是LR 0 文法时 才能对它构造不含冲突动作的LR 0 分析表来 为了方便起见 我们用整数0 1 2 表示状态I0 I1 I2 分析表的内容由两部分组成 一部分为动作 ACTION 表 它表示当前状态下所面临的输入符号应做的动作是移进 归约 接受或出错 另一部分为状态转移 GOTO 表 它表示在当前状态下面临文法符号时应转向的下一个状态 相当于识别活前缀的有限自动机DFA的状态转换矩阵 分析表的行标为状态号 动作表的列标为只包含终结符和 状态转移表的列标为非终结符 而将其有关终结符的各列并入到ACTION表的各列中去 也就是把当前状态下面临终结符应作的动作和状态转移用同一数组元素表示 以便节省存储空间 构造LR 0 分析表的算法为 1 对于每一项目集Ii中形如A X 的项目 且有GO Ii X Ij 若X为一终结符号a时 则置ACTION i a Sj 若X为一非终结符号时 则仅置GOTO i X j 2 若Ii中有归约项目A 设A 为文法第j个产生式 则对文法的任何终结符和 均记为a 置ACTION i a Rj 3 若接受项目S S 属于Ii 则置ACTION i acc 4 在分析表中 凡不能按上述规则填入信息的元素 均置为 出错 如上例可构造分析表为 构造LR 0 分析表的算法为 1 对于每一项目集Ii中形如A X 的项目 且有GO Ii X Ij 若X为一终结符号a时 则置ACTION i a Sj 若X为一非终结符号时 则仅置GOTO i X j 2 若Ii中有归约项目A 设A 为文法第j个产生式 则对文法的任何终结符和 均记为a 置ACTION i a Rj 6 LR 0 分析器的工作过程 对于一个文法构造了它的LR 0 分析表就可以在LR分析器的总控程序控制下对输入串进行分析 即根据输入串当前符号a和分析栈栈顶状态i查找分析表应采取的动作 对状态栈和符号栈进行相应的操作即移进 归约 接受或报错 具体为 1 若ACTION i a Sj a VT 则把a移进符号栈 j移进状态栈 2 若ACTION i a Rj a VT或 则用第j个产生式归约 并将两个栈的指针减去K 其中K为第j个产生式右部的串长度 并把产生式的左部符号A压入符号栈 同时用符号对 Si k A 去查GOTO表 其中Si k为状态栈当前栈顶元素 若GOTO Si k A j 则j压入状态栈 使得两个栈内的元素一样多 3 若ACTION i a Acc 此时a应为 号 则表明分析成功 结束分析 4 若ACTION i a 空白 转出错处理 7 3SLR 1 分析 因大多数程序设计语言的文法不能满足LR 0 文法的条件 即使是描述一个变量这样简单的文法也不是LR 0 文法 因此下面将介绍对LR 0 规范族中有冲突的项目集 状态 用向前查看一个 输入 符号的办法进行处理 以解决冲突 这种分析方法因为只对有冲突的状态才向前查看一个符号 以确定做什么动作 故称这种分析方法为简单的LR 1 分析法 用SLR 1 表示 假定有一个LR 0 规范族中含有如下项目集 状态 I I X b A B 其中 为符号串 b VT 显然I中含有移进 归约和归约 归约冲突 那么只要在所有含有A或B的句型中 直接跟在A或B后面的可能终结符集合FOLLOW A 和FOLLOW B 互不相交 且都不包含b 即只要满足 即 FOLLOW A FOLLOW B b 那么 当在状态I面临某输入符号为a时 则动作可由下述规定决策 1 若a b 则移进 2 若a FOLLOW A 则用产生式A 归约 3 若a FOLLOW B 则用产生式B 归约 一般地 对于LR 0 规范族的一个项目集I可能含有多个移进项目和多个归约项目 我们可假设项目集I中有m个移进项目 A1 1 b1 1 A2 2 b2 2 Am m bm m 同时含有n个归约项目 B1 1 B2 2 Bn n 只要集合 b1 b2 bm 和FOLLOW B1 FOLLOW B2 FOLLOW Bn 两两交集都为空 则我们仍可用上述归则来解决冲突 1 若a b1 b2 bm 则移进 2 若a FOLLOW Bi i 1 n 则用Bi i进行归约 3 此外 则报错 所以 我们只须把构造LR 0 分析表算法中的规则 2 即 2 若Ii中有归约项目A 设A 为文法第j个产生式 则对文法的任何终结符和 均记为a 置ACTION i a Rj 修改为 即 1 对于每一项目集Ii中形如A X的项目 且有GO Ii X Ij 若X为一终结符号a时 则置ACTION I a Sj 若X为一非终结符号时 则仅置GOTO i X j 2 若归约项目A 属于Ii 设A 为文法第j个行产生式 则对任何属于FOLLOW A 的输入符号a 置ACTION i a Rj 3 若接受项目S S 属于Ii 则置ACTION i acc 4 在分析表 凡不能按上述规则填入信息的元素 均置为 出错 2 若归约项目A 属于Ii 设A 为文法第j个行产生式 则对任何属于FOLLOW A 的输入符号a 置ACTION i a Rj 其余的规则不变 就得到了构造SLR 1 分析表的算法 例如 有算术表达式文法G E 构造其LR 0 项目规范簇和SLR 1 分析表 G E E E T TT T F FF E i 解 1 拓广文法为G S 0 S EE E TE TT T FT FF E F i 2 再求识别G 的全部活前缀的DFA 即LR 0 的项目集规范簇 I0 S EGO I0 E I1E E TGO I0 E I1E TGO I0 T I2T T FGO I0 T I2T FGO I0 F I3F E GO I0 I4F iGO I0 i I5 I1 S E E E TGO I1 I6 I2 E T T T FGO I2 I7 I3 T F I4 F E GO I4 E I8E E TGO I4 E I8E TGO I4 T I2T T FGO I4 T I2T FGO I4 F I3F E GO I4 I4F iGO I4 i I5 I5 F i I6 E E TGO I6 T I9T T FGO I6 T I9T FGO I6 F I3F E GO I6 I4F iGO I6 i I5 I7 T T FGO I7 F I10F E GO I7 I4F iGO I7 i I5 I8 F E GO I8 I11E E TGO I8 I6 I9 E E T T T FGO I9 I7 I10 T T F I11 F E DFA 图7 6识别文法G S 活前缀的DFA 3 解决冲突 可以看到 项目I1 I2 I9中都同时包含有移进项目和归约项目 存在移进 归约冲突 因而该文法不属于LR 0 文法 故不能构造LR 0 分析表 FOLLOW S FOLLOW E FOLLOW T FOLLOW F 现在分别考虑上述三个冲突项目中的冲突是否能用SLR 1 方法解决 在I1中 由于FOLLOW S 而S E 是唯一的接受项目 所以当且仅当遇到句子的结束符 号时才被接受 又因 故I1中的冲突可解决 对于I2 因FOLLOW E 因此当面临输入符号为 或 号时 则用产生式E T归约 当面临输入符为 时 则移进 其它情况则报错 对于I9 与I2类似 当面临输入符号为 或 时 则用产生式E E T归约 当面临输入符号为 时 则移进 其余情况报错 4 构造SLR 1 分析表 对于上述三个冲突项目等均可用SLR 1 方法解决冲突 因此该文法是SLR 1 文法 我们可造成其相应的SLR 1 分析表为 下面给定输入串i i i 使用上述SLR 1 分析进行分析 步状态栈符号栈输入串ACTIONGOTO 10 i i i S5 205 i i i R63 303 F i i R42 402 T i i R21 501 E i i S6 6016 E i i S5 70165 E i i R63 80163 E T i R49 90169 E T i S7 1001697 E T i S5 11016975 E T i R610 120169710 E T F R39 130169 E T R11 1401 E acc 本章作业 P165 题1 题2 1 7 4LR 1 分析 本节介绍比SLR 1 功能更强的LR 1 分析法 例7 4 有下列文法G 构造构造识别文法G 的识别活前缀的有限自动机 0 S S 1 S aAd 2 S bAc 3 S aec 4 S bed 5 A e我们首先用S S作为初态集的项目 然后用闭包函数和转换函数构造识别文法G 的识别活前缀的有限自动机DFA如图7 7所示 图7 7LR 0 识别G 的活前缀的DFA 如图7 7所示 可以发现在项目集I5和I7中存在移进和归约冲突 I5 S ae cI7 S be dA e A e 而归约项目左部非终结符的FOLLOW A c d 在I5中 FOLLOW A c c d c 在I7中 FOLLOW A d c d d 因此I5 I7中冲突不能用SLR 1 方法解决 只能考虑用下面将要介绍的LR 1 方法解决 由于用SLR 1 方法解决动作冲突时 对于归约项目A 只要当前面临输入符为a FOLLOW A 时 就确定采用产生式A 进行归约 但是如果栈中的符号串为 归约后变为 A 再移进当前符a 则栈里变为 Aa 而实际上 Aa未必为文法规范句型的活前缀 现在我们再看图7 7在I5 I7项目集中的移进 归约冲突 不能用SLR 1 方法解决的原因如下 I5 S ae c因A e 0 S S 1 S aAd 2 S bAc 3 S aec 4 S bed 5 A e 这两个最右推导已包括了活前缀为a的所有句型 因此 不难看出对活前缀ae来说 当面临输入符号为c时应移进 面临d时应用产生式A e归约 因为 这说明从S 出发不能用最右推导 规范推导 推出aAc句型 所以aAc不是该文法的规范句型 回顾LR分析过程 若输入符号串是所给文法的句子 那么分析过程的任何时刻在文法符号栈中的符号和剩余的输入串符号合起来总是构成该文法的规范句型 这也说明了并不是FOLLOW A 的每个元素在含A的所有句型中在A的后面都会出现 例中d只在规范句型aAd中A的后面出现 因此面临输入符为d才应归约 再看在I7中 I7 S be d而A e 0 S S 1 S aAd 2 S bAc 3 S aec 4 S bed 5 A e 这两个最右推导 包含了活前缀为b的所有句型 因此FOLLOW A 中的c只能跟在句型bAc中A的后面 这样在I7中当面临输入符为c时才能归约 根据项目集的构造原理有 若 A B 项目集I 则 B B 为一产生式 也包含在I中 不妨考虑 把FIRST 作为用产生式B 归约的搜索符 称为向前搜索符 作为归约时查看的符号集合 用以代替SLR 1 分析中的FOLLOW集 把此搜索符号的集合也放在相应项目的后面 这种处理方法即为LR 1 方法 其原因是 一个非终结符号的FOLLOW集合 包含了所有含该非终结符的任一句型中在该非终结符后的向前搜索符集合 如在项目集I中有项目 A B B 当分析经过若干步后在项目集J中含有项目 B 需要用产生式B 归约 这时向前查看的符号集合是FIRST 而FIRST FOLLOW B 7 4 1LR 1 项目集族的构造 一个LR 1 项目可以看成两个部分组成 一部分和LR 0 项目相同部分我们称它为心 另一部分为向前搜索符集合 如让S S 属于初始项目集中 把 号作为向前搜索符 表示活前缀为 若 是有关S产生式的某一右部 要归约成S时 必须面临输入符为 号才行 因此对初始项目 S S 求闭包后再用转换函数逐步求出整个文法的LR 1 项目集族 具体构造步骤如下 1 构造LR 1 项目集的闭包函数 a 项目集I的任何项目都属于CLOSURE I b 若有项目 A B a 属于CLOSURE I B 是文法中的产生式 V b FIRST a 则 B b 也属于CLOSURE I 中 c 重复b 直到CLOSURE I 不再增大为止 2 转换函数的构造LR 1 转换函数的构造与LR 0 的相似 GO I X CLOSURE J 其中I是LR 1 的项目集 X是文法符号 J 任何形如 A X a 的项目 A X a I 现给出直接由产生式构造识别活前缀的DFA的LR 1 项目集的闭包CLOSURE的算法 functionCLOSURE I I是项目集 J I repeat对J中的每个项目 A B a 和产生式B V b FIRST a 若B b不在J中Do将B b加到J中until再没有项目加到J中returnJ 对项目 A B a 计算B的向前搜索符时 应为FIRST a 这是因为 V 即 可能为 而a是用产生式A B 归约时的向前搜索符 而现在 为 就等于用A B归约 向前搜索符为a 那么用A B归约前 必须先用产生式B 归约成B 因此 B的向前搜索符时也应为a 对文法G 的LR 1 项目集族的构造仍以 S S 为初态集的初始项目 然后对其求闭包和转换函数 直到项目集不再增大 也就是对状态I经过符号X后转向状态J 求出J的基本项目后 对基本项目求闭包即为CLOSURE J 现在我们可以对上面7 4例中不能用SLR 1 方法解决I5 I7中移进 归约冲突的文法构造它的LR 1 项目集规范族如下 0 S S 1 S aAd 2 S bAc 3 S aec 4 S bed 5 A e 这样LR 1 方法构造的项目集规范族在项目集I5和I7中的移进 归约冲突 由于归约项目的搜索符集合与移进项目的待移进符号不相交 所以在I5中 当面临输入符为d时归约 为c时移进 而在I7中则当面临输入符为c时归约 为d时移进 冲突已全部可以解决 因此该文法为LR 1 文法 7 4 2LR 1 分析表的构造 由于一个LR 1 项目可以看成两个部分组成 一部分和LR 0 项目相同部分我们称它为心 另一部分为向前搜索符集合 因而LR 1 分析表的构造与LR 0 分析表的构造大部分相同 仅对归约项目的归约动作取决于该归约项目的向前搜索符集 只有当面临输入符属于向前搜索符的集合 才做归约动作 其它情况均出错 具体构造过程如下 若已构造出某文法的LR 1 项目集族C C I0 I1 In 其中Ik的k为分析器的状态 则动作ACTION表和状态转换GOTO表构造方法如下 1 若项目 A a b 属于Ik 且GO Ik a Ij 其中a VT 则置ACTION k a Sj 其Sj的含义是把输入符号a和状态j分别移入文法符号栈和状态栈 2 若项目 A a 属于Ik 则置ACTION k a rj其中a VT rj的含义为把当前栈顶符号串 归约为A 即用产生式A 归约 j为在文法中对产生式A 的编号 3 若项目 S S 属于Ik 则置ACTION k acc 表示 接受 4 若GO Ik A Ij 其中A VN 则置GOTO k A j 表示转入j状态 置当前文法符号栈顶为A 状态栈顶为j 5 凡不能用规则 1 4 填入分析表中的元素 均置 报错标志 我们用 空白 表示之 LR 1 分析表的构造除 2 外 其余同LR 0 或SLR 1 即若项目 A a 属于Ik 则置ACTION k a rj 也就是归约时向前查看的符号为向前搜索符 根据上述规则 我们对7 4例中文法的LR 1 项目集族构造其相应的LR 1 分析表如表7 10 表7 10LR 1 分析表 由表7 10可以看出对LR 1 的归约项目不存在任何无效归约 但在多数情况下 同一个文法的LR 1 项目集的个数比LR 0 项目集的个数多 甚至可能多好几倍 这是由于对同一个LR 0 项目集的搜索符集合不同 而对应着多个LR 1 项目集 也可以看成LR 1 项目集的构造使某些同心集进行了分裂 因而项目集的个数增多了 同心集是指两个项目集它们所含的LR 0 项目相同 即不看搜索符时 而加了搜索符变成不同的LR 1 项目集 这种现象也可以看成是由于LR 1 项目集的构造使某些同心集进行了分裂 同心集是指两个项目集它们所含的LR 0 项目相同 即不看搜索符时 而加了搜索符变成不同的LR 1 项目集 这种现象也可以看成是由于LR 1 项目集的构造使某些同心集进行了分裂 若文法G 为 0 S S 2 B aB 1 S BB 3 B b它的LR 1 项目集族和转换函数如图7 8 LR 1 分析表如表7 11 只要仔细分析该文法的LR 1 每个项目集的项目 不难发现 即使不考查搜索符 它的任何项目集中都没有动作冲突 因此实际上这个文法是LR 0 文法 读者可以自己构造它的LR 0 项目集 可以得知它的LR 0 分析器只含7个状态 而现在LR 1 分析器却含有10个状态 其中I3和I6 I4和I7 I8和I9分别为同心集 图7 8LR 1 识别G 的活前缀的DFA 如果一个文法的LR 1 分析表不含多重入口时 或任何一个LR 1 项目集中无移进 归约冲突或归约 归约冲突 则称该文法为LR 1 文法 所构造的相应分析表称为LR 1 分析表 能使用LR 1 分析表的分析器称为LR 1 分析器或称规范的LR分析器 结论 LR 1 文法是无二义的 LR 1 项目集的构造对某些同心集的分裂可能使状态数目剧烈的增长 一个文法是LR 0 文法一定也是SLR 1 文法 也是LR 1 文法 反之则不一定成立 7 5LALR 1 分析 LR 1 分析表的构造 对归约时向前查看的符号由SLR 1 用的FOLLOW集改为向前搜索符 计算方法比较确切 对文法放宽了要求 也就是适应的文法类广 因此 可以解决SLR 1 方法解决不了的问题 但是 由于它的构造对某些同心集的分裂可能对状态数目引起剧烈的增长 从而导致存储容量的急剧增加 也使应用受到一定的限制 为了克服LR 1 的这种缺点 我们可以采用对LR 1 项目集规范族合并同心集的方法 若合并同心集后不产生新的冲突 则为LALR 1 项目集 它的状态个数与LR 0 SLR 1 的相同 例如 我们分析图7 8中的项目集可发现同心集如下 I3 B a B a bI6 B a B B aB a bB aB B b a bB b I4 B b a bI7 B b I8 B aB a bI9 B aB 即I3和I6 I4和I7 I8和I9分别为同心集 将同心集合并后为 I3 I6 B a B a b B aB a b B b a b I4 I7 B b a b I8 I9 B aB a b 同心集合并后仍不包含冲突 因此该文法满足LALR 1 要求 合并同心集有几个问题需要说明 1 同心集是指心相同的项目集合并在一起 因此同心集合并后心仍相同 只是超前搜索符集合为各同心集超前搜索符集合的并集 2 对于合并同心集后的项目集的转换函数仍为同心集 因为相同的心之转换函数的心仍相同 即仍属同心集 所以合并同心集后转换函数为自动合并 如例中I3和I6为同心集 它们的转换函数分别为 I3 GO I3 a I3I6 GO I6 a I6GO I3 b I4GO I6 b I7GO I3 B I8GO I6 B I9然而 I3和I6 I4和I7 I8和I9分别都为同心集 3 若文法是LR 1 文法 合并同心集后若有冲突也只可能是归约 归约冲突 而不可能产生移进 归约冲突 4 合并同心集后对某些错误发现的时间会产生推迟现象 但错误的出现位置仍是准确的 这意味着LALR 1 分析表比LR 1 分析表对同一输入串的分析可能会有多余归约 现在构造上述文法的LALR 1 分析表 对于一个文法是否为LALR 1 文法 通常所采用的方法是首先构造它的LR 1 项目集族 若不含任何冲突 则合并同心集 若仍不产生归约 归约冲突 则该文法便是LALR 1 文法 那么就可以根据合并同心集后的项目集族构造该文法的LALR 1 分析表 其构造步骤如下 构造文法G的LR 1 项目集族 C I0 I1 In 2 合并所有的同心集 使C变为C J0 J1 Jm 便是LALR 1 的项目集族 由于构造LALR 1 分析表 通常所采用的方法是首先构造它的LR 1 项目集族 若不含任何冲突 则合并同心集 若仍不产生归约 归约冲突 则该文法便是LALR 1 文法 再根据合并同心集后的项目集族构造该文法的LALR 1 分析表 所以LALR 1 分析表的构造除了步骤 2 外 其余步骤与LR 1 分析表的构造相同 3 由C 构造动作 ACTION 表 其方法与LR 1 分析表的构造相同 a 若 A a b Jk 且GO Jk a Jj 其中a VT 则置ACTION k a Sj 其Sj的含义是把输入符号a和状态j分别移入文法符号栈和状态栈 a 若 A a b Jk 且GO Jk a Jj 其中a VT 则置ACTION k a Sj 其Sj的含义是把输入符号a和状态j分别移入文法符号栈和状态栈 b 若项目 A a 属于Jk 则置ACTION k a rj 其中a VT rj的含义是设A 是文法的第j个产生式 此时为把栈顶符号串 归约为A c 若项目 S S 属于Ik则置ACTION k acc 表示分析成功 接受 d GOTO表的构造 对于不是同心集的项目集 转换函数的构造与LR 1 的相同 对同心集项目 由于合并同心集后 新集的转换函数也为同心集 所以 转换函数的构造也相同 为了说明步骤d 假定Ii1 Ii2 Iin是同心集 合并后的新集为Jk 转换函数GO Ii1 X GO Ii2 X GO Iin X 也为同心集 将其合并后记作Ji 因此 有GO Jk X Ji 所以当X为非终结符时 GO Jk X Ji 则置GOTO k X i 表示在k状态下遇非终结符X时 把X和i分别移到文法符号栈和状态栈 当X为终结符时 和ACTION表重合 e 分析表中凡不能填入信息的空白均填 出错标志 例见P149表7 12 表7 12合并同心集后的LALR 1 分析表 由于合并同心集后在新的集合中不含归约 归约冲突所以该文法是LALR 1 文法 能用LALR 1 分析表进行语法分析的分析器称为LALR 1 分析器 LALR 1 文法小结 一个LR 1 文法项目集的同心集合并后心仍相同 只是超前搜索符集合为各同心集超前搜索符的和集 合并同心集后转换函数自动合并 一个LR 1 文法合并同心集后只可能出现归约 归约冲突 而没有移进 归约冲突 合并同心集后 对错误的输入串分析可能会推迟发现错误的时间 但错误出现的位置仍是准确的 P149 LR分析器 LR分析器是一个确定的下推自动机 作为LR分析器的核心的分析表由两个子表组成 分析动作表ACTION和状态转移表GOTO 一个LR分析器如图