《自底向上优先分析法精品文稿.ppt》由会员分享，可在线阅读，更多相关《自底向上优先分析法精品文稿.ppt（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、自底向上优先分析法自底向上优先分析法第1页，本讲稿共54页第第06章章自底向上优先分析法自底向上优先分析法v自底向上优先分析概述v简单优先分析法v算符优先分析法第2页，本讲稿共54页自底向上分析方法概述自底向上分析方法概述v自底向上分析方法，也称自底向上分析方法，也称移进移进-归约归约分析法。分析法。v实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。v重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。v示例第3页
2、，本讲稿共54页abb c de步骤符号栈输入符号串动作1）#abbcde#移进2）#abbcde#移进A3）#abbcde#归约(Ab)4）#aAbcde#移进A5）#aAbcde#归约(AAb)6）#aAcde#移进7）#aAcde#移进B8）#aAcd e#归约(Bd)9）#aAcBe#移进11）#S#接受S10）#aAcBe#归约(SaAcBe)分析符号串abbcde是否GS的句子对输入串abbcde#的移进-规约分析过程SaAcBe aAcde aAbcde abbcde最右推导：最右推导：示例示例文法GS：(1)SaAcBe(2)Ab(3)AAb(4)Bd第4页，本讲稿共54页简单
3、优先分析法简单优先分析法v按照文法符号（包括终结符和非终结符）的优先关系确定句柄。v定义优先关系简单优先文法v优先关系矩阵：表示文法符号之间关系的矩阵。v算法v示例第5页，本讲稿共54页v优先关系X Y：表示X、Y的优先关系相同，当且仅当文法G中存在产生式A.XY；XY：表示X的优先性比Y的要低，当且仅当文法G中存在产生式A.XB.，且BY.XY：表示X的优先性比Y的要高，当且仅当文法G中存在产生式A.BD.，且B.X，DY优先关系的定义优先关系的定义第6页，本讲稿共54页简单优先文法的定义简单优先文法的定义v满足以下条件的文法是简单优先文法：（1）在文法符号集V中，任意两个符号之间最多只有一
4、种优先关系成立；（2）在文法中任意两个产生式没有相同的右部。第7页，本讲稿共54页简单优先分析法简单优先分析法算法算法v根据已知优先文法构造相应优先关系矩阵，并将文法的产生式保存，设置符号栈S，算法步骤如下：1.将输入符号串a1a2a3.an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性.下一个待输入符号aj时为止。2.栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1ak为止。3.由句柄ak.ai在文法的产生式中查找右部为ak.ai的产生式，若找到则用相应左部代替句柄，若找不到则为出错，这时可断定输入串不是该文法的句子。4.重复上述三步，直到归约完输入符号串，
5、栈中只剩文法的开始符号为止。第8页，本讲稿共54页简单优先文法分析示例简单优先文法分析示例v文法GS：(1)SbAb(2)A(B|a(3)BAa)v1、确定文法符号之间的关系v2、求出文法的简单优先关系矩阵v3、对输入串进行分析（输入串b(aa)b#）第9页，本讲稿共54页确定文法符号之间的关系确定文法符号之间的关系1.求 关系：由(1)：b AA b由(2)：(B由(3)：A aa)2.求 关系：由(1)(2)：b(b a由(2)(3)：(A(a3.求 关系：由(1)：B ba b)b由(3)：B aa a)a第10页，本讲稿共54页求出文法的简单优先关系矩阵求出文法的简单优先关系矩阵“#”
6、用来表示语句括号，其优先关系低于所有与其有相邻关系的文法符号。第11页，本讲稿共54页对输入串进行分析对输入串进行分析（输入串（输入串b(aa)b#）步骤符号栈输入符号串动作1）#b(aa)b#b,移进2）#b(aa)b#b(,移进3）#b(aa)b#(a,移进4）#b(aa)b#a.a,归约Aa 5）#b(Aa)b#A.=a,移进 6）#b(Aa)b#a.=),移进7）#b(Aa)b#).b,归约BAa)8）#b(Bb#B.b,归约A(B 9）#bAb#A.=b,移进10）#bAb#b.#,归约SbAb11）#S#接受文法文法GS：(1)SbAb(2)A(B|a(3)BAa)第12页，本讲稿
7、共54页算符优先分析法算符优先分析法v某些文法具有“算符”特性表达式运算符（优先级、结合性）；人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性；v只考虑算符之间的优先关系来确定句柄。v定义算符文法算符优先关系算法优先文法最左素短语v算符优先关系表的构造v算符优先分析法概述v算符优先文法的性质v算符优先分析算法v优先函数v算符优先分析法的局限性第13页，本讲稿共54页算符文法的定义算符文法的定义v如果不含空产生式的上下文无关文法G中没有形如UBC的产生式，其中B，CVN，则称G为算符文法（OperaterGrammar，OG）。v性质1：在算符文法中任何句型都不包含两个相邻的非终结符
8、。（归纳法）2：如Vx或xV出现在算符文法的句型中，其中VVN,xVT,则中任何含x的短语必含有V。（反证法）第14页，本讲稿共54页用归纳法用归纳法v设设 是句型，即是句型，即S*vS=01.n-1n=v推导长度为推导长度为n，归纳起点，归纳起点n=1时，时，vS=01=，即，即S，必存在产生式，必存在产生式S，而由算符文法的定义，而由算符文法的定义，文法的产生式中无相邻的非终结符，显然满足性质文法的产生式中无相邻的非终结符，显然满足性质1。v假设假设n1,n-1满足性质满足性质1。v若若n-1=A，A为非终结符。为非终结符。v由假设知由假设知的尾符号和的尾符号和的首符号都不可能是非终结符，
9、否则与假的首符号都不可能是非终结符，否则与假设矛盾。设矛盾。v又若又若A 是文法的产生式，则有是文法的产生式，则有vn-1n=v而而A 是文法的原产生式，不含两个相邻的非终结符，所以是文法的原产生式，不含两个相邻的非终结符，所以 也不含也不含两个相邻的非终结符。满足性质两个相邻的非终结符。满足性质1。证毕。证毕。第15页，本讲稿共54页反证法反证法v因为由算符文法的性质1知可有：vS*=bAv若存在B*b，这时b和A不同时归约，则必有S*BA,这样在句型BA中存在相邻的非终结符B和A，所以与性质1矛盾，证毕。v注意：含注意：含b的短语必含的短语必含A，含，含A的短语不一定的短语不一定含含b。第
10、16页，本讲稿共54页算符优先关系的定义算符优先关系的定义 v设设G G是不含是不含 产生式的文法产生式的文法,a,a、b b是任意两个终结符，是任意两个终结符，A A、B B、C C是非终结符，算符优先关系的定义如下：是非终结符，算符优先关系的定义如下：a b当且仅当当且仅当G中有形如中有形如A Aab或或AaBb的产生式。的产生式。a b当且仅当当且仅当G中有形如中有形如A AaB的产生式的产生式,且且B+b或或B B+CbCba b当且仅当当且仅当G中有形如中有形如A ABb的产生式的产生式,且且B+a或或B BaC Cv注意：注意：算符优先关系中不存在递推关系，即算符优先关系中不存在递
11、推关系，即a b b c a c或或 a b b c a c或或a b b c a cv优先关系的语法树表示方式优先关系的语法树表示方式第17页，本讲稿共54页优先关系的语法树表示方式优先关系的语法树表示方式第18页，本讲稿共54页算符优先文法的定义算符优先文法的定义v设设G G是不含是不含 产生式的算符文法产生式的算符文法,如果对任意如果对任意两个终结符对两个终结符对a a、b b之间之间至多只有一种至多只有一种算符优算符优先关系存在，则称先关系存在，则称G为算符优先文法。为算符优先文法。v结论结论算符优先文法是无二义的。算符优先文法是无二义的。第19页，本讲稿共54页算符优先关系表的构造算
12、符优先关系表的构造v集合的定义：集合的定义：FIRSTVT(B)=b|B+b或或B+Cb.对于非终结符对于非终结符B，其往下推导所可能出现的首个算符，其往下推导所可能出现的首个算符（终结符）（终结符）LASTVT(B)=a|B+a或或B+.aC对于非终结符对于非终结符B，其往下推导所可能出现的最后一个算，其往下推导所可能出现的最后一个算符（终结符）符（终结符）v构造方式：构造方式：由定义直接构造由定义直接构造由关系图法构造由关系图法构造v构造算法构造算法第20页，本讲稿共54页由定义计算算符优先关系由定义计算算符优先关系v直接计算直接计算v算法计算算法计算v关系图计算关系图计算第21页，本讲稿
13、共54页直接计算算符优先关系直接计算算符优先关系v关系关系直接看产生式的右部，若出现了直接看产生式的右部，若出现了Aab或或AaBb,则则abv 关系关系求出每个非终结符求出每个非终结符B的的FIRSTVT(B)若若AaB,则则 bFIRSTVT(B),a bv关系关系求出每个非终结符求出每个非终结符B的的LASTVT(B)若若ABb,则则 aLASTVT(B),abv示例示例第22页，本讲稿共54页直接计算示例直接计算示例文法文法GE：(0)E#E#(1)EE+T(2)ET(3)TT*F(4)TF(5)FP F|P(6)P(E)(7)PiFIRSTVT(E)=#FIRSTVT(E)=+,*,
14、(,iFIRSTVT(T)=*,(,iFIRSTVT(F)=,(,iFIRSTVT(P)=(,iLASTVT(E)=#LASTVT(E)=+,*,),iLASTVT(T)=*,),iLASTVT(F)=,),iLASTVT(P)=),i1)关系关系由产生式由产生式(0)和和(6),得得#，（，（）3)关系关系找形如：找形如：ABb的产生式的产生式E#,则则LASTVT(E)#E+,则则LASTVT(E)+T*,则则LASTVT(T)*P,则则LASTVT(P)E),则则LASTVT(E)2）关系关系找形如：找形如：AaB的产生式的产生式#E：则：则#FIRSTVT(E)+T:则则+FIRSTV
15、T(T)*F:则则*FIRSTVT(F)F:则则 FIRSTVT(F)(E:则则(FIRSTVT(E)+*i()#+*i()#第23页，本讲稿共54页算法计算算符优先关系算法计算算符优先关系v算法规则：算法规则：1、若有产生式、若有产生式A Aa或或ABa，则，则a FIRSTVT(A)，其中，其中A、B为非终结符，为非终结符，a为终结符；为终结符；2、若、若a FIRSTVT(B)且有产生式且有产生式ABb，则有，则有a FIRSTVT(A)。v算法：算法：文本描述文本描述按规则按规则1对每个数组元素对每个数组元素FA，a赋初值，并对数组元素赋初值，并对数组元素FA，a初值为真的初值为真的符
16、号对符号对(Aa)都放入栈中，然后对栈做如下运算。都放入栈中，然后对栈做如下运算。当栈不空时，就将栈顶项弹出，并记为当栈不空时，就将栈顶项弹出，并记为(B，a)，再用规则，再用规则2，若，若FA，a为假，则使其变为真，且将为假，则使其变为真，且将(A，a)推进栈，如此重复直到栈折空为止。推进栈，如此重复直到栈折空为止。程序描述程序描述v示例示例第24页，本讲稿共54页程序描述程序描述v将置为真的操作：将置为真的操作：PROCEDUREINSERT(Aa);IFNOTFA，aTHENBEGINFAa：TRUNPUSH(Aa)0NT0STRACKENDv主程序：主程序：BEGIN(MAIN)FOR
17、每一个非终结符每一个非终结符A和终结符和终结符a，DOFA，a：FALSE；FOR每个形如每个形如Aa或或ABa的产生式的产生式DOINSERT(A，a)WHILESTACK非空非空DOBEGIN把把STACK的顶项记为的顶项记为(B，a)托出去托出去FOR每个形如每个形如AB的产生式的产生式DoINSERT(A，a)ENDEND第25页，本讲稿共54页算法计算示例算法计算示例文法文法GE：(0)E#E#(1)EE+T(2)ET(3)TT*F(4)TF(5)FP F|P(6)P(E)(7)Pi首次扫描首次扫描STRACK的初值：的初值：(6)(P,i)(5)(P,()(4)(F,)(3)(T,
18、*)(2)(E,+)(1)(E,#)栈顶（栈顶（6）的改变：）的改变：FP(F,i)TF(T,i)ET(E,i)由于无右部以由于无右部以E开始的产生式，开始的产生式，所以所以(E,i)弹出后无进栈项，此时当前弹出后无进栈项，此时当前的栈顶为的栈顶为(P,()。栈顶（栈顶（5）的改变：）的改变：FP(F,()TF(T,()ET(E,()(E,（)弹出后无进栈项，此时当前的栈顶为弹出后无进栈项，此时当前的栈顶为(F,)。栈顶（栈顶（4）的改变：）的改变：TF(T,)ET(E,)(E,)弹出后无进栈项，此时当前的栈顶为弹出后无进栈项，此时当前的栈顶为(T,*)。栈顶（。栈顶（3）的）的改变：改变：E
19、T(E,*)以下逐次弹出栈顶元素后，都以下逐次弹出栈顶元素后，都再无进栈项，直至栈空。再无进栈项，直至栈空。+*i()#E1E11111T111F111P11FIRSTVT(E)=#FIRSTVT(E)=+,*,(,iFIRSTVT(T)=*,(,iFIRSTVT(F)=,(,iFIRSTVT(P)=(,i第26页，本讲稿共54页关系图计算算符优先关系关系图计算算符优先关系v关系图的构造方法图中的结点为非终结符的FIRSTVT(A)和终结符;对每一个形如Aa或ABa的产生式，则构造由FIRSTVT(A)结点到终结符结点(a)用箭弧连接的图形；对每一个形如AB的产生式，则对应图中由FIRSTVT
20、(A)结点到FIRSTVT(B)结点用箭弧连接；对每一非终结符的FIRSTVT(A)经箭弧有路径能到达的终结符结点(a)，则有aFIRSTVT(A)。v示例第27页，本讲稿共54页关系图计算示例关系图计算示例FIRSTVT(E)FIRSTVT(E)FIRSTVT(T)FIRSTVT(F)FIRSTVT(P)#+*()文法文法GE：(0)E#E#(1)EE+T(2)ET(3)TT*F(4)TF(5)FP F|P(6)P(E)(7)Pi第28页，本讲稿共54页由关系图法计算算符优先关系由关系图法计算算符优先关系v文法符号的关系定义v优先关系与符号关系之间的联系v算符关系构造规则的关系构造规则的关系
21、构造规则v示例文法符号之间的关系文法终结符之间的关系图文法终结符之间的关系图第29页，本讲稿共54页文法符号的关系定义（文法符号的关系定义（6.46.4）v设G=(VN，VT，P，S)是一个上下文无关文法，则：AFIRSTB当且仅当存在形如AB的产生式；ALASTB当且仅当存在形如AB的产生式；BFIRSTTERMb当且仅当存在形如Bb或BCb的产生式；BLASTTERMa当且仅当存在形如Ba或BaC的产生式；XFOLLOWEDBYY当且仅当存在形如AXY的产生式，中必须是一个为终结符，另一个为非终结符；AFIRST*B当且仅当存在形如AB或存在AX1，X1X2，Xn-1Xn，XnB的产生式序
22、列；ALAST*B当且仅当存在形如BA或存在AX1，X1X2，Xn-1Xn，XnB的产生式序列。第30页，本讲稿共54页优先关系与符号关系之间的联系优先关系与符号关系之间的联系vabaFOLLOWEDBYBBFIRST*PPFIRSTTERMbab存在形如AaB的产生式,其中B+b或B+Cb而B+b可写成B*PbB+Cb可写成B*PCb所以B+b或B+CbBFIRST*PPFIRSTTERMbvab(BLAST*PPLASTTERMa)TBFOLLOWEDBYbab存在形如ABb的产生式,其中B+a或B+aC而B+a可写成B*PaB+aC可写成B*PaC所以B+a或B+aCBLAST*PPLA
23、STTERMa第31页，本讲稿共54页 的关系构造规则的关系构造规则v凡有终结符在前非终结符在后相邻关系的，则由终结符结点到非终结符结点画一箭弧。v对有FIRSTTERM关系的非终结符和终结符对，则从非终结符结点到终结符点画一箭弧。v对非终结符对之间存在FIRST关系的，从左边的非终结符结点到右边的非终结符结点画一箭弧。v对每个终结符结点a凡有路径能到达另一终结符结点b的，则有ab关系存在。第32页，本讲稿共54页 的关系构造规则的关系构造规则v对非终结符和终结符相邻关系的，由非终结符结点到终结符结点画一箭弧。v对有LASTTERM关系的，由终结符结点到非终结符结点画一箭弧。v对LAST关系的
24、非终结符对，由后面的非终结符结点到前面的非终结符结点画一箭弧。v对每个终结符结点a凡有路径能到达另一终结符结点b的，则有ab的关系成立。第33页，本讲稿共54页文法符号之间的关系文法符号之间的关系ELASTTTLASTFFLASTFFLASTPFIRST关系有EFIRSTEEFIRSTTTFIRSTTTFIRSTFFFIRSTPFIRSTTBRM关系有EFIRSTTBRM+TFIRSTTBRM*FFIRSTTBRM PFIRSTTBRM(PFIRSTTBRMi终结符在前非终结符在后的相邻关系有#FOLLOWEDBYE(FOLLOWEDBYE+FOLLOWEDBYT*FOLLOWEDBYF FO
25、LLOWEDBYFELASTTERM+TLASTTERM*FLASTTERM PLASTTERM)PLASTTERMiEFOLLOWEDBY#EFOLLOWEDBY+EFOLLOWEDBY)TFOLLOWEDBY*PFOLLOWEDBY 文法文法GE：(0)E#E#(1)EE+T(2)ET(3)TT*F(4)TF(5)FP F|P(6)P(E)(7)Pi第34页，本讲稿共54页文法终结符之间的文法终结符之间的 关系图关系图FP+*(i#+(*ET第35页，本讲稿共54页文法终结符之间的文法终结符之间的 关系图关系图P+*(i#+(*ETF第36页，本讲稿共54页构造文法的优先关系算法构造文法的
26、优先关系算法for(每个产生式AX1X2Xn)for(i=1;i=n-1;i+)if(Xi和Xi+1均为终结符)置XiXi+1；if(in-2且Xi和Xi+2均为终结符,但Xi+1为非终结符)置XiXi+1；if(Xi为终结符,Xi+1为非终结符)for(FIRSTVT(Xi+1)中的每个b)置Xib;if(Xi为非终结符,Xi+1为终结符)for(LASTVT(Xi)中的每个a)置aXi+1;第37页，本讲稿共54页最左素短语最左素短语v文法GS句型的素短语是这样一个短语，它至少包含一个终结符号，并且，除它自身之外，不再包含其他素短语。v最左素短语是指处于句型最左边的那个素短语。算符优先文法
27、句型的最左素短语是唯一的。v示例v查找最左素短语的方法：在句型中加入优先关系，例如：i+i*i#ii+ii*ii#1、找最左素短语的右端；从左至右扫描符号串直至遇到第一个为止。2、找最左素短语的左端；然后向回扫描(向左)越过任何，直至一个被发现。3、归约；可归约串包括在第1步所遇到的的左边和第2步所遇到的的右边的所有终结符号，包括插入在中间的或环绕在两旁的非终结符号。第38页，本讲稿共54页文法文法GE：(1)EE+T(2)ET(3)TT*F(4)TF(5)FP F|P(6)P(E)(7)Pi句型句型#T+T*F+i#其短语有：其短语有：T+T*F+iT+T*FTT*Fi最左素短语为：最左素短
28、语为：T*F素短语：素短语：T*F，i*EET+ETFFTTi句型句型T+T*F+i的语法树的语法树最左素短语示例最左素短语示例第39页，本讲稿共54页算符优先分析法概述算符优先分析法概述v1.算符优先分析法是一种特别有利于表达式分析，宜于手工实现的语法分析方法。v2.算符优先分析过程是自下而上的归约过程，但未必是严格的最左归约，因此，它不是一种规范归约法。v3.所谓算符优先分析法就是仿效算术表达式的运算过程而设计的一种语法分析方法；这种方法的关键在于规定算符（终结符）的优先顺序和结合性质。v示例第40页，本讲稿共54页算符优先分析法示例算符优先分析法示例文法文法GE：(1)EE+T(2)ET
29、(3)TT*F(4)TF(5)F(E)(7)Fiv对输入串对输入串i+i#的规约过程：的规约过程：规范规约规范规约算符优先规约算符优先规约第41页，本讲稿共54页规范规约示例规范规约示例步骤步骤栈栈剩余输入串剩余输入串句柄句柄归约用产生式归约用产生式1#i+i#2#i+i#iFi3#F+i#FTF4#T+i#TET5#E+i#6#E+i#7#E+i#iFi8#E+F#FTF9#E+T#E+FEE+T10#E#接受接受第42页，本讲稿共54页算符优先规约示例算符优先规约示例步骤步骤栈栈优先关系优先关系当前符号当前符号剩余输入串剩余输入串移进或归约移进或归约1#ii+i#移进移进2#i+i#归约归
30、约3#F+i#移进移进4#F+i#移进移进5#F+i#归约归约6#F+F#归约归约7#F#接受接受第43页，本讲稿共54页算符优先文法的性质算符优先文法的性质n对于算符优先文法，如果aNb(或ab)出现在句型r中,则之间有且仅有一种优先关系，即：n若ab，则在r中必含有b而不含a的短语存在；n若ab，则在r中必含有a而不含b的短语存在；n若ab，则在r中含有a的短语必含有b，反之亦然。v算符文法的任一句型有如下形式：#N1a1N2a2.NnanNn+1#,v若Niai.NjajNj+1为句柄，则Ni、Nj+1在句柄中，且该句柄中终结符之间的关系为：ai-1aiaiai+1.aj-1ajajai
31、+1第44页，本讲稿共54页算符优先分析算法算符优先分析算法v算符优先分析归约的关键是寻找最左素短语。开始开始当前输入符读入当前输入符读入a置初值置初值k=1,Sk=#Sk VT?Sj a?Sj a?j=kj=k-1Q=SjSj-1 VT?j=j-1j=j-2Sj Q?Sj+1 Sk归约为归约为Nk=j+1Sk=NK=k+1Sk=aSj.=a?Sj.=#?出错出错检查是检查是否否正常正常结束结束？结束结束YNNYYYNNYYYYYNNN第45页，本讲稿共54页优先函数优先函数v定义v构造方法由定义进行构造由关系图进行构造v示例通过定义计算优先函数关系通过关系图计算优先函数关系v优先函数分析的特
32、点第46页，本讲稿共54页优先函数定义优先函数定义v定义两个函数f、g，满足如下条件：当ab，则令f(a)g(b)当ab，则令f(a)g(b)当ab，则令f(a)g(b)对f、g可称它为优先函数。v优先函数的值可以用整数表示。优先函数的值可以用整数表示。v对优先函数每个元素的值都增加同一个常数，优先关系不对优先函数每个元素的值都增加同一个常数，优先关系不变，所以对同一个文法的优先关系矩阵对应的优先函数不变，所以对同一个文法的优先关系矩阵对应的优先函数不唯一。唯一。v有一些优先关系矩阵中的优先关系是唯一的，却不存有一些优先关系矩阵中的优先关系是唯一的，却不存在优先函数。在优先函数。示例示例第47
33、页，本讲稿共54页由定义构造优先函数由定义构造优先函数v若已知文法G终结符之间的优先关系，可按如下步骤构造其优先函数f，g:a)对每个终结符aVT(包括#在内)令f(a)g(a)1(也可是其它整数)。b)如果ab，而f(a)g(b)，则令f(a)g(b)+1c)如果ab而f(a)g(b)，则令g(b)f(a)+1d)如果ab，而f(a)g(b)，则令minf(a)，g(b)=maxf(a)，g(b)e)重复b)d)直到过程收敛。v如果重复过程中有一个值大于2n，则表明该算符优先文法不存在算符优先函数。第48页，本讲稿共54页由关系图构造优先函数由关系图构造优先函数va对所有终结符a(包括#)用
34、有下脚标的fa，gb为结点名，画出2n个结点。vb若aiaj；或aiaj，则从fai到gaj画一条箭弧。vc若aiaj；或aiaj，则从gaj到fai画一条箭弧。vd给每个结点赋一个数，此数等于从该结点出发所能到达的结点(包括该结点自身在内)的个数。赋结结点fai的数，就是函数f(ai)的值，赋给gaj的数，就是函数g(aj)的值。ve对构造出的优先函数，按优先关系矩阵检查一遍是否满足优先关系的条件，若不满足时，则在关系图中有回路说明不存在优先函数。第49页，本讲稿共54页由定义计算优先函数关系示例由定义计算优先函数关系示例v其优先函数的构造过程为：首先；把所有f(a)、g(a)的值置为1如右
35、表中的初值(0次迭代)。然后对算符优先关系矩阵远行扫描，按前述算法规则的b)e)修改函数f(a)，g(a)的值，这是个迭代过程，一直进行到优先函数的值再无变化为止(收敛)。+*i()#+*i ()#迭代次数迭代次数+*i()#0(初值初值)f1111111g11111111f2446151g23555112f3557171g24666113f3557171g2466611第50页，本讲稿共54页由关系图计算优先函数关系示例由关系图计算优先函数关系示例i*+#i *+#i*+#f6642g7532figig*f*f+g+g#f#第51页，本讲稿共54页不存在优先函数关系示例不存在优先函数关系示例
36、v由于若存在优先函数f，g，则必定满足下列条件：由矩阵的第一行应有f(a)g(a)，f(a)g(b)由矩阵的第二行应有f(b)g(a)，f(b)g(b)这样导致有f(a)g(a)f(b)g(b)与f(a)g(b)矛盾，因而优先函数不存在。aba b fafbgagbabf44g44第52页，本讲稿共54页优先函数分析的特点优先函数分析的特点v优点：占用空间少。v缺点：在利用优先关系矩阵进行优先分析时，当两个终结符对无优先关系的情况时，优先关系矩阵的相应元素为出错信息，用优先函数进行优先分析时，对两个终结符对没有优先关系时不能区分，因而出错时不能准确地指出错误位置。v例如：若有表达式i+ii*i
37、#在分析过程中只能在匹配产生式时，用算符优先文法的性质(任何句型不可能有相邻的非终结符出现)或对于表达式可用运算对象和运算符相间的方式检查是否出错。如例中表达式串当归约到N十NN可发现错误，是由于句型中有两个相邻的非终结符，而不是由于ii不能相邻。表达式为i+i*i(i+i)#按算符优先矩阵i与(无优先关系，当归约分析N十N*i时，能即时发现错误，而用优先函数分析则此时发现不了错误，直到归约到N+N*NN时，才能由两非终结符相邻的出现而发现错误，因而不能准确指出错误位置。第53页，本讲稿共54页算符优先分析法的局限性算符优先分析法的局限性v一般语言的文法很难满足算符优先文法的条件；v很难避免把错误的句子得到正确的归约；v算符优先分析法仅适用于表达式的语法分析。第54页，本讲稿共54页