编译原理
7.5 LALR(1)分析表的构造 1. LR(1)方法的不足——分析表太庞大。如何解决存储空间的有效使用问题?
G[Z]:[1] Z→S[2] S→L=R[3] S→R[4] R→L[5] L→*R[6] L→i
I1
I2[Z→S.,#] I3[S→L.=R,#][R→L.,#][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.,#]
R L I0[Z→.S,#][S→.L=R,#][S→.R,#][R→.L,#][L→.*R,=][L→.i,=][L→.*R,#][L→.i,#] S i *
*
G[Z]:[1] Z→S[2] S→L=R[3] S→R[4] R→L[5] L→*R[6] L→i
I1
I2[Z→S.,#] I3[S→R.,#] I411[L→*.R,=][L→*.R,#][R→.L,=][R→.L,#][L→.*R,=][L→.i,=][L→.*R,#][L→.i,#] i I512[L→i.,=][L→i
.,#] L[S→L.=R,#][R→L.,#]
I9[S→L=R.,#]= I6 R[S→L=.R,#][R→.L,#][L→.*R,#][L→.i,#] i * I512 I713 R I810[R→L.,=][R→L.,#][L→*R.,=][L→*R.,#] L I810
状态 0 1 2 3 411 512 6 713 810
ACTION i S5 * S4 acc S6 S512 S12 S411 r5 S11 r4 r3 r4 r3 r5 r3 r2=# S 1
GOTO L 2 R 3
ACTION[i,a]=“Sj”。②若[S′→S.,$]∈Ii, i则ACTION[i,$]=“acc”。③若[U→x.,a]∈Ii,则置ACTION[i,a]=“rj”。④若GOTO(Ii,U)=Ij,则置GOTO[i,U]=“j”。⑤其余元素均置“报错标志”。
R S L[Z→.S,#][S→.L=R,#][S→.R,#][R→.L,#][L→.*R,=][L→.i,=]①若[U→x.ay,b]∈Ii,[L→.*R,#] GO(Ii,a)=Ij,则[L→.i,#] I0 *
*
810
713
810
9
411
7.6二义文法的LR分析 文法的二义性在分析表中体现为一个表项的冲突定义,从而导致语法分析程序无法依据分析表进行语法分析。二义性文法的优势:◆灵活——对优先级、结合顺序的修改不影响原文法规则和识别程序的状态个数。◆效率高——不必为单非产生式(描述结合顺序、优先级)进行归约。◆可读性好——易于理解。
7.6二义文法的LR分析 为二义性文法构造LR分析表:⑴先构造出识别规范句型活前缀的有穷自动机;⑵得到有冲突的LR分析表;⑶分析冲突原因,确定无二义性规则;⑷根据无二义性规则去除分析表中的冲突定义。

第七章 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...
热门文档