编译原理实践及应用第4章LR分析方法(2638KB).ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 在LR(1)分析表中，若存在两个状态（项目集）除向前有哪些信誉好的足球投注网站符不同外，其它部分都是相同的，称这样的两个LR(1)项目集是同心的 。 如果把同心的LR(1)项目集合并，心仍相同（心就是一个LR(0)项目集），超前有哪些信誉好的足球投注网站符集为各同心集超前有哪些信誉好的足球投注网站符的并集，合并同心集后go函数自动合并。称为LALR方法。 构造LALR分析表的算法： （1）构造LR(1)项目集规范族，C={I0，I1，…，In}。 （2）合并所有的同心集，得到LALR(1)的项目集族C={J0，J1，…，Jm}。含有项目[S→·S,#] 为初态。 （3）由C‘构造动作(action)表。 ① 若[A→α·aβ,b]∈Jk，且GO(Jk,a)＝Jj，其中a∈VT，则置action[k,a]=Sj， ② 若项目[A→α·,a]∈Jk，其中a∈VT，则置action[k,a]=rj，rj的含义是按产生式A→α进行归约 ③ 若项目[S→S·,#]∈Ik，则置action[k,#]=acc，表示分析成功，接受。 （4）goto表的构造。若不是同心集的项目集，转换函数的构造与LR(1)的相同；假定Ii1,Ii2，…，Iin是同心集，合并后的新集为Jk，转换函数GO(Ii1,X)，GO(Ii2,X)，…，GO(Iin,X)也为同心集，将其合并后记作Ji，因此，有GO(Jk,X)= Ji，所以当X为非终结符时，GO(Jk,X)=Ji，则置goto[k,X]=i，表示在k状态下遇到非终结符X时，把X和i分别移到文法符号栈和状态栈。 （5）分析表中凡不能用(3)、(4)填入信息的空白均填上“出错标志”。 该文法的LR(1)项目集规范族 例：文法 （0）S→S （1）S→BB （2）B→bB （3）B→a LR(1)分析表为： 状 态 action goto b a # S B 0 S3 S4 1 2 1 acc 2 S6 S7 5 3 S3 S4 8 4 r3 r3 5 r1 6 S6 S7 9 7 r3 8 r2 r2 9 r2 I3和I6，I4和I7，I8和I9分别为同心集，将同心集合并后为： I36：B→a·B,a/b/# B→·aB,a/b/# B→·b,a/b/# I47：B→b·，a/b/# I89：B→aB·，a/b/# 同心集合并后仍不包含冲突，因此该文法是LALR文法。 得到LALR分析表： 状态 action goto b a # S B 0 S3,6 S4,7 1 2 1 acc 2 S3,6 S4,7 5 3,6 S3,6 S4,7 8,9 4,7 r3 r3 r3 5 r1 8,9 r2 r2 r2 * * * * * * * * * * * * * * * * * * * * * * * * * * * 1. 拓广文法：在原文法G[S]上增加一个产生式S →S，这是为了得到唯一的接受状态S →S · 2. 设项目集规范族C只包含第一个状态{S→ · S}的闭包，即C = { Closure({S → · S}) } 3. 利用GO函数对C中的每个项目集和每个符号X计算其下一状态，并将下一状态GO(I,X)加入到C中，直到C中状态数不再增加 C即为文法G的LR(0) 项目集规范族 LR(0)项目集规范族的构造算法： 前述的例子中，是已经拓广了的文法 1. S ?·E 2. S ?E · 3. E ?·aA 4. E ?a·A 5. E ?aA· 6. A ? · cA 7. A ?c · A 8. A ?cA · 9. A ?·d 10. A ? d· 11. E ?·bB 12. E ? b·B 13. E ? bB· 14. B ?·cB 15. B ?c·B 16. B ?cB · 17. B ?·d 18. B ? d· 初始时，设置 C = { Closure( {S ?·E} ) }, 是一个状态,即 C ={ {S?·E, E ?·aA , E ?·bB } } 再根据C中的每个状态的go函数，求出更多的状态，直到状态数不再增多为止 例：设文法G为： E ?aA｜ bB A ?cA｜d B ?cB｜d 求该文法的LR(0)分析表。 (0) S ?E (1) E ?aA (2) E ?bB (3) A ?cA (4) A ?d (5) B ?c