《编译第五章08本cp.ppt》由会员分享，可在线阅读，更多相关《编译第五章08本cp.ppt（190页珍藏版）》请在三一办公上搜索。
1、第五章 自下而上 语法分析,语法分析推导：自上而下的语法分析过程预测分析程序，递归下降分析法（最左推导）注：要求文法是LL(1)文法归约：自下而上的语法分析过程简单优先分析法，算符优先分析法、LR分析法,5.1 自下而上分析的基本问题,自下而上的语法分析过程,1.自下而上的语法分析过程思想自下而上的语法分析过程是一个最左归约的过程，从输入串开始。朝着文法的开始符号进行归约，直到到达文法的开始符号为止的过程注意：输入串在这里是指从词法分析器送来的单词符号组成的二元式的有限序列2.自下而上分析的PDA,a+b#,语法分析程序 语法表,输出带,#,工作方式：“移进归约”方式即：自左至右把输入串的符号
2、一个一个移进栈，在移进过程中不断查看栈顶符号串，一旦形成某个句型的句柄时，就将此句柄用相应的产生式左部替换（归约），若再形成句柄，就继续替换，直到栈顶不再形成句柄为止，然后继续移进符号，重复上面的过程直到栈顶只剩下文法的开始符号，输入串读完为止，这样就认为识别了一个句子。,注：1）初态时栈内仅有栈底符“#”，读头指在最左边的单词符号上.2）语法分析程序执行的动作：a)移进：读入一个单词并压入栈内，读头后移；b)归约：检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编号.c)识别成功：移进归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符.d)识
3、别失败.,一、自下而上的语法分析过程,自下而上分析的中心问题:怎样判断栈顶的符号串的可归约性，以及如何归约。这是5.2节(算符优先分析)和5.3节(LR分析法)将讨论的问题。,各种不同的自下而上分析法的一个共同特点:边输入单词符号(移进符号栈)，边归约。也就是在从左到右移进输入串的过程中，一旦发现栈顶呈现可归约串就立即进行归约。,例如：有文法如下：(1)S aAcBe(2)A b(3)A Ab(4)B d 问语句abbcde是否是该文法的合法语句?,举例,S,a A c B e,A b,d,b,5.1.2 规范规约简述,令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 S A
4、且A 则称是句型相对于非终结符A的短语。特别是，如果有 A 则称是句型相对于规则A的直接短语，一个句型的最左直接短语称为该句型的句柄。,*,+,规范归约是关于的一个最右推导的逆过程。因此，规范归约也称最左归约。S aAcBe aAcde aAbcde abbcde 注：文法是无二义的,(1)SaAcBe(2)Ab(3)AAb(4)Bd,（1）,（4）,（3）,（2）,句柄与归约,修剪子树过程,二、自下而上语法分析方法,1.优先分析器（Precedence Parser)简单优先分析法 算符优先分析法2.LR分析器,一、简单优先分析法,基本思想1.确定相邻文法符号之间的优先关系在句型中，句柄内各
5、相邻符号之间具有相同的优先级，相同优先级用“”由于句柄要先归约,所以规定句柄两端符号的优先级要比位于句柄之外的相邻符号的优先级高,优先级低于表示为“”,优先级高于表示为“”某句型中:N1.Ni-1 Ni Nj Nj+1.Nn,.,5.2 算符优先分析法,.,.,.,.,注：句型中的Ni.Nj是句柄，语法分析程序通过寻找 Ni-1Ni和Nj Nj+1来确定句柄的头尾，从而确定句柄进行归约。,.,.,.,.,二、简单优先文法,1.定义：一个文法G，如果它不含e产生式，也不含任何右部相 同的不同产生式，并且它的任何符号对（X，Y）X，Y是终结符或非终结符 或者没有关系，或者存在优先级相同或低于、高于
6、等关系之一，则这是一个简单优先文法。,2.优先级别定义：X Y 当且仅当G中含有形如P.XY.X Y当且仅当G中含有形如P.XQ.的产生式,其中Q Y X Y,当且仅当Y为文法G的终结符,G中P QR,且Q.X,Yfirst(R),.,对任何X,若文法开始符号S X,则#X;若有S.X,则X#,+,+,三、简单优先矩阵1、简单优先矩阵：根据优先关系的定义，将简单优先文法中各文法符号之间的这种关系用一个矩阵表示，称作简单优先矩阵,二、简单优先文法,PDA读入一个单词后，比较栈顶符号和该单词的优先级，若栈顶符号优先级低于该单词，继续读入；若栈顶符号优先级高于或等于读入符号，则找句柄进行归约，找不到
7、句柄就继续读入，直到最后栈内只剩下开始符号，输入串读到“#”为止，此时识别正确。,四、简单优先分析法实现过程,五、简单优先分析法的优缺点优点：算法理解简单，技术简单缺点：适用范围小，分析表尺寸太大,5.2 算符优先分析法一、什么是算符优先分析法,1.算符优先分析法：所谓算符优先分析法是仿效四则运算的计算过程而构造的一种语法分析方法.2.算符优先分析法的特点：简单直观，特别方便于表达式分析，易于手工实现，是自下而上的归约过程，但未必按照句柄归约.3.算符优先分析法的关键：规定算符（终结符）的优先级及结合性质例如：8+7-6*5/3的运算,5.2 算符优先分析法,例：表达式文法：E E+E|E-E
8、|E*E|E/E|(E)|i 对这个二义文法可能会有好几个规范推导和归约，真正运算时也有几种不同结果，但若按算符优先顺序和结合规则的规定进行归约，句子的归约过程就是唯一的，运算结果也唯一.,注：对所有的终结符定义某种优先关系，借助这种关系找出可归约的串，进行归约，达到自下而上分析的目的.,如：i+i-i*(i+i)归约过程如下：1）i+i-i*(i+i)设算数级别最高，最先归约2）E+i-i*(i+i)3）E+E-i*(i+i)+,-同级，先归约左边“+”4）E-i*(i+i)5）E-E*(i+i)-,不同级，先归约右边“”6）E-E*(E+i)7）E-E*(E+E)先算括号内，再算括号外8）
9、E-E*(E)9）E-E*E 先归约“”，再归约“+”10）E-E11）E,直观算符分析法,5.2 算符优先分析法,a+b#,直观算符优先程序 优先表,OPND操作数,Q,#,OPTR操作符,p,下推栈,直观算符分析法1）直观算符分析法使用两个工作栈：一个算符栈（OPTR）存放运算符和括号，一个算量栈（OPND)用于存放操作数和运算结果；OPTR的栈顶符号用Q表示，OPND的栈顶符号用p表示2）初态时，OPND为空，OPTR只有”#“,5.2 算符优先分析法,OPND=“”;OPTR=“#”flag=true;advance;/*读入一个单词*/While flagIf Q=“#”and SY
10、M=“#”then flag=false/*成功*/else if Q=“(“and SYM=“)”then/*匹配括号对*/OPTR栈顶出栈；advanceelse if SYM是算量 then/*移进算量*/,直观算符分析算法如下：,SYM入OPND栈；advance；else if Q SYM then/*移进算符*/SYM入OPTR栈；advance；else if Q SYM then/*归约*/OPND栈顶两个元素p1,p2弹出；弹出OPTR栈顶元素Q;将p1Qp2的结果入OPND栈；else ERROR,此算法的优缺点：优点：1）简单明了，易于手工实现，适于分析各种算术表达式 2
11、）使用此算法可以很方便地把表达式译成目标指令，只要在归约时把计算p1Qp2值改为生成相应指令（Q,p1,p2,T)即可缺点：1）算法采用两个栈，有时会把错误句子当成合法句子；而且，它也无法指出输入串出错位置 2）对于含有单目正负号的算术表达式不好处理。因为负号的优先级高于加减法，低于乘除法，但负号的形式与减号相同，不容易识别。,1、确定运算符的优先级算符优先分析法的关键是比较两个相继出现的终结符的优先级而决定应采取的动作要完成运算符间优先级的比较，可以先定义各种可能相继出现的运算符的优先级，并表示为矩阵的形式，使得能够在分析中通过查询矩阵元素而得到算符之间的优先关系,5.2.1 算符优先分析技
12、术的改进,2.对于任何两个可能相继出现的终结符a,b，若具有以下形式：“.ab.”,“.aQb.”,其中Q是某非终结符，则a,b之间的关系为：1)a b,a的优先级低于b2)a b,a的优先级等于b3)a b,a的优先级高于b4)若a,b在任何情况下都不可能相继出现，则a,b无关系,.,5.2.1 算符优先分析技术的改进,5.2 算符优先分析,右符,左符,.,注：)在此表中，包括，包括，“”是一个特殊符号，用于语句的开始符号和结束符号。)这张表满足是通常数学上的习惯约定，值得注意的是：运算量i的优先级高于算符 语句开始和结束符号“”与终结符a相继出现时，应该有 a或a#,以此来保证语句内先归约
13、。（）表示括号是成对归约的 优先关系和代数中的大于小于关系不同,a b并不意味着b a，与终结符所处的左右位置很重要.,.,1.算符文法的定义给定上下文无关文法G，若G中所有产生式右部都不包含两个相继的非终结符，则G为算符文法注：算符文法保证了两个运算符之间只有一个操作数2.算符优先文法定义：设G是一个不含有空串产生式的算符文法，并设a,bVT;P.Q,RVN 对于任何一对终结符有如下几种关系：,5.2.2 算符优先文法及优先表的构造,2.算符优先文法定义：a b 当且仅当G中含有形如P.ab.产生式，或者P aQb.产生式；a b 当且仅当G中含有形如P.aR产生式,其中R b.或R Qb.
14、;a b 当且仅当G中含有形如 P Rb,产生式,其中R.a,或R.aQ.若G中任何终结符序偶（a,b)至多满足上述关系之一，则称G为算符优先文法（OPG),.,+,+,+,+,3.算符文法和算符优先文法定义的意义这两个定义相当于对文法的句型和可归约的短语做了如下规定：设A1A2Ai-1AiAi+1An是文法G的一个句型.1.若AiVN，则Ai-1,Ai+1VT,即不允许出现相继两个非终结符；2.若B1B2Bm是当前可归约短语，并可归约为Ai，则：,a)B1B2Bm中不能有相继两个非终结符且相邻的终结符优先级全相等；b)对于B1B2Bm中首终结符b有Ai-1 bc)对于B1B2Bm中尾终结符b
15、有b Ai+1注：实际上，可归约短语是某产生式右部符号串，所以通过检查G的每一个产生式的每个候选式。可以查找出任意优先级相同的终结符序偶，要找出所有满足关系 和 的终结符序偶，就要找出各非终结符P的首终结符集和尾终结符集。,4.求各非终结符P的首终结符集和尾终结符集1）定义：首终结符集FIRSTVT(P)=a|P a.或P Qa.,aVT;P,QVN尾终结符集LASTVT(P)=a|P.a或P.aQ,aVT;P,QVN有了这两个集合后，就可以通过检查每个产生式的每个候选式，确定满足关系 和 的所有终结符序偶,+,+,+,+,例：假定产生式右部有形如：.aP串，则对于任何bFIRSTVT(P),
16、有a b;假定产生式右部有形如：.Pb.的串，则 对于任何aLASTVT(P),有a b;例：设文法G的产生式为：S aAcBe A Ab|b B d 计算每个非终结符的FIRSTVT与LASTVT及所有终结符之间的关系,解：FIRSTVT(S)=a LASTVT(S)=e FIRSTVT(A)=b LASTVT(A)=b FIRSTVT(B)=d LASTVT(B)=d,左,右,.,.,5.构造算法1）构造集合FIRSTVT(P)的算法a)方法1：根据FIRSTVT(P)的定义，按下面的规则来构造：(1)若有产生式P a.或P Qa.,则aFIRSTVT(P)(2)若aFIRSTVT(Q)，
17、且有产生式P Q则 aFIRSTVT(P).注：规则1是求FIRSTONE a的关系；规则2是求P FIRST*Q的关系.,5.构造算法1）构造集合FIRSTVT(P)的算法b)方法2：在此算法中使用了两个数据结构一个是二维布尔矩阵F，行标为非终结符P，列标为终结符a；FP,a=true,当且仅当aFIRSTVT(P);另一个是堆栈STACK;栈中动态存放曾在FP,a中为真的序偶（P,a).算法如下：,(1)初始化：将布尔矩阵F中各元素置为假；栈清空；(2)按规则1，查看产生式，对于形如P a或 P Qa.的产生式，置相应的FP,a为真，并将序偶(P,a)入栈；(3)按规则2，对栈施加如下操作
18、：弹出栈顶序偶并记为（Q,a)，查看所有产生式，看有无形如P Q.的产生式，若有，且aFIRSTVT(P)(即FP,a为假），则将FP,a置为真，并把（P,a)入栈；(4)重复步骤3，直到栈空为止.那么，在FP,a中，凡是“真”的元素即属于P的首终结符集,1）构造算符优先表算法算法过程：FOR 每条产生式P X1X2.Xn DO FOR(i=1,i=n-1,i+)if Xi 和Xi+1均为终结符 then置Xi Xi+1 if i=n-2 and Xi和Xi+2均为终结符 and Xi+1为非终结符 then置Xi Xi+2 if Xi为终结符而Xi+1为非终结符 then FOR FIRST
19、VT(Xi+1)中的每个a DO 置Xi a if Xi为非终结符而Xi+1为终结符 then FOR LASTVT(Xi)中的每个a DO 置a Xi+1,.,.,算符优先文法的另一个定义：如果文法G按此算法构造出的优先表没有重定义项，则文法G是一个算符优先文法,例：构造下面文法的算符优先表S if Eb then E else E E E+T|TT T*F|F F i Eb b,解：1）求各非终结符的首终结符和尾终结符集，为了考虑语句的开始和结束符号“#”,对文法拓广,加一个产生式 S#S#FIRSTVT(S)=if LASTVT(S)=else,+,*,iFIRSTVT(E)=+,*,i
20、 LASTVT(E)=+,*,iFIRSTVT(T)=*,i LASTVT(T)=*,iFIRSTVT(F)=i LASTVT(F)=iFIRSTVT(Eb)=b LASTVT(Eb)=b 2)填写算符优先表,左,右,.,.,5.2.3 算符优先分析算法,1.优先表构造算法的讨论构造优先表的算法仅仅反因反映文法符号间关系，并不反映附加条件，对二义性文法构造算符优先表。可能会出现多重定义项。2.非规范分析（1）.规范规约严格按照句柄进行归约，终结符和非终结符一起考虑，只要栈顶形成句柄。不管句柄是否包含终结符都要进行归约。,5.2 算符优先分析法,例：考虑非二义的表达式文法G(E):E E+T|T
21、 T T*F|F F(E)|i 识别句子i+i*i的过程（1）规范归约 i+i*i#1.F+i*i#2.T+i*i#3.E+i*i#4.E+F*i#5.E+T*i#,6.E+T*F#7.E+T#8.E#,2.非规范分析(2).算符优先分析在算符优先分析，仅研究终结符之间的优先关系，而不考虑非终结符之间的优先关系；但句柄是由终结符和非终结符一起构成的，所以算符优先分析相对来说是非规范的分析。对上题的分析过程：i+i*i#1.E+i*i#2.E+T*i#3.E+T*F#,4.E+T#5.E#,两种分析的语法树对比：,E,E+T,T,F,i,T*F,F,i,i,E,E+T,i,T*F,i,i,2.非
22、规范分析(2).算符优先分析注：在算符优先分析中，可归约的短语不再称为句柄，而称为最左素短语，素短语是指这样一个短语，至少含有一个终结符，且除它自身外不再包含其它素短语，最左边的素短语称为最左素短语。例：考虑非二义的表达式文法G(E):E E+T|T T T*F|F F(E)|i 句型#T+T*F+i#的素短语，为什么？,E,E+T,E+T,T*F,T,F,i,由定义可知，素短语：T*F,i 最左素短语：T*F,3.通用算符优先分析(1)最左素短语的判断假定文法的句型的一般形式为：#N1a1N2a2.NnanNn+1#其中ai是终结符，Ni是可有可无的非终结符，设最左素短语为ajNiaiNi+
23、1,则必有：aj-1 aj ai+1.ai ai+1 则，ajNiaiNi+1一定能归约为某非终结符 注意：在程序设计语言中会经常看到这种素短语(如：S for(i=E,i=E,i+),当栈顶形成某素短语时就可以进行归约，算符优先分析中也要考虑到这种归约）,.,.,.,3.通用算符优先分析(2).通用算符优先分析算法注：1).算法结束时，若栈内只有“#”和某非终结符，读头下为“#”，则表示分析成功，否则输入串有错。2).在进行最左素短语归约时，只要能找出产生式，其右部的终结符与栈顶的若干终结符有一一对应的关系，当名称相同，位置也相同时即可进行归约，由于最左素短语不考虑非终结符，所以归约成什么符
24、号无关紧要。,例如：根据下面文法及其算符优先表，按通用通用算符优先分析的算法分析语句 if b then i else i#S if Eb then E else E E E+T|TT T*F|F F i Eb b,左,右,4.算符优先分析的优缺点：A.算符优先分析比规范规约要快得多，因为它跳过了许多单非终结符的归约，但是，由于忽略了非终结符在归约中的作用，它可能会把错误的输入串误认为是合法的句子。B.算符优先文法适用范围比简单优先文法大得多 许多程序设计语言都可以用它来分析，算符优先分析表构造简单。甚至可以用手工构造。C.缺点在于有些文法不满足算符优先文法，必须先改写，有些甚至无法改写，若终
25、结符数目多，优先表可能会占有太多空间,5.2.4 算符优先分析中的出错处理,使用算符优先分析法时，可在两种情况下，发现语法错误：(1)若在栈顶终结符号与下一输入符号之间不存在任何优先关系；(2)若找到某一“句柄”(此处“句柄”指素短语)，但不存在任一产生式，其右部为此“句柄”。,本节介绍上下文无关文法的LR分析方法及分析程序的自动构造LR：自左至右扫描,最右推导的逆过程一、LR方法1.基本思想 在规范归约过程中，一方面记住已移进和归约的整个符号串，另一方面根据当前所用的产生式推测未来可能碰到的输入符号.,5.3 LR分析法,一、LR方法概述,2.优缺点优点：与其它技术相比，适应文法范围更广。能
26、力更强，识别效率相当，尤其在自左向右扫描输入串时就能发现其中错误，并能准确指出出错位置。缺点：若用手工构造分析程序，工作量太大，且容易出错，所以必须使用自动产生这种分析程序的产生器。3.产生器的作用应用产生器产生一大类上下文无关文法的LR分析程序对二义性文法或难分析的特殊文法，施加一些限制，使之能用LR分析。,LR分析法通过LR分析器来实现,总控程序 分析表,输出带,5.3.1 LR分析器,输入带,下推栈,1、从逻辑上说，LR分析器包括两部分：总控程序（称为语法分析程序）；分析表注：后面要学习的所有LR分析器的总控程序都相同。仅仅是它们的分析表不同2、总控程序作用：查分析表，根据分析表的内容做
27、若干简单动作，如读头后移，入栈出栈等。注：由于总控程序很简单，所以产生器的任务就是产生分析表,5.3.1 LR分析器,一个文法的LR分析器常常对应着若干不同分析表，所有分析表都恰好识别文法所产生的所有语句本章将讨论四种不同分析表构造方法1.LR(0)分析表：分析能力有限，但这是建立其它LR分析法的基础。2.SLR分析表：简单LR分析表构造法，是一种容易实现又有实用价值的方法，但存在一些文法构造不出SLR分析表,5.3.1 LR分析器,3、规范LR分析表它能力最强，但实现代价过高，分析表尺寸太大4、LALR分析表向前看LR分析表构造文法，也是一种常用方法注：实际上，SLR和LALR分别是对LR(
28、0)和规范LR的改进最后，将讨论如何使用二义文法构造LR分析器并产生高效的分析技术,5.3.1 LR分析器,在规范归约时，当一串貌似句柄的符号串呈现于栈顶时，LR分析法根据三方面的信息找句柄：历史：记录在栈内的符号串移进，归约的历史情况 展望：预测句柄之后可能出现的信息；现实：读头下的符号注：LR分析法的基本思想是符合人的思维习惯的，但实现有困难，因为基于“历史”对未来的“展望”可能存在多种可能。当把“历史”和“展望”材料综合在一起时复杂性就大大增加。如果简化对“展望”的要求，就可获得实际可行的分析算法。,一、LR分析法的基本思想,5.3.1 LR分析器,总控程序 分析表,输出带,输入带,下推
29、栈,二、LR分析器一个LR分析器实际上是带有下推栈的确定的有限状态自动机。可将一个“历史”与这个“历史”下的展望信息综合为抽象的一个状态,5.3.1 LR分析器,1、下推栈：下推栈用于存放分析输入串过程中的所有和“历史”及相应“展望”信息形成的抽象状态 由于每个状态都概括了从分析开始到归约阶段的全部“历史”和“展望”信息，所以LR分析器的每步动作可由栈顶状态和读头下符号唯一确定,5.3.1 LR分析器,1、下推栈：,sm,s0,xm,#,状态栈,符号栈,下推栈,栈顶指针,把一个“历史”和这个“历史”下的“展望”信息综合为抽象的一个状态，下推栈用于存放在对输入串进行分析的过程中这些状态，由于每个
30、状态都概括了从分析开始到归约阶段的全部“历史”和“展望”信息，所以栈顶的状态就可用于决定当前的动作 初始时，状态栈放S0（初态），符号栈放“#”（栈底 符）；栈顶Sm代表符号栈内的符号串XmXm-1X1及其展望信息,5.3.1 LR分析器,2.分析表LR分析器的核心是分析表,这张分析表包含两部分：动作表（Action)和转向表(GoTo)，它们都是二维数组。Si表示状态，ai表示终结符，Ai表示非终结符,Action,goto,5.3.1 LR分析器,2.分析表 动作表ACTION ACTIONS,a表示在当前状态S下，面临读头下的符号a所应采取的动作，注：该动作有四种可能：移进，归约，出错，
31、接受 转向表(GOTO)GOTOS,X表示：若XVT，表示在当前状态下，读入X应转向什么状态；若XVN，表示当前栈顶句柄归约成X后，应转向什么状态 注：对终结符的移进动作和转向动作可以合并在一起填在动作表中，这样，转向表可以只保留非终结符转向部分,5.3.1 LR分析器,3.总控程序的动作 1）移进 把(Sm,ai)的下一个状态S=GOTO(Sm,ai)连同读头下 符号推进栈内,栈顶成为(S,ai),读头前进一格2）归约 指用某产生式A b进行归约。若b的长度为g，则弹出栈顶的g个元素，使得栈顶的状态变成Sm-g,然后把（Sm-g,A)的下一个状态S=GOTO(Sm-g,A)连同非终结符A一起
32、 推进栈，栈顶变成（S,A)，读头不动。3）接受 分析成功，退出总控程序4）报错 输入串出错，调出相应出错程序 注：不管哪一类分析程序，总控程序的动作都一样。程序本身很简单，按动作表中填的内容具体实施而已。,5.3.1 LR分析器,注：表中符号的含义：Sj shift j,指将读入符号a移进栈内并转到j状态，栈顶变成（j,a);rj reduce j,按第j号产生式进行归约；acc accept,分析成功；空白格 出错标志，若填入相应出错处理程序的编号，便转相应程序处理。分析过程：LR分析器的动作情况也可以描述成机器内部的格局间转换，其格局用三元式表示为（状态栈，已归约的符号栈，待继续分析的输
33、入串）,5.3.1 LR分析器,举例：根据表达式文法的LR分析表分析输入串i*i+i的LR动作过程E E+TE TT T*FT FF(E)F i,5.3.1 LR分析器,0,#,状态、符号栈,i*i+i#,E E+TE TT T*FT FF(E)F i,0,#,状态、符号栈,*i+i#,E E+TE TT T*FT FF(E)F i,5,i,5 i,0,#,状态、符号栈,*i+i#,E E+TE TT T*FT FF(E)F i,3,F,0,#,状态、符号栈,*i+i#,E E+TE TT T*FT FF(E)F i,3 F,0,#,状态、符号栈,*i+i#,E E+TE TT T*FT FF
34、(E)F i,2,T,0,#,状态、符号栈,i+i#,E E+TE TT T*FT FF(E)F i,2,T,7,*,0,#,状态、符号栈,+i#,E E+TE TT T*FT FF(E)F i,2,T,5,i,7,*,0,#,状态、符号栈,+i#,E E+TE TT T*FT FF(E)F i,2,T,7,*,5 i,0,#,状态、符号栈,+i#,E E+TE TT T*FT FF(E)F i,2,T,7,*,10 F,0,#,状态、符号栈,+i#,E E+TE TT T*FT FF(E)F i,F*2 T,0,#,状态、符号栈,+i#,E E+TE TT T*FT FF(E)F i,2,T
35、,4、LR文法定义：如果某一文法能够构造一张分析表，使得表中每一元素至多只有一种明确动作，则该文法称为LR文法注：1）并非所有CFG都是LR文法，但对于多数程序设计语言来说，一般都可以用LR文法描述 2）和LL(1)分析法相比，LR分析法适应的文法范围要广一些,5.3.1 LR分析器,5.3.2 LR(0)项目集族和LR(0)分析表的构造,一、LR(0)分析表构造基本思想只根据历史信息识别呈现于栈顶的句柄注：LR(0)分析表构造的思想和方法是构造其它LR分析法的基础二、构造LR(0)分析表基本策略 构造文法G的一个有限自动机，它能识别文法中的所有活前缀,1.活前缀字的前缀是指该字的任意首部 例
36、如：字ABC的前缀有e,A,AB,ABC活前缀的概念：指规范句型的一个前缀，这种前缀不含句柄之后的任何符号,5.3.2 LR(0)项目集族和LR(0)分析表的构造,一、LR(0)分析表构造,举例：根据下面的文法识别输入串abbcde1)S aAcBe2)A b3)A Ab4)B d为每条产生式的尾部加上用I表示的产生式序号1)S aAcBe12)A b23)A Ab34)B d4,用最右推导方式来识别，推导时把序号也带上 S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1若用最左归约的方式进行识别，则完全是上面的逆过程规范句型abbcde的前缀有：e,a ab规范句型a
37、Abcde的前缀有:e,a,aA,aAb规范句型aAcde的前缀有:e,a,aA,aAc,aAcd规范句型aAcBe的前缀有:e,a,aA,aAc,aAcB,aAcBe,1.活前缀活前缀有两种类型：1）归态活前缀:活前缀的尾部正好是句柄之尾，这时可以进行归约，归约之后又成为另一句型的活前缀 2）非归态活前缀:句柄尚未形成，需要继续移进若干符号之后才能形成句柄,5.3.2 LR(0)项目集族和LR(0)分析表的构造,一、LR(0)分析表构造,2.构造自动机识别活前缀对于一个文法。可以构造有限自动机，它能识别G的所有活前缀由于产生式右部的符号串就是句柄。若某些符号串都已进栈，则表示它已处于归态活前
38、缀。若只有部分进栈，则表示它处于非归态活前缀。要想知道活前缀有多大部分进栈了，可以为每个产生式构造一个自动机，由它的状态来记住当前情况，此“状态”称为“项目”，这些自动机的全体就是能识别所有活前缀的有限自动机。,5.3.2 LR(0)项目集族和LR(0)分析表的构造,一、LR(0)分析表构造,2.构造自动机识别活前缀1）项目：在文法的每个产生式右部添加一个圆点，就成为G的一个LR(0)项目（简称项目）注：圆点在产生式中的位置不同则是不同项目注：（1）可以把圆点理解为栈内外的分界线（2）产生式右部符号串的长度为n，则可以分解为n+1个项目（3）产生式A e只有一个项目A,5.3.2 LR(0)项
39、目集族和LR(0)分析表的构造,一、LR(0)分析表构造,举例，产生式A XYZ对应四个项目A XYZ,预期要归约的句柄是XYZ，但都未进栈A XYZ,预期要归约的句柄是XYZ，但X进栈A XYZ,预期要归约的句柄是XYZ，仅XY进栈A XYZ,Z处于归态活前缀，XYZ可进行归约，这个项目就是归约项目,5.3.2 LR(0)项目集族和LR(0)分析表的构造,一、LR(0)分析表构造,2.构造自动机识别活前缀2）由项目构造NFA的构造方法（1）将文法进行拓广，保证文法开始符号S不出现在任何产生式右部，即增加产生式 S S,并令S S作为初态项目；（2）凡圆点右串的最右边的项目称终态项目或称归约项
40、目。而 S S称为接受项目；（3）设项目i为X X1.Xi-1XiXn,项目j为 X X1.XiXi+1Xn,则从项目画一弧线射向j，标记为Xi;若Xi是终结符，则项目i称为移进项目，Xi是非终结符则称项目i为待约项目；（4）若项目i为X aAb,其中A是非终结符，则从i项目画e弧射向所有A g的项目，gV*,5.3.2 LR(0)项目集族和LR(0)分析表的构造,一、LR(0)分析表构造,5.3.2 LR(0)项目集族和LR(0)分析表的构造,一、LR(0)分析表构造,注：1）构造出的NFA是包含有e串的NFA，可以使用子集法使之确定化，使之成为一个以项目集为状态的DFA，这个DFA就是建立
41、LR分析算法的基础 2）相应DFA的每个状态是一个项目集，称作LR(0)项目集，整个状态集称为LR(0)项目集规范簇 3）在DFA的一个状态对应的项目集内，每个项目是“等价”的，即从期待归约的角度看相同 4）有一个唯一的初态和一个唯一的接受态，但有若干个归约态，表示有若干种活前缀的识别状态 5）状态反映了识别句柄的情况，既句柄的大多部分已进栈，即知道了历史情况 6）手工构造文法的项目集规范簇很困难,举例：有一拓广的文法构造识别活前缀的NFAS E E aA|bB A cA|d B cB|d解：这个文法的项目有：1.S E 2.S E 3.E aA4.E aA 5.E aA 6.A cA7.A
42、cA 8.A cA 9.A d10.A d 11.E bB 12.E bB13.E bB 14.B cB 15.B cB16.B cB 17.B d 18.B d,构造识别活前缀的NFA,3,8,6,7,4,9,10,1,5,2,11,15,14,12,16,13,18,17,e,a,E,e,c,e,A,b,e,d,B,e,c,B,d,e,e,e,e,A,e,确定化后,1:S E,0:S E E aA E bB,4:A cA A cA A d,2:E aA A cA A d,3:E bB B cB B d,5:B cB B cB B d,6:E aA,10:A d,8:A cA,7:E bB,
43、11:B d,9:B cB,c,c,b,E,c,c,a,B,d,d,B,A,d,A,d,5.3.2 LR(0)项目集族和LR(0)分析表的构造二、LR(0)项目集规范族的构造,3.LR(0)项目集规范族的机器构造1）拓广文法：增加S S产生式,使文法的开始符号不出现在任何产生式右部，从而保证有唯一的接受项目注：即使原开始符号S不出现在任何产生式右部，为了统一起见也要增加该产生式,2）定义和构造项目集的闭包设I是拓广文法G的一个项目集，定义和构造I的闭包CLOSURE(I)构造文法：A.I的任何项目都属于CLOSURE(I);B.若A aBb属于CLOSURE(I),B是非终结符,那么，对于任何
44、关于B的产生式B g,项目B g 也属于CLOSURE(I);C.重复执行步骤B,直到CLOSURE(I)不再扩大为止,5.3.2 LR(0)项目集族和LR(0)分析表的构造二、LR(0)项目集规范族的构造,3）状态转换函数GOGO(I,X)定义为CLOSURE(J),其中I,J都是项目集，X(VNVT),J=任何形如A aXb的项目|A aXbI 注：其含义是对于任意项目集I,由于I中有 A aXb项目，J中有A aXb项目，表示识别活前缀又移进一个符号X,5.3.2 LR(0)项目集族和LR(0)分析表的构造二、LR(0)项目集规范族的构造,4)构造LR(0)项目集规范族的算法过程如下：C
45、=CLOSURE(S S)/*初态项目集*/DO FOR(对C中每个项目集I和G中每个文法符号X)DO IF(GO(I,X)非空且不属于C)把GO(I,X)加入C中 WHILE C 仍然在扩大 注：其中C是集合，用于存放全部项目集,注：1）此算法是迭代算法。置了C的初态（初态仅包含第一个项目集）后，每经过一次FOR语句。就扩大一次C中的项目集数，直到项目集数不再增加为止。2）此算法是从I0开始，按该项目集内的项目顺序依次求出所有后继项目集，由这样一层一层向下生成的所有项目集的方法避免了项目集的遗漏。3）若在项目集中存在A e，不应再做GO函数转向其它项目集，因为A e和A e是同一项目，都是A
46、 项目，它本身是归约项目，不存在后继项目。4）由这个项目集规范族C中各个状态及状态函数GO可构造一张识别活前缀的DFA图。,举例：有一拓广的文法构造识别活前缀的NFAS E E aA|bB A cA|d B cB|d解：这个文法的项目有：1.S E 2.S E 3.E aA4.E aA 5.E aA 6.A cA7.A cA 8.A cA 9.A d10.A d 11.E bB 12.E bB13.E bB 14.B cB 15.B cB16.B cB 17.B d 18.B d,2）定义和构造项目集的闭包设I是拓广文法G的一个项目集，定义和构造I的闭包CLOSURE(I)构造方法：A.I的任
47、何项目都属于CLOSURE(I);B.若A aBb属于CLOSURE(I),B是非终结符,那么，对于任何关于B的产生式B g,项目B g也属于CLOSURE(I);C.重复执行步骤B,直到CLOSURE(I)不再扩大为止,0:S E E aA E bB,0:S E E aA E bB,2:E aA A cA A dc,1:S E,3:E bB B cB B d,a,E,b,0:S E E aA E bB,2:E aA A cA A d,1:S E,3:E bB B cB B d,a,E,b,4:A cA A cA A d,10:A d,6:E aA,c,d,A,1:S E,0:S E E aA
48、 E bB,4:A cA A cA A d,2:E aA A cA A d,3:E bB B cB B d,5:B cB B cB B d,6:E aA,10:A d,7:E bB,11:B d,c,b,E,c,a,d,B,A,d,确定化后,1:S E,0:S E E aA E bB,4:A cA A cA A d,2:E aA A cA A d,3:E bB B cB B d,5:B cB B cB B d,6:E aA,10:A d,7:E bB,11:B d,9:B cB,c,c,b,E,c,a,B,d,d,B,A,d,确定化后,1:S E,0:S E E aA E bB,4:A cA
49、A cA A d,2:E aA A cA A d,3:E bB B cB B d,5:B cB B cB B d,6:E aA,10:A d,8:A cA,7:E bB,11:B d,9:B cB,c,c,b,E,c,c,a,B,d,d,B,A,d,A,3,8,6,7,4,9,10,1,5,2,11,15,14,12,16,13,18,17,e,a,E,e,c,e,A,b,e,d,B,e,c,B,d,e,e,e,e,A,e,构造识别活前缀的NFA,设C=I0,I1.In,以各项目集Ik（k=0,.n)的k作为状态符号，并以包含S S的项目集作为初始状态，同时将G文法的产生式进行编号，然后按下列
50、步骤填写ACTION表和GOTO表；1）若项目A aab 属于Ik的状态且GO(Ik,a)=Ij;a为终结符，则置ACTIONk,a=sj;即移进a，并转向Ij状态。2）若项目A aIk,则对任何终结符a（包括语句结束符#），置ACTIONk,a=rj;即根据j号产生式进行归约。3）若项目S S属于Ik，则置ACTIONk,#=accept,简写acc；4）若GO(Ik,A)=Ij,A是非终结符，则置GOTOk,A=j；5）分析表中凡不能用步骤1)至4)填入信息的空白项，均置上出错标志。,三、构造LR(0)分析表,确定化后,1:S E,0:S E E aA E bB,4:A cA A cA A
