资源描述
*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,6,章 自底向上优先分析法,自底向上分析法的基本思想及主要方法,自底向上分析法也称移进-归约法。,自底向上分析法的基本思想是：,从待输入的符号串开始，利用文法的规则步步向上归约，试图归约到文法的识别符号。,从语法树的角度来看：,自底向上分析的过程是以输入符号串作为末端结点符号串，向着根结点的方向往上构造语法树，使识别符号正好是该语法树的根结点。,自底向上分析法的关键在于：,如何在每一步归约当中，找到当前句型的句柄，并判断句柄是否唯一。,主要的分析方法有：,简单优先分析法、算符优先分析法、,LR,类分析法。,自底向上分析法中面临的问题及解决方法,采用自底向上分析法分析的每一步中，会遇到两个基本问题：,（1）如何找出进行直接归约的简单短语？,（2）找出的简单短语应直接归约到哪一个非终结符号？,解决方法：,由于分析过程是从左往右扫描源程序，所以遇到的第一个简单短语正好是句柄，因此，第一个问题变为：如何找到句柄。对于如何找到句柄，找到句柄后应归约到哪一个非终结符号这两个问题，不同的自底向上分析法有不同的解决方法,。,简单短语：,只经过一次推导得到的短语叫简单短语；,句柄：,句型的最左简单短语。,自底向上分析法的基本实现方法,自底向上分析的基本实现方法是：,移进-归约法。,引入,“,#,”,作为栈底标志符号。,在整个分析过程中，共有4类动作：,（1）移入：,读入下一个输入符号并把它下推进栈。,（2）归约：,当栈顶的（部分）符号串形成一个句柄时，对此句柄进行归约，把形成句柄的符号串替换为相应的非终结符号。,（3）接受：,当识别程序发现栈顶除了栈底标志符号#外仅有识别符号，而输入也以达到右端标志符号#时，便识别出输入符号串是一个句子，执行接受动作并结束本次识别。,（4）报错：,发现输入符号串不是句子而无法继续识别。,自底向上优先分析法的基本思想,常见的自底向上的分析算法：,（1）优先分析法,（2）,LR,类分析法,优先分析法分为：,（1）简单优先分析法,：,采用规范归约，考虑所有文法符号（包括终结符号、非终结符号）之间的优先关系。,（2）算符优先分析法,：,不是规范归约，只考虑算符（即终结符号）之间的优先关系。,自底向上优先分析法的基本思想：,利用文法符号中相邻符号之间的优先关系找出句柄。,简单优先分析法及简单优先文法,简单优先分析法按照文法符号（终结符号和非终结符号）的优先关系确定句柄。,如何确定任意两个文法符号之间的优先关系？,如何构造优先关系表,补充内容,FIRST,关系：,U,FIRST,S,存在规则,U,S,（注：,S,可以是终结符号，也可以是非终结符号。）,FIRST,关系的传递闭包：,FIRST,+,=,FIRST,FIRST,2,FIRST,3,LAST,关系：,U,LAST,S,存在规则,U,S,（注：,S,可以是终结符号，也可以是非终结符号。）,LAST,关系的传递闭包：,LAST,+,=,LAST,LAST,2,LAST,3,例：求文法,G,的,FIRST,关系和,LAST,关系,GA,：,A,Af|B,BDdc|De,Ce,DBf,AAf,AB,BDdc,BDe,Ce,DBf,A FIRST A,A FIRST B,B FIRST D,B FIRST D,C FIRST e,D FIRST B,FIRST=,（,A,，,A,），（,A,，,B,），（,B,，,D,），（,C,，,e,），（,D,，,B,）,A LAST f,A LAST B,B LAST c,B LAST e,C LAST e,D LAST f,LAST=,（,A,，,f,），（,A,，,B,），（,B,，,c,），（,B,，,e,）,，（,C,，,e,），（,D,，,f,）,FIRST=,（,A,，,A,），（,A,，,B,），（,B,，,D,），（,C,，,e,），（,D,，,B,）,FIRST,2,=,（,A,，,A,），（,A,，,B,），（,A,，,D,），（,B,，,B,），（,D,，,D,）,FIRST,3,=,（,A,，,A,），（,A,，,B,），（,A,，,D,），（,B,，,D,），（,D,，,B,）,FIRST,4,=FIRST,2,FIRST,+,=,FIRST,FIRST,2,FIRST,3,=(A,，,A),，,(A,，,B),，,(A,，,D),，,(B,，,D),，,(C,，,e),，,(D,，,B),，,(D,，,D),LAST=(A,，,f),，,(A,，,B),，,(B,，,c),，,(B,，,e),，,(C,，,e),，,(D,，,f),LAST,+,=(A,，,f),，,(A,，,B),，,(A,，,c),，,(A,，,e),，,(B,，,c),，,(B,，,e),，,(C,，,e),，,(D,，,f),优先关系的形式定义：,（1）相等关系,X,=Y：,当且仅当,G,中存在规则,A,XY,（2）,小于关系,X,Y）,（3）,大于关系,X,Y：,当且仅当,G,中存在规则,A,BD，,且,B LAST,+,X（,即,B=X）,和,D FIRST*Y（,即,D=Y）,。在此限定,S,为终结符号。,简单优先文法满足条件：,（1）,在文法符号集,V,中，任意两个符号之间最多只有一种优先关系成立。,（2）,在文法中任意两个产生式没有相同的右部。,由简单优先文法的定义可知，简单优先文法是无二义性的。,+,+,*,构造优先关系,构造相等关系“,=”,很简单，只需要顺次考察文法的各规则即可。如：例,6.2,（,1,）。,构造大于和小于关系，可以使用如下两个公式：,其中，（,FIRST,*,）为,FIRST,的自反传递闭包；,（,LAST,+,）,T,为,LAST,+,的逆关系。,例：构造文法,GZ,的简单优先关系表,GS,：,S,bAb,，,A,（,B|a,，,BAa,）,首先构造相等（,=,）关系。根据文法规则：,=,（,b,，,M,）,（,M,，,b,）,（，,L,），（,A,，,a,）,（,a,，）,构造小于（,）关系：,FIRST=,（,S,，,b,）,（,A,，（）,（,A,，,a,）,（,B,，,A,）,FIRST,+,=,（,S,，,b,）,（,A,，（）,（,A,，,a,）,（,B,，,A,）,（,B,，（）,（,B,，,a,）,）关系：,LAST=,（,S,，,b,）,（,A,，,B,）,（,A,，,a,）,（,B,，）,LAST,+,=,（,S,，,b,）,（,A,，,B,）,（,A,，,a,）,（,A,，）,（,B,，）,（,LAST,+,）,T,=,（,b,，,S,）,（,B,，,A,）,（,a,，,A,）,（），,B,）,（），,A,）,=,（,LAST,+,）,T,（,=,）（,FIRST*,）,=,（,B,，,b,）,（,B,，,a,）,（,a,，,b,）,（,a,，,a,）,（），,b,）,（），,a,）,S,b,A,B,a,（,）,S,b,=,a,=,（,=,文法,GZ,的优先关系矩阵,课堂练习：利用公式求出例,6.2,的三个优先关系，并给出其优先关系矩阵。,简单优先分析法算法,根据给定的简单优先文法构造出相应的简单优先关系表，并将文法的产生式保存，设置符号栈,S，,再根据如下算符步骤进行分析：,（1）,将输入符号串,a,1,a,2,a,n,#,依次逐个存入符号栈,S,中，直到遇到栈顶符号,a,i,的优先性,下一个待输入符号,a,j,时为止。,（2）,栈顶当前符号,ai,尾句柄尾，由此向左在栈中找句柄的头符号,a,k,，,即找到,a,k-1,a,k,，,为止。,（3）,由句柄,a,k,a,i,在文法的产生式中查找右部尾,a,k,a,i,的产生式，若找到则用相应左部代替句柄，若找不到则出错。,（4）,重复上述三个步骤直到规约完输入符号串，栈中只剩文法的开始符号或出错为止。,算符优先分析法,算符优先分析法常用于高级语言的,表达式,的语法分析。,算符优先关系的形式定义：,（1）相等关系,a,=b：,当且仅当,G,中存在,A,ab,或,A,aBb,的规则。,（2）,小于关系,a,b,或,B=Cb,（3）,大于关系,a,b,：,当且仅当,G,中存在规则,A,Bb，,且,B=a,或,B=aC,算符优先分析法的基本思想：,根据算符（广义为终结符号）之间的优先关系来决定如何归约。,+,+,+,+,算符文法及其性质,算符文法的形式定义：,设有一文法,G，,如果,G,中,没有,形如,A,BC,的规则，其中,B,和,C,为非终结符，则称,G,为算符文法，也称,OG,文法。,算符文法的性质：,（1）在算符文法中任何句型都不包含两个相邻的非终结符。,（2）如果,Ab（,或,bA）,出现在算符文法的句型,中，其中,AV,N,，bV,T,，,则中任何含,b,的短语必含有,A。,算符优先文法及其性质,算符优先文法的形式定义：,设有一,不含,产生式,的算符文法,G，,如果对任意两个终结符对,a,b,之间至多只有,=,、,三种关系中的一种成立，则称,G,是一个算符优先文法。也称为,OPG,文法。,算符优先文法的性质：,如果,aNb,或,ab,出现在句型,r,中，则,a,和,b,之间有且仅有一种优先关系即：,（1）若,a,b 则,在,r,中必有含,a,而不含,b,的短语存在,（3）若,a,=,b 则,在,r,中含有,a,的短语必含有,b，,反之亦然。,算符优先关系表的构造,由定义直接构造,（1）,FIRSTVT,集合：,FIRSTVT（B）=b|B=b,或,B=Cb,（2）,LASTVT,集合：,LASTVT（B）=,a|B,=a,或,B=aC,由关系图法构造,（,1）,FIRST,关系：,A FIRST B,当且仅当存在形如,A,B,的产生式。,（2）,LAST,关系：,A LAST B,当且仅当存在形如,A,B,的产生式。,（3）,FIRSTTERM,关系：,B FIRSTTERM b,当且仅当存在形如,B,b,或,B,Cb,的产生式。,（4）,LASTTERM,关系：,B FIRSTTERM a,当且仅当存在形如,B,a,或,B,aC,的产生式。,（5）,FOLLOWEDB,关系：,X FOLLOWEDB Y,当且仅当存在形如,A,XY,的产生式（,X、Y,中必须是一个为终结符，另一个为非终结符）。,用公式法构造,（1）,=（LAST*）,（LASTTERM）,T,（,=）,+,+,+,+,编译方法,中对公式的证明：,注意：此处相等关系的符号为“,”,，与教材采用的符号不同。规则中连接左部与右部的符号也不同，为,EBNF,中的形式。,例：用公式构造文法,GE,的算符优先关系表,课堂练习：求该文法的优先关系“,”,用程序构造算符优先关系的方法和步骤,教材,算符优先分析法与最左素短语,引入最左素短语的目的：,解决在算符优先分析过程中如何寻找句柄的问题。,最左素短语的形式定义：,设有文法,GS，,其句型的素短语是一个短语，该短语至少包含一个终结符，并且除自身外不包含其他素短语，最左边的素短语称最左素短语。由句型的语法图我们可以直接找出所有的素短语和最左素短语。,算符优先分析法的关键问题是,寻找最左素短语,。,算符优先分析法的局限性：,算符优先分析法去掉了单个非终结符之间的归约，使得其在分析过程中很难完全避免把错误的句子得到正确的归约。,算符优先分析法算法,算符优先分析法的算法用到一个符号栈,S,和一个存放输入符号串的数组,R，,算法中的,Q,为一工作单元，用于存放待比较的终结符号：,（1）将输入符串,R,1,R,2,R,K,依次逐个存入符号栈,S,中，直至符号栈顶元素,S,j,与下一个待输入的符号,R,k,有关系,S,j,R,k,为止；,（2）最左素短语尾,S,j,已在符号栈,S,的栈顶，由此往前（左）在栈中找最左素短语的头符号,S,i,，,直至找到第一个,S,i,Q,（,Q=Sj,）为止；,（3）已找到最左素短语,S,
展开阅读全文