编译原理清华大学第6章自底向上优先分析法

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Compile,第,6,章 自底向上优先分析,(Bottom-up Parsing),6.1,概述,原理,:,在采用,自左向右,扫描，,自底向上,分析的前提下，该类,分析方法是从输入符号串入手，通过反复查找当前句,型的句柄（最左简单短语），并使用文法的产生式把,句柄归约成相应的非终极符来一步步地进行分析的。,最终把输入串归约成文法的开始符号，表明分析成功。,所以，任何自底向上分析方法的,关键,就是要找出,当前句型的句柄,（或是他的变型），然后根据产生式判别将它,归约成非终极符号。,两种常用的分析方法：,优先分析法,和,LR,分析法,。,自底向上分析的一般过程：,先设置一个寄存符号的栈，称为,分析,栈。其作用是用来记录分析的历史和指示分析的下一步动作。分析进行时，把输入符号一个一个地按扫描顺序移进栈中，当栈顶符号形成一个句柄（即为某产生式的右部）时，就进行一次归约，把栈顶构成句柄的那个符号串用相应的产生式左部符号来替换,。,接着再检查在栈顶是否又出现了新的句柄，则再进行归约，直至整个输入符号串处理完。最终如果栈顶为文法的开始符号，则所分析的输入符号串为合法的符号串，报告分析成功,否则，是不合格的符号串，报告错误。,给定句型找句柄的步骤：,短语 简单短语 句柄,注意,：短语、简单短语是相对于句型而言，一个句型,可能有多个短语、简单短语，句柄只能有一个。,句型的短语、简单短语和句柄,定义 给定文法,GZ,w=xuy,V,+,，为该文法的句型,若,Z=xUy,且,U,=,u,则,u,是句型,w,相对于,U,的短语；,若,Z=xUy,且,U,=,u,则,u,是句型,w,相对于,U,的简单短语。,其中,U,V,N,，,u,V,+,，,x,y,V,*,*,*,直观理解：短语是前面句型中的某个非终结符所能推出的符号串。,例：给定文法,G,：,ET|E+T|E,T,TF|T*F|T,F,Fi|(E),符号串（,T+i,）*,i,F,是文法,G,的一个句型，求其短语、简单短语和句柄。,E,E,T,T,T,T*F,T,F*F,T,(E)*F,T,(T+T)*F,T,(T+F)*F,T,(T+i)*F,T,(T+i)*i,T,(T+i)*i,T,解：短语有,8,个：,1.E,E,，,E,（,T+i,）*,i,F,则有：,（,T+i,）*,i,F,2.,E,T,F,，,T,（,T+i,）*,i,则有：,（,T+i,）*,i,3.E,T,*i,F,，,T,（,T+i,）,则有：,（,T+i,）,4.E,(,E,)*i,F,，,E,T+i,则有：,T+i,5.E,(,E,+i)*i,F,，,E,T,则有：,T,6.E,(T+,F,)*i,F,，,F,i,则有：第一个,i,7.E,(T+i)*,F,F,，,F,i,则有：第二个,i,8.E,(T+i)*F,T,，,T,F,则有：,F,*,+,*,+,*,+,*,+,*,+,*,+,*,+,*,+,其简单短语有,4,个：,1.,E,(,E,+i)*i,F,E,T,则有：,T,2.,E,(T+,F,)*i,F,F,i,则有：第一个,i,3.,E,(T+i)*,F,F,F,i,则有：第二个,i,4.,E,(T+i)*F,T,T,F,则有：,F,句柄有,1,个：,T,E,E,T,T,T,*,F,F,(,E,),F,i,E,+,T,T,F,i,用语法树求,短语、简单短语和句柄,的方法：,1,）每个句型都有一棵语法树；,2,）每棵语法树的叶（从左到右）组成一句型；,3,）每个子树 的叶（从左到右）组成一短语；,4,）每个简单子树 的叶（从左到右）组成一简单短语；,5,）最左简单子树 的叶（从左到右）组成一句柄。,例：考虑文法,G(E),：,EE+T,|,T TT*F,|,F Fi,|,(E),并假定输入串为（,i+i)*i,，考察,自底向上的分析过程。,分析过程图表：,为了具体实现上的方便，统一约定以,“,#,”,作为输入串的左右分界符（开始和结束标志）。作为初始状态，先将符号串的开始标志,“,#,”,压入分析栈中，作为栈底符号，则分析过程为：,步骤 分析栈 输入串 动作,#(i+i)*i#,移进,#(i+i)*i#,移进,#(i +i)*i#,归约,#(F +i)*i#,归约,#(T +i)*i#,归约,#(E +i)*i#,移进,#(E+i)*i#,移进,#(E+i )*i#,归约,#(E+F )*i#,归约,步骤 分析栈 输入串 动作,10#(E+T )*i#,归约,11#(E )*i#,移进,12#(E)*i#,归约,13#F *i#,归约,14#T *i#,移进,15#T*i#,移进,16#T*i#,归约,17#T*F#,归约,18#T#,归约,19#E#,接受,分析过程图表：,步骤 分析栈 输入串 动作,#(i+i)*i#,移进,#(i+i)*i#,移进,#(i +i)*i#,归约,#(F +i)*i#,归约,#(T +i)*i#,归约,#(E +i)*i#,移进,#(E+i)*i#,移进,#(E+i )*i#,归约,#(E+F )*i#,归约,步骤 分析栈 输入串 动作,10#(E+T )*i#,归约,11#(E )*i#,移进,12#(E)*i#,归约,13#F *i#,归约,14#T *i#,移进,15#T*i#,移进,16#T*i#,归约,17#T*F#,归约,18#T#,归约,19#E#,接受,需要说明的是分析栈上的候选式不一定是句柄。例如，在第,14,步对栈顶为,T,，它是,E,的一候选式，但它不是句柄，不能归约成,E,。判定候选式是极为简单的事情，但判定句柄就不那么容易。而不同的自底向上方法给出不同的判定方法。,从上述例子可知，自底向上方法主要包括以下四个动作：,移进：把输入流的头符读到分析栈中。,归约：把分析栈顶的句柄归约为一非终极符。,接受：分析成功。,报错：处理错误。,6.2,简单优先方法,(,Simple-precedence Parsing,),6.2.1,概述,简单优先方法是一种简单直观，广为使用的自底向上的分析方法，它是经由算符优先方法变化而来的。这种方法特别有利于分析表达式。,大家知道，在做算术式的四则运算时，为了保证计算过程和结果的唯一性，人们作了统一的四则运算规则的规定。这个法则的主要方面就是规定运算符之间的优先顺序。即先乘除后加减，同优先级的运算符先左后右（左结合律）。还有先括号内后括号外的规定。,而简单优先方法就是根据上述算术运算的计算过程而设计的一种语法分析方法。,这种方法的基本思想为：,首先规定文法符号之间的优先关系和结合性质，然后在利用这种关系，通过比较句型中两个相邻的符号之间的优先顺序来确定句型的,“,句柄,”,并进行归约。,6.2.2,相邻关系：,设,S,i,和,S,j,是文法,G,的任意两个符号，那么它们在句型中可相邻出现的充要条件是必须满足下列条件之一：,1,、有形如,U,S,i,S,j,的产生式,2,、有形如,U,S,i,W,的产生式，且有,W,S,j,+,3,、有形如,U,V,S,j,的产生式，且有,V,S,i,+,4,、有形如,U,VW,的产生式，且有,V,S,i,和,W,S,j,+,+,(1),有形如,U,S,i,S,j,的产生式,U,S,i,S,j,S,U,S,i,S,j,图,6.1,采用,U,S,i,S,j,的推导,+,S,j,U,S,i,W,图,6.2,采用,U,S,i,W,的推导,(2),有形如,U,S,i,W,的产生式，且有,W,S,j,+,S,U,S,i,W,S,i,S,j,+,+,S,i,U,V,S,j,图,6.3,采用,U,V,S,j,的推导,(3),有形如,U,V,S,j,的产生式，且有,V,S,i,+,S,U,V,S,j,S,i,S,j,+,+,S,i,U,V,W ,S,j,图,6.4,采用,U,V,W,的推导,(4),有形如,U,VW,的产生式，且有,V,S,i,和,W,S,j,+,+,S,U,V,W,j,S,i,S,j,+,+,6.2.3,优先关系：,为了把上述条件加以形式化，引进三种优先关系。其定义如下：,当且仅当存在形如下面的产生式,U,S,i,S,j,Si,Sj,当且仅当存在形如下面的产生式,U,S,i,W,的生产式，,且有,W,S,j,Si,Sj,+,当且仅当存在形如下面的产生式,U,VW,的生产式,且有,V,S,i,和,W,S,j,Si,Sj,+,*,在实际使用这些优先关系去识别句子时，我们希望采用一种简洁的方法去表示这些关系，优先关系矩阵是一种常用的方式。,其定义为：,例：设有文法,G,z,：,Z,bMb,M,a(L,L,Ma),则可根据定义求出其优先矩阵来（如下）,MSi,，,Sj=,空,当,Si,与,Sj,无关系,(,不相邻出现,),时,当,Si,Sj,当,Si,Sj,当,Si,Sj,优先关系矩阵,：,Z,bMb M,a(L L,Ma),Z,b,M,b,a,Z,b,M,b,(,L,Z,b,M,b,(,L,M,a,),),=,a,(,=,b,L,=,=,M,Z,Z M L b (a ),.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,=,.,构造优先关系矩阵的一种简便方法：,STEP 1,对每个非终极符,W,求下面两种集合：,STEP 2,对每个符号对,Si,Sj,填写优先关系矩阵元素,(,其中,W,VV,N,):,Z M L,HEAD b (,a M,(,a,LAST b ),L,a ),如对,Ga,我们有：,Z,bMb M,a(L L,Ma),MSi,Sj=,，如果有,U,S,i,W,且,S,j,HEAD(W),MSi,Sj=,，如果有,U,VW,且有,S,i,LAST(V),和,S,j,HEAD(W)W,MSi,Sj=,，如果有,U,S,i,S,j,HEAD(W)=,SW,S,S(V,N,UV,T,),LAST(W)=,S,W,S,S(V,N,UV,T,),+,+,6.2.4,简单优先文法的分析方法：,(1),简单优先文法的定义：,定义：满足下面两个条件的文法称为简单优先文法：,(1),任意两个符号至多成立一种优先关系。,(2),任意两个产生式具有不同右部。,为了处理方便，引进特殊符号,#,，并定义,#S,，,S#(SV,N,UV,T,),(2),简单优先文法的句柄,这个定理给我们提供确定句柄的一种方法。,简单优先文法分析算法的主要思想是找出句柄并归纳之。,而给定一个句型,X,，寻找它的句柄是这样进行的：从左向右进行扫描，每次只查看两个相邻的文法符号，并由此得知什么时候查到句柄的尾,S,j,，,然后再返过头来向句型左端进行加工，仍然只查看相邻的两个运算符，找出句柄的头,S,i,。此时就可以进行归约了。,定理：设,S,1,S,2,S,n,是简单优先文法的规范句型，其子串,S,i,S,i+1,S,j,是满足下列条件的最左子串：,则,S,i,S,i+1,S,j,定是,S,1,S,2,S,n,的句柄,。,证明：略,。,S,i-1,S,i,S,i,S,i+1,S,i+2,=S,j,S,j,S,j+1,(3),分析算法的要点：,STEP 3:,用,S,i,S,i+1,S,j,去查产生式表的右部，并用相应的左,部符号代替,(,归约,),句柄,S,i,S,j,，,若查不到，则为出错,。,STEP 4,：重复上述过程，直至归约完为止。,STEP 2,：从,S,j,开始往回,(,左,),找第一个使,S,i-1,S,i,的,S,i,STEP 1,：找出第一个使,S,j,S,j+1,的,S,j,(4),语法分析程序：,首先设置保存句型前端的,S,栈和输入串后端的,T,队列；,然后用,S,j,1,S,j,1,+1,S,i,去查生产式表，,若查到有相同右部的产生式即,U,S,j,1,S,j,1,+1,S,i,则从栈中退掉子串,S,j,1,S,j,1,+1,S,i,，,并把,U,进栈；然后转,(2),。,若查不到转出错处理