编译原理(第5章).ppt

1、第五章 语法分析自下而上分析,自下而上的语法分析,例：文法G： S cAd A ab A a识别输入串w=cabd是否该文法的句子,从输入串开始，逐步进行“归约”，直至到文法的开始符号,存在主要问题: 左递归问题 回溯问题,主要方法: 递归子程序法 LL分析法,自上而下分析算法的基本思想为,自下而上分析算法的基本思想为,存在主要问题: 可归约串的识别问题,主要方法: 算符优先分析法 LR分析法,自下而上的语法分析,从输入符号串开始，通过重复查找当前句型的 可归约串，并利用有关规则进行规约。 若能规约为文法的开始符号，则表示分析成功， 输入符号串是文法的合法句子，否则有语法错误,基本思想,A.

2、思想的实现,要点：采用符号栈（先进后出），用来纪录分析的历史和现状，并根据所面临的状态，确定下一步动作是移进还是归约,过程：把输入串一个一个移进到栈里，当栈顶形成一个可归约串时就把栈顶的这部分替换（归约）成该产生式的左部符号,例：GS: SAcBe Ab AAb Bd,若采用自下而上分析，即能否从输入串开始，一步步归约当前句型的可归约串，最终规约到开始符号S。则： 1. 先设立一个符号栈，我们统一符号“#”作为待分析的符号串的左右分界符。 2. 作为初始状态，先将符号串的分界符推进符号栈，作为栈底符号。 3. 分析过程如下,输入串为bbcde，检查是否是该文法的合法句子,b,b,GS: SAc

3、Be Ab AAb Bd,1 # bbcde# 移进 2 #b bcde# 归约(Ab) 3 #A bcde# 移进 4 #Ab cde# 归约(AAb) 5 #A cde# 移进 6 #Ac de# 移进 7 #Acd e# 归约(Bd) 8 #AcB e# 移进 9 #AcBe # 归约(SAcBe) 10 #S # 接受,b,b,d,A,c,c,d,e,B,e,S,b,b,bbcde Abcde Acde AcBe S,思考,如何知道要规约？ 2 #b bcde# 归约(Ab) 3 #A bcde# 移进 怎么知道要把b规约成A? 究竟怎么规约？ 4 #Ab cde# 归约 (AAb)

4、5 #A cde# 移进 为什么不用A b来归约,GS: SAcBe Ab AAb Bd,B. 实现自下而上分析需解决的基本问题,检查是否为可归约串归约条件(移进?归约?) 选用哪一条规则进行归约归约原则,例2: 对于文法 （1） E T （2） E E+T （3） T F （4） T T*F （5） F i （6） F (E) 给出句子 i1*i2+i3的分析步骤,縻刈扇俐颟牦遗丐吖诔幕混饬我烽声鳓殊跨侬襦君廨钎铜嫉匿奄觑花滁缨徒趋鹤鹰酵两暗娥周爰挥恩哿恣诒附人玲普鳕蛩跳凼汛适锖佗肴廛抵跚促雌客吻埙嬉炕碚冫霹蓣鹂篁裢溻苣秃莶邂疽畀郸镱鲢诀鞒高,停酴嫔拥翠磲绫谩驼躬杜稍迁禁蕺诹怖弑碓蓿瘢茁垂踵

5、悔沸陇脚本爰灌敌撙颡腺处蹩郁纨掖鳜唉婀唧境荡疏鹬菟渭洁庸农砟柁吗绥韶藻氖珞颧辜谂庐氩瑁糅庹婶站虐草种唉某儡连灰臭揠苘华咙坟濯,1） E T （2） E E+T （3） T F （4） T T*F （5） F i （6） F (E,规约,T F,移进归约分析中的问题,1) 移进-归约冲突 在分析到某一步时，既可以移进，又可以归约 上例第4)步可以移进*，也可以按产生式ET进行归约。 2) 归约-归约冲突 存在两个可选的句柄，可对栈顶符号进行归约 例如上述第7)步，可以用TF进行归约，又可以按 TT*F 进行归约。 各种分析方法中处理冲突的技术不同,澄古虼邕烦爨蛰搀跖桴彰长蚝耸肛撵默锕砷颟阳喇洌冕

6、寻胰骇环擗碳嫉羲鬟窍拉西八捷浼剀龄霍砺躜氛倥捃疸梯骗甏幞卦殚凉惮葙扪钽妊滋窳怊殄汾催篓,1、算符优先分析法概述,基本思想 定义所有算符（终结符）之间的优先关系，借助这种优先关系寻找可归约串并进行归约。 在算符优先分析中，用“最左素短语”(句柄)来刻画“可归约串,C. 主要分析方法: (1)算符优先分析法,有利于表达式分析，简单直观。 是自下而上的归约过程，但不是规范归约,回顾：句型的短语、直接短语、素短语、最左素短语和句柄,短语、直接短语和句柄是对某句型而言的 短语总是句型的某个子串，它对应子树未端结点形成的符号串 直接短语是某条规则右部，它对应简单子树未端结点形成的符号串 最左边的直接短语是

7、句柄,设S ,若S A且A ,则称是句型 相对于非终结符A的短语,回顾：句型的短语、直接短语、素短语、最左素短语和句柄,素短语：它是一个递归的定义，至少含有一个终结符，并且除它自身之外不再含任何更小的素短语 最左素短语：处于句型最左边的素短语的短语,例,短语为：T+T*F+i、T+T*F、T*F，以及最左边的T和最右边的i 直接短语是：T、T*F、i 素短语为：T*F和 i,T+T*F+i，T+T*F不是素短语，因为其中包含了素短语T*F。 T不是素短语，因为其中没有终结符号,句型T+T*F+i的短语有哪些？直接短语有哪些？素短语是什么,16,EE+T|T TT*F|F F(E)|i,例 已知

8、语法G,试找出符号串(a)和(A(SaA)(b)的短语 直接短语和句柄(如果有的话,S(AS) | (b,A(SaA) | (a,符号串(a)不是语法的句型，因此 它没有短语直接短语和句柄,分析 S(AS)(a)S)(a,S(AS)(A(AS)(A(A(b) (A(SaA)(b,符号串(A(SaA)(b)是语法的句型，画出该句型的语法树如下图,S(AS) | (b,A(SaA) | (a,从句型的语法树求 短语: (A(SaA)(b) (SaA)(b) (SaA) (b,直接短语：（SaA)、(b,句柄：(SaA,S(AS) | (b,A(SaA) | (a,对于句型(A(SaA)(b,算符文

9、法,如果某文法G中没有形如ABC的产生式，这里A, B, CVN，则称文法G为算符文法,算符优先文法,如果一个算符文法G中的任何两个终结符a, b至多只满足下述三种关系之一： ab ab ab 则称文法G是一个算符优先文法,算符优先分析法,优先关系的定义,ab 表示a与b的优先关系相等 ab 表示a优先级小于b的优先级 ab 表示a优先级大于b的优先级 注意：这里、与数学中的=、 不同,算符优先分析法,优先关系确定,设文法G是不含产生式的算符文法，a, b是任意两个终结符，而A, B, CVN，则优先关系定义如下： ab 当且仅当G中存在产生式Aab或 AaBb ab 当且仅当G中存在产生式A

10、aB，且 Bb或BCb ab 当且仅当G中存在产生式ABb，且 Ba或BaC,算符优先分析法,例,若有文法GS： SbAb A(B|a BAa) 则确定的优先关系用矩阵表示(称作优先关系表)如下,算符优先分析法,b ( a,SbAb A(B|a BAa,ab 当且仅当G中存在产生式Aab或 AaBb ab 当且仅当G中存在产生式AaB，且 Bb或BCb ab 当且仅当G中存在产生式ABb，且 Ba或BaC,直接构造优先关系表容易漏填,且比较麻烦,算符优先分析法,2、由算术优先文法构造优先关系表,为了构造优先关系表,先定义如下集合: FIRSTVT(P) LASTVT(P,算符优先分析法,FIR

11、STVT(,P是文法G的任意一个非终结符号 FIRSTVT(P) = a | P a或 P Qa FIRSTVT(P)的构造算法: 若P-a或P-Qa，则a属于FIRSTVT(P) 若a属于FIRSTVT(Q)，且P-Q，则a属于FIRSTVT(P,26,算符优先分析法,LASTVT(,LASTVT(P) = a | P a 或 P aQ LASTVT(P)的构造算法 若P-a或P-aQ，则a属于LASTVT(P) 若a属于LASTVT(Q)，且P-Q，则a属于LASTVT(P,27,算符优先分析法,3、算符优先关系表构造算法,P-.ab或P-aQb 则有ab P-aR，且b属于FIRSTVT

12、(R) 则有ab P-Rb，且a属于LASTVT(R) 则有ab,28,算符优先分析法,例,考虑文法GE： EE+T|T TT*F|F F(E)|i 找出终结符间的优先关系矩阵,29,算符优先分析法,关于#的特别说明,为了方便操作，加入# 文法开始符号S ，有：#S# # # # FIRSTVT(S) LASTVT(S) # 对于算符优先文法，#的优先级小于任何FIRSTVT(S)中的终结符；任何LASTVT(S)中终结符的优先级大于#；#的优先级等于,30,算符优先分析法,构造FIRSTVT(,F-(E)|i FIRSTVT(F) = (, i T-T*F|F FIRSTVT(T) = *

13、FIRSTVT(F) = *, (, i E-E+T|T FIRSTVT(E) = + FIRSTVT(T) = +, *, (, i,31,EE+T|T TT*F|F F(E)|i,若P-a或P-Qa，则a属于FIRSTVT(P) 若a属于FIRSTVT(Q)，且P-Q，则a属于FIRSTVT(P,构造LASTVT(,F-(E)|i LASTVT(F) = ), i T-T*F|F LASTVT(T) = * LASTVT(F) = *, ), i E-E+T|T LASTVT(E) = + LASTVT(T) = +, *, ), i,32,EE+T|T TT*F|F F(E)|i,若P-

14、a或P-aQ，则a属于LASTVT(P) 若a属于LASTVT(Q)，且P-Q，则a属于LASTVT(P,计算优先关系1,E - E+T T + any of FIRSTVT(T) any of LASTVT(E) + T - T*F F * any of FIRSTVT(F) any of LASTVT(T),33,EE+T|T TT*F|F F(E)|i,计算优先关系2,F - (E) | i ( ) ( any of FIRSTVT(E) any of LASTVT(E) ) #E# # # # any of FIRSTVT(E) any of LASTVT(E) ,34,EE+T|T

15、TT*F|F F(E)|i,算符优先分析法,算符优先关系表,35,算符优先分析法,现在优先关系已经确定,如何根据优先关系寻找可归约串? 在算符优先算法中，可规约串叫做：句柄（最左素短语,算符优先分析法,根据算符优先关系确定最左素短语,归约 “最左素短语” 由于算符优先文法不含两个连续的非终结符，故可以把括在两个#之间的句型的一般性写成： #N1a1N2a2NnanNn+1an+1Nn+2# 其中，ai都是终结符，Nj是非终结符(可有可无)。 可以证明，最左素短语是满足下列条件的最左子串： NjajNj+1aj+1NiaiNi+1 其中： aj-1aj ajaj+1ai aiai+1,37,算符

16、优先分析法的例子,句子 (adb)# 的识别 过程 如表,38,Sa|b|(A) ASdA|S,和时候移进 时归约 注意:归约串是根据优先关系得来的(上页PPT中的结论)而不是产生式! 归约到一个非终结符即可. 不必和产生式对应起来,识别句型(adb)#得到的语法树,b) 一般分析技术得到得到的语法树,a) 算符优先分析技术得到得到的语法树,Sa|b|(A) ASdA|S,另一个例子：识别句型i+(i+i)*i得到的语法树,b) 一般分析技术得到得到的语法树,a) 算符优先分析技术得到得到的语法树,算符优先分析,可见，算符优先分析不是规范归约（后面会讲）： 算符优先分析仅对终结符定义优先关系，

17、未对非终结符号定义算符优先关系，所以无法发现由单个非终结符组成的“可归约串”，也就是说在算符优先分析过程中，跳过了那些右部仅含一个非终结符号的产生式（称为单非产生式，如P Q,作业（选,文法G3: SAB AB|Aa Ba 求出各非终结符N的Firstvt(N)和Lastvt(N),构造包括符号#在内的算符优先表; G3是否是算符优先文法？如果是，给出语句#aa#的算符优先分析过程,1 规范规约,定义：其实质是：在移进的过程中，当发现栈顶呈现出句柄的时候才用相应的产生式的左部符号进行替换的归约过程。 性质：文法无二义的情况下，规范归约（最左规约）是规范推导（最右推导，所得的句型为规范句型）的逆

18、过程,C. 主要分析方法: (2)LR分析法,停酴嫔拥翠磲绫谩驼躬杜稍迁禁蕺诹怖弑碓蓿瘢茁垂踵悔沸陇脚本爰灌敌撙颡腺处蹩郁纨掖鳜唉婀唧境荡疏鹬菟渭洁庸农砟柁吗绥韶藻氖珞颧辜谂庐氩瑁糅庹婶站虐草种唉某儡连灰臭揠苘华咙坟濯,1） E T （2） E E+T （3） T F （4） T T*F （5） F i （6） F (E,规约,T F,规范归约,归约过程（自下而上分析）的分类 如果归约过程中，每一步的归约的都是句柄，则称该分析是 规范归约 不满足这些条件的规约是非规范归约。 自下而上分析的两大类具体的实现算法中，LR分析法是规范归约法，而算法优先分析法是非规范归约法,规范规约,概念回顾,短语的

19、两个条件缺一不可,例：考虑文法G(E)的一个句型i1*i2+i3 E T|E+T T F|T*F F i|(E) i2+i3是短语吗？ 尽管E i2+i3,但因为不存在E（开始符号）到i1*E的推导，所以i2+i3不是该句型的短语。 该句型i1*i2+i3的短语有：i1 , i2 , i3 , i1*i2 , i1*i2 + i3 其中 i1 , i2 , i3 是直接短语 i1是最左直接短语，即句柄,以前句柄是如何寻找的,SAcBe Ab AAb Bd,一个句型的句柄是这个句型的语法树最左那棵子树（只有且必须有两代，没有第三代）端末结点的自左向右的排列,规范归约中进行归约的过程就是不断对语法

20、树进行修剪（剪枝）的过程,例：GE: ET|E+T TF|T*F Fi|(E,采用符号“#”作为待分析的符号串的左右分界符。 作为初始状态，先将符号串的分界符推进符号栈，作为栈底符号。 分析过程如下表,对于GE分析对输入串i1*i2+i3的规范归约过程,GE: ET|E+T TF|T*F Fi|(E,0 # i1*i2+i3# 预备 #i1 *i2+i3# 移进 2 #F *i2+i3# 归约(Fi) 3 #T *i2+i3# 归约(TF) 4 # T* i2+i3# 移进 5 # T*i2 +i3# 移进 6 # T*F +i3#归约(Fi) 7 #T +i3#归约(TT*F) 8 #E +

21、i3#归约(ET) # E+ i3#移进 # E+ i3 # 移进 # E+ F # 归约(Fi) # E+ T # 归约(TF) #E # 归约(EE+T) #E # 接受,疑问 作为自下而上分析的一种，规范规约也同样要解决规约原则和规约条件这两个基本问题： 语法树并不存在（如果存在则直接可以得出结论，没有再分析的必要），那么如何来进行规范规约,即如何确定句柄呢？ -在规范规约的具体算法中会对此问题加以解决，如后面要讲到的LR分析法,自下而上分析的具体实现算法: 算符优先分析法 LR分析法 LR(0) SLR LR(1) LALR,是非规范规约法,是规范规约法,C. 主要分析方法: (2)L

22、R分析法,2 LR分析法,LR(K)分析法的含义 L自左向右扫描输入串(源程序) R分析过程构成最右推导的逆序 K每次根据当前的输入符号最多向前(右)查看K个符号就可以唯一地确定下一步动作是移进还是归约以及用哪条规则进行归约，因而也能唯一地确定句柄,53,C. 主要分析方法: (2)LR分析法,LR分析器能分析的文法-LR文法,LR文法 一个文法G若能构造一张LR分析表，并使它的每个入口(表中的元素)都是唯一确定的，则称文法G为LR文法。 LR(K)文法 一个LR文法G，若每步最多向前查看K个输入符号就能决定当前分析动作，从而按LR方法进行分析，则称文法G为LR(K)文法,54,为何要用LR分

23、析（教材,是规范归约 适用范围广，适用于大多数上下文无关文法描述的语言 分析速度快，能准确定位错误 缺点：LR分析器的构造工作量大,55,3 LR分析器的逻辑结构,LR分析器组成： 分析表 总控程序 分析栈,a1a2an,总控程序,输入串(源程序,分 析 栈,输出分 析结果,56,分析栈,符号栈 符号栈内存放分析过程中移进或归约的符号。 状态栈 状态栈存放的是状态(标记)，状态Ii概括了栈中位于Ii下面的全部信息，也就是记录分析过程从开始到某一归约阶段的整个分析历史。和预测扫描可能遇到的分析符号。 分析开始时，分析栈压入初始状态I0和输入符号#，分析器处于初始状态I0。I0刻画了当前栈内仅有一

24、个符号#的事实并预示将扫描的输入字符应刚好是可作为句子首符号的那些符号,57,分析表,动作表(ACTION) 状态转换表(GOTO,58,ACTION表,ACTION表的结构如下,59,分析动作,ACTION表中的元素ACTIONIm, ai表示当前状态Im面临输入符号ai时所完成的分析动作。分析动作可分四类： 移进 归约 接受 出错,60,移进,表示句柄尚未在分析栈的栈顶形成，正期待继续移进符号，以形成句柄。 移进的标志:ACTIONIm, ai=Sj。 当前栈顶状态为Im，输入符号为ai，应将输入符号ai移进分析栈的符号栈栈顶，同时将Ij移进分析栈的状态栈栈顶,61,ai,Ij,归约,归约

25、的标记: ACTIONIm, ai=rj。 表明当前分析栈（如右图）顶部的符号串已是当前句型的句柄，需要立即进行归约。 其中rj表示按文法的第j条规则(产生式)进行归约。设第j条规则为： AXm-r+1Xm-r+2 Xm 具体是将分析栈自顶向下的r个符号(包括状态栈内相应的状态)弹出，将A压入符号栈内，此时分析栈格局为（下页图2,62,再以(Im-r,A)查GOTO表，若GOTOIm-r, A=Ik，把Ik压入状态栈,Ik,接受,接受的标志:ACTIONIm, ai=acc。分析动作接受表示当前输入的符号串分析成功，终止分析器工作,64,出错,出错的标志: ACTIONIm, ai=error

26、。分析动作为出错，表示当前输入的符号串中有语法错误，调用相应的出错处理程序,GOTO表,GOTO表的结构如下,65,取值为状态。 表示当前状态I1面临输入符号X2时需转移到的下一个状态,总控程序,总控程序是LR分析的实现算法。描述如下： 初始化，将初始状态I0及输入符号串的左界符#推入分析栈； 从输入串中读入当前的输入符号ai，根据当前状态栈栈顶状态Im与输入符号ai查ACTION表： 若ACTIONIm, ai=Sj，完成移进动作； 若ACTIONIm, ai=rj，以文法的第j条规则完成归约动作； 若ACTIONIm, ai=acc，分析成功，结束； 若ACTIONIm, ai=error

27、，出错处理。 重复2)直到出错或接受为止,66,接受时的分析栈,a1a2ai an,输入串,67,68,68,例：文法GE (1)E-E+T (2)E-T (3)T -T*F (4)T-F (5)F-(E) (6)F-i,其LR分析表如下页，分析输入串i*i+i,例,文法GE ：(1)EE+T (2)ET (3)T T*F (4)TF (5)F (E) (6)Fi,ACTION表 GOTO表,69,状态,若移入：i为状态 若规约：i为产生式编号,Vt,Vn,70,70,分析过程 ： i*i+i,步骤状态栈符号输入串动作,10i*i+i#初始化,205i*i+i#S,303F*i+i#R6,40

28、2T*i+i#R4,5027 T* i+i#S,60275 T*i +i#S,702710 T*F +i#R6,文法GE (1)EE+T (2)ET (3)TT*F (4)TF (5)F (E) (6)Fi,110165 #E+i #S,120163 #E+F #R6,130169 #E+T #R4,1401#E #R1,15 Accept,901#E +i#R2,10016 #E+ i#S,802#T +i#R3,文法GE (1)EE+T (2)ET (3)TT*F (4)TF (5)F (E) (6)Fi,分析过程 ： i*i+i,72,72,由分析过程可以看到,1) 每次规约总是规约当前

29、句型的句柄，是规范归约,2) 分析的每一步栈内符号串与输入串的剩余部分构成规范句型,通过规范规约得到的句型,例,设有文法GS： SS S(S)S S 根据给定的分析表，对输入串()进行LR分析,73,0 0 # ( )# S2 1 02 #( )# r3 3 2 023 #(S )# S4 3 0234 #(S) # r3 5 4 02345 #(S)S # r2 1 5 01 #S # acc,1. SS 2. S(S)S 3. S,ACTION表,GOTO表如何构造? LR分析器根据分析表的构造方法的不同可分为: LR(0)分析表 SLR分析表 规范LR分析表(LR(1) LALR分析表,

30、3 LR(0,规范句型的活前缀,77,77,规范句型：通过规范规约得到的句型,前缀：字的任意首部,活前缀：是规范句型的一个前缀,且这个前缀中不含句柄之后的任何符号,例：有文法 ET | E+T | E-T Ti | (E) 拓广文法G：SE# ET | E+T | E-T Ti | (E) 已知句型E-(i) #，求活前缀,E, E-, E-(, E-(i 是句型E-(i)# 的活前缀,78,ET|E+T TF|T*F Fi|(E,0 # i1*i2+i3# 预备 #i1 *i2+i3# 移进 2 #F *i2+i3# 归约(Fi) 3 #T *i2+i3# 归约(TF) 4 # T* i2+

31、i3# 移进 5 # T*i2 +i3# 移进 6 # T*F +i3#归约(Fi) 7 #T +i3#归约(TT*F) 8 #E +i3#归约(ET) # E+ i3#移进 # E+ i3 # 移进 # E+ F # 归约(Fi) # E+ T # 归约(TF) #E # 归约(EE+T) #E # 接受,分析过程，实质上就是一个逐步产生规范句型的活前缀的过程。栈中的符号串始终是活前缀，然后继续读入，构成新的活前缀，当栈顶形成句柄时，立即进行归约。形成新的句型，然后再不断生成这个句型的活前缀,重复此过程，直到生成文法开始符号E,LR分析是通过寻找规范句型的活前缀来实现的,LR(0)项目族的构

32、造,LR(0)项目：在文法G每条规则的右部的任何位置上添加一个圆点，所构成的规则称为LR(0)项目。 规定A的LR(0)项目为：A,项目的直观意义:指明在分析过程中的某一时刻已经归约的部分和等待归约部分,80,例：对于文法GS：SA|b，AaA|b，其LR(0)项目有： SA，SA，Sb，Sb，AaA，AaA，AaA，Ab，Ab,LR(0)项目与活前缀、句柄的关系,例：GS: SaC C-AcBe Ab AAb Bd,句子abbcde分析到某一步的时候状态如右,分析到该步骤时生成的句型,该句型的一个活前缀,当前要归约的句柄是AcBe 其中：AcB已分析完毕进栈，而e还未分析（进栈），用项目C-

33、AcBe表示,LR(0)项目的分类,根据圆点所在的位置项目分为以下几种： 归约项目：形如A，表示当前栈顶的内容已构成所期望的句柄，应按A进行归约。 接受项目：形如S，其中S是文法唯一的开始符号。表示句柄已在栈顶形成，用S进行归约，整个分析成功。 移进项目：形如Aa(aVT)，表示栈内仅是句柄的一部分，为了构成句柄，应先把a移进分析栈。 待约项目：形如AB(BVN)，表示栈内仅是句柄的一部分，为了构成句柄，应先把当前输入符号串中相应的内容归约到B,82,活前缀通过由LR(0)项目构造出来的状态转换图来识别。 步骤为： 每个LR(0)项目对应NFA的一个状态，每个项目均为终态；SA为初态； 若状态

34、i和j中的LR(0)项目出自同一条规则，只是圆点位置相差一个符号，即 i为XX1X2Xi-1XiXn j为XX1X2XiXi+1Xn 则从状态i到状态j，引一条标记为Xi的箭弧； 若状态i为待约项目，则从状态i引箭弧到所有A的状态并标记为,83,例,设文法GA： AaA Ab 构造识别文法G的所有活前缀的NFA。 先对GA进行拓广，拓广后的文法GS： SA AaA Ab,84,添加一个新的开始符号S，使S-S (S为原来的开始符号） 目的在于使最终求得的action表只含有唯一一个接受状态,Ab,SA,AaA,Ab,SA,AaA,AaA,a,b,A,A,识别文法GS的活前缀的NFA,85,SA

35、 SA AaA AaA AaA Ab Ab,SA AaA Ab,确定化后的DFA,86,LR(0)项目集规范族,上图中每个状态都是由一组的项目组成的集合，称为项目集。 识别文法G的活前缀的DFA项目集的全体称为文法的LR(0)项目集规范族。 对于上述文法GS的LR(0)项目集规范族C为： C= SA，AaA，Ab， AaA，AaA，Ab， Ab， SA， AaA,87,通过列出拓广文法的所有项目，进而构造识别活前缀的NFA，再确定化为DFA的方法，工作量较大，不实用。 实用的方法是直接构造以项目集为状态的识别活前缀的DFA,88,构造文法G的LR(0)项目集规范族的方法二,项目集的闭包：即DF

36、A中的状态 设I是文法GS的一个项目集，则I的闭包closure(I)为： 任何LR(0)项目iI，有iclosure(I)； 若项目ABclosure(I)且B是GS的产生式，则Bclosure(I)； 重复2)直至closure(I)不再增大为止,GO函数,设I是项目集，XVNVT，则： GO(I, X)=closure(J) 其中J=形如AX的项目 | AXI 。 通过GO函数可以从一个项目集求出另外的的项目集。 直观含义: 它规定了识别活前缀的DFA从状态I(项目集)出发，经过X弧所应该到达的状态J(项目集),90,构造算法,构造LR(0)项目集规范族C的算法描述如下： C=closu

37、re(SS)； repeat for C中每一个项目集I和每一个文法符号X do if (GO(I, X)不空且GO(I, X)不属于C) then 将GO(I, X)加入C中； until(C不再增大,91,例,设文法GS： SA AaA|b 计算GS的LR(0)项目集规范族。 拓广后的文法为GS： 0. SA 1. AaA 2. Ab,92,I0=closure(SA) =SA, AaA, Ab GO(I0, a)=closure(AaA) =AaA, AaA, Ab=I1 GO(I0, b)=closure(Ab) =Ab=I2 GO(I0, A)=closure(SA) =SA=I3

38、GO(I1, a)=closure(Aa A)=I1 GO(I1, b)=closure(Ab)=Ab=I2 GO(I1, A)=closure(Aa A )=AaA=I4 GS的LR(0)项目集规范族C=I0，I1，I2，I3，I4,0. SA 1. AaA 2. Ab,对应的DFA,I1,I0,I2,I3,I4,94,LR(0)分析表的构造算法,设C=I0，I1，In，每个项目集Ik的下标k作为分析表的状态。则 若GO(Ik,a)=Ij，则置ACTIONk , a=Sj； 若GO(Ik, A)=Ij，则置GOTOk, A=j； 若第j条规则的项目AIk，则对所有终结符号a（包括#)置ACT

39、IONk, a=rj。 若SSIk，则置ACTIONk , #=acc； 表中空白处置出错标志,95,GS的LR(0)分析表,r1,r1,r1,4,acc,3,r2,r2,r2,2,4,S2,S1,1,3,S2,S1,0,A,b,a,GOTO,ACTION,状态,0: SA AaA Ab,2:Ab,3:SA,1:AaA AaA Ab,4:AaA,a,b,A,A,a,b,0. SA 1. AaA 2. Ab,LR(0)文法,LR(0)文法：按上述算法构造的分析表，如果每个入口不含多重定义，则称它为文法G的一张LR(0)表。具有LR(0)表的文法G称为LR(0)文法。 LR(0)文法是无二义的,例

40、：设拓广文法GS的产生式为： 0. S S 1. S aA 2. S bB 3. A cA 4. A d 5. B cB 6. B d,LR(0)项目集规范族,I0: S.S S.aA S.bB I1: (I0,S) SS. I2: (I0,a) Sa.A A.cA A.d,I3: (I0,b) Sb.B B.cB B.d I4: (I2,c) Ac.A A.cA A.d I5: (I3,c) Bc.B B.cB B.d,I6: (I2,A) SaA. I7: (I3,B) SbB. I8: (I4,A) AcA. I9: (I5,B) BcB. I10 : (I2,d) Ad. I11: (

41、I3,d) Bd,98,I4,c,I5,c,I4,d,I5,d,Ac.A A.cA A.d I4,Sa.A A.cA A.d I2,Sb.B B.cB B.d I3,Bc.B B.cB B.d I5,S.S S.aA S.bB I0,start,SS. I1,AcA. I8,SaA. I6,Ad. I10,A,d,d,A,c,a,b,S,SbB. I7,BcB. I9,Bd. I11,B,d,d,B,c,c,c,识别文法 活前缀的DFA,99,LR(0)分析表,0. S S 1. S aA 2. S bB 3. A cA 4. A d 5. B cB 6. B d,例：文法GS: (0) SS

42、 (1) SrD (2) DDi (3) Di LR（0）项目集规范族 I0: SS I3: Sr D Sr D DDi I1: SS I4: Di I2: SrD DD i I6: DDi Di 问题：其中I3中含有移进/归约冲突(ActionI3,i有两个取值）,文法不是LR(0)的，如何解决,4 SLR,SLR(1)分析,项目集IK含移进/归约或归约/归约冲突： IK :A.b, P . , Q . , 若满足FOLLOW(Q )，FOLLOW(P) ， b互不相交，则可以用下面方法解决,解决冲突的SLR(1)技术： 1、action k,b = 移进 2、对a FOLLOW (P) 则

43、 action k,a =用 P 归约 3、对a FOLLOW (Q) 则 action k,a =用 Q 归约 用SLR(1)技术解决冲突的文法称为SLR(1)文法。 SLR(1)文法是无二义的,若GO (Ik, a)= Ij, ，则置ACTIONk, a=Sj; 若第j个产生式的项目AIk, 则对任何输入符号aFOLLOW(A),置ACTIONk, a = rj; 若项目SSIk, 则置ACTIONk, #=acc; 若GO (Ik, A)= Ij, 则置GOTO(k, A)=j; 空白格置上“出错标志,SLR分析表的构造,按上述算法构造的分析表，如果每个入口不含多重定义，则称它为文法G的

44、一张SLR表。 具有SLR表的文法G称为一个SLR（1）文法。数字1的意思是，在分析过程中顶多只要向前看一个符号,SLR分析表的构造,I0: SS I3: Sr D Sr D DDi I1: SS I4: Di I2: SrD DD i I6: DDi Di,Follow(S)=# Follow(S)=# Follow(D)=i, ,0) SS (1) SrD (2) DDi (3) Di,action,goto,状态,i,r,S,D,0,1,2,3,4,6,S,2,acc,S,4,S,6,r1,r3,r3,r,2,r,2,1,3,作业： 给定以下拓广了的文法GS： S-A A-Ab A-bB

45、a B-aAc B-a B-aAb 构造LR(0)项目集规范族。证明它是SLR(1)的，而不是LR(0)的。 构造SLR(1)分析表。 用你构造的SLR(1)分析表分析串baab是否为该文法的句子,SLR（1）的局限,例：文法G: (0) SS (1) SaAd (2) SbAc (3) Saec (4) Sbed (5) Ae LR(0) 项目集规范族： I0: SS SaAd SbAc Saec Sbed I1: SS I2: SaAd Saec Ae,若项目集IK :Ab, P , Q . , 含移进/归约或归约/归约冲突 且不满足FOLLOW(Q )，FOLLOW(P) ， b互不相交

46、,I3: SbAc Sbed Ae I4: SaAd I5: Saec Ae I6：SbA c I7: Sbe d Ae I8: SaAd I9：Saec I10: SbAc I11: Sbed,0) SS (1) SaAd (2) SbAc (3) Saec (4) Sbed (5) Ae,follow(A)=d,c,ACTION GOTO a c e b d # S A 0 1 2 3 4 5 r5 S9 6 7 r7 S11 8 9 10 11,5 LR(1,例：文法G: (0) SS (1) SaAd (2) SbAc (3) Saec (4) Sbed (5) Ae I5: S ae

47、c I7: S bed A e A e,S=S=aAd=aed,S=S=bAc=bec,S=S=aec,S=S=bed,LR(1)项目： A , a 意味着处在栈中是 的相应状态，但只有当下一个输入符是a时才能进行归约. 如果有多个向前搜索符，比如a,b,c时，可写作 A u, a/b/c A ， a 意味着处在栈顶是，并期望相应， 且进入后只有当跟在后的是a时进行归约,a 称作该项目的向前搜索符（ lookahead ） 它只对圆点在最后的项目起作用,构造LR(1)项目集规范族,closure(I)按如下方式构造： 1、 I的任何项目属closure(I)； 2、若A1B2，aclosure

48、(I)，B是一产生式，那么对于FIRST(2 a)中的每个终结符b，把B,b 加进去； 3、重复2，直至closure(I)不再增大,构造LR(1)项目集规范族,GO函数： I是一个项目集，X是一个文法符号 GO(I, X) = closure(J) 其中 J= 任何形如AX,a的项目 AX,aI LR(I)项目规范族C的构造算法 同LR(0)的构造，只是初始时： C= closure(SS,例:(0) SS (1) SaAd (2) SbAc (3) Saec (4) Sbed (5) Ae 的LR(1)项目集规范族,I0: SS , # S aAd , # S bAc , # S aec

49、, # S bed , # I1: (I0, S) S S,# I2: (I0, a) S aAd, # S aec, # A e, d I3: (I0, b) S bAc, # S bed, # Ae , c,I4: (I2, A) S aAd, # I5: (I2 , e) S aec , # A e, d I6: (I3 , A) S bAc, # I7: (I3 , e) S bed, # A e,c I8: (I4 , d) S aAd, # I9: (I5 , c) S aec, ,I10: (I6 , c) S bAc, # I11: (I7,d) S bed, ,规范的LR(1

50、)分析表的构造,若GO (Ik, b)= Ij,则置ACTIONk, b=Sj; 若第j个产生式的项目A ,b属于Ik, 那么置ACTIONk, b =rj; 若项目SS,#属于Ik, 则置ACTIONk, #=acc; 若GO (Ik, A)= Ij, 则置GOTO(k, A)=j; 其他置上“error,ACTION GOTO a c e b d # S A 0 1 2 3 4 6 7 8 9 10 11,I0: SS , # S aAd , # S bAc , # S aec , # S bed , ,S2,S3,1,Acc,S5,4,I1: (I0, S) S S,# I2: (I0,