设为首页 | 加入收藏夹

八文网 - 汇聚八方文档 - 做最优秀的免费文档下载网站

编译原理

文档类型：

Microsoft PowerPoint PPT 演示文稿文档大小：556.5KB

编译原理
第一章编译程序概述
第二章PL0编译程序的实现
第三章文法和语言
第四章词法分析
第五章自顶向下语法分析方法
第六章自底向上优先分析方法
第七章LR分析方法
第八章语法制导翻译和中间代码生成
第九章符号表
第一○章代码优化
第一一章代码生成
第六章我们学过自底向上分析法的关键问题是在分析过程中如何确定句柄.LR分析法与第6章介绍的运算符优先函数一样,LR方法也是通过求句柄逐步归约进行语法分析.在运算符优先函数中、句柄是通过运算符的优先关系而求得,LR方法中句柄是通过求可归前缀而求得.
LR分析概述LR(k)分析是根据当前分析栈中的符号串和向右顺序查看输入串的k(k≥0)个符号就可以唯一确定分析的动作是移进还是归约以及用哪个产生式归约.
从左到右扫描(L)自底向上进行规约(R)
(是规范规约)LR分析的优缺点1)适合文法类足够大,适用于大多数上下文无关文法2)分析效率高3)报错及时4)手工实现工作量大5)可以自动生成美国Bell实验室推出的编译程序自动构造工具YACC:能接受一个用BNF描述的满足LALR(1)上下文无关文法并对其自动构造出LALR(1)分析器.
第七章LR分析法
一、LR分析概述(基本构造原理与方法)
二、LR(0)分析
三、SLR(1)分析
四、LR(1)分析
五、LALR (1)分析LR分析器模型总控程序outputInputXm栈状态文法符号ACTIONGOTOLR分析表产生式表
逻辑上说,一个LR分析器由3个部分组成:
(1) 总控程序,也可以称为驱动程序.对所有的LR分析器总控程序都是相同的.
(2)_分析表或分析函数,不同的文法分析表将不同、同一个文法采用的LR分析器不同时,分析表也不同、分析表又可分为动作表(ACTION)和状态转换(GOTO)表两个部分,它们都可用二维数组表示.
(3) 分析栈,包括文法符号栈和相应的状态栈,它们均是先进后出栈.
分析器的动作就是由栈顶状态和当前输入符号所决定.
2,LR分析方法的逻辑结构总控程序根据不同的分析表来决定其下一步的处理动作,分析表是根据具体的文法按某种规则构造出来的.LR方法是根据具体文法的分析表对输入串进行分析处理.
LR分析过程的思想是在总控程序的控制下,从左到右扫描输入符号串,根据分析栈中的状态和文法及当前输入符号,按分析表完成相应的分析工作.
分析表的组成:
(1) 分析动作表Actionaction[Sn , at]Snat符号表中action[Si,aj]为二维数组,指出当前栈顶为状态Si,输入符号为aj是所执行的动作.其动作有四种可能,分别为移进(S),归约(r),接受(acc),出错(error).
(2) 状态转换表gotoxt表中goto[Si,xj]指出栈顶状态为Si,文法符号为xj时应转到的下一状态.
分析表种类的不同决定使用不同的LR分析方法a) SLR分析表(简单LR分析表)b) LR分析表(规范LR分析表)构造简单,最易实现,大多数上下文无关文法都可以构造出SLR分析表,所以具有较高的实用价值.使用SLR分析表进行语法分析的分析器叫SLR分析器适用文法类最大,大多数上下文无关文法都能构造出LR分析表,但其分析表体积太大.暂时实用价值不大.c) LALR分析表(超前LR分析表)这种表适用的文法类及其实现上难易在上面两种之间,在实用上很吸引人.使用LALR分析表进行语法分析的分析器叫LALR分析器.
例:YACC文法规则文件YACC源文件YACC某语言的LALR分析器
1.三种分析表对应三类文法几点说明
2.一个SLR文法必定是LALR文法和LR文法
3,LR分析过程:
LR分析步骤:
(a) 将初始状态S0和句子的左界符分别进分析栈.
(b) 根据栈顶状态和当前输入符号查动作表,进行如下的工作.
※移进:当前输入符号进符号栈,根据状态转换表新的状态进状态栈,继续扫描,从而下一输入符号变成当前输入符号.
※归约: (1)按某个产生式进行归约,若产生式的右端长度为n,则符号栈顶和状态顶n个元素同时相应退栈.(2)归约后的文法符号进符号栈,(3)查状态转换表,新的状态进状态栈.
(c) 接受:分析成功,终止分析.
(d) 出错:报告出错信息.
(2) 具体分析过程:
举例说明具体分析过程:设文法为G[L] (假定已存在LR分析表)LR分析算法置ip指向输入串w的第一个符号令S为栈顶状态a是ip指向的符号重复beginif ACTION[S,a=Sjthen begin PUSH j,a(进栈)ip 前进(指向下一输入符号)endelse if ACTION[S,a=rj (第j条产生式为A )then beginpop | | 项令当前栈顶状态为Spush GOTO[S,A]和A(进栈)else if ACTION[s,a=accthen return (成功)else errorend.重复为了介绍LR分析过程,在这里直接给出该文法的分析表,之后再介绍如何生成该表.
accEL,bari表示按第i个产生式进行归约Si表示把当前输入符号移进栈,且转第i个状态、即第i个状态进状态栈.
i表示转第i个状态、即第i个状态进状态栈.空白表示分析动作出错.根据上述分析表,即可对输入串进行分析.如输入串为a,b,a具体分析过程如下:b和S4进栈E,b, 和S5进栈b,ab和S4退栈E和S2进栈E bE,Ea和S3退栈E aa和S3进栈S0和进栈说明输入符号产生式符号栈状态栈E,L和S2S5S6退L和S1进栈L和S6进栈E,LE和S2退栈L E自底向上分析法的关键问题是在分析过程中如何确定句柄.LR方法中的句柄是通过求可归前缀而求得.
例:文法G[S]为:SaAcBeAbAAbBd
为产生式加序号变为:SaAcBe[1]
对于输入串abbcde句子的最右推导(规范推导)如下:活前缀与可归前缀
对它的逆过程最左归约(规范归约)为:aAcdS用哪个产生式继续归约仅取决于当前句型的前部.我们把每次采取归约动作前的符号串部分称为可归前缀.LR分析的关键就是识别何时到达可归前缀.在规范句型中形成可归前缀之前包括可归前缀的所有前缀称为活前缀.活前缀为一个或若干规范句型的前缀.在规范归约过程中的任何时刻只要已分析过的部分即在符号栈中的符号串均为规范句型的活前缀、则表明输入串的已被分析过的部分是某规范句型的一个正确部分.
例如:有下面规范句型的前缀:
左部均为活前缀、其中、红色部分为可归前缀活前缀的定义及在LR分析中的应用G=(Vn,Vt,P,S),若有S αAωαβω、Aβ( β是句柄)γ是αβ的前缀、则称是文法G的活前缀αβ是含句柄的活前缀、并且句柄是αβ的后端,则称αβ是可归前缀或可规范前缀.
在LR分析过程中、实际上是把αβ的前缀(即文法G的活前缀)列出放在符号栈中、一旦在栈中出现αβ(形成可归前缀)、即句柄已经形成,则用产生式A β进行归约.
RP126 识别活前缀的有限自动机对任何一个上下文无关文法,只要能构造出它的识别可归前缀的有限自动机、就可以构造其相应的分析表(状态转换表和动作表).
☆状态栈:S0,S1,Sm 状态S0-初始状态Sm-栈顶状态栈顶状态概括了从分析开始到该状态的全部分析历史.
☆符号栈: X1X2. Xm为从开始状态(S0)到当前状态(Sm)所识别的规范句型的活前缀.
☆分析表
是一个矩阵:行-分析器的状态列-文法符号TF:GOTO表a. 状态转移表(GOTO表)Si-1 -当前状态(栈顶状态)xi - 新的栈顶符号Si新的栈顶状态(状态转移)
Si需要满足条件是:
若X1X2. Xi-1是由S0到Si-1所识别的规范句型的活前缀、则X1X2. Xi是由S0到Si所识别的规范句型的活前缀
通过对有穷自动机的了解,我们可以看出:
状态转移函数GOTO是定义了一个以文法符号集为字母表的有穷自动机、该自动机识别文法所有规范句型的活前缀及可归前缀.
SiXib. 分析动作表(ACTION表)状态s输入符号aiACTION表ACTION[Si,a=动作分析a∈Vt识别为活前缀的,则移进;识别为可归前缀的,则归约
分析动作:1)移进(shift)ACTION[Si,a=S
动作:将a推进栈,并设置新的栈顶状态SjSj=GOTO[Si,a,将指针指向下一个输入符号2)规约(reduce)ACTION[Si,a=rd
d:文法规则编号(d) A→β
动作:将符号串β(假定长度为n)连同状态从栈内弹出把A推进栈,并设置新的栈顶状态Sj , Sj=GOTO[Si-n,A]3)接受(accept)ACTION[Si=accept4)出错(error)ACTION[Si,a=error
☆控制程序:(Driver Routine)1) 根据栈顶状态和现行输入符号,查分析动作表(ACTION表),执行有分析表所规定的操作;
2) 并根据GOTO表设置新的栈顶状态(即实现状态转移)
例:文法G[E]
(2) LR分析过程该文法是SLR文法,故可以构造出SLR分析表(ACTION表和GOTO表)ACTION表GOTO表文法G=ET (2)E=T (3)T 表GOTO 表文法G[E]
Si:移入,i为状态
Ri:规约,i为产生式编号
分析过程:iii步骤状态栈符号输入串动作
10 iii 初始化15EAccepti S
由分析过程可以看到:
(1) 每次规约总是规约当前句型的句柄,是规范规约,可以看到语法树(算符优先是规约最左素短语)
1 (2) 分析的每一步栈内符号串均是规范句型的活前缀、与输入串的剩余部分构成规范句型.
LR方法概述(回顾)LR分析法如何分析句子移进归约(从左到右扫描(L)自底向上进行规约(R) )移进归约的关键问题是什么判断符号栈顶的符号串是否构成句柄.LR分析法如何识别句柄LR分析法在分析过程中并不是直接分析符号栈中的符号是否形成句柄,而是通过识别可归前缀来识别句柄.
具体地,LR分析法的分析过程可以看作识别活前缀和可归前缀的过程,只要符号栈中的符号串构成活前缀、就表示已分析过的部分是正确的,继续移进;直到符号栈中的符号串构成可归前缀、则表示当前栈顶符号串已形成句柄,则进行归约.
如何识别活前缀和可归前缀通过有限自动机来识别.如何构造识别活前缀和可归前缀的有限自动机根据文法规则
状态集合:列出所有活前缀的识别状态
符号表:所有的终结符和非终结符
状态转换函数: f(Ki ,a)= Kj 某一个活前缀的识别状态、在输入符号表中的一个符号之后,转向另一个活前缀的识别状态.
终态集:所有可归前缀的识别状态LR(0)分析构造LR分析器的关键是构造其分析表
构造LR分析表的方法是:
(1)根据文法构造识别规范句型活前缀的有穷自动机DFA(2)由DFA构造LR分析表
1. 构造DFA (1) DFA是一个五元式
S:有穷状态集在此具体情况下,S=LR(0)项目集规范族LR(0).
项目集规范族:其元素是由项目所构成的集合.
V:文法字汇表Vn∪Vt
S0:初始状态
GOTO:状态转移函数GOTO[Si,X=SjSi ,Sj∈S Si ,Sj为项目集合X∈Vn∪Vt表示当前状态Si面临文法符号为X时,应将状态转移到Sj
Z:终态集合1) 确定S集合,即LR(0)项目集规范族,同时确定S02) 确定状态转移函数GOTO
∴构造DFA方法:确定状态集合每一个状态对应文法中某一个产生式规则的某一个项目每一个产生式规则的每一个项目代表一个活前缀的识别状态.产生式规则的项目
活前缀与句柄的关系:若S > αAω>αβωr是αβ的前缀、则称r是G的一个活前缀
1.活前缀已含有句柄的全部符号,表明产生式A→β的右部β已出现在栈顶
2.活前缀只含句柄的一部分符号表明A→β1β2的右部子串β1已出现在栈顶,期待从输入串中看到β2推出的符号
3. 活前缀不含有句柄的任何符号,此时期望A→β的右部所推出的符号串活前缀、与句柄,与LR(0)项目为刻划这种分析过程中的文法G的每一个产生式的右部符号已有多大一部分被识别(出现在栈顶)的情况,分别用标有圆点的产生式来指示位置.
A→β.刻划产生式A→β的右部β已出现在栈顶A→β1.β2 刻划A→β1β2的右部子串β1已出现在栈顶,期待从输入串中看到β2推出的符号A→.β刻划没有句柄的任何符号在栈顶,此时期望A→β的右部所推出的符号串对于A→ε的LR(0)项目只有A→.
项目:文法G的每个产生式(规则)的右部添加一个圆点就构成一个项目.
例:产生式:A→XYZ
项目: A→.XYZ
产生式:A→ε
项目: A→.
项目的直观意义:指明在分析过程中的某一时刻已经规约的部分和等待规约部分.
其中、 ε, X,XY, XYZ为活前缀、XYZ是可归前缀.
例如:产生式S aAcBe对应有6个项目.
项目类型:项目类型有归约项目,移进项目,待约项目和接受项目.
归约项目:后继符号为空的项目称为归约项目.
如:A ・此时已把分析结束, 已在栈顶,从而可按相应的产生式进行归约.
移进项目:后继符号为终结符的项目称为移进项目.如A ・X ,X Vn此时把X移进、即X进符号栈.
待约项目:后继符号为非终结符的项目,称为待约项目.此时期待着从余留的输入符号中进行归约而得到X.
接受项目:当归约项目为SS・时则表明已分析成功,即输入串为该文法的句子,相应状态为接受状态.
构造识别活前缀的NFA P131NFA的确定化将NFA的一些状态组成集合构成DFA的状态状态集合的闭包状态内容是项目集组成的,它分为基本(BASIC)部分和闭包(CLOSURE)部分.
※求BASIC和CLOSURE的方法如下:设Si是Sk关于符号X的后继状态、则有
BASIC(Si)的计算:
CLOSURE(Si)的计算:BASIC(Si) 项目集规范族的构造若A ・Y CLOSURE(Si), 且Y Vn则Y・r CLOSURE(Si),r为符号串重复直到CLOSURE(Si)不再增加为止.
例如:文法G[S:SAAaAbAc
设开始状态为S0,则S0的状态内容为:
A.项目集闭包closure的定义和计算:
令I是文法G的任一项目集合,定义closure(I)为项目集合I的闭包、可用一个过程来定义并计算closure(I).
Procedure closure(I);begin将属于I的项目加入closure(I);repeatfor closure(I)中的每个项目A→α.Bβ(B∈Vn) do将B→.r(r∈V )加入 closure(I)不再增大
例:G[E] 令I{E→.E}
B 状态转移函数GOTO的定义
I:项目集合
X:文法符号,X∈V
J:项目集合J{任何形如A→αX.β的项目| A→α.Xβ∈I}
closure(J):项目集J的闭包仍是项目集合所以的直观意义是:它规定了识别文法规范句型活前缀的DFA从状态I(项目集)出发,经过X弧所应该到达的状态(项目集合)
LR(0)项目集规范族的构造算法:P133步骤Procedure ITEMSETS(G);for LR(0)中的每个项目集I和G的每个符号X doif GOTO(I , X)非空、且不属于LR(0)then 把GOTO(I , X)放入LR(0)中until LR(0)不再增大例.求G[E]的LR(0)G[E]共有20个项目LR(0){I0,I1,I2.I11} 有12个项目组成:T→.TF GOTO(I1,其他符号)为空F→.(E) GOTO(I2,其他符号)为空F→.i GOTO(I3,其他符号)为空GOTO(I4,))=φGOTO(I5,其他符号)=φ求完所有Ii的后继GOTO(I10,所有符号)=φ, GOTO(I11,所有符号)=φ构造DFAstart除I0以外,其余状态都是活前缀的识别状态、从I0到每一状态的每条路径都识别和接受一个规范句型的活前缀.
项目集的相容性:
〖定义〗满足下列两个条件的项目集称为相容的项目集. P134
※无移进项目和归约项目并存.
※无多个归约项目并存.
例如:若有项目集{A ・,B ・}此时栈顶为、根据项目集无法确定是移进还是归约.项目集是不相容的.
对一个文法的LR(0)项目集规范族不存在移进归约或归约归约冲突时,称该文法为LR(0)文法.
LR(0)分析表的构造
LR(0)分析表由两部分组成:动作表表示当前状态下面临输入符号应做的动作是移进、归约,接受或出错;
状态转换表表示在当前状态下面临文法符号时应转向的下一个状态.
(2) LR(0)分析表的构造
构造原则:
设有文法G[S,则LR(0)分析表的构造规则为:对于A ・X 若X Vt,则置action[Si,X=Sj若X Vn,则置goto[Si,X=j对于A ・Si,若A 是文法的第j个产生式,则对所有的x Vt,均置action[Si,x=rj若S ・Si,则置action[Si=acc其他均置出错.假定C{I0, IIn,令每个项目集Ik的下标k 为分析器的一个状态、因此,G` 的LR(0)分析表含有状态n.令那个含有项目S`→.S的Ik的下标k为初态.ACTION和GOTO可按如下方法构造:
若项目A→α.aβ属于Ik且GO (Ik, a)= Ij, a为终结符,则置ACTION[k, a]为把状态j和符号a移进栈,简记为sj;
若项目A→α.属于Ik, 那么,对任何终结符a, 置ACTION[k, a]为用产生式A→α进行规约,简记为rj;其中、假定A→α为文法G`的第j个产生式;
若GO (Ik, A)= Ij, A为非终结符,则置GOTO(k, A)=j;
若项目S`→S.属于Ik, 则置ACTION[k, ]为接受,简记为acc;
分析表中凡不能用规则1至4填入信息的空白格均置上出错标志
例子:文法G为:
该文法的状态描述序列见下表:后继状态后继符号项目集BcdAS EA cAE bBE aAB dA dB cB根据状态描述序列和分析表的构造规则得到的LR(0)分析表如下:状态接受bBbcBbccBd和S11退栈B和S9进栈bccdd和S11进栈bccc和S5进栈cdbcccdb和S3进栈gotoaction输入符
对于输入串bccd的分析过程如下:
三、SLR(1)分析表的构造
1,问题的提出:
只有当一个文法G是LR(0)文法,即G的每一个状态项目集相容(P134)时,才能构造出LR(0)分析表;
由于大多数适用的程序设计语言的文法不能满足LR(0) 文法的条件,因此本节将介绍对于LR(0)规范族中冲突的项目集(状态)用向前查看一个符号的办法进得处理,以解决冲突.
因为只对有冲突的状态才向前查看一个符号,以确定做那种动作,因而称这种分析方法为简单的LR(1)分析法,用SLR(1)表示.
文法G为:SrDDD,iDi
状态描述序列见下表:S SrD iS rDD分析每个状态包含的项目集,不难发现在状态S3中含项目:SrD ・为归约项目DD ・,i 为移进项目也就是按S rD ・项目的动作认为用S rD产生式进行归约的句柄已形成,不管当前的输入符号是什么,都应把rD归约成S.但是按DD・,i 项目当面临输入符为、号时,应将,号移入符号栈,状态转向S5.显然该文法不是LR(0)文法,S3项目集不相容.也可在构造它的LR(0)分析表时发现这个问题,如下表所示.
1 如何解决这种移进-归约冲突LR(0)在归约时不向前看输入符号;在LR(0)基础上,如果出现不相容的项目(存在移进-归约冲突或归约-归约冲突)则LR(k)方法通过向前看k个输入符号来解决冲突(利用上下文信息来消除当前的歧义)SLR只在项目出现冲突时S,(2)才向前看1个输入符号LR(1);
SLR(1)分析表的构造方法思想在出现移进-归约冲突或归约-归约冲突时,通过观察归约成的非终结符的后跟符号集合,来区分移进-归约动作或不同的归约动作.
上例冲突的解决归约还是移进如果归约,那么要构成一个合法的句子,该非终结符后都可以跟哪些终结符而输入符号串中的当前符号是什么是否匹配
匹配:则归约;不匹配:则不归约.
后跟符号集合的定义:设G=(VT,VN,P,S)是上下文无关文法,A∈VN,S是开始符号,Follow(A){a |SuAβ且a∈VT,a ∈First(β),u∈VT,β∈V.针对非终结符若S uAβ,且βε,则∈Follow(A)
(表示输入串的结束符,或句子括号)
可写成为:若S .A,则∈是所有句型中出现在紧接A之后的终结符或.
2,SLR(1)分析表的构造方法思想在构造SLR(1)分析表时,根据不同的向前看符号,将Si中的各项目所对应的动作加以区分,从而即可使冲突动作得到解决.
假定一个LR(0)规范族中含有如下的项目集(状态)Si_Si{ X→・bβ,A→・, B→δ・}也就是在该项目集中含有移进-归约冲突和归约-归约冲突.其中、β, ,δ为文法符号串,b为终结符.方法如下:对于归约项目A ・,B δ・分别求Follow(A)和Follow(B ),
如果满足如下条件:那么,当在状态Si时面临某输入符号为a时,则构造分析表时用以下方法即可解决冲突动作.
(1) 若a=b,则移进.
(2) 若a∈Follow(A),则用产生式A →进行归约._(3) 若a∈Follow(B),则用产生式B →δ进行归约.
(4) 此外,报错.如果对于一个文法的LR(0)项目集规范族所含有的动作冲突都能用以上方法来解决,则称该文法为SLR(1)文法.
3,SLR(1)分析表的构造
_____ 例如文法: (0)S→E
状态描述序列如下:E→・TT→・F由上图可见、S1,S2和S9的项目集均不相容、其有移进项目和归约项目并存,构造LR(0)分析表如下:
1 从上表也可见在S1, S2, S9中存在移进-归约冲突.这个表达式不是LR(0)文法,也就不能构造LR(0)分析表,现在分别考查这三个项目(状态)中的冲突是否能用SLR(1)方法解决.
对于S1{S→E ・, E→E ・T }由于Follow(S),而S→・E是唯一的接受项目,所以当且仅当遇到句子的结束符号时才被接受.又因∩= ,因此S1中的冲突可解决.
对于S2 : S2{ET ・,TT ・F }计算Follow(E) = { , , ) }所以Follow(E)∩=因此面临输入符为、)或号时,则用产生式E→T进行归约.当面临输入符为号时,则移进、其它情况则报错.
对于S9 : S9{EET ・,TT ・F }计算Follow(E) = { , , ) } , 所以Follow(E)∩=因此面临输入符为、)或号时,则用产生式E→ET进行归约.当面临输入符为号时,则移进. 其它情况则报错.由以上考查,该文法在S1,S2,S9三个项目集(状态)中存在的移进-归约冲突都可以用SLR(1)方法解决,因此该文法是SLR(1)文法.我们可构造其相应的SLR(1)分析表.
SLR(1)分析表的构造与LR(0)分析表的构造类似,仅在含有冲突的项目集中分别进行处理.
进一步分析我们可以发现如下事实:例如在状态S3中、只有一个归约项目T→F ・,按照SLR(1)方法,在该项目中没有冲突、所以保持原来LR(0)的处理方法,不论当前面临的输入符号是什么都将用产生式T→F进行归约.
但是很显然T的后跟符没有(符号,如果当前面临输入符是(,也进行归约显然是错误的.因此我们对所有归约项目都采取SLR(1)的思想,即对所有非终结符都求出其Follow集合,这样凡是归约项目仅对面临输入符号包含在该归约项目左部非终结符的Follow集合中、才采取用该产生式归约的动作.
对于这样构造的SLR(1)分析表我们称它为改进的SLR(1)分析表.
改进的SLR(1)分析表的构造方法如下:对于A ・X ,GO[ Si ,X] Sj ,若X Vi ,则置actoin[Si , X=Sj若X Vn ,则置goto[Si , X=j(2) 对于归约项目A ・Si , 若A 为文法的第j个产生式,则对任何输入符号a,若a Follow(A),则置action[Si , a=rj(3) 若S ・Si,则置action[Si , =acc(4) 其它情况均置出错.
改进的SLR(1)分析表如下:
1
四、LR(1)分析表的构造
1,问题的提出在SLR(1)方法中、对于某状态Si,其项目集若不相容时,可根据SLR(1)分析表的构造规则来解决冲突分析动作,但如果不相容的项目集中的向前看集合及其有关集合相交时,就不可能通过SLR(1)分析表构造规则来构造SLR(1)分析表.这时就用LR(1)分析.
SLR
例:文法G:S aAdS bAcS aecS bed
文法G:SSSaAdSaecA eSbAcSbedS aA dS ae cAeS bA cS be d查看I5 ,I7中的冲突、体会LR(1)如何解决S>S>aAd>aedS>S>aec活前缀ae遇到c应移进;遇到d应归约S>S>bAc>becS>S>bed活前缀be遇到d应移进;遇到c应归约并不是Follow(A)的每个元素在含A的所有句型中都会在A的后面出现LR(1)方法在每个项目中增加向前搜索符若项目集[A→B ]属于I时,则[B→]也属于I把FIRST作为用产生式归约的搜索符(称为向前搜索符),作为用产生式B→归约时查看的符号集合(用以代替SLR(1)分析中的FOLLOW集),并把此搜索符号的集合也放在相应项目的后面,这种处理方法即为LR(1)方法
LR(1)项目集族的构造:针对初始项目S→S,求闭包后再用转换函数逐步求出整个文法的LR(1)项目集族.
1)构造LR(1)项目集的闭包函数a)I的项目都在CLOSURE(I)中b)若A→B ,a属于CLOSURE(I), B→是文法的产生式, V,b FIRST( a),则B→,b也属于CLOSURE(I)c)重复b)直到CLOSURE(I)不再扩大2)转换函数的构造GOTO(I,X)= CLOSURE(J)
其中:I为LR(1)的项目集,X为一文法符号J{任何形如A→X ,a的项目| A→X ,a属于I}
一个文法符号串的first集合计算方法:如果文法符号串V, =X1X2.Xn,
1,当X1 ε,则
2,当对任何j(1≤j≤i-1,2 ≤i ≤n),εfirst(Xj)
则{ε}) ∪(first(X2){ε}) ∪.∪(first(Xi-1){ε}) ∪first(Xi)
3,当first(Xj)都含有ε时(1 ≤j ≤n),则 ∪first(X2) ∪.∪first(Xj) ∪{ε} SS,S aAd,S bAc,S aec,S 分析表的构造LR(1)分析表的构造与LR(0)分析表的构造在形式上基本相同、不同之处在于:归约项目的归约动作取决于该归约项目的向前搜索符号集.
1) 若项目[A→a ,b]属于Ik,且转换函数GO(Ik,a)= Ij ,当a为终结符时,则置ACTION[k,a]为Sj2) 若项目[A→,a]属于Ik ,则对a为任何终结符或,置ACTION[k,a] = rj ,j为产生式在文法G中的编号3) 若GO(Ik,A)= Ij ,则置GOTO[k,A=j,其中A为非终结符,j为某一状态号4) 若项目[S→S ]属于Ik ,则置ACTION[k] = acc5) 其它填上报错标志
例:P146 表7.10LALR(1)分析 abBaB, abLR(1)项目集和转换函数分析可发现I3和I6 , I4和I7 , I8和I9分别为同心集SaB, ab合并为如果两个LR(1)项目集去掉搜索符之后是相同的,则称这两个项目集具有相同的心.对LR(1)项目集规范族合并同心集,若合并同心集后不产生新的冲突、则为LALR(1)项目集.
合并同心集的几点说明同心集合并后心仍相同、只是超前搜索符集合为各同心集超前搜索符的和集合并同心集后转换函数自动合并LR(1)文法合并同心集后也只可能出现归约-归约冲突、而没有移进-归约冲突合并同心集后可能会推迟发现错误的时间,但错误出现的位置仍是准确的合并同心集后判断该文法是否是文法.
构造LR(0)项目集规范族If 所有的项目集都是相容的,则为LR(0)文法;Else if 冲突项目可以通过考察非终结符的后跟符号集来解决,则为SLR(1)文法;
Else 构造LR(1)项目集规范族If 任何项目集中都不存在动作冲突、则为LR(1)文法;对LR(1)项目集规范族进行同心集的合并,如合并之后仍不存在冲突、则为LALR(1)文法.
几种文法的比较
SLR(1): 生成的LR(0)项目集如有冲突、则根据非终结符的FOLLOW集决定
LR(1),LR(k): 项由核心与向前搜索符组成,搜索符长度为1或k
LALR(1): 对LR(1)项目集规范族合并同心集
由弱到强中的向前搜索符号集合是与该项目相关的非终结符号的Follow集的子集;
LALR项目的搜索符一般是与该项目相关的非终结符号的Follow集的子集,这正是LALR分析法比SLR分析法强的原因.
作业P

ppt文档的标签：编译原理

更多推荐标签：空姐英文简历绩效考核样本汽车销售代理学生注册政治侦察文化产业园空域分类零售商品浙江初中科学制造工程师实验工作人员网络统计工龄审定表立功竞赛台帐管理学斯蒂芬电梯招标网污水处理工电蚊香说明书中国主要铁路会议联络函生产技术员王保长后传兵役法学论文兼爱包容高考生物策略仿真软件商场销售表格新疆维吾尔财务状况建议页实训芙