编译原理(版)LR().pptVIP

6.4 LR(1)和LALR(1)分析规范LR分析 例1文法G 0）S`→S (1) S→aAd (2) S→bAc (3) S→aec (4) S→bed (5) A→e I0: S`→．S I1: S`→S． I2: S→a．Ad S→．aAd S→a．ec S→．bAc A→．e S→．aec S→．bed I3: S→b．Ac I4: I5: S→b．ed S→aA．d S→ae．c A→．e A→e ． I6: I7: I8: S→bA．c S→be．d S→aAd． A→e． I9: S→aec． I10: S→bAc． I11: S→bed． ( 0）S’→S (1) S→aAd (2) S→bAc (3) S→aec (4) S→bed (5) A→e非 LR(0),非SLR(1) I5: S →ae．c I7: S →be．d A →e． A →e． S’==S==aAd==aed S’==S==bAc==bec S’==S==aec S’==S==bed ae是活前缀 be是活前缀 aAc不是规范句型 , bAd不是规范句型 不作无效归约 ？信息－ 在特定的规范推导中，哪些输入符号能跟在句柄之后 G[S]: 若S = αAω =αβω r是αβ的前缀，则 称r是G的一个活前缀. 哪个项目在什么条件下对某个活前缀有效 例2 G[S]:(0) S`→S (1) S→L=R (2) S→R(3) L→ *R (4) L→id (5) R→L I0: S – ?S S – ?L = R S – ?R R – ?L L – ?id L – ?*R I1: S – S? I2: S – L? = R R – L? I3: S – R? I4: L – *?R R – ?L L – ?*R L – ?id I5: L – id? I6: S – L =?R R – ?L L – ?*R L – ?id I7: L – *R? I8: R – L? I9: S – L=R? I2: S – L? = R R – L? 考虑分析表达式 id = id时，在工作到 I2 处已经把第一个 id 归约到 L了, 看到下一个输入 = 要作决策，第一个项目要设置 Action[2,=] 为S6, 即把赋值的其它部分找到. 但 =也是属于 Follow(R) 的. 第二个项目要用 R–L归约.出现 shift-reduce 冲突. 若将栈顶的符号序列归约到 R,会有问题！因为不可能有规范句型以 R = …开头 (有以 *R = ... 开头的规范句型). SLR（1）的局限 follow 集包含了在任何句型中跟在 R 后的符号但没有严格地指出在一个特定的推导里哪些符号跟在 R后.所以需要扩充状态以包含更多的信息：follow 集的哪些部分 才是进到该状态最恰当的归约依据. 处在状态 2时，试图构建句子有两条路： 1.S ?L = R 或 2.S ? R ? L. 如下一符号是 =, 那就不能用第二个选择，必须用第一个,即移进. 只有下一个符号是#时才能归约. 尽管