编译原理
7.4 LR(1)分析表的构造 3.解决问题的方法分析文法G[S]中所有以T作为句柄的句型:当T作为一个句型的句柄时,T后的符号一定在FOLLOW(E),但并不是FOLLOW(E)中的每一个符号都可以出现在每一个句柄T后。句柄一定和某条产生式的右部相同,但并非和产生式右部相同的符号串都是句柄。如何记住每一个句柄的上下文? 4.LR(1)项目
7.4 LR(1)分析表的构造 向前搜索符号[U→v.w, a]含义:已经从输入符号串中获得了句柄vw中的v,还希望从输入符号串中进一步获得w,并且当在分析栈顶获得完整的vw后,只有下一个输入符号是a时,才可将vw归约成U,否则不能归约。向前搜索符a只对归约项目[U→vw.,a]有意义。在其它项目中,a只是起一个传递作用。
7.4 LR(1)分析表的构造 5.构造识别规范句型活前缀的DFA——以LR(1)项目集为状态◆构造一个状态假设I为文法的任一项目集(开始时仅包含[S′→.S,$],S′为拓广文法的识别符号),重复下述步骤求CLOSURE(I):ⅰ. I的任何项目均属于CLOSURE(I)ⅱ.如果[A→α.Bβ,a]属于CLOSURE(I),则所有[B→.γ,b]也属于CLOSURE(I),这里终结符b∈FIRST(βa)。上述工作重复到CLOSURE(I)不再扩大为止,此CLOSURE(I)即为所求的一个项目子集,将其作为DFA的一个状态。
7.4 LR(1)分析表的构造 5.构造识别规范句型活前缀的DFA——以LR(1)项目集为状态◆构造DFA的映射ⅰ.若状态Ii中含有项目[A→α.Xβ,a](X∈V,α,β为任一符号串),则从Ii出发,以X为标记作一弧,引出一新状态Ij Ij=CLOSURE({[A→αX.β,a]|[A→α.Xβ,a]在Ii中}) Ii和Ij之间的这种转换关系用函数GOTO(Ii,X)=Ij表示。ⅱ.若Ii和Ij相同,则取消Ij,而GOTO函数为GOTO(Ii,X)=Ii。
7.4 LR(1)分析表的构造 6.构造识别规范句型活前缀的DFA——举例 G[Z]:[1] Z→S[2] S→L=R[3] S→R[4] R→L[5] L→*R[6] L→i
1 G[Z]:[Z→S.,#][1] Z→S[2] S→L=R[3] S→R[4] R→L I0 S L R[Z→.S,#][5] L→*R[S→.L=R,#][6] L→i
I
I2[S→L.=R,#][R→L.,#] I3[S→R.,#] I4[L→*.R,=][L→*.R,#][R→.L,=][R→.L,#][L→.*R,=][L→.i,=][L→.*R,#][L→.i,#] i I5[L→i.,=][L→i.,#] L
I9[S→L=R.,#]= R I10[S→L=.R,#] L[R→L.,#][R→.L,#][L→.*R,#] * *[L→.i,#] L I11 i I12[L→*.R,#] i[R→.L,#][L→i.,#][L→.*R,#][L→.i,#] I7 R[L→*R.,=] I R 13[L→*R.,#][L→*R.,#] I6 I8[R→L.,=][R→L.,#]
[S→.R,#][L→.*R,=][L→.i,=][R→.L,#][L→.*R,#][L→.i,#] i
*
*
LR(1)项目集规范族:{ I0,I1,…,I11}

第七章 LR分析法 基本思想:LR分析法也是一种自底向上的分析过程,第六章讨论的自底 向上的分析是一种移进—归约过程,当分析栈顶符号串形成句柄时就归 约,...
第七章 LR分析法 分析法 7.1 LR分析法概述 分析法概述 7.2 LR(0)分析法 分析法 7.3 SLR(1)分析法 分析法 7.4 LR(1)分析法 分析法 1 7.1 LR...
4. 1. LR分析概述:一个LR分析器由以下三部分组成: ① LR分析程序 对于同类的LR分析器,分析程序是相同的。 ② 分析表 是核心,分为动作表(ACTION)和状态转换...
第7章 LR分析主讲:张丽虹 计算机工程学院 网络工程系 【知识结构】 第七章 LR分析 ? 本章内容– ––––– 7.1 7.2 7.3 7.4 7.5 7.6 LR分析...
LR分析中的应用。 【学习指南】 LR分析法的归约过程是规范推导的逆过程,所以LR分析 过程是一种规范归约过程。 LR分析法正是给出一种能根据当前分析栈中的符号...
4. 1. LR分析概述: 分析概述: 分析概述一个LR分析器由以下三部分组成: 一个 分析器由以下三部分组成: 分析器由以下三部分组成 ① LR分析程序 分析程序 对于...
bcde# bcde# cde# cde# de# e# e# # # (4)B->d ACTION GOTO S2 S4 R2 3 S6 R3 3 S5 S8 R4 7 S9 R1 1 acc 7.2 LR(0) 分析 ? ...
编译方法 第7章 LR分析法 7.1 LR分析概述 7.2 LR(0)分析表 7.3 SLR(1)分析表 7.4 LR(1)分析表 7.5 LALR(1)分析表 第7章 LR分析法 7.1 LR...
第7章 LR分析法 LR(k)---从左向右扫描的右分析方法 其中:k代表向后看k个符号来决定归约的句柄。 LR(0) :向后看0个符号来决定的句柄 LR(1) :向后看1...
S0 … # LR分析程序 输出 action goto 分析表 LR分析器的模型 1、分析栈:由状态栈与归约符号栈两部分 2、分析表:由动作表与状态转换表两部分组成 1)action...
热门文档