《SLR分析表的构造》课件.pptVIP

有效项目 如果存在规范推导 则项目A??1·?2 对活前缀 ??1 是有效的。 如果?2 ? ?，应该移进 如果?2 = ?，应该用产生式A??1归约 5.3.3 SLR分析表的构造 SLR(1)分析法的引入: LR(0)文法的活前缀识别自动机的每一状态(项目集)都不含冲突性的项目 大多数的程序设计语言的文法不能满足LR(0)文法的条件 用向前查看一个符号的办法解决冲突 例：设文法G的LR(0)项目集规范族中含有如下一个项目集（状态）I： I = { X?? ?b? /*移进项目*/ A??? /*归约项目*/ B?γ? /*归约项目*/ } 用SLR(1)方法解决冲突 假定LR(0)规范族的一个项目集I中含有m个移进项目: A1→α·a1β1，A2→α·a2β2，…，Am→α·amβm 同时含有n个归约项目: B1→α1·, B2→α2·, …, Bn→αn· 如果集合｛a1,…,am｝、FOLLOW(B1)、…、FOLLOW(Bn)两两不相交，a是现行输入符号，则: （1）若a是某个ai，i=1,2,…,m，则移进； （2）若a∈FOLLOW(Bi)，i=1,2,…,n， 则用产生式Bi→αi进行归约； （3）此外，报错。 例5.11 p111 考虑下面的拓广文法 (文法5.8) （0） S?? E （1） E? E+T （2） E? T （3） T? T*F （4） T? F （5） F? (E) （6） F? I 构造其LR(0)项目集规范族 SLR(1) 解决方法 FOLLOW(S′) = { # }, {#}∩{+}＝φ，因此I1中的冲突可解决。 遇 ‘+’移进 ，遇 ‘#’接受 其它情况则报错。 FOLLOW(E) = { +, ) , # } FOLLOW(E)∩{*}= φ,因此I2中的冲突可解决。 FOLLOW(E) = { + , ) , # } FOLLOW(E)∩{*}= φ,因此I9中的冲突可解决。 构造SLR(1)分析表 (1)若 A→α·aβ 属于Ik , 且GO(Ik, a)=Ij , 则置 ACTION[k, a] 为 sj (2)若 A→α· 属于Ik，a∈FOLLOW(A) ， 则置 ACTION[k,a] 为 rj j是产生式A→α的编号 。 (3)若 S?→S·属于Ik, 则置 ACTION[k,#]为 acc (4)若 GO(Ik,A)=Ij ， 则置 GOTO[k, A]=j (5)凡不能用规则(1)~(4)填入的空白格均置为“出错标志”。 SLR分析表: 按上述方法构造分析表, 每个入口不含多重定义 SLR(1)文法: 具有SLR表的文法 SLR分析器 : 使用SLR表的分析器 例：一个非SLR文法的例子 p113 有如下文法: (文法5.9) (0) S ?S (1) S ?L=R (2) S ?R (3) L ?*R (4) L ? i (5) R ?L 求LR(0)项目集规范族及识别活前缀的DFA * * 图5.7 p106 识别文法 活前缀的DFA 从初态出发,经读出活前缀γ后,而到达的项目集称为活前缀γ的有效项目集 I0: S??E E? ?aA E? ?bB I5: B?c?B B? ?cB B? ?d I3: E?b?B B? ?cB B? ?d I2:E?a?A A? ?cA A? ?d I1: S ? E ? I4:A?c?A A? ?cA A? ?d I8:A?c A? I10:A? d ? I6:E?aA ? I7:E?bB? I11:B? d ? I9:B?cB ? b E a c c c c d d d d A A B B ? * R ? R ??1?2? ?A? S LR分析理论的一条基本定理: 在任何时候，分析栈中的活前缀X1X2...Xm的有效项目集正是栈顶状态Sm所代表的那个集合。 I0: S??E E? ?aA E? ?bB I5: B?c?B B? ?cB B? ?d I3: E?b?B