自底向上优先分析法.ppt

第6章 自底向上优先分析法,6.1 概 述,对待分析的符号串，自左向右逐个扫描，输入符号栈，一旦栈顶符号串形成某个句型的句柄或可归约串（对应于某产生式的右部），就用该产生式的左部非终结符代替相应右部的文法符号，即归约成识别符号。在分析过程中，每次归约的都是最左边的简单短语（或其它短语）。从语法树的角度，以输入符号为树的末端结点，试图向根结点方向往上构造语法树。,讨论前提,和自顶向下技术同样，不考虑符号的具体构成方式。识别过程是从左到右，自底向上进行的。一般都采用规范归约：每一步都是对句柄进行归约（特例除外）。,基本方法,采用移入-归约方法。使用一个栈来存放归约得到的符号。在分析的过程中，识别程序不断地移入符号。移入的符号暂时存放在一个栈中。一旦在已经移入的（和归约得到的）符号串中包含了一个句柄时，将这个句柄归约成为相应的非终结符号。,参看课本P102例6.1,基本方法（续）,归约中的动作有4类移入：读入一个符号并把它归约入栈。归约：当栈中的部分形成一个句柄（栈顶的符号序列）时，对句柄进行归约。接受：当栈中的符号仅有#和识别符号的时候，输入符号也到达结尾的时候，执行接受动作。错误处理：当识别程序发现输入符号串不是句子时，即出错，调用错误处理模块。,例 子,i*i+i i*i+i i E:=iE*i+iE*i+iE*i+iE*i+iE*i+iE*i+i i E:=iE*E+iE*E+i E*E E:=E*EE+iE+iE+iE+i i E:=iE+EE+EE+E E:=E+EE,文法GEE:E:=E+E|E*E|(E)输入符号串：i*i+i已处理 未处理 句型 句柄 规则,不用此页,例子的解释,当栈中的符号的栈顶部分还不能形成句柄时，进行移入操作。一旦发现栈顶部分形成了句柄的时候，对该句柄进行归约。将句柄出栈，然后将归约得到的非终结符号压栈。如果输入是句子，则栈中的符号（从底到上）和未处理的符号组成句型。在例子中，发现句柄和归约是人为干预的结果。所以移入-归约不是实际可运行的技术，而是技术的模板。,不用此页,基本问题,如何找出进行直接归约的简单短语？即如何知道栈顶符号串已形成了句柄？将找到的简单短语归约到哪个非终结符号？即如何选取适当的产生式进行归约?,6.2 两种优先分析法,简单优先分析法：求出该文法所有符号（终结符和非终结符）之间的优先关系，按照这种关系确定归约过程中的句柄。规范归约。分析准确规范，但效率低，不实用。算符优先分析法：规定算符之间的优先关系，即只考虑终结符之间的优先关系，而不考虑非终结符的优先关系。不是规范归约。分析速度快，适用于表达式的分析。,基本思想,简单优先分析法,思路：每次察看句型中相邻的两个符号。通过两个符号的关系判定出前一个符号是句柄的尾。然后，反向找出句柄的头。这样我们就找到了一个句柄。,优先关系,和书上的写法不一样。等同：Si Sj先于：Si Sj后于：SiSj注意：，和不同于=，和。由SiSj不能导出SjSi。,简单优先分析技术(思路续）,我们要通过两个相邻符号SiSi+1之间的关系来找到句柄：SiSi+1在句柄内：必然有规则U SiSi+1Si在句柄内部，但是Si+1在句柄之后：必然有规则USi，且存在规范句型USi+1。如果Si+1在句柄内，而Si在句柄外，那么必然存在规范句型SiU，且 USi+1。,优先关系的定义,Sj=Si：当且仅当G中有规则 U SjSi Sj Si：当且仅当 U SjV，且+V=Si；Sj Si：当且仅当 U VW，其中V和W分别满足+V=Sj*W=Si 且 Si为终结符号。,优先关系的例子,文法：SbAbA(B|aBAa)语言：bab,b(aa)b,b(aa)a)b,可以从语法树里面导出部分优先关系。,优先矩阵,可以将优先关系填写到一个矩阵，得到优先矩阵。(将矩阵作为关系的表示形式）,=,#b(a a)a)b#,句柄:a 归约为A,#b(A a)a)b#,=,句柄:A a)归约为B,#b(B a)b#,=,句柄:(B 归约为A,识别过程(例子续),#b(B b#,=,句柄:(B 归约为A,#b(A a)b#,=,句柄:Aa)归约为B,#b(A a)b#,=,句柄:Aa)归约为B,#b A b#,=,句柄:bAb 归约为S,#b(B b#,=,句柄:(B 归约为A,优先关系的构造,根据优先关系的构造性的定义（定义6.1），我们立刻可以得到构造算法。(1)=的构造：直接对每个规则右部处理，对所有右部X1X2Xn，都有Xi=Xi+1。,Sj,Si,=,当且仅当G中有规则 U SjSi,（2）的构造：由定义，Sj Si 可以得到存在规则U SjV，也就是Sj=V,+HEAD(V)Sk|V=Sk Si1,Si2,Sin。,Sj,Si1 Si2 Sin,（3）关系的构造：由定义，Sj Si 表示:存在规则 U VW 其中V=W+TAIL(V)Sl|V=Sl Sj1,Sj2,Sjm。+HEAD(W)Sk|W=Sk Si1,Si2,Sin。,Sj1,Si1 Si2 Sin,Sj2,Sjm,=,简单优先关系矩阵（表）,文法：SbAbA(B|aBAa)HEAD(A)=(a HEAD(B)=(a A TAIL(A)=a)B,优先关系的冲突,当优先矩阵中出现值不唯一的元素时，文法不适合使用优先识别技术来识别句型。,简单优先文法,定义6.2 如果某个文法满足：字汇表中的任意两个符号之间至多有一种优先关系成立。任何两个规则式的右部不相同。则称该文法为简单优先文法。第一点保证可以识别出句柄.第二点保证可以确定归约到哪个非终结符号。,定理6.4,一个简单优先文法是无二义性的，且其任何一个句型SmSn的唯一句柄是满足条件：Sj-1 Sj=Sj+1=Sj+2=Si-1=Si Si+1的最左子符号串SjSj+1Sj+2 Si-1Si。,定理6.4的证明,首先用反证法证明任何句型的句柄是唯一的。句型必然有句柄，且这个句柄必然满足Sj-1 Sj=Sj+1=Sj+2=Si-1=Si Si+1(句柄1)如果还有另外一个语法树，那么它对应的归约（称为归约过程2）必然不是把上面的句柄作为一个整体归约的。在归约过程2中，当首次有句柄1(包括Sj-1和Si+1)中间的某个符号St作为句柄（句柄2）的一部分被归约的时候，我们可以考虑以下的情况：（下一页）,定理6.4的证明(续),如果t=j-1，那么,由句柄1，Sj-1 Sj；由句柄2，Sj-1=Sj 或者Sj-1 Sj；矛盾！如果t=i+1，由句柄1，Si Si+1；由句柄2，Si Si+1 或者 Si=Si+1。如果i=t=j；那么Sj在句柄中：Si在句柄中：Sj和Si都不在句柄中：,定理6.4的证明(续),简单优先文法的无二义性是显而易见的：每个句型只有一个句柄。句柄只能归约到确定的非终结符号。该证明的实质就是：句柄1和句柄2相互交错，交错的边缘必然有多重定义的优先关系。,应用优先技术的困难与克服,简单优先技术只适应于简单优先文法。实际上，一般的程序设计语言的文法都不是简单优先文法。比如四则运算表达式的文法。可能的解决办法是：分离法（成层法）,简单优先分析技术的实现,识别过程:从左到右地扫描输入符号。已经扫描或归约得到的符号被存放在一个栈中。每次扫描的时候，将当前符号a和栈顶符号S相比较。如果S a表示已经碰到了一个句柄的尾。然后在栈里面向前（下）找，直到找到句柄的头。此时找到右部为该句柄的规则进行归约。,简单优先分析技术流程图,开始,初始化,R=下一个输入符号,栈顶SiR?,把R入栈,找出栈中第一个满足Sj-1 Sj的值,A,B,否,是,简单优先分析技术流程图(续),A,寻找其右部和句柄匹配的规则,存在这样的规则,是句子？,出错处理,停止,将句柄中的符号退去，将规则的左部入栈。,B,是,是,否,否,例 子,简单优先技术的局限性,文法的适用范围小。虽然使用成层法可以使一些文法变成简单优先文法，但是成层法的技术非常复杂。当两个关系既有又有时，成层法无能为力。如果使用高阶矩阵，将使得算法的内存需求更加大。,6.3 算符优先分析法,简单优先技术对字汇表中的所有符号之间建立优先关系。但是，有些情况下，不需要对所有两个符号之间建立优先关系。算符优先分析技术只在部分符号（终结符）之间建立优先关系。,算符优先分析技术基本思想,对于算术表达式，只需要按照操作符之间的优先关系，就可以确定运算的顺序。不需要考虑操作数就可以对表达式进行分析。例如：E+T*F。只需要知道*的优先级高于+，就可以知道T*F时句柄。在一般的文法中，终结符的地位相当于操作符。,算符文法,定义6.4：如果文法中没有形状如U:=VW 的规则，则该文法称为算符文法。其中，U，V和W均为非终结符。,算符文法的性质,定理6.5 对于算符文法，不存在包含有相邻两个非终结符的句型。定理6.6 如果TU出现在句型中，其中T为终结符，U为非终结符，那么包含T的短语也必然包含U.定理6.7 如果UT出现在句型中，其中T为终结符，U为非终结符，那么包含T的短语也必然包含U.,定理6.5的证明,只需要证明：如果x不包含两个相邻的非终结符，且x=y，那么y也不包含相邻的非终结符。假设x=wUv，而y=wuv。由于x不包含两个相邻的非终结符，那么w和v中没有不相邻的非终结符。根据算符文法的定义，u中也不包含相邻的非终结符。根据假设，w的结尾不是非终结符（否则，x中包含有相邻的非终结符）。同样，v的开始符也不是非终结符。综上所述：y中不存在相邻的非终结符。,定理6.6 和 6.7 的证明,假设w=xvy是文法的句型，而v是相对于V的短语。那么xVy也是句型。如果w中有两个相邻的符号TU，且T在v中，而U不在v中。显然U是y的头符号。因此xVy中存在两个相邻的非终结符VU。和定理6.5矛盾。定理6.7的证明和定理6.6类似。,算符优先关系,定义6.5 设文法G是一个算符文法，Tj和Ti是两个任意的终结符，而U,V,WVN，定义算符优先关系如下：当且仅当文法G中存在以下形式的规则：U:=TjTi 或者 U:=TjVTi：当且仅当文法G中存在形如 U:=TjV 的规则，且V=Ti 或者 V=WTi：当且仅当文法G中存在形如 U:=VTi 的规则，且V=Tj 或者 V=TjW。,+,+,+,+,算符优先关系的直观意义,算符优先分析技术的基本思想是通过终结符之间的优先关系，确定句型的句柄。对于句型 N1T1Ni-1Ti-1NiTiNjTjNj+1Tj+1NkTkNk+1满足关系Ti-1Ti Ti+1 TjTj+1的最左子符号串就是要被归约的短语。,优先关系例子,文法：Z:=EE:=T|E+TT:=F|T*FF:=(E)|i等同关系：（）只有左、右括号1对由推导ZEE+TE+FE+iZEE+TE+T*FE+T*(E)E+T*(E+T)ZEE+TE+T+TE+T+FE+T+(E)得到以下关系：+i，+*，*(，(+，+)，+，+(等,优先关系的构造,优先关系的构造，只需要按照定义，枚举各个规则的右部就可以得到。对于关系和的构造，我们需要引入两个辅助的关系：FIRSTTERM和LASTTERM。U FIRSTTERM T 当且仅当存在规则U:=T 或者 U:=VTU LASTTERM T 当且仅当存在规则U:=T 或者 U:=TV,FIRSTTERM+关系的构造,FIRSTTERM+并不是FIRSTTERM的传递闭包。U FIRSTTERM+T 表示T是U经过若干步推导得到的字的首终结符。构造算法如下：步骤1：如果 U FIRSTTERM T，那么 U FIRSTTERM+T.步骤2：如果U:=V，且V FIRSTTERM+T，那么U FIRSTTERM+T。步骤3：重复步骤2，直到过程收敛。,LASTTERM+的构造算法,LASTTERM+不是LASTTERM的传递闭包。U LASTTERM+S 表示U经过若干步推导得到的字的尾终结符为S。构造算法为：步骤1：如果 U LASTTERM T，那么 U LASTTERM+T。步骤2：如果 U:=V，且 V LASTTERM+T，那么 U LASTTERM+T。步骤3：重复步骤2，直到收敛。,关系和的构造,关系的构造：=()(HEAD*)(FIRSTTERM)=()(FIRSTTERM+)=(TAIL*)(LASTTERM)T()=(LASTTERM+)T(),算符优先文法,定义6.6：设有算符文法G，如果在其任意两个终结符之间，算符优先关系最多只有一种关系成立，那么该文法G称为算符优先文法。,算符优先文法句型的识别,由于算符优先分析技术在分析的过程中，非终结符是“不可见”的。因此，对于单规则，算符优先技术无法处理。定义6.7 素短语是满足下面条件的短语：（1）至少包含一个终结符号。（2）该短语不再包含满足第一个条件的 更小的短语。,素短语的例子,短语有T+T*F+i，T+T*F，T*F，最左边的T，i。其中，素短语为T*F，i。T+T*F+i，T+T*F不是素短语，因为其中包含了T*F。T不是素短语，因为其中不含终结符。,定理6.8,定理6.8：句型 N1T1Ni-1Ti-1NiTiNjTjNj+1Tj+1NkTkNk+1中满足关系Ti-1Ti Ti+1 TjTj+1的最左子符号串NiTi NjTjNj+1就是句型的最左素短语。,句型识别过程,识别得到的语法树,算符优先技术的说明,在算符优先技术的应用中，分析过程并不考虑非终结符。可以认为：编译程序不考虑具体符号的名字，只考虑它的意义。需要有处理素短语的语义处理子程序。在使用算符优先技术的过程中，我们可以使用同一个符号N来表示归约得到的非终结符，分析过程照样可以进行。,识别算法流程图,开始,i=1;Si=#,R=Next Symbol,SiVT或Si=#,j=i-1,j=i,SjR,否,i=i+1;Si=R,A,N,Y,Y,识别算法流程图(续),A,Q=Sj;j=j-1,SjVT,j=i-1,SjQ,调用语义处理子程序,判断是否素短语?,出错处理,归约,归约已经完成?,N,N,Y,Y,N,语义处理子程序,语义处理子程序需要根据栈里面的符号（和其它信息）分析是否是一个素短语。建议归约的时候，遵照以下法则：对于素短语w=Ni-1TiNiTi+1TjNj+1归约到如下的非终结符V：V u w且在u到w的推导过程中，只用到了形如U:=W的单规则。U，W为非终结符。,+,实际应用的算符优先分析技术,可以使用优先函数来替代优先矩阵。优先函数的求解方法等同于简单优先矩阵的算法。（前面的算法不考虑优先关系的种类）可以使用两个栈：运算符栈，运算分量栈。运算分量（非终结符号）和运算符（终结符号）将分别存放在两个栈中。,算符优先文法的范围,可以被用来处理各种表达式。如果把各个关键字看作算符，这个技术也可以被使用来处理程序设计语言。对于实际使用的程序设计语言，只需要对文法稍微修改就可以应用算符优先分析技术。对于有些情况，比如表达式，我们可以使用单优先函数来解决。实际上即f(S)=g(S),两种优先技术的比较,