图5.7 p106.ppt

图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 有效项目 如果存在规范推导 则项目A??1·?2 对活前缀 ??1 是有效的。 如果?2 ? ?，应该移进 如果?2 = ?，应该用产生式A??1归约 ? * 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 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 G: S→E E→aA|bB A→cA|d B→cB|d 项目集I5对活前缀bc有效 考虑如下规范推导 (1) S?? E ? bB ? bcB (2) S?? E ? bB ? bcB ? bccB (3) S?? E ? bB ? bcB ? bcd 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 同一个项目可能对好几个活前缀都有效 G: S→E E→aA|bB A→cA|d B→cB|d 同一个活前缀，可能存在若干个项目对它都是有效的，而且告诉我们应做的事情各不相同，相互冲突。 这种冲突通过向前多看几个输入符号, 或许能够获得解决。 5.3.3 SLR分析表的构造 SLR(1)分析法的引入: LR(0)文法的活前缀识别自动机的每一状态(项目集)都不含冲突性的项目 大多数的程序设计语言的文法不能满足LR(0)文法的条件 用向前查看一个符号的办法解决冲突 例：设文法G的LR(0)项目集规范族中含有如下一个项目集（状态）I： I = { X?? ?b? /*移进项目*/ A??? /*归约项目*/ B?γ? /*归约项目*/ } 移进－归约冲突 归约－归约冲突 解决冲突策略 （1）若a=b，则移进 （2）若a∈Follow(A), 则用 A?? 归约 （3）若a∈Follow(B), 则用 B?γ归约 （4）此外，报错 用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?