第五章 语法分析 自下而上 4.0.ppt

* 由规则（1）得： E’-.E 因为E紧挨在圆点的右侧，由规则（2） E-.E+T E-.T T-.T*F T-.F F-.(E) F-.id C、 利用LR(1)项目构造NFA 构造方法：同LR(0)构造识别活前缀的NFA方法相同 D、构造有效的LR(1)项目集族(即求DFA) 项目集I的闭包CLOSURE(I)构造方式 函数GO（I,X)的定义 LR(1)项目集族C的构造算法 E、根据DFA,构造LR分析表 a、若项目[A→?·a?,b]属于Ik且GO(Ik,a)＝ Ij，a为终结符，则置 ACTION[k，a]为“把（j，a）移进栈”，简记为“sj”； b、若项目[A→?·,a]属于Ik，则置ACTION[k，a]为“用产生式A→?归约”，简记为“rj”；其中，假定A→?为文法G’的第j个产生式； c、若项目[S’→S·,#]属于Ik，则置ACTION[k，＃]为“接受”，简记为 “acc”； d、若GO（Ik，A）＝Ij，A为非终结符，则置GOTO[k，A]＝j； e、分析表中凡不能使用规则1至4填入信息的空白格均置上“出错标 志”。 例6 拓广文法 的规范LR分析表 (0)S’-S (2) B-aB (1) S-BB (3) B-b 状态 ACTION(动作) GOTO(转换) a b # S B 0 s3 s4 1 2 1 acc 2 s6 s7 5 3 s3 r4 8 4 r3 r3 5 r1 6 s6 s7 9 7 r3 8 r2 r2 9 r2 r3 5、LALR分析表的构造 问题：对于一般的语言，规范LR分析表要用几千个状态，无法实际应用 分析：由例6中可以看到，有些状态集除了有哪些信誉好的足球投注网站符不同外是两两相同的 解决办法：合并同心集，构造LALR分析表 我们称两个LR(1)项目集具有相同的心，如果除去有哪些信誉好的足球投注网站符之后，这两个集合是相同的。 将所有同心的LR(1)项目集合并后，得到一个心就是一个LR(0)项目集。 说明： 合并同心集不会产生新的移进-归约冲突，但有可能产生新的“归约-归约”冲突。 对于同一个文法，LALR分析表和SLR分析表永远具有相同数目的状态，却能处理一些SLR所不能对付的事情。 合并项目集时不用修改转换函数，即GO(I,X)；动作ACTION应进行修改，使得能够反映各被合并的集合的既定动作。 A、构造LALR分析表的第一个算法 步骤： 构造文法G的LR(1)项目集族C={I0,I1,In} 把所有的同心集合并在一起，记C’={J0,J1,Jm}为合并后的新族。那个含有项目[S’-S,#]的Jk为分析表的初态 从C’构造ACTION表 构造GOTO表 分析表中凡不能用3、4天入信息的空白格均填上“出错标志” a、若项目[A→?·a?,b]属于Jk且GO(Jk,a)＝ Jj，a为终结符，则置ACTION[k，a]为 “sj”； b、若项目[A→?·,a]属于Jk，则置ACTION[k，a]为“用产生式A→?归约”，简记为“rj”；其中，假定A→?为文法G’的第j个产生式； c、若项目[S’→S·,#]属于Jk，则置ACTION[k，＃]为“接受”，简记为“acc”； 从C’构造ACTION表 例7 拓广文法 的LALR分析表 (0)S’-S (2) B-aB (1) S-BB (3) B-b ①把状态3，6、4，7和8，9分别合并成 I36: [B-a?B,a /b/#] [B-?aB,a /b/#] [B-?b,a /b/#] I47: [B-b?,a /b/#] I89: [B-aB?,a /b/#] ②由合并后的集族所构成的LALR分析表 状态 ACTION(动作) GOTO(转换) a b # S B 0 s36 s47 1 2 1 acc 2 s36 s47 5 36 s36 r47 89 47 r3 r3 r3 5 r1 89 r2 r2 r2 B、构造LALR分析表的另一算法 问题：对任何文法G，通过构造它的LR(1)项目集，合并同心集，最后形成LALR(1)项目集 ，该算法太费存储空间。 解决办法：注意到各种项目集都是以一定项目为核的闭包。若用核代替闭包，则不论哪一种项目集都将大大缩小它的存储空间 相关定义 使用核构造分析表 任何项目集的核是由此集中所有那些圆