天津科技大学编译原理----第4章语法分析.ppt

语法分析 * I1、I2和I9都含有“移进－归约”冲突。 FOLLOW(E)＝{#, ), +}， I2: E→T· T→T·*F I1: S?→E· E→E·+T I9: E→E+T· T→T·*F 4.5.3 SLR(1)分析法 语法分析 * 其分析表如下: 语法分析 * S’→?S S’→S? S→r?D r S S→rD? D→D?,i D→i? D→D,?i , i S→?rD I0 I1 I2 I3 I4 I5 D→?D,i D→?i D→D,i? i I6 D 例 文法G’：(0) S’→S (1) S→rD (2) D→D, i (3) D→i FOLLOW(S’)={$} FOLLOW(S)={$} FOLLOW(D)={$ ，} 状态 ACTION GOTO r , i $ S D 0 S2 ? ? ? 1 ?1 ? ? acc 2 ? S4 ? 3 3 S5 ? r1 4 r3 ? r3 5 ? S6 ? 6? r2 ? r2 语法分析 * 本章小结 两种自顶向下分析方法 递归子程序法 预测分析法 一种文法：LL(1)文法 判别方法 非LL(1)到LL(1)的转换 算符优先分析法 应用于算符优先文法 构造算符优先关系表和算符优先关系函数 算符优先分析 语法分析 * LR(0)、SLR(1)、LR(1)、LALR(1)方法比较实际上不同LR方法之间的主要区别就在于归约的判定方法上： LR(0)是不看展望符判定归约； SLR(1)是看展望符，但把所有B→? ? 的展望符集均定义为Follow(B)。即把符号栈顶上的句柄?归约为B的条件是：展望符为Follow(B)中的元素。换句话说，归约任何位置上的B，都用统一的展望符集； 本章小结 语法分析 * 4.5.4 LR(1)分析法 仍有许多文法构造的LR(0)项目集规范族存在的动作冲突不能用SLR(1)方法解决 语法分析 * 例如：文法G: (0) S →S (1) S → L=R (2) S →R (3) L →*R (4) L →i (5) R →L 识别文法活前缀的DFA I0: S’-?S S- ?L=R S- ?R L- ?*R L- ?i R- ?L I5: L →i ? I2: S- L ? =R R- L ? I3: S- R ? I4: L →* ? R R → ? L L → ? *R L → ? i I1: S’-S ? I6: S →L= ? R R →L ? R → ? L L → ? i L → ? *R I7: L →*R ? I8: R →L ? I9: S →L= R ? S L R * i = R L * i R L i * 语法分析 * I6: S →L= ? R R →L ? R → ? L L → ? i L → ? *R Follow(R)={$,=}与移进符号集{ *, i}交集为空，可用SLR(1)方法解决冲突 I2: S- L ? =R R- L ? Follow(R)={$,=}与移进符号集{=}交集不为空，SLR(1)方法不能解决冲突，该文法不是SLR(1)文法。 S →S S →L=R |R L →*R | i R →L Follow S’ $ S $ L =，$ R $，= 语法分析 * 4.5.4 LR(1)分析法 SLR(1)用FOLLOW信息作为展望信息（只对属于FOLLOW集的输入符号归约），缩小了归约范围，消除了一些无效归约，解决了项目集中的一些简单的冲突。 尽管FOLLOW(A)中包含了所有含A的句型中A后的可能终结符，但并不是每个含有A的句型中，A的后面都可以出现Follow(A)中的每一个符号，所以SLR(1)未能从根本上消除所有无效归约。 语法分析 * S →S S →L=R |R L →*R | i R →L S’ S L = R * R L 在*L=R中，L可以被归约为R，此时L后只能是‘=’，而不能是Follow(R)={$,=}中的‘$’ S’ S L1 = R L2 在L1=L2中，L2可以被归约为R，此时L2后只能是‘$’，而不能是Follow(R)={$,=}中的‘=’ LR(1)方法正是要解决SL