最新【考研计算机专业课】天津大学 编译原理讲义 自下而上3.5-3.6(共45张PPT课件).pptx

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

1、一一. . 句型的语法句型的语法(yf)(yf)树和文法的二义性树和文法的二义性 1. 语法语法(yf)(yf)树树 语法树语法树是一棵树，这棵树表示一个是一棵树，这棵树表示一个(y )(y )句型的推导过程。句型的推导过程。 句型句型E+F* *i对应的语法树，对应的语法树，如右图所示如右图所示: : EET+TF*Fi例例，文法，文法G的产生式的产生式: EE+TTTT* *FFF(E)i 3.5 自下而上分析自下而上分析第一页，共四十五页。由图不难看出由图不难看出: : F是句型是句型E+F* *i相对于相对于T的的直接短语直接短语；i是句型是句型E+F* *i相对于相对于F的的直直接短

2、语接短语；F* *i是句型是句型E+F* *i相对于相对于T的的短语短语；E+F* *i是是句型句型E+F* *i相对于相对于E的的短语短语。F是是句柄句柄。 EET+TF*Fi第二页，共四十五页。2. 文法文法(wnf)(wnf)的二义性的二义性 若一个文法存在某个若一个文法存在某个(mu )句型对应两棵不同的语法树，则称句型对应两棵不同的语法树，则称此文法是此文法是二义性文法二义性文法。 例例，文法，文法(wnf)G: EE+EE*E(E)i 句型句型E*E+i 对应的两棵语法树对应的两棵语法树 EEE*EE+iEEE+EE*iG虽是二义性文法，但虽是二义性文法，但L( (G) )不是二义

3、性语言。不是二义性语言。 第三页，共四十五页。定理定理: : 若文法是非若文法是非(shfi)(shfi)二义的，则此文法的规范推导句二义的，则此文法的规范推导句型的句柄是唯一的。型的句柄是唯一的。 1. 给定一非二义性文法给定一非二义性文法G=(VN,VT,P,S)，且任意给一符号串，且任意给一符号串VT*，若，若L( (G) )，则，则按规范归约按规范归约(句柄是唯一句柄是唯一(wi y)(wi y)的的)一定能归约成开始符一定能归约成开始符S；否则，一定失败。；否则，一定失败。 2. 给定文法给定文法G，可用规范归约识别，可用规范归约识别(shbi)(shbi)文法文法G的句子。的句子。

4、 例例，文法，文法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. 规范规范(gufn)(gufn)规约算法规约算法 ( “移进移进- -规约规约”分析法分析法) 符号栈符号栈SK，存放存放(cnfng)(cnfng)句型的前缀句型的前缀, ,初始初始S1=1=#；输入缓冲区输入缓冲区R，存放，存放(cnfng)要识别的符号串，初

5、始为要识别的符号串，初始为i+i*i#。工具工具:从输入串中读出的符号存在从输入串中读出的符号存在单元单元a中，每读一次符号，指针中，每读一次符号，指针下推一个符号位置。下推一个符号位置。 第五页，共四十五页。算法算法(sun f)(sun f): 1. . 置初值置初值 a=“”“”； k=1； Sk=“#”； 2. . 从从R中读下一个中读下一个(y )(y )符号存放入符号存放入a a； 3. . 若若Sk的内容的内容(nirng)(nirng)=“#E”a”a=“#”，则，则归约成功归约成功，结，结束；否则，执行束；否则，执行4； 4. . Sk栈顶部分是否为当前句型的栈顶部分是否为当

6、前句型的句柄？句柄？是则执行是则执行5；否则，；否则，执行执行6； 5. . Sk栈顶部分一定可用某个产生式左部替换。例如，栈顶部分一定可用某个产生式左部替换。例如，Sk栈顶的符号栈顶的符号X1Xn是句柄，且有产生式是句柄，且有产生式AX1Xn则则X1Xn出栈，出栈，K=K-n+1，A进进Sk栈。转栈。转3； 6. . K=K+1；a a中符号移进中符号移进Sk栈，转栈，转2； 例例，i+i* *i 的规约过程如下的规约过程如下:第六页，共四十五页。SK栈栈输入串输入串动作动作#i+i* *i# 移进移进#i+i* *i# 规约，规约，Fi#F+i* *i# 规约，规约，TF#T+i* *i#

7、 规约，规约，ET#E+i* *i# 移进移进#E+i* *i# 移进移进#E+i* *i# 规约，规约，Fi#E+F* *i# 规约，规约，TF#E+T* *i# 移进移进#E+T* *i# 移进移进#E+T* *i# 规约，规约，Fi#E+T* *F# 规约，规约，TT* *F#E+T# 规约，规约，EE+T#E#空空 成功！成功！第七页，共四十五页。 3.6算符优先算符优先(yuxin)(yuxin)分析算法分析算法算符优先分析法是算符优先分析法是自下向上自下向上分析方法中的一种，特别分析方法中的一种，特别(tbi)适合表达式适合表达式的分析，也宜于手工实现。的分析，也宜于手工实现。在算

8、术表达式的运算过程在算术表达式的运算过程(guchng)中，为了确保计算过程中，为了确保计算过程(guchng)和结果的和结果的唯一性，规定了四则运算法则，实际上就是规定了运算之间的优先顺序和唯一性，规定了四则运算法则，实际上就是规定了运算之间的优先顺序和结合性质。第一，运算分为两级，乘除为一级，加减为另一级，乘除结合性质。第一，运算分为两级，乘除为一级，加减为另一级，乘除优先优先于于加减。第二，同级运算服从加减。第二，同级运算服从左结合左结合。所谓算符优先分析法就是仿照上述算术四则运算的运算过程，而设计的所谓算符优先分析法就是仿照上述算术四则运算的运算过程，而设计的一种语法分析方法。它首先要

9、规定运算符之间的一种语法分析方法。它首先要规定运算符之间的优先关系优先关系，然后利用这，然后利用这种关系确定句型的种关系确定句型的“句柄句柄”，进行归约。，进行归约。第八页，共四十五页。例例，有文法，有文法(wnf)GE: EE+E| |E- -E| |E* *E| |E/E| |(E)| |i 并有输入串并有输入串 i+i- -i* *(i+i)这个文法是一个二义性这个文法是一个二义性文法，因此有几种不同文法，因此有几种不同的规范规约，但若定义的规范规约，但若定义了了算符优先顺序算符优先顺序(shnx)和和结合规则结合规则，归约过程，归约过程就唯一了。就唯一了。1i i+i-i+i-i* *

10、(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-EE-E* *( (i i+i)+i)7E-EE-E* *( (E+EE+E) )8E-EE-E* *(E)(E)9E-E-E E* *E E10E-EE-E11E EE-EE-E* *(E+(E+i i) )6算符优先分析的规算符优先分析的规约过程不是一种规约过程不是一种规范规约。范规约。第九页，共四十五页。4.1.1 直观直观(zhgun)的算符优先分析法的算符优先分析法从上面的例子可以看到，算符优先分析法的关键就是要定义任意

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

12、ab .ab但但 .- -+ .+ +- -与数学中的与数学中的含义不同，如含义不同，如:同样同样:，不一定有，不一定有:. .ab. .ab() 但却没有但却没有 )(. . .第十一页，共四十五页。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .(3)若若 a，则根据，则根据EE1 E2进行归约，其中进行归约，其中E2和和E1分别代分别代表表OPND的次栈顶和栈顶，从的次栈顶和栈顶，从OPND中弹出中弹出E2和和E1，并将结，并将结果果E压入压入OPND中，同时中，同时OPTR栈顶栈顶 弹出，重新执行弹

13、出，重新执行(3)。(5)若若 . .a, 则则a入算符栈，成为算符栈新栈顶，转入算符栈，成为算符栈新栈顶，转(1)；(6)若若 与与a不存在不存在(cnzi)优先关系，报告出错。优先关系，报告出错。(4)若若 . .a, 这只有两种可能这只有两种可能: 其一，其一， = ( 而而 a = )，逐，逐出出OPTR顶的顶的(，放弃，放弃a中的中的)，转，转(1)；其二，；其二， = a =#，分析过程，分析过程成功成功。(1)当前输入当前输入(shr)符号送符号送a；(2)若若a为基本为基本(jbn)运算数运算数i, 则送则送OPND并转并转(1);算法描述如下算法描述如下:第十四页，共四十五页

14、。序号序号OPNDOPTR优先关系优先关系a单元单元输入串输入串0#i+i* *i#1#i+i* *i#3i#+i* *i#5i i#+*i#i* *i#+#i2 . .i#*#+i i4 . .#e8. 例例，试用上述，试用上述(shngsh)算法分析表达式算法分析表达式i+i* *i，即分析，即分析#i+i* *i#t=it=i* *i ie=i+te=i+t =a=#=a=# 第十五页，共四十五页。4. 直观算符优先分析的缺陷直观算符优先分析的缺陷算法可能产生离奇的结果。算法可能产生离奇的结果。i i+i*+i( )这种缺陷表明这种缺陷表明(biomng)，算符优先分析方法不能准确的，算

15、符优先分析方法不能准确的指出输入串出错的位置。指出输入串出错的位置。算符优先算符优先(yuxin)分析方法简单明了，易于实现。分析方法简单明了，易于实现。第十六页，共四十五页。3.6.1 直观直观(zhgun)的算符优先分析法的算符优先分析法在文法的基础上定义了算符的优先关系和结合规则，实在文法的基础上定义了算符的优先关系和结合规则，实现现(shxin)规约的唯一性。规约的唯一性。是对算术表达式计算过程的一种是对算术表达式计算过程的一种(y zhn)模拟。模拟。例例，有文法，有文法GE: EE+E EE- -E EE* *EE(E)| |i 输入串输入串 i+i- -i* *i1# #i i+

16、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 算符优先算符优先(yuxin)(yuxin)分析法分析法1、算符优先文法、算符优先文法(wnf)的定义的定义算符文法算符文法: 任给一上下文无关任给一上下文无关(wgun)文法文法G，若，若G的任何产的任何产生式右部都不含两个相继的非终极符，则称文法生式右部都不含两个相继的非终极符，则称文法G为算符为算符文法。文法。例例，文法，文

17、法G: SUV Ua Vb就不是算符文法。就不是算符文法。 第十八页，共四十五页。算符优先关系算符优先关系: 设设G是一个算符文法，是一个算符文法，a，b VT， A、R、Q VN，则，则a，b优先关系定义优先关系定义(dngy)如下如下:ab .ba(1)，当且仅当，当且仅当G中含有产生式中含有产生式: Aab，或，或AaQb；. .ab 第十九页，共四十五页。算符优先文法算符优先文法: 如果一个如果一个算符文法算符文法G不含空产生式，且不含空产生式，且G中的任中的任意终极符对意终极符对(a，b)至多至多满足下列满足下列(xili)算符优先关系之一算符优先关系之一: . . . .a ba

18、b则称则称G为算符优先为算符优先(yuxin)文法。文法。. .ab总控程序总控程序算符优先算符优先关系表关系表栈栈中心问题中心问题: 算符优先关系表的构造。算符优先关系表的构造。第二十页，共四十五页。(1) 定义两个定义两个(lin )重要集合重要集合: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) 传递定义传递定义: 若有产生式若有产

19、生式UV，且，且b FIRSTVT(V)，则则 b FIRSTVT(U)2、算符优先、算符优先(yuxin)关系表的构造关系表的构造若存在若存在 AaU，就可以确定就可以确定a b，b FIRSTVT(U) . .第二十一页，共四十五页。现将算符文法的非终极符给出一种排序现将算符文法的非终极符给出一种排序A1，Am；终极符给出一种；终极符给出一种排序排序a1，a an n；而；而aj( (j=1，n)FIRSTVT(n)FIRSTVT(Ai i) () (i=1，m)m)可用可用布尔矩阵表示布尔矩阵表示(biosh)(biosh)，布尔矩阵的格式如下表所示，布尔矩阵的格式如下表所示 ，若，若a

20、jFIRSTVT(FIRSTVT(Ai i) )则布尔矩阵的元素则布尔矩阵的元素MAi，aj“”； a1a2.anA1 Y Y. YA2 Y. . .Y Am (3) FIRSTVT(Ai i)的矩阵的矩阵(j zhn)(j zhn)第二十二页，共四十五页。FIRSTVT(Ai i)的矩阵的矩阵(j zhn)(j zhn)构造算法构造算法: : i 对所有的对所有的Ai （i=1，m），若有产生式），若有产生式Ai aj 或或 AiAkaj ,1i,km, 1jn则置则置MAi ，aj=“Y”，且将符号对（且将符号对（Ai ，aj）推进）推进S栈。栈。将将S栈顶符号对栈顶符号对(Ai ，aj)

21、 逐出，由符号对逐出，由符号对(Ai ，aj)检查产检查产生式集合，看是否有形如生式集合，看是否有形如 AKAi的产生式，若有，的产生式，若有，且且MAK ，aj“Y”，则置，则置MAK ，aj=“Y”，将符号，将符号对对(Ak ，aj)推进推进S栈。栈。ii repeatuntil S栈栈=空空第二十三页，共四十五页。例例，对于，对于(duy)文法文法构造构造FIRSTVT(Ai)的布尔矩阵的布尔矩阵(j zhn)，(Ai取值为取值为: E、T、F)，如下表所示。如下表所示。EE+T | | TTT*F | | FF(E) | | i +*i()EYY YY T YYY F YY 第二十四页

22、，共四十五页。解解: 因为非终极符因为非终极符E、T、F有如下有如下(rxi)产生式产生式: EE+T EE+ TT*F TT* F(E)| |i F( | |i 所以，需要在表中置初值：所以，需要在表中置初值： ME，+=MT，*=MF，(=MF，i=“Y” 又因为又因为(yn wi)有产生式有产生式 TF ET所以，需在表中填写：所以，需在表中填写： ME，i=ME，(=ME，*=MT，i=MT，(=“Y” 第二十五页，共四十五页。现将算符文法现将算符文法(wnf)(wnf)的非终极符给出一种排序的非终极符给出一种排序A1，Am；终极符；终极符给出一种排序给出一种排序a1，a an n；而

23、；而aj( (j=1，n)LASTVT(n)LASTVT(Ai i) ) ( (i=1，m)m)可用布尔矩阵表示，布尔矩阵的格式如下表所示可用布尔矩阵表示，布尔矩阵的格式如下表所示 ，若若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)的矩阵构造的矩阵构造(guzo

24、)(guzo)算法算法: : i 对所有的对所有的Ai （i=1，m），若有产生式），若有产生式Ai aj 或或 AiajAk ,1i,km, 1jn则置则置MAi ，aj=“Y”，且将符号对（且将符号对（Ai ，aj）推进）推进S栈。栈。将将S栈顶符号对栈顶符号对(Ai ，aj) 逐出，由符号对逐出，由符号对(Ai ，aj)检查产检查产生式集合，看是否是形如生式集合，看是否是形如 AKAi 的产生式，若有，的产生式，若有，且且MAK ，aj“Y”，则置，则置MAK ，aj=“Y”，将符号，将符号对对(Ak ，aj)推进推进S栈。栈。ii repeatuntil S栈栈=空空第二十七页，共四十

25、五页。例例，对于，对于(duy)文法文法构造构造(guzo)LASTVT(Ai)的布尔矩阵，的布尔矩阵，(Ai取值为取值为: E、T、F)，如下表所示。如下表所示。EE+T | | TTT*F | | FF(E) | | i +*i()EYY Y YT YY YF Y Y 第二十八页，共四十五页。解解: 因为非终极符因为非终极符E、T、F有如下有如下(rxi)产生式产生式: EE+T E+T TT*F T*F F(E)| |i F)| |i 所以，需要在表中置初值：所以，需要在表中置初值： ME，+=MT，*=MF，)=MF，i=“Y” 又因为有产生式又因为有产生式 ET TF所以所以(suy

26、)，需在表中填写：，需在表中填写： ME，i=ME，)=ME，*=MT，i=MT，)=“Y” 第二十九页，共四十五页。(5)(5) 构造算符优先关系构造算符优先关系(gun x)(gun x)表的算法表的算法: : 文法文法G，设每个非终极符，设每个非终极符P 的的FIRSTVT( (P) )和和LASTVT( (P) )已求出，已求出，则构造算符优先则构造算符优先(yuxin)(yuxin)关系表的算法如下所示。关系表的算法如下所示。 for ( G的每个产生式的每个产生式PX1X2Xn ) for ( i=1；i=n-1；i+ ) if ( Xi ,Xi+1VT ) 置置XiXi+1； i

27、f ( 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 ( a LASTVT(Xi) 的每个的每个a ) 置置aXi+1 ； . . .第三十页，共四十五页。例例，有文法，有文法(wnf)GE: EE+T| |T，TT*F| |F，F(E)| |i 则优先则优先(yuxin)关系表为：关系表为：#)(i *+#)(i*+. .= = . . . . . . . . . . . . . . . . .

28、 . . . . . . . . . . . . . . . . . . . . . . .= =第三十一页，共四十五页。4、最左素短语、最左素短语(duny)素短语素短语: 若一个文法的句型的若一个文法的句型的短语短语称为素短语，则此短语称为素短语，则此短语至少包含有一至少包含有一个终结符号个终结符号(fho)，并且，并且除它自身之外，不再包含其它更小的素短除它自身之外，不再包含其它更小的素短语语。例例，设有文法，设有文法GE: EE+T| |TTT*F| |FF(E) | | i 的句型的句型(j xn)为为T+T*F+i,要求找出其要求找出其素短语。素短语。句型对应的语法树为句型对应的语

29、法树为:T是句柄，但不是是句柄，但不是素短语素短语最左素短语是当前最左素短语是当前归约的对象归约的对象EE+TE+TT*FTFi 第三十二页，共四十五页。句型句型(j xn)的短语有的短语有:其中其中(qzhng)素短语素短语有有:T*F, i最左素短语最左素短语(duny): 任意句型最左边的素短语。任意句型最左边的素短语。T*F是句型是句型T+T*F+i最左素短语。最左素短语。T(E), T*F(T), i(F), T+T*F(E), T+T*F+i(E)EE+TE+TT*FTFi第三十三页，共四十五页。算符优先文法的句型的最左素短语的判定算符优先文法的句型的最左素短语的判定(pndng)

30、定理定理:(1) 算符文法算符文法(wnf)句型的一般形式句型的一般形式:#N1a1N2a2NnanNn+1# 其中其中(qzhng)，Ni VN, ai VT由由n个终结符号组成，而每个相个终结符号组成，而每个相邻的终结符号之间至多有一个非邻的终结符号之间至多有一个非终结符。终结符。(2) 最左素短语是满足下列条件的最左子串最左素短语是满足下列条件的最左子串:NjajNj+1aj+1NiaiNi+1其中优先关系为其中优先关系为: . .ai ai+1aj aj+1 ai ，. . . .给出了根据句型之间的终结符号给出了根据句型之间的终结符号的优先关系判断最左素短语的方的优先关系判断最左素短

31、语的方法。法。 第三十四页，共四十五页。例例，有文法，有文法(wnf)GE: EE+T | |TTT*F | | FF(E) | | i 已知优先已知优先(yuxin)关系矩阵为：关系矩阵为：= =#)(i *+#)(i*+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .= = . . . . . . . . . . .第三十五页，共四十五页。步骤步骤句型句型优先关系优先关系最左素最左素短语短语归约归约符号符号5#E#确认！确认！TT*F#T+T*F+i#1# + * + i # . . . . . . . .ET

32、+T#T+T+i#2# + + i # . . . . . .Fi#E+i#3# + i # . . . .EE+F#E+F#4# + # . .要求用归约当前最左素短语要求用归约当前最左素短语(duny)的方法分析句型的方法分析句型T+T*F+i:可见可见(kjin)，素短语可，素短语可以通过终结符号的优以通过终结符号的优先关系确认。先关系确认。 第三十六页，共四十五页。5、算符优先分析、算符优先分析(fnx)算算法法K=1; SK=”#”;do 将输入串的下一个符号读进将输入串的下一个符号读进a中中;if ( SKVT ) j=K; else j=K-;while ( Sja ) do Q

33、=Sj;if ( Sj-1 VT ) j-; else j- -=2; while ( ! (Sj Q) );将将Sj+1SK归约成某个归约成某个P(PVN);K=j+;SK=P; if ( Sja ) | ( Sja ) K+; SK=a; else error() ； while (!awhile (!a# ) . . . .= g( 2) . .f称为称为(chn wi)入栈优先函数入栈优先函数(左左)，g称为比较优先函数称为比较优先函数(右右)。 若若 1 . . 2 则则f( 1)(2n-1)(2n-1)，则过程收敛，其中，则过程收敛，其中，n n是集是集合合(jh)(jh)VT#中

34、元素的个数。中元素的个数。 (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)= )= maxmaxf(f(1 1),g(),g(2 2) )； =. .第四十页，共四十五页。116642g151553f#)(i*+其优先函数为其优先函

35、数为:#)(i *+#)(i*+例例:根据以上原则，根据以上原则，文法文法 GE: EE+E| |E*E| |(E)| |i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .= =. .= =第四十一页，共四十五页。优先关系优先关系(gun x)矩阵已知为矩阵已知为:(0)+*()i#f111111g111111迭代迭代(di di)过程过程:+*()i#fg(1)+*()i#f241441g235151(2)+*()i#f351551g246161收敛收敛(shulin)！例例，为文法，为文法GE:

36、 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) 矛盾矛盾所以构造优先函数表不会收敛。所以构造优先函数表不会收敛。第四十四页，共四十五页。内容(nirng)总结一. 句型(j xn)的语法树和文法的二义性。由图不难看出: F是句型(j xn)E+F*i相对于T的直接短语。若一个文法存在某个句型(j xn)对应两棵不同的语法树，则称此文法是二义性文法。G虽是二义性文法，但L(G)不是二义性语言。2. 给定文法G，可用规范归约识别文法G的句子。规范归约是上述规范推导的逆过程。6. K=K+1。所谓算符优先分析法就是仿照上述算术四则运算的运算过程，而设计的一种语法分析方法。算符优先分析的规约过程不是一种规范规约第四十五页，共四十五页。