《编译原理534-规范LR分析表的构造》精选课件.pptVIP

5.3.4 规范LR分析表的构造 通过例子引入LR(k)项目 1.LR(k)项目定义 2.有效LR(1)项目 3.构造LR(1)项目集规范族 4.构造LR(1)分析表 5.LR(1)文法 小结: SLR(1)分析法中的无效归约 1.LR(K)项目定义 重新定义项目: [A→α·β，a1a2…ak] A→α·β是一个LR(0)项目, 称为心, a1a2…ak 称为它的向前有哪些信誉好的足球投注网站符串(展望串), ai是终结符, 这样的一个项目称为一个LR(k)项目。 2.有效LR(1)项目 例5.12 : S ? BB B ? aB | b 3.构造LR(1)项目集规范族 一、项目集I的闭包CLOSURE(I) (1)I的任何项目都属于CLOSURE(I) (2)若项目[A→α·Bβ，a]属于CLOSURE(I) 如果[B→·γ,b]原来不在CLOSURE(I)中， 则把它加进去。 B→γ是一个产生式, b∈FIRST(βa) (3)重复执行步骤(2),直到CLOSURE(I)不再增大为止 二、GO函数 令I是一个项目集，X是一个文法符号， GO(I,X) = CLOSURE(J)，其中 J={ 任何形如[A??X??,a]的项目 | [A???X?,a]?I } 注：在执行转换函数GO时，有哪些信誉好的足球投注网站符并不改变。 三、构造G的LR(1)项目集族C的算法 BEGIN C:= { CLOSURE({ [S??S, #] }) }; REPEAT FOR C中的每个项目集I和G的每个文法符号X IF GO(I, X)非空 且不属于 C THEN 把GO(I, X)加入C中； UNTILL C不再增大； END 例5.13 考虑如下拓广文法 p115 (0)S? S (1)S ? BB (2)B ? aB (3)B ? b 构造LR(1)项目集规范族 4.构造LR(1)分析表 (1)若项目[A→α·aβ,b]?Ik 且GO(Ik,a)=Ij ， 置 ACTION[k,a]为 sj。 (2)若项目[A→α· ,a]?Ik ，j是产生式A→α的编号 置 ACTION[k,a]为rj ， (3)若项目[S→S· ，#]?Ik， 置 ACTION[k,#]为 acc。 (4) 若GO(Ik,A)=Ij， 置 GOTO[k,A]=j。 (5)分析表中凡不能用规则(1)～(4)填入的空白格均置为“出错标志”。 5.LR(1)文法 若文法G按构造LR(1)分析表算法构造出来的分析表不包含多重定义项，则该文法G是LR(1)文法。 注: 1）每个SLR(1)文法都是LR(1)文法， 反之不一定成立； 2）一个文法的规范LR分析表☆比其SLR分析表含有更多的状态。在严重的情况下，状态数可能成倍增长。因此需要简化。 补充练习 LR(0)分析, 归约时向前查看的符号为____________ SLR(1)分析,归约时向前查看的符号为____________ LR(1)分析, 归约时向前查看的符号为____________ * * 文法5.9 p113 (0)S ?S (1)S ?L=R (2)S ?R (3)L ?*R (4)L ? i (5)R ?L I2:移进-归约冲突 例: I0: S??S S? ?L=R S? ?R L? ?*R L? ? i R? ?L I6: S?L=?R R? ?L L? ?*R L? ?i I2: S?L?=R R? L? I4:L?*?R R? ?L L? ?*R L? ?i I1: S?S? I3:S?R? I7:L?*R? I8:R?L? I5:L?i ? I9:S?L=R? = R * R L i R S * i i L * L FOLOW(R) = {# , =} 文法不含有以 R= 为前缀的规范句型, 因此不能用 R?L 对于栈顶的L进行归约 (0) S? S　　 (1) S ? aAd　　 (2) S ? bA