编译-第六章.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第六章,LR,分析法及分析程序自动构造,第六章,LR,分析法及分析程序自动构造（,1,）,第一节 概述,本章介绍上下文无关文法的,LR,分析方法及分析程序的自动构造,LR,：自左至右扫描,最右推导的逆过程,一、,LR,方法,1.,基本思想,在规范归约过程中，一方面记住已移进和归约的整个符号串，另一方面根据当前所用的产生式推测未来可能碰到的输入符号,.,第六章,LR,分析法及分析程序自动构造（,2,）,第一节 概述,一、,LR,方法,2.,优缺点,优点：与其它技术相比，适应文法范围更广。能力更强，识别效率相当，尤其在自左向右扫描输入串时就能发现其中错误，并能准确指出出错位置。,缺点：若用手工构造分析程序，工作量太大，且容易出错，所以必须使用自动产生这种分析程序的产生器。,3.,产生器的作用,应用产生器产生一大类上下文无关文法的,LR,分析程序,对二义性文法或难分析的特殊文法，施加一些限制，使之能用,LR,分析。,第六章,LR,分析法及分析程序自动构造（,3,）,LR,分析法通过,LR,分析器来实现,总控程序,分析表,输出带,第一节 概述二、,LR,分析器,输入带,下推栈,第六章,LR,分析法及分析程序自动构造（,4,）,1,、从逻辑上说，,LR,分析器包括两部分：,总控程序，或称为语法分析程序；,分析表,注：后面要学习的所有,LR,分析器的总控程序都相同。仅仅是它们的分析表不同,2,、总控程序作用：,查分析表，根据分析表的内容做若干简单动作，如读头后移，入栈出栈等。,注：由于总控程序很简单，所以产生器的任务就是产生分析表,第一节 概述二、,LR,分析器,第六章,LR,分析法及分析程序自动构造（,5,）,一个文法的,LR,分析器常常对应着若干不同分析表，所有分析表都恰好识别文法所产生的所有语句,本章将讨论四种不同分析表构造方法,1.LR(0),分析表：,分析能力有限，但这是建立其它,LR,分析法的基础。,2.SLR,分析表：,简单,LR,分析表构造法，是一种容易实现又有实用价值的方法，但存在一些文法构造不出,SLR,分析表,第一节 概述三、分析表,第六章,LR,分析法及分析程序自动构造（,6,）,6.1 LR,分析器,总控程序,分析表,输出带,输入带,下推栈,二、,LR,分析器,一个,LR,分析器实际上是带有下推栈的确定的有限状态自动机。可将一个“历史”与这个“历史”下的展望信息综合为抽象的一个状态,第六章,LR,分析法及分析程序自动构造（,9,）,1,、下推栈：,下推栈用于存放分析输入串过程中的所有和“历史”及相应“展望”信息形成的抽象状态,由于每个状态都概括了从分析开始到归约阶段的全部“历史”和“展望”信息，所以,LR,分析器的每步动作可由栈顶状态和读头下符号唯一确定,6.1 LR,分析器二、,LR,分析器,第六章,LR,分析法及分析程序自动构造（,10,）,1,、下推栈：,6.1 LR,分析器二、,LR,分析器,s,m,s,0,x,m,#,状态栈,符号栈,下推栈,栈顶指针,把一个“历史”和这个“历史”下的“展望”信息综合为抽象的一个状态，下推栈用于存放在对输入串进行分析的过程中这些状态，由于每个状态都概括了从分析开始到归约阶段的全部“历史”和“展望”信息，所以栈顶的状态就可用于决定当前的动作,第六章,LR,分析法及分析程序自动构造（,11,）,1,、下推栈,：,6.1 LR,分析器二、,LR,分析器,s,m,s,0,x,m,#,状态栈,符号栈,下推栈,栈顶指针,为了便于了解栈顶状态对正规分析过程的作用，我们把栈分为两栏：状态栏和符号栏。符号栈仅用于记录迄今移进,-,归约所得到的文法符号，由于它们已经被概括在“状态”里了，所以对语法分析不起作用。,初始时，状态栈放,S,0,（初态），符号栈放“,#”,（栈底符）；栈顶,S,m,代表符号栈内的符号串,X,m,X,m-1,X,1,及其展望信息,第六章,LR,分析法及分析程序自动构造（,12,）,6.1 LR,分析器二、,LR,分析器,2.,分析表,LR,分析器的核心是分析表,a,1,a,2,a,n,a,1,a,2,a,n,A,1,A,2,A,n,S,0,.,.,S,k,这张分析表包含两部分：动作表（,Action),和转向表,(,GoTo,),，它们都是二维数组,S,i,表示状态，,a,i,表示终结符，,A,i,表示非终结符,Action,goto,第六章,LR,分析法及分析程序自动构造（,13,）,状态,ACTION,GOTO,i,+,*,(,),#,E,T,F,0,S,5,S,4,1,2,3,1,S,6,acc,2,r,2,S,7,r,2,r,2,3,r,4,r,4,r,4,r,4,4,S,5,S,4,8,2,3,5,r,6,r,6,r,6,r,6,6,S,5,S,4,9,3,7,S,5,S,4,10,8,S,6,S,11,9,r,1,r,1,r,1,10,r,3,r,3,r,3,r,3,11,r,5,r,5,r,5,r,5,第六章,LR,分析法及分析程序自动构造（,15,）,2.,分析表,2,）动作表,ACTION,ACTIONS,a,表示在当前状态,S,下，面临读头下的符号,a,所应采取的动作，,注：该动作有四种可能：移进，归约，出错，接受,3,）转向表,(GOTO),GOTOS,X,表示：若,XV,T,，表示在当前状态下，读入,X,应转向什么状态；若,XV,N,，表示当前栈顶句柄归约成,X,后，应转向什么状态,注：对终结符的移进动作和转向动作可以合并在一起填在动作表中，这样，转向表可以只保留非终结符转向部分,6.1 LR,分析器二、,LR,分析器,第六章,LR,分析法及分析程序自动构造（,14,）,状态,ACTION,GOTO,i,+,*,(,),#,E,T,F,0,S,5,S,4,1,2,3,1,S,6,acc,2,r,2,S,7,r,2,r,2,3,r,4,r,4,r,4,r,4,4,S,5,S,4,8,2,3,5,r,6,r,6,r,6,r,6,6,S,5,S,4,9,3,7,S,5,S,4,10,8,S,6,S,11,9,r,1,r,1,r,1,10,r,3,r,3,r,3,r,3,11,r,5,r,5,r,5,r,5,第六章,LR,分析法及分析程序自动构造（,15,）,3.,总控程序的动作,1,）移进 把,(S,m,a,i,),的下一个状态,S=GOTO(S,m,a,i,),连同读头下符号推进栈内,栈顶成为,(S,a,i,),读头前进一格,2,）归约 指用某产生式,A,b,进行归约。若,b,的长度为,g,，则弹出栈顶的,g,个元素，使得栈顶的状态变成,S,m-,g,然后把,（,S,m-,g,A),的下一个状态,S=GOTO(S,m-,g,A),连同非终结符,A,一起推进栈，栈顶变成（,S,A),，读头不动。,3,）接受 分析成功，退出总控程序,4,）报错 输入串出错，调出相应出错程序,注：不管哪一类分析程序，总控程序的动作都一样。程序本身很简单，按动作表中填的内容具体实施而已。,6.1 LR,分析器二、,LR,分析器,第六章,LR,分析法及分析程序自动构造（,17,）,6.1 LR,分析器,例：根据表达式文法的,LR,分析表分析输入串,i*i+i,的,LR,动作过程,E E+T,E T,T T*F,T F,F (E),F i,第六章,LR,分析法及分析程序自动构造（,18,）,状态,ACTION,GOTO,i,+,*,(,),#,E,T,F,0,S,5,S,4,1,2,3,1,S,6,acc,2,r,2,S,7,r,2,r,2,3,r,4,r,4,r,4,r,4,4,S,5,S,4,8,2,3,5,r,6,r,6,r,6,r,6,6,S,5,S,4,9,3,7,S,5,S,4,10,8,S,6,S,11,9,r,1,r,1,r,1,10,r,3,r,3,r,3,r,3,11,r,5,r,5,r,5,r,5,第六章,LR,分析法及分析程序自动构造（,19,）,注：表中符号的含义：,S,j,shift j,指将读入符号,a,移进栈内并转到,j,状态，栈顶变成（,j,a);,r,j,reduce j,按第,j,号产生式进行归约；,acc accept,分析成功；,空白格 出错标志，若填入相应出错处理程序的编号，便转相应程序处理。,分析过程,LR,分析器的动作情况也可以描述成机器内部的格局间转换，其格局用三元式表示为（状态栈，已归约的符号栈，待继续分析的输入串）,6.1 LR,分析器,第六章,LR,分析法及分析程序自动构造（,16,）,状态,ACTION,GOTO,i,+,*,(,),#,E,T,F,0,S,5,S,4,1,2,3,1,S,6,acc,2,r,2,S,7,r,2,r,2,3,r,4,r,4,r,4,r,4,4,S,5,S,4,8,2,3,5,r,6,r,6,r,6,r,6,6,S,5,S,4,9,3,7,S,5,S,4,10,8,S,6,S,11,9,r,1,r,1,r,1,10,r,3,r,3,r,3,r,3,11,r,5,r,5,r,5,r,5,第六章,LR,分析法及分析程序自动构造（,19,）,0,#,状态、符号栈,i*i+i#,E E+T,E T,T T*,F,T,F,F (E),F i,第六章,LR,分析法及分析程序自动构造（,20,）,状态,ACTION,GOTO,i,+,*,(,),#,E,T,F,0,S,5,S,4,1,2,3,1,S,6,acc,2,r,2,S,7,r,2,r,2,3,r,4,r,4,r,4,r,4,4,S,5,S,4,8,2,3,5,r,6,r,6,r,6,r,6,6,S,5,S,4,9,3,7,S,5,S,4,10,8,S,6,S,11,9,r,1,r,1,r,1,10,r,3,r,3,r,3,r,3,11,r,5,r,5,r,5,r,5,第六章,LR,分析法及分析程序自动构造（,19,）,0,#,状态、符号栈,*i+i#,E E+T,E T,T T*,F,T,F,F (E),F i,5,i,5 i,第六章,LR,分析法及分析程序自动构造（,21,）,状态,ACTION,GOTO,i,+,*,(,),#,E,T,F,0,S,5,S,4,1,2,3,1,S,6,acc,2,r,2,S,7,r,2,r,2,3,r,4,r,4,r,4,r,4,4,S,5,S,4,8,2,3,5,r,6,r,6,r,6,r,6,6,S,5,S,4,9,3,7,S,5,S,4,10,8,S,6,S,11,9,r,1,r,1,r,1,10,r,3,r,3,r,3,r,3,11,r,5,r,5,r,5,r,5,第六章,LR,分析法及分析程序自动构造（,19,）,0,#,状态、符号栈,*i+i#,E E+T,E T,T T*,F,T,F,F (E),F i,3,F,第六章,LR,分析法及分析程序自动构造（,22,）,状态,ACTION,GOTO,i,+,*,(,),#,E,T,F,0,S,5,S,4,1,2,3,1,S,6,acc,2,r,2,S,7,r,2,r,2,3,r,4,r,4,r,4,r,4,4,S,5,S,4,8,2,3,5,r,6,r,6,r,6,r,6,6,S,5,S,4,9,3,7,S,5,S,4,10,8,S,6,S,11,9,r,1,r,1,r,1,10,r,3,r,3,r,3,r,3,11,r,5,r,5,r,5,r,5,第六章,LR,分析法及分析程序自动构造（,19,）,0,#,状态、符号栈,*i+i#,E E+T,E T,T T*,F,T,F,F (E),F i,3 F,第六章,LR,分析法及分析程序自动构造（,23,）,状态,ACTION,GOTO,i,+,*,(,),#,E,T,F,0,S,5,S,4,1,2,3,1,S,6,acc,2,r,2,S,7,r,2,r,2,3,r,4,r,4,r,4,r,4,4,S,5,S,4,8,2,3,5,r,6,r,6,r,6,r,6,6,S,5,S,4,9,3,7,S,5,S,4,10,8,S,6,S,11,9,r,1,r,1,r,1,10,r,3,r,3,r,3,r,3,11,r,5,r,5,r,5,r,5,第六章,LR,分析法及分析程序自动构造（,19,）,0,#,状态、符号栈,*i+i#,E E+T,E T,T T*,F,T,F,F (E),F i,2,T,第六章,LR,分析法及分析程序自动构造（,24,）,状态,ACTION,GOTO,i,+,*,(,),#,E,T,F,0,S,5,S,4,1,2,3,1,S,6,acc,2,r,2,S,7,r,2,r,2,3,r,4,r,4,r,4,r,4,4,S,5,S,4,8,2,3,5,r,6,r,6,r,6,r,6,6,S,5,S,4,9,3,7,S,5,S,4,10,8,S,6,S,11,9,r,1,r,1,r,1,10,r,3,r,3,r,3,r,3,11,r,5,r,5,r,5,r,5,第六章,LR,分析法及分析程序自动构造（,19,）,0,#,状态、符号栈,i+i#,E E+T,E T,T T*,F,T,F,F (E),F i,2,T,7,*,第六章,LR,分析法及分析程序自动构造（,25,）,状态,ACTION,GOTO,i,+,*,(,),#,E,T,F,0,S,5,S,4,1,2,3,1,S,6,acc,2,r,2,S,7,r,2,r,2,3,r,4,r,4,r,4,r,4,4,S,5,S,4,8,2,3,5,r,6,r,6,r,6,r,6,6,S,5,S,4,9,3,7,S,5,S,4,10,8,S,6,S,11,9,r,1,r,1,r,1,10,r,3,r,3,r,3,r,3,11,r,5,r,5,r,5,r,5,第六章,LR,分析法及分析程序自动构造（,19,）,0,#,状态、符号栈,+i#,E E+T,E T,T T*,F,T,F,F (E),F i,2,T,5,i,第六章,LR,分析法及分析程序自动构造（,26,）,7,*,状态,ACTION,GOTO,i,+,*,(,),#,E,T,F,0,S,5,S,4,1,2,3,1,S,6,acc,2,r,2,S,7,r,2,r,2,3,r,4,r,4,r,4,r,4,4,S,5,S,4,8,2,3,5,r,6,r,6,r,6,r,6,6,S,5,S,4,9,3,7,S,5,S,4,10,8,S,6,S,11,9,r,1,r,1,r,1,10,r,3,r,3,r,3,r,3,11,r,5,r,5,r,5,r,5,第六章,LR,分析法及分析程序自动构造（,19,）,0,#,状态、符号栈,+i#,E E+T,E T,T T*,F,T,F,F (E),F i,2,T,7,*,5 i,第六章,LR,分析法及分析程序自动构造（,27,）,状态,ACTION,GOTO,i,+,*,(,),#,E,T,F,0,S,5,S,4,1,2,3,1,S,6,acc,2,r,2,S,7,r,2,r,2,3,r,4,r,4,r,4,r,4,4,S,5,S,4,8,2,3,5,r,6,r,6,r,6,r,6,6,S,5,S,4,9,3,7,S,5,S,4,10,8,S,6,S,11,9,r,1,r,1,r,1,10,r,3,r,3,r,3,r,3,11,r,5,r,5,r,5,r,5,第六章,LR,分析法及分析程序自动构造（,19,）,0,#,状态、符号栈,+i#,E E+T,E T,T T*,F,T,F,F (E),F i,2,T,7,*,10 F,第六章,LR,分析法及分析程序自动构造（,28,）,状态,ACTION,GOTO,i,+,*,(,),#,E,T,F,0,S,5,S,4,1,2,3,1,S,6,acc,2,r,2,S,7,r,2,r,2,3,r,4,r,4,r,4,r,4,4,S,5,S,4,8,2,3,5,r,6,r,6,r,6,r,6,6,S,5,S,4,9,3,7,S,5,S,4,10,8,S,6,S,11,9,r,1,r,1,r,1,10,r,3,r,3,r,3,r,3,11,r,5,r,5,r,5,r,5,第六章,LR,分析法及分析程序自动构造（,19,）,0,#,状态、符号栈,+i#,E E+T,E T,T T*,F,T,F,F (E),F i,F,*,2 T,第六章,LR,分析法及分析程序自动构造（,29,）,状态,ACTION,GOTO,i,+,*,(,),#,E,T,F,0,S,5,S,4,1,2,3,1,S,6,acc,2,r,2,S,7,r,2,r,2,3,r,4,r,4,r,4,r,4,4,S,5,S,4,8,2,3,5,r,6,r,6,r,6,r,6,6,S,5,S,4,9,3,7,S,5,S,4,10,8,S,6,S,11,9,r,1,r,1,r,1,10,r,3,r,3,r,3,r,3,11,r,5,r,5,r,5,r,5,第六章,LR,分析法及分析程序自动构造（,19,）,0,#,状态、符号栈,+i#,E E+T,E T,T T*,F,T,F,F (E),F i,2,T,第六章,LR,分析法及分析程序自动构造（,30,）,状态栈,符号栈,输入串,动作,0,#,i*i+i#,05,#i,*,i+i#,移进,03,#F,*,i+i#,R6,归约,02,#T,*,i+i#,R4,归约,027,#T*,i+i#,移进,0275,#T*i,+i#,移进,02710,#T*F,+i#,R6,归约,02,#T,+i#,R3,归约,01,#E,+i#,R2,归约,016,#E+,i#,移进,0165,#E+i,#,移进,0163,#E+F,#,R6,归约,0169,#E+T,#,R4,归约,01,#E,#,acc,分析成功,第六章,LR,分析法及分析程序自动构造（,31,）,4,、,LR,文法,定义：如果某一文法能够构造一张分析表，使得表中每一元素至多只有一种明确动作，则该文法称为,LR,文法,注：,1,）并非所有,CFG,都是,LR,文法，但对于多数程序设计语言来说，一般都可以用,LR,文法描述,2,）和,LL(1),分析法相比，,LR,分析法适应的文法范围要广一些,6.1 LR,分析器,二、,LR,分析器,第六章,LR,分析法及分析程序自动构造（,32,）,6.2 LR(0),项目集族和,LR(0),分析表的构造,一、,LR(0),分析表构造基本思想,构造,LR(0),分析表基本思想：,只根据历史信息识别呈现于栈顶的句柄,注：,LR(0),分析表构造的思想和方法是构造其它,LR,分析法的基础,构造,LR(0),分析表基本策略,构造文法,G,的一个有限自动机，它能识别文法中的所有活前缀,第六章,LR,分析法及分析程序自动构造（,33,）,1.,活前缀,字的前缀是指该字的任意首部,例如：字,ABC,的前缀有,e,A,AB,ABC,活前缀的概念：,指规范句型的一个前缀，这种前缀不含句柄之后的任何符号,6.2 LR(0),项目集族和,LR(0),分析表的构造,一、,LR(0),分析表构造,第六章,LR,分析法及分析程序自动构造（,34,）,例如：根据下面的文法识别输入串,abbcde,1)S aAcBe,2)A b,3)A Ab,4)B d,为每条产生式的尾部加上用,I,表示的产生式序号,1),S aAcBe1,2)A b2,3)A Ab3,4)B d4,第六章,LR,分析法及分析程序自动构造（,35,）,用最右推导方式来识别，推导时把序号也带上,S,aAcBe,1,aAcd,4e1,aAb,3cd4e1,ab,2b3cd4e1,若用最左归约的方式进行识别，则完全是上面的逆过程,规范句型,abbcde,的前缀有：,e,a ab,规范句型,aAbcde,的前缀有,:,e,a,aA,aAb,规范句型,aAbcde,的前缀有,:,e,a,aA,aAc,aAcd,规范句型,aAbcde,的前缀有,:,e,a,aA,aAc,aAcB,aAcBe,第六章,LR,分析法及分析程序自动构造（,36,）,1.,活前缀,活前缀有两种类型：,1,）归态活前缀,:,活前缀的尾部正好是句柄之尾，这时可以进行归约，归约之后又成为另一句型的活前缀,2,）非归态活前缀,:,句柄尚未形成，需要继续移进若干符号之后才能形成句柄,6.2 LR(0),项目,集族和,LR(0),分析表的构造,一、,LR(0),分析表构造,第六章,LR,分析法及分析程序自动构造（,37,）,2.,构造自动机识别活前缀,对于一个文法。可以构造有限自动机，它能识别,G,的所有活前缀,由于产生式右部的符号串就是句柄。若某些符号串都已进栈，则表示它已处于,归态活前缀,。若只有部分进栈，则表示它处于,非归态活前缀,。要想知道活前缀有多大部分进栈了，可以为每个产生式构造一个自动机，由它的状态来记住当前情况，此“状态”称为“,项目,”，这些自动机的全体就是能识别所有活前缀的有限自动机。,6.2 LR(0),项目集族和,LR(0),分析表的构造一、,LR(0),分析表构造,第六章,LR,分析法及分析程序自动构造（,38,）,2.,构造自动机识别活前缀,1,）项目：,在文法的每个产生式右部添加一个圆点，就成为,G,的一个,LR(0),项目（简称项目）,注：圆点在产生式中的位置不同则是不同项目,注：,（,1,）可以把圆点理解为栈内外的分界线,（,2,）产生式右部符号串的长度为,n,，则可以分解为,n+1,个项目,（,3,）产生式,A,e,只有一个项目,A,6.2 LR(0),项目集族和,LR(0),分析表的构造一、,LR(0),分析表构造,第六章,LR,分析法及分析程序自动构造（,39,）,2.,构造自动机识别活前缀,1,）项目：,例如，产生式,A XYZ,对应四个项目,A XYZ,预期要归约的句柄是,XYZ,，但都未进栈,A XYZ,预期要归约的句柄是,XYZ,，但,X,进栈,A XYZ,预期要归约的句柄是,XYZ,，仅,XY,进栈,A XYZ,Z,处于归态活前缀，,XYZ,可进行归约，这个项目就是归约项目,6.2 LR(0),项目集族和,LR(0),分析表的构造一、,LR(0),分析表构造,第六章,LR,分析法及分析程序自动构造（,41,）,2.,构造自动机识别活前缀,2,）由项目构造,NFA,的构造方法,（,1,）将文法进行拓广，保证文法开始符号,S,不出现在任何产生式右部，即增加产生式,S S,并令,S S,作为初态项目；,（,2,）凡圆点右串的最右边的项目称终态项目或称归约项目。而,S S,称为接受项目；,6.2 LR(0),项目集族和,LR(0),分析表的构造一、,LR(0),分析表构造,第六章,LR,分析法及分析程序自动构造（,40,）,2.,构造自动机识别活前缀,2,）由项目构造,NFA,的构造方法,（,3,）设项目,i,为,X X,1,.X,i-1,X,i,X,n,项目,j,为,X X,1,.X,i,X,i+1,X,n,则从项目画一弧线射向,j,，标记为,X,i,;,若,X,i,是终结符，则项目,i,称为移进项目，,X,i,是非终结符则称项目,i,为待约项目；,（,4,）若项目,i,为,X,a,A,b,其中,A,是非终结符，则从,i,项目画,e,弧射向所有,A ,g,的项目，,g,V,*,6.2 LR(0),项目集族和,LR(0),分析表的构造一、,LR(0),分析表构造,第六章,LR,分析法及分析程序自动构造（,42,）,2.,构造自动机识别活前缀,2,）由项目构造,NFA,的构造方法,注：,1,）构造出的,NFA,是包含有,e,串的,NFA,，可以使用子集法使之确定化，使之成为一个以项目集为状态的,DFA,，这个,DFA,就是建立,LR,分析算法的基础,2,）相应,DFA,的每个状态是一个项目集，称作,LR(0),项目集，整个状态集称为,LR(0),项目集规范簇,3,）在,DFA,的一个状态对应的项目集内，每个项目是“等价”的，即从期待归约的角度看相同,6.2 LR(0),项目集族和,LR(0),分析表的构造一、,LR(0),分析表构造,第六章,LR,分析法及分析程序自动构造（,43,）,2.,构造自动机识别活前缀,2,）由项目构造,NFA,的构造方法,注：,4,）有一个唯一的初态和一个唯一的接受态，但有若干个归约态，表示有若干种活前缀的识别状态,5,）状态反映了识别句柄的情况，既句柄的大多部分已进栈，即知道了历史情况,6,）手工构造文法的项目集规范簇很困难,6.2 LR(0),项目集族和,LR(0),分析表的构造一、,LR(0),分析表构造,第六章,LR,分析法及分析程序自动构造（,44,）,例如：有一拓广的文法,G6.1,构造识别活前缀的,NFA,S E E aA|bB A cA|d B cB|d,解：,1,、这个文法的项目有：,1.S E 2.S E 3.E aA,4.E aA 5.E aA 6.A cA,7.A cA 8.A cA 9.A d,10.A d 11.E bB 12.E bB,13.E bB 14.B cB 15.B cB,16.B cB 17.B d 18.B d,第六章,LR,分析法及分析程序自动构造（,45,）,2.,构造识别活前缀的,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,第六章,LR,分析法及分析程序自动构造（,46,）,确定化后,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,11:B d,9:B cB,c,c,b,E,c,c,a,B,d,d,B,A,d,A,d,第六章,LR,分析法及分析程序自动构造（,47,）,6.2 LR(0),项目集族和,LR(0),分析表的构造一、,LR(0),项目集规范族的构造,3.,LR(0),项目集规范族的机器构造,1,）拓广文法：,增加,S S,产生式,使文法的开始符号不出现在任何产生式右部，从而保证有唯一的接受项目,注：即使原开始符号,S,不出现在任何产生式右部，为了统一起见也要增加该产生式,第六章,LR,分析法及分析程序自动构造（,48,）,3,.LR(0),项目集规范族的机器构造,2,）定义和构造项目集的闭包,设,I,是拓广文法,G,的一个项目集，定义和构造,I,的闭包,CLOSURE(I),构造文法：,A.I,的任何项目都属于,CLOSURE(I);,B.,若,A,a,B,b,属于,CLOSURE(I),B,是非终结符,那么，对于任何关于,B,的产生式,B,g,项目,B ,g,也属于,CLOSURE(I);,C.,重复执行步骤,B,直到,CLOSURE(I),不再扩大为止,6.2 LR(0),项目集族和,LR(0),分析表的构造一、,LR(0),项目集规范族的构造,第六章,LR,分析法及分析程序自动构造（,49,）,3,.LR(0),项目集规范族的机器构造,3,）状态转换函数,GO,GO(I,X),定义为,CLOSURE(J),其中,I,J,都是项目集，,X(V,N,V,T,),J=,任何形如,A,a,X,b,的项目,|A,a,X,b,I,注：其含义是对于任意项目集,I,由于,I,中有,A,a,X,b,项目，,J,中有,A,a,X,b,项目，表示识别活前缀又移进一个符号,X,6.2 LR(0),项目集族和,LR(0),分析表的构造一、,LR(0),项目集规范族的构造,第六章,LR,分析法及分析程序自动构造（,50,）,3.LR(0),项目集规范族的机器构造,4),构造,LR(0),项目集规范族的算法,过程如下：,C=CLOSURE(S S)/*,初态项目集*,/,DO,for(,对,C,中每个项目集,I,和,G,中每个文法符号,X),IF(GO(I,X),非空且不属于,C),把,GO(I,X),加入,C,中,WHILE C,仍然在扩大,注：其中,C,是集合，用于存放全部项目集,6.2 LR(0),项目集族和,LR(0),分析表的构造一、,LR(0),项目集规范族的构造,第六章,LR,分析法及分析程序自动构造（,51,）,6.2 LR(0),项目集族和,LR(0),分析表的构造,注：,1,）此算法是迭代算法。置了,C,的初态（初态仅包含第一个项目集）后，每经过一次,FOR,语句。就扩大一次,C,中的项目集数，直到项目集数不再增加为止。,2,）此算法是从,I,0,开始，按该项目集内的项目顺序依次求出所有后继项目集，由这样一层一层向下生成的所有项目集的方法避免了项目集的遗漏。,3,）若在项目集中存在,A,e,，不应再做,GO,函数转向其它项目集，因为,A ,e,和,A,e,是同一项目，都是,A ,项目，它本身是归约项目，不存在后继项目。,4,）由这个项目集规范族,C,中各个状态及状态函数,GO,可构造一张识别活前缀的,DFA,图。,第六章,LR,分析法及分析程序自动构造（,52,）,例如：有一拓广的文法,G6.1,构造识别活前缀的,NFA,S E E aA|bB A cA|d B cB|d,解：,1,、这个文法的项目有：,1.S E 2.S E 3.E aA,4.E aA 5.E aA 6.A cA,7.A cA 8.A cA 9.A d,10.A d 11.E bB 12.E bB,13.E bB 14.B cB 15.B cB,16.B cB 17.B d 18.B d,第六章,LR,分析法及分析程序自动构造（,45,）,3,.LR(0),项目集规范族的机器构造,2,）定义和构造项目集的闭包,设,I,是拓广文法,G,的一个项目集，定义和构造,I,的闭包,CLOSURE(I),构造文法：,A.I,的任何项目都属于,CLOSURE(I);,B.,若,A,a,B,b,属于,CLOSURE(I),B,是非终结符,那么，对于任何关于,B,的产生式,B,g,项目,B ,g,也属于,CLOSURE(I);,C.,重复执行步骤,B,直到,CLOSURE(I),不再扩大为止,6.2 LR(0),项目集族和,LR(0),分析表的构造一、,LR(0),项目集规范族的构造,第六章,LR,分析法及分析程序自动构造（,49,）,0:S E,E aA,E bB,第六章,LR,分析法及分析程序自动构造（,67,）,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,第六章,LR,分析法及分析程序自动构造（,68,）,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,第六章,LR,分析法及分析程序自动构造（,69,）,1:S E,0:S E,E aA,E bB,4:A cA,A cA,E d,2:E aA,A cA,E dc,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,第六章,LR,分析法及分析程序自动构造（,70,）,确定化后,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,第六章,LR,分析法及分析程序自动构造（,71,）,确定化后,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,11:B d,9:B cB,c,c,b,E,c,c,a,B,d,d,B,A,d,A,第六章,LR,分析法及分析程序自动构造（,72,）,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,第六章,LR,分析法及分析程序自动构造（,46,）,1,、,构造,LR(0),分析表,设,C=I,0,I,1,.I,n,以各项目集,I,k,（,k=0,.n),的,k,作为状态符号，并以包含,S S,的项目集作为初始状态，同时将,G,文法的产生式进行编号，然后按下列步骤填写,ACTION,表和,GOTO,表；,1,）若项目,A,a,ab,属于,Ik,的状态且,GO(I,k,a)=I,j,;a,为终结符，则置,ACTIONk,a=s,j,;,即移进,a,，并转向,I,j,状态。,2,）若项目,A a,I,k,则对任何终结符,a,（包括语句结束符,#,），置,ACTIONk,a=r,j,;,即根据,j,号产生式进行归约。,6.2 LR(0),项目集族和,LR(0),分析表的构造二、,LR(0),分析表的构造算法,第六章,LR,分析法及分析程序自动构造（,54,）,确定化后,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,11:B d,9:B cB,c,c,b,E,c,c,a,B,d,d,B,A,d,A,d,第六章,LR,分析法及分析程序自动构造（,47,）,1,、,构造,LR(0),分析表,3,）若项目,S S,属于,I,k,，则置,ACTIONk,#=accept,简写,acc,；,4,）若,GO(I,k,A)=I,j,A,是非终结符，则置,GOTOk,A=j,；,5,）分析表中凡不能用步骤,1,至,4,填入信息的空白项，均置上出错标志。,6.2 LR(0),项目集族和,LR(0),分析表的构造二、,LR(0),分析表的构造算法,第六章,LR,分析法及分析程序自动构造（,55,）,2.LR(0),文法,定义：若文法,G,按上面算法构造出来的分析表不包含多重定义项，则该文法,G,是,LR(0),文法。,注：,1,）这说明,LR(0),文法的每个项目集中不包含有任何冲突项目,2,）,LR(0),文法的能力很弱，没有使用价值，但可以利用它的构造算法来构造出其它,LR,分析表。,6.2 LR(0),项目集族和,LR(0),分析表的构造二、,LR(0),分析表的构造算法,第六章,LR,分析法及分析程序自动构造（,56,）,例如：下面的文法是,LR(0),文法，但对这个文法的各个产生式给予编号并写成：,0.S E 1.E aA 2.E bB,3.A cA 4.A d 5.B cB,6.B d,第六章,LR,分析法及分析程序自动构造（,57,）,确定化后,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,11:B d,9:B cB,c,c,b,E,c,c,a,B,d,d,B,A,d,A,d,第六章,LR,分析法及分析程序自动构造（,47,）,例如：下面文法,G,的,LR(0),项目集规范族中含有如下一个项目集（状态）,I:,I=X,d,b,b,/*,移进项目*,/,A,a,/*,归约项目*,/,B,a,/*,归约项目*,/,这三个项目告诉我们应做的动作各不相同，出现了移进,归约冲突和归约,归约冲突。这个文法一定