【精品】【考研计算机专业课】天津大学 编译原理讲义 自下而上3.5-3.6（可编辑.ppt

《【精品】【考研计算机专业课】天津大学 编译原理讲义 自下而上3.5-3.6（可编辑.ppt》由会员分享，可在线阅读，更多相关《【精品】【考研计算机专业课】天津大学 编译原理讲义 自下而上3.5-3.6（可编辑.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【考研计算机专业课】天津大学 编译原理讲义 自下而上3.5-3.6由图不难看出由图不难看出:F是句型是句型E+F*i相对于相对于T的的直接短语直接短语；i是句型是句型E+F*i相对于相对于F的的直直接短语接短语；F*i是句型是句型E+F*i相对于相对于T的的短语短语；E+F*i是是句型句型E+F*i相对于相对于E的的短语短语。F是是句柄句柄。EET+TF*Fi2.文法的二义性文法的二义性若一个文法存在某个句型对应两棵不同的语法树，则若一个文法存在某个句型对应两棵不同的语法树，则称此文法是称此文法是二义性文法二义性文法。例例，文法，文法G:EE+EE*E(E)i句型句型E*E+i对应的两棵语法树

2、对应的两棵语法树EEE*EE+iEEE+EE*iG虽是二义性文法，但虽是二义性文法，但L(G)不是二义性语言。不是二义性语言。定理定理:若文法是非二义的，则此文法的规范推导句型的若文法是非二义的，则此文法的规范推导句型的句柄是唯一的。句柄是唯一的。1.给定一非二义性文法给定一非二义性文法G=(VN,VT,P,S)，且任意给一符号串，且任意给一符号串VT*，若，若L(G)，则，则按规范归约按规范归约(句柄是唯一的句柄是唯一的)一一定能归约成开始符定能归约成开始符S；否则，一定失败。；否则，一定失败。2.给定文法给定文法G，可用规范归约识别文法，可用规范归约识别文法G的句子。的句子。例例，文法，文

3、法G:EE+TT，TT*FF，F(E)i句子句子i+i*i的的规范推导规范推导为为:E E+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*i规范归约规范归约是上述是上述规范推导规范推导的逆过程。的逆过程。3.规范规约算法规范规约算法(“移进移进-规约规约”分析法分析法)符号栈符号栈SK，存放句型的前缀存放句型的前缀,初始初始S1=1=#；输入缓冲区输入缓冲区R，存放要识别的符号串，初始为，存放要识别的符号串，初始为i+i*i#。工具工具:从输入串中读出的符号存在从输入串中读出的符号存在单元单元a中，每读一次符中，每读一次符号，指针下推一个符号位置。号，指针

4、下推一个符号位置。3.6算符优先分析算法算符优先分析算法算符优先分析法是算符优先分析法是自下向上自下向上分析方法中的一种，特别适合表分析方法中的一种，特别适合表达式的分析，也宜于手工实现。达式的分析，也宜于手工实现。在算术表达式的运算过程中，为了确保计算过程和结果的唯一在算术表达式的运算过程中，为了确保计算过程和结果的唯一性，规定了四则运算法则，实际上就是规定了运算之间的优先性，规定了四则运算法则，实际上就是规定了运算之间的优先顺序和结合性质。第一，运算分为两级，乘除为一级，加减为顺序和结合性质。第一，运算分为两级，乘除为一级，加减为另一级，乘除另一级，乘除优先于优先于加减。第二，同级运算服从

5、加减。第二，同级运算服从左结合左结合。所谓算符优先分析法就是仿照上述算术四则运算的运算过程，所谓算符优先分析法就是仿照上述算术四则运算的运算过程，而设计的一种语法分析方法。它首先要规定运算符之间的而设计的一种语法分析方法。它首先要规定运算符之间的优优先关系先关系，然后利用这种关系确定句型的，然后利用这种关系确定句型的“句柄句柄”，进行归约。，进行归约。例例，有文法，有文法GE:EE+E|E-E|E*E|E/E|(E)|i并有输入串并有输入串i+i-i*(i+i)这个文法是一个二这个文法是一个二义性文法，因此有义性文法，因此有几种不同的规范规几种不同的规范规约，但若定义了约，但若定义了算算符优先

6、顺序符优先顺序和和结合结合规则规则，归约过程就，归约过程就唯一了。唯一了。1i i+i-i*(i+i)+i-i*(i+i)2E+E+i i-i*(i+i)-i*(i+i)3E+EE+E-i*(i+i)-i*(i+i)4E-E-i i*(i+i)*(i+i)5E-E*(E-E*(i i+i)+i)7E-E*(E-E*(E+EE+E)8E-E*E-E*(E)(E)9E-E-E*EE*E10E-EE-E11E EE-E*(E+E-E*(E+i i)6算符优先分析的规算符优先分析的规约过程不是一种规约过程不是一种规范规约。范规约。4.1.1直观的算符优先分析法直观的算符优先分析法从上面的例子可以看到，

7、算符优先分析法的关键就是要定从上面的例子可以看到，算符优先分析法的关键就是要定义任意两个相继出现的义任意两个相继出现的终结符号终结符号a和和b之间的优先关系之间的优先关系(a与与b之间可有一个非终结符之间可有一个非终结符)，一旦确定了这种优先关系，就可，一旦确定了这种优先关系，就可以用它来确定以用它来确定“句柄句柄”进行归约。进行归约。1.优先关系，终结符之间的优先关系有三种优先关系，终结符之间的优先关系有三种:a的优先级高于的优先级高于b记为记为:.baa的优先级等于的优先级等于b记为记为:.abab.a的优先级低于的优先级低于b记为记为:若有若有:ab .ab但但.-+.+-与数学中的与数

8、学中的含义不同，如含义不同，如:同样同样:，不一定有，不一定有:.ab.ab()但却没有但却没有)(.(3)若若 a，则根据，则根据EE1 E2进行归约，其中进行归约，其中E2和和E1分别代分别代表表OPND的次栈顶和栈顶，从的次栈顶和栈顶，从OPND中弹出中弹出E2和和E1，并将结，并将结果果E压入压入OPND中，同时中，同时OPTR栈顶栈顶 弹出，重新执行弹出，重新执行(3)。(5)若若 .a,则则a入算符栈，成为算符栈新栈顶，转入算符栈，成为算符栈新栈顶，转(1)；(6)若若 与与a不存在优先关系，报告出错。不存在优先关系，报告出错。(4)若若.a,这只有两种可能这只有两种可能:其一，其

9、一，=(而而a=)，逐，逐出出OPTR顶的顶的(，放弃，放弃a中的中的)，转，转(1)；其二，；其二，=a=#，分析过程分析过程成功成功。(1)当前输入符号送当前输入符号送a；(2)若若a为基本运算数为基本运算数i,则送则送OPND并转并转(1);算法描述如下算法描述如下:序号序号OPNDOPTR优先关系优先关系a单元单元输入串输入串0#i+i*i#1#i+i*i#3i#+i*i#5i i#+*i#i*i#+#i2 .i#*#+ii4 .#e8.例例，试用上述算法分析表达式，试用上述算法分析表达式i+i*i，即分析，即分析#i+i*i#t=i*it=i*ie=i+te=i+t=a=#=a=#4

10、.直观算符优先分析的缺陷直观算符优先分析的缺陷算法可能产生离奇的结果。算法可能产生离奇的结果。ii+i*+i()这种缺陷表明，算符优先分析方法不能准确的指出这种缺陷表明，算符优先分析方法不能准确的指出输入串出错的位置。输入串出错的位置。算符优先分析方法简单明了，易于实现。算符优先分析方法简单明了，易于实现。3.6.1直观的算符优先分析法直观的算符优先分析法在文法的基础上定义了算符的优先关系和结合规则，在文法的基础上定义了算符的优先关系和结合规则，实现规约的唯一性。实现规约的唯一性。是对算术表达式计算过程的一种模拟。是对算术表达式计算过程的一种模拟。例例，有文法，有文法GE:EE+EEE-EEE

11、*EE(E)|i输入串输入串i+i-i*i1#i i+i-i+i-i*i#i#2#E+#E+i i-i-i*i#i#3#E+EE+E-i-i*i#i#4#E-#E-i i*i#i#5#E-E#E-E*i i#6#E-#E-E E*E E#7#E-EE-E#8#E#E#3.6.2算符优先分析法算符优先分析法1、算符优先文法的定义、算符优先文法的定义算符文法算符文法:任给一上下文无关文法任给一上下文无关文法G，若，若G的任何产生的任何产生式右部都不含两个相继的非终极符，则称文法式右部都不含两个相继的非终极符，则称文法G为算为算符文法。符文法。例例，文法，文法G:SUVUaVb就不是算符文法。就不是

12、算符文法。算符优先关系算符优先关系:设设G是一个算符文法，是一个算符文法，a，b VT，A、R、Q VN，则，则a，b优先关系定义如下优先关系定义如下:ab .ba(1)，当且仅当，当且仅当G中含有产生式中含有产生式:Aab，或，或AaQb；.ab 算符优先文法算符优先文法:如果一个如果一个算符文法算符文法G不含空产生式，且不含空产生式，且G中的任意终极符对中的任意终极符对(a，b)至多至多满足下列算符优先关系满足下列算符优先关系之一之一:.abab则称则称G为算符优先文法。为算符优先文法。.ab总控程序总控程序算符优先算符优先关系表关系表栈栈中心问题中心问题:算符优先关系表的构造。算符优先关

13、系表的构造。(1)定义两个重要集合定义两个重要集合:FIRSTVT(U)=b|U+b或或U+Vb,b VT,U,V VNLASTVT(U)=a|U+a或或U+aV,a VT,U,V VN(2)求法求法(以以FIRSTVT(U)为例说明为例说明):直观定义直观定义:若有产生式若有产生式Ub或或UVb，U,V VN，则则b FIRSTVT(U)传递定义传递定义:若有产生式若有产生式UV，且且b FIRSTVT(V)，则则b FIRSTVT(U)2、算符优先关系表的构造、算符优先关系表的构造若存在若存在AaU，就可以确定，就可以确定ab，b FIRSTVT(U).现将算符文法的非终极符给出一种排序现

14、将算符文法的非终极符给出一种排序A1，Am；终极符；终极符给出一种排序给出一种排序a1，a an n；而；而aj(j=1，n)FIRSTVT(n)FIRSTVT(Ai i)(i=1，m)m)可用布尔矩阵表示，布尔矩阵的格式如下表所可用布尔矩阵表示，布尔矩阵的格式如下表所示示，若，若ajFIRSTVT(FIRSTVT(Ai i)则布尔矩阵的元素则布尔矩阵的元素MAi，aj“”；a1a2.anA1YY.YA2Y.YAm(3)FIRSTVT(Ai i)的矩阵的矩阵FIRSTVT(Ai i)的矩阵构造算法的矩阵构造算法:i对所有的对所有的Ai（i=1，m），若有产生式），若有产生式Aiaj或或AiAk

15、aj,1i,km,1jn则置则置MAi，aj=“Y”，且将符号对（且将符号对（Ai，aj）推进）推进S栈。栈。将将S栈顶符号对栈顶符号对(Ai，aj)逐出，由符号对逐出，由符号对(Ai，aj)检查产检查产生式集合，看是否有形如生式集合，看是否有形如AKAi的产生式，若有，的产生式，若有，且且MAK，aj“Y”，则置，则置MAK，aj=“Y”，将符号对，将符号对(Ak，aj)推进推进S栈。栈。iirepeatuntilS栈栈=空空例例，对于文法，对于文法构造构造FIRSTVT(Ai)的布尔矩阵，的布尔矩阵，(Ai取值为取值为:E、T、F)，如下表所示。，如下表所示。EE+T|TTT*F|FF(E

16、)|i+*i()EYYYYTYYYFYY解解:因为非终极符因为非终极符E、T、F有如下产生式有如下产生式:EE+TEE+TT*FTT*F(E)|iF(|i所以，需要在表中置初值：所以，需要在表中置初值：ME，+=MT，*=MF，(=MF，i=“Y”又因为有产生式又因为有产生式TFET所以，需在表中填写：所以，需在表中填写：ME，i=ME，(=ME，*=MT，i=MT，(=“Y”现将算符文法的非终极符给出一种排序现将算符文法的非终极符给出一种排序A1，Am；终极符；终极符给出一种排序给出一种排序a1，a an n；而；而aj(j=1，n)LASTVT(n)LASTVT(Ai i)(i=1，m)m

17、)可用布尔矩阵表示，布尔矩阵的格式如下表所可用布尔矩阵表示，布尔矩阵的格式如下表所示示，若，若ajLASTVT(LASTVT(Ai i)则布尔矩阵的元素则布尔矩阵的元素MAi，aj“”；(4)LASTVT(Ai i)直观定义直观定义:若有产生式若有产生式Ub或或UbV，U,V VN，则则b LASTVT(U)传递定义传递定义:若有产生式若有产生式UV，且且b LASTVT(V)，则则b LASTVT(U)LASTVT(Ai i)的矩阵构造算法的矩阵构造算法:i对所有的对所有的Ai（i=1，m），若有产生式），若有产生式Aiaj或或AiajAk,1i,km,1jn则置则置MAi，aj=“Y”，且

18、将符号对（且将符号对（Ai，aj）推进）推进S栈。栈。将将S栈顶符号对栈顶符号对(Ai，aj)逐出，由符号对逐出，由符号对(Ai，aj)检查产检查产生式集合，看是否是形如生式集合，看是否是形如AKAi的产生式，若有，的产生式，若有，且且MAK，aj“Y”，则置，则置MAK，aj=“Y”，将符号对，将符号对(Ak，aj)推进推进S栈。栈。iirepeatuntilS栈栈=空空例例，对于文法，对于文法构造构造LASTVT(Ai)的布尔矩阵，的布尔矩阵，(Ai取值为取值为:E、T、F)，如下表所示。，如下表所示。EE+T|TTT*F|FF(E)|i+*i()EYYYYTYYYFYY解解:因为非终极符

19、因为非终极符E、T、F有如下产生式有如下产生式:EE+TE+TTT*FT*FF(E)|iF)|i所以，需要在表中置初值：所以，需要在表中置初值：ME，+=MT，*=MF，)=MF，i=“Y”又因为有产生式又因为有产生式ETTF所以，需在表中填写：所以，需在表中填写：ME，i=ME，)=ME，*=MT，i=MT，)=“Y”(5)(5)构造算符优先关系表的算法构造算符优先关系表的算法:文法文法G，设每个非终极符，设每个非终极符P的的FIRSTVT(P)和和LASTVT(P)已已求出，则构造算符优先关系表的算法如下所示。求出，则构造算符优先关系表的算法如下所示。for(G的每个产生式的每个产生式PX

20、1X2Xn)for(i=1；i=n-1；i+)if(Xi,Xi+1VT)置置XiXi+1；if(i=n-2&Xi,Xi+2VT&Xi+1VN)置置XiXi+2；if(XiVT&Xi+1VN)for(bFIRSTVT(Xi+1)的每个的每个b)置置Xib；if(XiVN&Xi+1VT)for(aLASTVT(Xi)的每个的每个a)置置aXi+1；.例例，有文法，有文法GE:EE+T|T，TT*F|F，F(E)|i则优先关系表为：则优先关系表为：#)(i*+#)(i*+.=.=4、最左素短语、最左素短语素短语素短语:若一个文法的句型的若一个文法的句型的短语短语称为素短语，则此短语称为素短语，则此短

21、语至至少包含有一个终结符号少包含有一个终结符号，并且，并且除它自身之外，不再包含其它除它自身之外，不再包含其它更小的素短语更小的素短语。例例，设有文法，设有文法GE:EE+T|TTT*F|FF(E)|i的句型为的句型为T+T*F+i,要求找出其素短语。要求找出其素短语。句型对应的语法树为句型对应的语法树为:T是句柄，但不是句柄，但不是素短语是素短语最左素短语是当前最左素短语是当前归约的对象归约的对象EE+TE+TT*FTFi 句型的短语有句型的短语有:其中素短语有其中素短语有:T*F,i最左素短语最左素短语:任意句型最左边的素短语。任意句型最左边的素短语。T*F是句型是句型T+T*F+i最左素

22、短语。最左素短语。T(E),T*F(T),i(F),T+T*F(E),T+T*F+i(E)EE+TE+TT*FTFi算符优先文法的句型的最左素短语的判定定理算符优先文法的句型的最左素短语的判定定理:(1)算符文法句型的一般形式算符文法句型的一般形式:#N1a1N2a2NnanNn+1#其中，其中，Ni VN,ai VT由由n个终结符号组成，而每个终结符号组成，而每个相邻的终结符号之间至多个相邻的终结符号之间至多有一个非终结符。有一个非终结符。(2)最左素短语是满足下列条件的最左子串最左素短语是满足下列条件的最左子串:NjajNj+1aj+1NiaiNi+1其中优先关系为其中优先关系为:.aia

23、i+1ajaj+1ai，.给出了根据句型之间的终结给出了根据句型之间的终结符号的优先关系判断最左素符号的优先关系判断最左素短语的方法。短语的方法。例例，有文法，有文法GE:EE+T|TTT*F|FF(E)|i已知优先关系矩阵为：已知优先关系矩阵为：=#)(i*+#)(i*+.=.步骤步骤句型句型优先关系优先关系最左素最左素短语短语归约归约符号符号5#E#确认确认！TT*F#T+T*F+i#1#+*+i#.ET+T#T+T+i#2#+i#.Fi#E+i#3#+i#.EE+F#E+F#4#+#.要求用归约当前最左素短语要求用归约当前最左素短语的方法分析句型的方法分析句型T+T*F+i:可见，素短语

24、可以通可见，素短语可以通过终结符号的优先关过终结符号的优先关系确认。系确认。5、算符优先分析算法、算符优先分析算法K=1;SK=”#”;do将输入串的下一个符号读进将输入串的下一个符号读进a中中;if(SKVT)j=K;elsej=K-;while(Sja)doQ=Sj;if(Sj-1VT)j-;elsej-=2;while(!(SjQ);将将Sj+1SK归约成某个归约成某个P(PVN);K=j+;SK=P;if(Sja)|(Sja)K+;SK=a;elseerror()；while(!awhile(!a#).=g(2).f称为入栈优先函数称为入栈优先函数(左左)，g称为比较优先函数称为比较优

25、先函数(右右)。若若 1.2则则f(1)(2n-1)(2n-1)，则过程收敛，其中，则过程收敛，其中，n n是集合是集合VT#中元素的个数。中元素的个数。(2)(2)若若1 12 2，但，但f(f(1 1)g(g(2 2)，则，则f(f(1 1)=g()=g(2 2)+1)+1；.(3)(3)若若1 12 2，但，但f(f(1 1)g(g(2 2)，则，则g(g(2 2)=f()=f(1 1)+1)+1；.(4)(4)若若1 12 2，但，但f(f(1 1)g()g(2 2)，则，则f(f(1 1)=g()=g(2 2)=max)=maxf f(1 1),g(),g(2 2)；=.116642

26、g151553f#)(i*+其优先函数为其优先函数为:#)(i*+#)(i*+例例:根据以上原则，根据以上原则，文法文法GE:EE+E|E*E|(E)|i .=.=优先关系矩阵已知为优先关系矩阵已知为:(0)+*()i#f111111g111111迭代过程迭代过程:+*()i#fg(1)+*()i#f241441g235151(2)+*()i#f351551g246161收敛！收敛！例例，为文法，为文法GE:EE+E|E*E|(E)|i构造算符优先函数。构造算符优先函数。#)(i*+#)(i*+.按照变换规则，有按照变换规则，有f(a)=g(a)f(a)g(b)f(b)=g(a)f(b)=g(b)可推出可推出:f(a)g(a)与与f(a)=g(a)矛盾矛盾所以构造优先函数表不会收敛。所以构造优先函数表不会收敛。