温故知新compiler-principle10编译器原理.pptxVIP

温故知新输入LR分析程序输出栈LR分析器的模型actiongotosmXmsm-1Xm-1…s0…a1ai…an$简单的LR方法（SLR）规范的LR方法向前看的LR方法(LALR）10/46LR分析器模型实现简单，分析表规模小；功能有限

3.5LR分析器3.5.4构造规范的LR分析表LR(1)项目： 重新定义项目，让它带上搜索符，成为如下形式 [A??·?,a]LR(0)项目[A??·?]点的左边代表历史信息，右边代表展望信息。直观地讲，项目表示在分析过程的某一阶段，已经看到了产生式的多大部分，以及希望看到的部分。

3.5LR分析器3.5.4构造规范的LR分析表LR(1)项目： 重新定义项目，让它带上搜索符，成为如下形式 [A??·?,a]LR(1)项目[A??·?,a]对活前缀?有效： 如果存在着推导S?*rm?Aw?rm???w，其中：?=??；a是w的第一个符号，或者w是?且a是$。

3.5LR分析器例 S?BB B?bB|a从最右推导S?*rmbbBba?rmbbbBba看出： [B?b·B,b]对活前缀?=bbb是有效的LR(1)项目[A??·?,a]对活前缀?有效： 如果存在着推导S?*rm?Aw?rm???w，其中：?=??；a是w的第一个符号，或者w是?且a是$。

3.5LR分析器例 S?BB B?bB|a从最右推导S?*rmbbBba?rmbbbBba看出： [B?b·B,b]对活前缀?=bbb是有效的对于项目[A??·?,a]，当?不为空时，采取移进操作（同LR(0)项目）；当?为空时，是根据搜索符a来决定归约，而不是根据A的后继符FOLLOW(A)来规约（不同于LR(0)项目）,通常搜索符a的集合是FOLLOW(A)的子集。

3.5LR分析器构造规范的LR分析表基于LR(1)项目来构造识别G?活前缀的DFA。1、拓广文法S??SS?BBB?bBB?a15/46

3.5LR分析器构造规范的LR分析表基于LR(1)项目来构造识别G?活前缀的DFA。2、构造LR(1)项目集规范族I0:S??.S,$ S?.BB,$ B?.bB,b/a B?.a,b/a 闭包函数closure(I)1、I的每个项目均加入closure(I)2、如果[A?α·Bβ,a]在closure(I)中，且B?η是产生式，那么如果项目[B?·η,b]还不在closure(I)中的话，那么把它加入(其中b属于FIRST(βa))。S??SS?BBB?bBB?a

3.5LR分析器构造规范的LR分析表基于LR(1)项目来构造识别G?活前缀的DFA。2、构造LR(1)项目集规范族I0:S??.S,$ (核心项目)S?.BB,$ (非核心项目， B?.bB,b/a 通过对核心项目求闭包 B?.a,b/a 而获得）S??SS?BBB?bBB?a

3.5LR分析器S??·S,$I0S?·BB,$B?·bB,b/aB?·a,b/aS??SS?BBB?bBB?a

3.5LR分析器S??·S,$I0S?·BB,$B?·bB,b/aB?·a,b/aS??S·,$I1S?B·B,$B?·bB,$B?·a,$I2SBB?b·B,b/aB?·bB,b/aB?·a,b/aI3B?a·,b/aI4abS??SS?BBB?bBB?a

3.5LR分析器S??·S,$I0S?·BB,$B?·bB,b/aB?·a,b/aS??S·,$I1S?B·B,$B?·bB,$B?·a,$I2SBB?b·B,b/aB?·bB,b/aB?·a,b/aI3B?a·,b/aI4aabbS?BB·,$I5B?b·B,$B?·bB,$B?·a,$I6B?bB·,$I9B?a·,$I7B?bB·,b/aI8BbbBaaB20/46S??SS?BBB?bBB?a

3.5LR分析器构造规范的LR分析表基于LR(1)项目来构造识别G?活前缀的DFA。从Ii构造分析器的状态i,状态i的action函数如下确定如果[A??·a?,b]在Ii中，且goto(Ii,a)=Ij，那么置action[i,a]为sj。如果[A??·,a