编译原理5.3.4-规范LR分析表的构造.ppt_第1页
编译原理5.3.4-规范LR分析表的构造.ppt_第2页
编译原理5.3.4-规范LR分析表的构造.ppt_第3页
编译原理5.3.4-规范LR分析表的构造.ppt_第4页
编译原理5.3.4-规范LR分析表的构造.ppt_第5页
已阅读5页,还剩16页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

5.3.4 规范LR分析表的构造,通过例子引入LR(k)项目 1.LR(k)项目定义 2.有效LR(1)项目 3.构造LR(1)项目集规范族 4.构造LR(1)分析表 5.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:移进-归约冲突,例:,FOLOW(R) = # , =,文法不含有以 R= 为前缀的规范句型, 因此不能用 RL 对于栈顶的L进行归约,(0) S S (1) S aAd (2) S bAc (3) S aec (4) S bed (5) A e,FOLLOW(A)=c,d,I5,I7中冲突不能用SLR(1)方法解决,补充例1,(0) S S (1) S aAd (2) S bAc (3) S aec (4) S bed (5) A e,I5:S aec A e,I7:S bed A e,所有可能的规范推导序列: S= S = aAd = aed S= S = bAc = bec S= S = aec S= S = bed,I5识别活前缀ae,不存在规范句型aAc, 当面临输入符号为c时应移进 面临d时应用产生式Ae归约,I7识别活前缀be,不存在规范句型bAd, 当面临输入符号为d时应移进 面临c时应用产生式Ae归约,结论: 并不是FOLLOW(A)的每个元素, 在含A的所有句型中,在A的后面都会出现,小结: SLR(1)分析法中的无效归约,I2: SL =R R L,(0)S S (1)S L=R (2)S R (3)L *R (4)L i (5)R L,FOLLOW(R) = # , =,(0) S S (1) S aAd (2) S bAc (3) S aec (4) S bed (5) A e,I5:S aec A e,I7:S bed A e,FOLLOW(A) = c,d,在SLR(1)方法中,若项目集Ik含有 A ,则在状态k时,只要所面临的输入符号aFOLLOW(A),就用A归约 栈里的符号串所构成的活前缀未必允许把归约为A,因为可能没有一个规范句型含有前缀Aa。因此,在这种情况下,用A进行归约未必有效。,1.LR(K)项目定义,重新定义项目: A,a1a2ak A是一个LR(0)项目, 称为心, a1a2ak 称为它的向前搜索符串(展望串), ai是终结符, 这样的一个项目称为一个LR(k)项目。,向前搜索符串仅对归约项目A,a1a2ak有意义.对于任何移进或待约项目不起作用。,若存在规范推导 则项目 A 对活前缀 是有效的。 若aFirst(), 若= 则 a=# 则LR(1)项目A, a对于活前缀 是有效的。 注: 1)如果aFirst(),即使aFollow(A), 项目A, a也是无效的。 2)规范LR分析法仅考虑有效的LR(1)项目。,2.有效LR(1)项目,例5.12 : S BB B aB | b,BaB, a 对活前缀 = aaa是有效的,BaB, # 对活前缀 = Baa是有效的,3.构造LR(1)项目集规范族,一、项目集I的闭包CLOSURE(I) (1)I的任何项目都属于CLOSURE(I) (2)若项目AB,a属于CLOSURE(I) 如果B,b原来不在CLOSURE(I)中, 则把它加进去。 B是一个产生式, bFIRST(a) (3)重复执行步骤(2),直到CLOSURE(I)不再增大为止,二、GO函数 令I是一个项目集,X是一个文法符号, GO(I,X) = CLOSURE(J),其中 J= 任何形如AX,a的项目 | AX,aI 注:在执行转换函数GO时,搜索符并不改变。,三、构造G的LR(1)项目集族C的算法,BEGIN C:= CLOSURE( SS, # ) ; 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)项目集规范族,I0 : CLOSURE(SS,#) S S, # S BB, # B aB, a/b B b, a/b,S,B,b,b,b,a,B,B,a,a,b,a,B,图5.10 LR(1)项目集和GO函数 p116,(0)S S (1)S BB (2)B aB (3)B b,4.构造LR(1)分析表,(1)若项目Aa,bIk 且GO(Ik,a)=Ij , 置 ACTIONk,a为 sj。 (2)若项目A ,aIk ,j是产生式A的编号 置 ACTIONk,a为rj , (3)若项目SS ,#Ik, 置 ACTIONk,#为 acc。 (4) 若GO(Ik,A)=Ij, 置 GOTOk,A=j。 (5)分析表中凡不能用规则(1)(4)填入的空白格均置为“出错标志”。,表5.5 例5.13 的 LR分析表 p116,5.LR(1)文法,若文法G按构造LR(1)分析表算法构造出来的分析表不包含多重定义项,则该文法G是LR(1)文法。 注: 1)每个SLR(1)文法都是LR(1)文法, 反之不一定成立; 2)一个文法的规范LR分析表比其SLR分析表含有更多的状态。在严重的情况下,状态数可能成倍增长。因此需要简化。,文法5.9 p113 (0)S S (1)S L=R (2)S R (3)L *R (4)L i (5)R L,例,求LR(1)项目集规范族,简化为,I1: Go(I0 , S) S S , #,I2: Go(I0 , L) SL =R, # RL , #,I3: Go(I0 , R) SR , #,I4: Go(I0 , *) L* R, =/# R L, =/# L *R, =/# L i, =/#,I5: Go(I0 , i) L i , =/#,I6: Go(I2 , =) SL= R, # R L, # L *R, # L i, #,I7: Go(I4 , R) L* R , =/#,I8: Go(I4 , L) R L , =/#,Go(I4 , *) 同 I4,Go(I4 , i) 同 I5,I9: Go(I6 , R) SL=R, #,I10: Go(I6 , L) R L , #,I11: Go(I6 , *) L* R, # R L, # L *R, # L i, #,I12: Go(I6 , i) L i , #,I13: Go(I11 , R) L* R ,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论