编译原理第七章ppt课件.ppt

《编译原理第七章ppt课件.ppt》由会员分享，可在线阅读，更多相关《编译原理第七章ppt课件.ppt（82页珍藏版）》请在三一办公上搜索。

1、第七章 LR分析法,第七章 LR分析法,3,复习： 自底向上分析,思想从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误核心寻找句型中的当前归约对象“句柄”进行归约,用不同的方法寻找句柄，就可获得不同的分析方法,4,优先法-ch6算符优先分析,根据归约的先后次序为句型中相邻的文法符号规定优先关系句柄内相邻符号同时归约，是同优先级的句柄两个端点符号的优先级要高于句柄外与之相邻的符号的优先级，句柄内相邻符号具有相同的优先级a1ai-1aj+1an,5,状态法-ch7 LR分析法,根据句柄的形成过程建立状态用状态来描述不同时刻句柄是否形成因为句柄

2、是产生式的右部，可用产生式来表示句柄的不同识别状态例如： SbBB可分解为如下识别状态S.bBB 移进bSb.BB 等待归约出BSbB.B 等待归约出BSbBB. 归约,LR分析法是1965年由Knuth提出的一种自底向上分析方法，它的适用范围很广，很受计算机理论界的重视。,自底向上分析法的关键问题是在分析过程中如何确定句柄。LR分析法能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的k个（k0）符号可唯一确定分析器的动作是移进还是归约和用哪个产生式归约，能唯一地确定句柄。,LR（K）表示“从左至右，每步向前（右）查看K个输入符号”。K=0表示不需要向右查看输入符号,LR分析法

3、严格执行最左归约，是一种规范归约，这一点与算符优先分析法不同。,LR分析法的优点： 对文法限制少，适用范围广。 分析速度快 能准确及时地报错,缺点： 构造分析器的工作量较大 K值愈大，实现愈困难,本章主要介绍LR分析的基本思想，及当K1时，LR分析器的基本构造原理和方法。着重介绍LR（0）、SLR（1）、LALR（1）、LR（1）四种分析器的构造方法。,7.1 LR分析概述,一 LR分析器的组成,一个LR分析器由3个部分组成：,(1)总控程序：也称驱动程序，所有LR分析器的总控程序都是相同的。,(2)分析表或分析函数:不同的文法分析表不同；同一个文法采用的LR分析器不同时，分析表也不同。 分析

4、表可分为动作表（ACTION）和状态转换 表 （GOTO）两部分，它们都可用二维数组表示。,(3) 分析栈：包括文法符号栈和状态栈,二 LR分析器工作过程,LR 分析器的动作由栈顶状态和当前输入符号决定。,SP：栈指针 Si：状态栈 Xi：文法符号栈 ACTION表和GOTO表分别为动作表和状态转换表。,GOTOSi，X=Sj表示栈顶状态为Si遇到当前文法符号为X时应转向状态Sj。,ACTIONSi，a规定了栈顶状态为Si时遇到输入符号a应执行的动作。动作有4种：,(1) 移进：把a移入文法符号栈，把Sj=GOTOSi，a移入到状态栈。其中i，j表示状态号。,(2) 归约：当栈顶形成句柄为时，

5、把归约为相应的非终结符A（A为文法中的产生式）。设的长度为r（即 | =r），则从状态栈和文法符号栈中自顶向下去掉r个符号（即栈指针SP-r），把A移入文法符号栈，Sj=GOTOSi，A移进状态栈，Si为修改指针后的栈顶状态。,(3)接受acc：文法符号栈中只有开始符S，输入串只 有#，则为分析成功。,(4) 报错：当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入串不是该文法能接受的句子。,LR分析器的关键部分是分析表的构造，下面将针对每种不同的LR分析器详细介绍其构造思想及方法。,7.2 LR（0）分析,LR（0）分析表构造的思想和方法是构造其它LR分析表的基础。 先引进

6、一些概念和术语：,拓广文法：对原文法GS增加一产生式SS，S只在左部出现。 对文法进行拓广的目的：为了对某些右部含有开始符的文法，在归约过程中能分清是否已归约到文法的最初开始符，还是在文法右部出现的开始符。拓广文法的开始符S只在左部出现，这样确保不会混淆。,活前缀：把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为活前缀。,例如：GS：（1） S aAcBe （2） A b （3） A Ab （4） B d,aAbcde是规范句型。因为:S=aAcBe =aAcde =aAbcde,从左至右，规范句型aAbcde的活前缀有、a、aA、aAb ，而aAbc不是活前缀，因为它包含句柄后面

7、的符号c。,由以上分析我们很容易理解，在LR分析过程中，实际上是把的前缀列出放在符号栈中，一旦在栈中出现（可归前缀），即句柄已经形成，则用产生式A进行归约。（参考P125-表7.2）,7.2.2 识别活前缀的有限自动机（略） 7.2.3 活前缀及其可归前缀的一般计算方法（略）7.2.4 LR（0）项目集规范族的构造,（1） LR（0）项目,在文法G中每个产生式的右部适当位置添加一个圆点构成项目。,例如：SaAc对应有4个项目: （右部长度3加1） 0 SaAc 1 Sa Ac 2 SaA c 3 SaAc ,一个产生式可对应的项目数为它的右部符号串长度加1,注意：A仅有项目A ,每个项目的含义

8、与圆点的位置有关，概括地说，圆点的左部表示分析过程的某时刻用该产生式归约时句柄已识别的部分，圆点的右部表示待识别部分。,项目 S aAc ： 希望用S的右部归约，当前输入串中符号应为a项目Sa Ac ： 已与第一个符号a匹配，需分析A的右部项目SaAc ： A的右部已分析完归约成A，希望输入串中符号为c项目SaAc ： S的右部分析完毕，句柄已形成，可以进行归约。,根据圆点所在位置和圆点后是终结符还是非终结符，把项目分为以下几种：,移进项目：圆点后为终结符的项目，对应状态为移进状态。 形如Aa，aVT,待约项目：圆点后为非终结符的项目，如AB，BVN。表示所对应的状态等待着分析完非终结符B所能

9、推出的串归约成B，才能继续分析A的右部。,归约项目：圆点在最右部的项目，如A，表明一个产生式的右部已分析完，句柄已形成，可以归约。,接受项目：形如S，S为拓广文法，S为左部的产生式只有一个，它是特殊的归约项目，对应状态为接受状态。,（3） LR（0）项目集规范族的构造,对于构成识别一个文法活前缀的DFA项目集的全体称为这个文法的LR（0）项目集规范族。按（2）中方法，列出拓广文法的所有项目，构造NFA再确定化，这样做确定化的工作量较大，可以用闭包函数求DFA项目集。,（2） 构造识别活前缀的NFA （了解）,定义和构造项目集 I 的闭包函数 CLOSURE（I）,a） I 的项目均在CLOSU

10、RE（I）中b）若AB属于CLOSURE（I），则每一形如B 的项目也属于CLOSURE（I）重复b）直到CLOSURE（I）不再扩大为止,定义转换函数GO（I，X）如下 ：,GO（I，X）= CLOSURE（J）其中：I为包含某一项目的状态，XVN VT J = 任何形如AX的项目 | A X属于I ,圆点不在产生式右部最左边的项目称为核（拓广文法S S除外）GO（I，X）转换函数得到的J为转向后状态所含项目集的核。,使用CLOSURE和GO（I，X）构造文法G的LR（0）项目集规范族：,a）置项目S S为初态集的核，求CLOSURE（ S S ）得到初态的项目集,b）对初态集或其它的项目集

11、应用转换函数 GO（I，X）=CLOSURE（J）求出新状态J的项目集。,重复b） 直到不出现新的项目集为止。,例如：GS： SS SaAc AAbb A b,LR（0）项目集规范族的项目分为四种：移进项目、归约项目、待约项目和接受项目。,一个项目集中可能包含以上四种不同的项目，但是一个项目集中不能有下列情况存在：,LR（0）文法：一个文法的LR（0）项目集规范族不存在移进归约或归约归约冲突时，这个文法为LR（0）文法。,(4) LR（0）分析表的构造,是LR（0）分析器的重要组成部分，是总控程序分析动作的依据。,LR（0）分析表可用一个二维数组表示，行标为状态号，列标为文法符号和 #。分析表

12、由两部分组成：,动作表ACTION：表示当前状态下面临输入符应做的动作。,转换表GOTO：表示当前状态下面临文法符号应转向的下一个状态。,构造一个文法的LR（0）分析表，首先构造其识别活前缀的自动机DFA，利用DFA的项目集和状态转换函数构造它的LR（0）分析表。,LR（0）分析表的构造算法如下：,假设已构造出LR（0）项目集规范族如下：C=I0，I1，In，其中Ik为项目集的名字，k为状态名，令包含S S项目的集合Ik的下标为分析器的初始状态，那么分析表的ACTION表和GOTO 表构造步骤为：,若项目Aa属于Ik且转换函数GO（Ik，a）=Ij，当aVT时，则置ACTIONk，a为Sj，其

13、动作含义为将a移进符号栈，j进入状态栈。,若项目A属于Ik，则对任意aVT和#，置ACTIONk，a和ACTIONk，# 为rj。j为A产生式序号。rj动作的含义是把当前文法符号栈顶的符号串归约为A，栈顶指针向下移动|的长度，非终结符A变为当前面临的符号。,若GO（Ik，A）=Ij，则置GOTOk，A为j，其中AVN，表示当前状态为k时，遇文法符号A时应转向j，因此A移入文法符号栈，j移入状态栈。,若项目SS 属于Ik，则置ACTIONk，#为acc，表示接受,凡不能用上述方法填入的分析表的元素，均应填上“报错标志”。为清晰起见，表中用空白表示出错。,例： SvI:T 1 拓广文法 SS 0

14、II,i 2 Ii 3 Tr 4 构造LR（0）分析表,先构造识别活前缀的DFA （即LR（0）项目集规范族）,然后构造LR（0）分析表，如下所示：,练习：构造下列文法的LR（0）分析表 SaAc AbB | ba BdB | e,(5) LR（0）分析器的工作过程,若ACTIONS，a=Sj，aVT，则 a 移入符号栈，j 移入状态栈。,若ACTIONS，a=rj，aVT或#，则用第 j个产生式归约，并将两个栈的指针减去 k，其中k 为第 j个产生式右部的符号串的长度，这时当前面临符号为第 j个产生式左部的非终结符。,若ACTIONS，a=acc，a=#，则为接受，表示分析成功。,若GOTO

15、S，A=j，AVN，表明前一动作是用关于A的产生式归约，当前面临非终结符A应移入符号栈，j移入状态栈。,若ACTIONS，a=空白，则转向出错处理,对于前例文法，句子vi，i：r的LR（0）分析过程。,步骤 状态栈 符号栈 输入串 ACTION GOTO,1 0 # vi，i：r# S2,2 02 #v i，i：r# S4,3 024 #vi ，i：r# r3 3,4 023 #vI ，i：r# S6,5 0236 #vI， i：r# S7,6 02367 #vI，i ：r# r2 3,7 023 #vI ：r# S5,8 0235 #vI： r# S9,9 02359 #vI：r # r4

16、8,10 02358 #vI：T # r1 1,11 01 #S # acc,步骤 状态栈 符号栈 输入串 ACTION GOTO,练习：SaAc AbB | ba BdB | e句子 abdec# 的LR（0）分析过程。,73 SLR（1）分析,大多数实用的程序设计语言的文法不能满足LR（0）文法的条件，本节将介绍对于LR（0）规范族中有冲突的项目集用向前查看一个符号的办法进行处理，以解决冲突。,简单的LR（1）分析法，用SLR（1）表示：对冲突的状态向前查看一个符号，确定动作（是移进还是归约，按哪一个产生式归约）,假定文法G的一个项目集 I 含有,m个移进项目：A11a11A22 a22

17、Amm amm,和n个归约项目： B11 Bnn ,如果集合a1，a2，am和集合FOLLOW（B1） FOLLOW（Bn）两两不相交，则项目集I中的冲突可按以下原则解决，设a是下一输入符号,1） 若aa1，a2，am，则移进a,2）若aFOLLOW（Bi），i=1，2n；则用Bii 归约。,此外，报错。,SLR（1）文法：如果一个文法的LR（0）项目表中所含冲突都能用上述方法解决，则这个文法是SLR（1）文法，所构造的分析表为SLR（1）分析表，使用SLR（1）分析表的分析器称为SLR（1）分析器,SLR（1）分析表的构造方法（改进）：,基本和LR（0）分析表的构造算法相同，只需将b）改为：

18、 若A属于IK，则任何aFOLLOW（A）或“#”，置ACTION k，a=rj，j为产生式A在文法G中的文法编号。,例如：拓广文法 G SS 0 S rD 1 D D，i 2 D i 3,其识别活前缀的DFA 为：,在I3 中存在移进归约冲突：移进项目D D , i， 归约项目SrD ,求各非终结符的FOLLOW集 FOLLOW（S）=# FOLLOW（S）=# FOLLOW（D）=，#,因为FOLLOW（S）=#，= 所以 可以用SLR（1）方法解决。,构造改进的SLR（1）分析表,句子ri，i的SLR（1）分析过程,步骤 状态栈 符号栈 输入串 ACTION GOTO,1 0 # ri，

19、i# S2,2 02 #r i，i# S4,3 024 #ri ，i# r3 3,4 023 #rD ，i# S5,5 0235 #rD， i# S6,6 02356 #rD，i # r2 3,7 023 #rD # r1 1,8 01 #S # acc,7.4 LR（1）分析,SLR（1）方法虽然相对LR（0）有所改进，但仍然存在着多余归约，说明SLR（1）方法向前查看一个符号的方法不够确切，LR（1）方法恰好是要解决SLR（1）方法在某些情况下存在的无效归约问题。,7.4 .1 LR（1）项目集族的构造,S S，# 属于初始项目集，#为向前搜索符。针对初始项目S S，#，求闭包后再用转换函

20、数逐步求出整个文法的LR（1）项目集族，具体构造步骤如下：,（1） 构造LR（1）项目集的闭包函数,a）I的任何项目都属于CLOSURE（I）,b）若有项目AB，a CLOSURE（I），B是产生式，V*， bFIRST（a），则B，b也属于CLOSURE（I）,重复b），直到CLOSURE（I）不再增大为止。,（2）转换函数的构造,LR（1）转换函数的构造与LR（0）的相似， GO（I，X）=CLOSURE（J）其中 I是LR（1）的项目集，X是文法符号。 J = 任何形如 AX ，a 的项目 | AX，a I ,例如： SS 0 SaAd 1 SbAc 2 Saec 3 Sbed 4 Ae

21、 5,构造它的LR（1）项目集规范族：,I0：SS，# I1：SS，# I3：SbAc，# SaAd，# I2：SaAd，# Sbed，# SbAc，# Saec，# Ae，c Saec，# Ae，d I4：SaAd，# Sbed，#I5：Saec，# I6：SbAc，# I7：Sbed，# Ae，d Ae，cI8：SaAd，# I9：Saec，# I10：SbAc，#I11：Sbed，#,在项目集I5和I7中存在移进归约冲突，I5：Saec，# Ae，d，面临输入符为c时移进，d时归约。I7：Sbed，# Ae，c，面临输入符d时移进，c时则归约。,7.4 .2 LR（1）分析表的构造,一个

22、LR（1）项目由两部分组成：和LR（0）项目相同部分（称为心），向前搜索符号集合。,LR（1）分析表的构造与LR（0）分析表的构造大部分相同，仅对归约项目的归约动作取决于该归约项目的向前搜索符集，只有当面临输入符属于向前搜索符的集合，才做归约动作，其它情况均出错。具体构造过程如下：,若已构造出某文法的LR（1）项目集族C，CI0，I1，In，其中Ik的k为分析器的状态，则动作表ACTION和状态转换表GOTO构造方法如下：,若项目Aa，b Ik，且GO（Ik，a）=Ij，其中aVT，则置ACTIONk，a=Sj,若项目A，a Ik，则置ACTIONk，a =rj，其中aVT，j为A编号。,若项

23、目SS ，#Ik，则置 ACTIONk，#=“acc”。,若GO（Ik，A）=Ij，其中AVN，置 GOTOk，A=j。,凡不能用上述规则填入的元素，均置“报错标志”，本书用“空白”表示。,上例的LR（1）分析表：,如果一个文法的LR（1）项目集中无移进归约冲突或归约归约冲突，则称这个文法为LR（1）文法，所构造的分析表为LR（1）分析表。能使用LR（1）分析表的分析器称为LR（1）分析器或规范的LR分析器。,LR（1）分析法的缺点：在多数情况下，同一个文法的LR（1）项目集的个数比LR（0）项目集的个数多，甚至可能多好几倍，导致存储量的急剧增加，使应用受到一定限制。,一个文法是LR（0）文法一定也是SLR（1）文法，也是LR（1）文法，反之则不一定成立。,7.5 LALR（1）分析,为了克服LR（1）缺点，可以对LR（1）项目集规范族合并同心集，若合并同心集后不产生冲突，则为LALR（1）项目集，它的状态个数与LR（0）、SLR（1）相同。,以下内容略讲,7.6 二义性文法在LR分析中的应用,一个二义性文法不是LR类文法，也不是算符优先文法或LL（K）文法，任何一个二义性文法，不存在与其相应的语法分析器，但是对某些二义性文法，可以人为地给出优先性和结合性的规定，可以构造出比相应非二义性文法更优越的LR分析器。（分析速度更快）,作业 8、 11,注意：文件包含关系 （补充）,