自底向上优先分析法

自底向上优先分析法第一页，共五十四页，2022年，8月28日第06章自底向上优先分析法自底向上优先分析概述简单优先分析法算符优先分析法第二页，共五十四页，2022年，8月28日自底向上分析方法概述自底向上分析方法，也称移进-归约分析法。实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。示例第三页，共五十四页，2022年，8月28日abbcde步骤符号栈输入符号串动作1）# abbcde# 移进2）#a bbcde# 移进A3）#ab bcde# 归约(A→b)4）#aA bcde# 移进A5）#aAb cde# 归约(A→Ab)6）#aA cde# 移进7）#aAc de# 移进B8）#aAcd e# 归约(B→d)9）#aAcB e# 移进11）#S # 接受S10）#aAcBe# 归约(S→aAcBe)分析符号串abbcde是否G[S]的句子对输入串abbcde#的移进-规约分析过程SaAcBeaAcdeaAbcdeabbcde最右推导：示例文法G[S]：

(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→d第四页，共五十四页，2022年，8月28日简单优先分析法按照文法符号（包括终结符和非终结符）的优先关系确定句柄。定义优先关系简单优先文法优先关系矩阵：表示文法符号之间关系的矩阵。算法示例第五页，共五十四页，2022年，8月28日优先关系X

≖Y：表示X、Y的优先关系相同，当且仅当文法G中存在产生式A→...XY…；X⋖Y：表示X的优先性比Y的要低，当且仅当文法G中存在产生式A→...XB...，且BY...X⋗Y：表示X的优先性比Y的要高，当且仅当文法G中存在产生式A→...BD...，且B...X，DY优先关系的定义第六页，共五十四页，2022年，8月28日简单优先文法的定义满足以下条件的文法是简单优先文法：（1）在文法符号集V中，任意两个符号之间最多只有一种优先关系成立；（2）在文法中任意两个产生式没有相同的右部。第七页，共五十四页，2022年，8月28日简单优先分析法——算法根据已知优先文法构造相应优先关系矩阵，并将文法的产生式保存，设置符号栈S，算法步骤如下：将输入符号串a1a2a3...an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性.>下一个待输入符号aj时为止。栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1⋖ak为止。由句柄ak...ai在文法的产生式中查找右部为ak...ai的产生式，若找到则用相应左部代替句柄，若找不到则为出错，这时可断定输入串不是该文法的句子。重复上述三步，直到归约完输入符号串，栈中只剩文法的开始符号为止。第八页，共五十四页，2022年，8月28日简单优先文法分析示例文法G[S]：(1)S→bAb(2)A→(B|a(3)B→Aa)1、确定文法符号之间的关系2、求出文法的简单优先关系矩阵3、对输入串进行分析（输入串b(aa)b#）第九页，共五十四页，2022年，8月28日确定文法符号之间的关系1.求≖关系：由(1)：b≖A A≖b由(2)：(≖B由(3)：A≖a a≖)2.求⋖关系：由(1)(2)：b⋖(b⋖a由(2)(3)：(⋖A(⋖((⋖a3.求⋗关系：由(1)：B⋗b a⋗b )⋗b由(3)：B⋗a a⋗a )⋗a第十页，共五十四页，2022年，8月28日求出文法的简单优先关系矩阵“#”用来表示语句括号，其优先关系低于所有与其有相邻关系的文法符号。第十一页，共五十四页，2022年，8月28日对输入串进行分析（输入串b(aa)b#）步骤符号栈输入符号串动作1）#b(aa)b##⋖b,移进2）#b(aa)b#b⋖(,移进3）#b(aa)b#(⋖a,移进4）#b(aa)b#a.>a,归约A→a5）#b(Aa)b#A.=a,移进6）#b(Aa)b#a.=),移进7）#b(Aa)b#).>b,归约B→Aa)8）#b(Bb#B.>b,归约A→(B9）#bAb#A.=b,移进10）#bAb#b.>#,归约S→bAb11）#S#接受文法G[S]：

(1)S→bAb

(2)A→(B|a

(3)B→Aa)

第十二页，共五十四页，2022年，8月28日算符优先分析法某些文法具有“算符”特性表达式运算符（优先级、结合性）；人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性；只考虑算符之间的优先关系来确定句柄。定义算符文法算符优先关系算法优先文法最左素短语算符优先关系表的构造算符优先分析法概述算符优先文法的性质算符优先分析算法优先函数算符优先分析法的局限性第十三页，共五十四页，2022年，8月28日算符文法的定义如果不含空产生式的上下文无关文法G中没有形如U…BC…的产生式，其中B，C∈VN，则称G为算符文法（OperaterGrammar，OG）。性质1：在算符文法中任何句型都不包含两个相邻的非终结符。（归纳法）2：如Vx或xV出现在算符文法的句型中，其中V∈VN,x∈VT,则中任何含x的短语必含有V。（反证法）第十四页，共五十四页，2022年，8月28日用归纳法设是句型，即S⇒*S=ω0⇒ω1⇒...⇒ωn-1⇒ωn=推导长度为n，归纳起点n=1时，S=ω0⇒ω1=

，即S⇒，必存在产生式S→，而由算符文法的定义，文法的产生式中无相邻的非终结符，显然满足性质1。假设n＞1,ωn-1满足性质1。若ωn-1=A，A为非终结符。由假设知α的尾符号和δ的首符号都不可能是非终结符，否则与假设矛盾。又若A→是文法的产生式，则有ωn-1⇒ωn==而A→是文法的原产生式，不含两个相邻的非终结符，所以也不含两个相邻的非终结符。满足性质1。证毕。第十五页，共五十四页，2022年，8月28日反证法因为由算符文法的性质1知可有：S⇒*=bAβ若存在B⇒*b，这时b和A不同时归约，则必有S⇒*BAβ,这样在句型BAβ中存在相邻的非终结符B和A，所以与性质1矛盾，证毕。注意：含b的短语必含A，含A的短语不一定含b。第十六页，共五十四页，2022年，8月28日算符优先关系的定义设G是不含产生式的文法,a、b是任意两个终结符，A、B、C是非终结符，算符优先关系的定义如下：a≖b当且仅当G中有形如A…ab…或A…aBb…的产生式。

a⋖b当且仅当G中有形如A…aB…的产生式,且B⇒+b…或B⇒+Cb…a⋗b当且仅当G中有形如A…Bb…的产生式,且B⇒+…a或B⇒…aC注意：算符优先关系中不存在递推关系，即a≖bb≖c⇏a≖c或a⋖bb⋖c⇏a⋖c或a⋗bb⋗c⇏a⋗c优先关系的语法树表示方式第十七页，共五十四页，2022年，8月28日优先关系的语法树表示方式第十八页，共五十四页，2022年，8月28日算符优先文法的定义设G是不含产生式的算符文法,如果对任意两个终结符对a、b之间至多只有一种算符优先关系存在，则称G为算符优先文法。

结论

算符优先文法是无二义的。第十九页，共五十四页，2022年，8月28日算符优先关系表的构造集合的定义：FIRSTVT(B)={b|B⇒+b…或B⇒+Cb...}对于非终结符B，其往下推导所可能出现的首个算符（终结符）LASTVT(B)={a|B⇒+…a或B⇒+...aC}对于非终结符B，其往下推导所可能出现的最后一个算符（终结符）构造方式：由定义直接构造由关系图法构造构造算法第二十页，共五十四页，2022年，8月28日由定义计算算符优先关系直接计算算法计算关系图计算第二十一页，共五十四页，2022年，8月28日直接计算算符优先关系‘≖‘关系直接看产生式的右部，若出现了

A→…ab…或A→…aBb,则a≖b’⋖‘关系求出每个非终结符B的FIRSTVT(B)若A→…aB…,则b∈FIRSTVT(B),a⋖b’⋗’关系求出每个非终结符B的LASTVT(B)若A→…Bb…,则a∈LASTVT(B),a⋗b示例第二十二页，共五十四页，2022年，8月28日直接计算示例文法G[E]：

(0)E’→#E#

(1)E→E+T

(2)E→T

(3)T→T*F

(4)T→F

(5)F→PF|P

(6)P→(E)

(7)P→iFIRSTVT(E’)={#}

FIRSTVT(E)={+,*,,(,i}

FIRSTVT(T)={*,,(,i}

FIRSTVT(F)={,(,i}

FIRSTVT(P)={(,i}

LASTVT(E’)={#}

LASTVT(E)={+,*,,),i}

LASTVT(T)={*,,),i}

LASTVT(F)={,),i}

LASTVT(P)={),i}1)≖关系

由产生式(0)和(6),得

#≖#，（≖）3)⋗关系

找形如：A→…Bb…的产生式

E#,则LASTVT(E)⋗#

E+,则LASTVT(E)⋗+

T*,则LASTVT(T)⋗*

P,则LASTVT(P)⋗

E),则LASTVT(E)>)2）⋖关系

找形如：A→…aB…的产生式

#E：则#⋖FIRSTVT(E)

+T:则+⋖FIRSTVT(T)

*F:则*⋖FIRSTVT(F)

F:则⋖FIRSTVT(F)

(E:则(⋖FIRSTVT(E)

+*↑i()#+⋗⋖⋖⋖⋖⋗⋗*⋗⋗⋖⋖⋖⋗⋗↑⋗⋗⋖⋖⋖⋗⋗i⋗⋗⋗

⋗⋗(⋖⋖⋖⋖⋖≖

)⋗⋗⋗

⋗⋗#⋖⋖⋖⋖⋖

≖第二十三页，共五十四页，2022年，8月28日算法计算算符优先关系算法规则：1、若有产生式Aa…或ABa…，则aFIRSTVT(A)，其中A、B为非终结符，a为终结符；2、若aFIRSTVT(B)且有产生式ABb…，则有aFIRSTVT(A)。算法：文本描述按规则1对每个数组元素F[A，a]赋初值，并对数组元素F[A，a]初值为真的符号对(A．a)都放入栈中，然后对栈做如下运算。当栈不空时，就将栈顶项弹出，并记为(B，a)，再用规则2，若F[A，a]为假，则使其变为真，且将(A，a)推进栈，如此重复直到栈折空为止。程序描述示例第二十四页，共五十四页，2022年，8月28日程序描述将置为真的操作：PROCEDUREINSERT(A．a);IFNOTF[A，a]THENBEGINF[A．a]：＝TRUNPUSH(A．a)0NT0STRACKEND主程序：BEGIN(MAIN)FOR每一个非终结符A和终结符a，DOF[A，a]：＝FALSE；FOR每个形如Aa··或ABa…的产生式DOINSERT(A，a)WHILESTACK非空DOBEGIN把STACK的顶项记为(B，a)托出去FOR每个形如AB…的产生式DoINSERT(A，a)ENDEND第二十五页，共五十四页，2022年，8月28日算法计算示例文法G[E]：

(0)E’→#E#

(1)E→E+T

(2)E→T

(3)T→T*F

(4)T→F

(5)F→PF|P

(6)P→(E)

(7)P→i首次扫描STRACK的初值：

(6)(P,i)

(5)(P,()

(4)(F,)

(3)(T,*)

(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）的改变：

ET(E,*)以下逐次弹出栈顶元素后，都再无进栈项，直至栈空。

+*↑i()#E’

1E11111

T

111

F

111

P

11

FIRSTVT(E’)={#}

FIRSTVT(E)={+,*,,(,i}

FIRSTVT(T)={*,,(,i}

FIRSTVT(F)={,(,i}

FIRSTVT(P)={(,i}第二十六页，共五十四页，2022年，8月28日关系图计算算符优先关系关系图的构造方法图中的结点为非终结符的FIRSTVT(A)和终结符;对每一个形如Aa…或ABa…的产生式，则构造由FIRSTVT(A)结点到终结符结点(a)用箭弧连接的图形；对每一个形如AB…的产生式，则对应图中由FIRSTVT(A)结点到FIRSTVT(B)结点用箭弧连接；对每一非终结符的FIRSTVT(A)经箭弧有路径能到达的终结符结点(a)，则有aFIRSTVT(A)。示例第二十七页，共五十四页，2022年，8月28日关系图计算示例FIRSTVT(E’)FIRSTVT(E)FIRSTVT(T)FIRSTVT(F)FIRSTVT(P)#+*()文法G[E]：

(0)E’→#E#

(1)E→E+T

(2)E→T

(3)T→T*F

(4)T→F

(5)F→PF|P

(6)P→(E)

(7)P→i第二十八页，共五十四页，2022年，8月28日由关系图法计算算符优先关系文法符号的关系定义优先关系与符号关系之间的联系算符关系构造规则⋖的关系构造规则⋗的关系构造规则示例文法符号之间的关系文法终结符之间的⋖关系图文法终结符之间的⋗关系图第二十九页，共五十四页，2022年，8月28日文法符号的关系定义（6.4）设G=(VN，VT，P，S)是一个上下文无关文法，则：AFIRSTB当且仅当存在形如AB⋯的产生式；ALASTB当且仅当存在形如A⋯B的产生式；BFIRSTTERMb当且仅当存在形如Bb⋯或BCb⋯的产生式；BLASTTERMa当且仅当存在形如B⋯a或B⋯aC的产生式；XFOLLOWEDBYY当且仅当存在形如A⋯XY⋯的产生式，中必须是一个为终结符，另一个为非终结符；AFIRST*B当且仅当存在形如AB或存在AX1⋯，X1X2⋯，⋯，Xn-1Xn⋯，XnB⋯的产生式序列；ALAST*B当且仅当存在形如BA或存在A⋯X1，X1⋯X2，⋯，Xn-1⋯Xn，Xn⋯B的产生式序列。第三十页，共五十四页，2022年，8月28日优先关系与符号关系之间的联系a⋖b⇔aFOLLOWEDBYBBFIRST*PPFIRSTTERMba⋖b⇔存在形如A⋯aB⋯的产生式,其中B⇒+b⋯或B⇒+Cb⋯而B⇒+b⋯可写成B⇒*P⋯⇒b⋯

B⇒+Cb⋯可写成B⇒*P⋯⇒Cb⋯所以B⇒+b⋯或B⇒+Cb⋯⇔BFIRST*PPFIRSTTERMba⋗b⇔(BLAST*PPLASTTERMa)TBFOLLOWEDBYba⋗b⇔存在形如A⋯Bb⋯的产生式,其中B⇒+a⋯或B⇒+aC⋯而B⇒+⋯

a可写成B⇒*⋯

P⇒⋯a

B⇒+⋯

aC可写成B⇒*⋯

P⇒⋯aC所以B⇒+⋯

a或B⇒+⋯

aC⇔BLAST*PPLASTTERMa第三十一页，共五十四页，2022年，8月28日⋖的关系构造规则凡有终结符在前非终结符在后相邻关系的，则由终结符结点到非终结符结点画一箭弧。对有FIRSTTERM关系的非终结符和终结符对，则从非终结符结点到终结符点画一箭弧。对非终结符对之间存在FIRST关系的，从左边的非终结符结点到右边的非终结符结点画一箭弧。对每个终结符结点a凡有路径能到达另一终结符结点b的，则有a⋖b关系存在。第三十二页，共五十四页，2022年，8月28日⋗的关系构造规则对非终结符和终结符相邻关系的，由非终结符结点到终结符结点画一箭弧。对有LASTTERM关系的，由终结符结点到非终结符结点画一箭弧。对LAST关系的非终结符对，由后面的非终结符结点到前面的非终结符结点画一箭弧。对每个终结符结点a凡有路径能到达另一终结符结点b的，则有a⋗b的关系成立。第三十三页，共五十四页，2022年，8月28日文法符号之间的关系ELASTTTLASTFFLASTFFLASTPFIRST关系有EFIRSTEEFIRSTTTFIRSTTTFIRSTFFFIRSTPFIRSTTBRM关系有EFIRSTTBRM+TFIRSTTBRM*FFIRSTTBRM

PFIRSTTBRM(PFIRSTTBRMi终结符在前非终结符在后的相邻关系有#FOLLOWEDBYE(FOLLOWEDBYE+FOLLOWEDBYT*FOLLOWEDBYF

FOLLOWEDBYFELASTTERM+TLASTTERM*FLASTTERM

PLASTTERM)PLASTTERMiEFOLLOWEDBY#EFOLLOWEDBY+EFOLLOWEDBY)TFOLLOWEDBY*PFOLLOWEDBY文法G[E]：

(0)E’→#E#

(1)E→E+T

(2)E→T

(3)T→T*F

(4)T→F

(5)F→PF|P

(6)P→(E)

(7)P→i第三十四页，共五十四页，2022年，8月28日文法终结符之间的⋖关系图FP+*(i#+(*ET第三十五页，共五十四页，2022年，8月28日文法终结符之间的⋗关系图P+*(i#+(*ETF第三十六页，共五十四页，2022年，8月28日构造文法的优先关系算法for(每个产生式A→X1X2…Xn)

for(i=1;i<=n-1;i++)

{

if(Xi和Xi+1均为终结符)置Xi≖Xi+1

；

if(i≤n-2且Xi和Xi+2均为终结符,但Xi+1为非终结符)

置Xi≖Xi+1

；

if(Xi为终结符,Xi+1为非终结符)

for(FIRSTVT(Xi+1)中的每个b)置Xi⋖b;

if(Xi为非终结符,Xi+1为终结符)

for(LASTVT(Xi)中的每个a)置a⋗Xi+1;

};第三十七页，共五十四页，2022年，8月28日最左素短语文法G[S]句型的素短语是这样一个短语，它至少包含一个终结符号，并且，除它自身之外，不再包含其他素短语。最左素短语是指处于句型最左边的那个素短语。算符优先文法句型的最左素短语是唯一的。示例查找最左素短语的方法：在句型中加入优先关系，例如：i+i*i

#⋖i

i⋗+

+⋖i

i⋗*

*⋖i

i⋗#1、找最左素短语的右端；从左至右扫描符号串直至遇到第一个⋗为止。2、找最左素短语的左端；然后向回扫描(向左)越过任何≖，直至一个⋖被发现。3、归约；可归约串包括在第1步所遇到的⋗的左边和第2步所遇到的⋖的右边的所有终结符号，包括插入在中间的或环绕在两旁的非终结符号。第三十八页，共五十四页，2022年，8月28日文法G[E]：

(1)E→E+T

(2)E→T

(3)T→T*F

(4)T→F

(5)F→PF|P

(6)P→(E)

(7)P→i句型#T+T*F+i#

其短语有：

T+T*F+i

T+T*F

T

T*F

i最左素短语为：T*F素短语：T*F，i*EET++ETFFTTi句型T+T*F+i的语法树最左素短语示例第三十九页，共五十四页，2022年，8月28日算符优先分析法概述1.算符优先分析法是一种特别有利于表达式分析，宜于手工实现的语法分析方法。2.算符优先分析过程是自下而上的归约过程，但未必是严格的最左归约，因此，它不是一种规范归约法。3.所谓算符优先分析法就是仿效算术表达式的运算过程而设计的一种语法分析方法；这种方法的关键在于规定算符（终结符）的优先顺序和结合性质。示例第四十页，共五十四页，2022年，8月28日算符优先分析法示例文法G[E]：

(1)E→E+T(2)E→T(3)T→T*F(4)T→F

(5)F→(E)(7)F→i对输入串i+i#的规约过程：规范规约算符优先规约第四十一页，共五十四页，2022年，8月28日规范规约示例步骤栈剩余输入串句柄归约用产生式1#i+i#

2#i+i#iF→i3#F+i#FT→F4#T+i#TE→T5#E+i#

6#E+i#

7#E+i#iF→i8#E+F#FT→F9#E+T#E+FE→E+T10#E#

接受第四十二页，共五十四页，2022年，8月28日算符优先规约示例步骤栈优先关系当前符号剩余输入串移进或归约1#⋖ii+i#移进2#i⋗++i#归约3#F⋖++i#移进4#F+⋖i#移进5#F+i⋗#

归约6#F+F⋗#

归约7#F≖#

接受第四十三页，共五十四页，2022年，8月28日算符优先文法的性质对于算符优先文法，如果aNb(或ab)出现在句型r中,则之间有且仅有一种优先关系，即：若a⋖b，则在r中必含有b而不含a的短语存在；若a⋗b，则在r中必含有a而不含b的短语存在；若a≖b，则在r中含有a的短语必含有b，反之亦然。算符文法的任一句型有如下形式：

#N1a1N2a2......NnanNn+1#,若Niai......NjajNj+1为句柄，则Ni、

Nj+1在句柄中，且该句柄中终结符之间的关系为：ai-1⋖aiai≖ai+1≖...≖aj-1≖ajaj⋗ai+1第四十四页，共五十四页，2022年，8月28日算符优先分析算法算符优先分析归约的关键是寻找最左素短语。开始当前输入符读入a置初值k=1,S[k]=‘#’S[k]VT?S[j]⋗a?S[j]⋖a?j=kj=k-1Q=S[j]S[j-1]VT?j=j-1j=j-2S[j]⋗Q?S[j+1]⋯S[k]归约为Nk=j+1S[k]=NK=k+1S[k]=aS[j].=a?S[j].=#?出错检查是否正常结束？结束YNNYYYNNYYYYYNNN第四十五页，共五十四页，2022年，8月28日优先函数定义构造方法由定义进行构造由关系图进行构造示例通过定义计算优先函数关系通过关系图计算优先函数关系优先函数分析的特点第四十六页，共五十四页，2022年，8月28日优先函数定义定义两个函数f、g，满足如下条件：当a≖b，则令f(a)＝g(b)当a⋖b，则令f(a)＜g(b)当a⋗b，则令f(a)＞g(b)对f、g可称它为优先函数。优先函数的值可以用整数表示。对优先函数每个元素的值都增加同一个常数，优先关系不变，所以对同一个文法的优先关系矩阵对应的优先函数不唯一。有一些优先关系矩阵中的优先关系是唯一的，却不存在优先函数。示例第四十七页，共五十四页，2022年，8月28日由定义构造优先函数若已知文法G终结符之间的优先关系，可按如下步骤构造其优先函数f，g:a)对每个终结符a∊VT(包括#在内)令f(a)＝g(a)＝1(也可是其它整数)。b)如果a⋗b，而f(a)≤g(b)，则令f(a)＝g(b)+1c)如果a⋖b而f(a)≥g(b)，则令g(b)＝f(a)+1d)如果a≖b，而f(a)≠g(b)，则令

min{f(a)，g(b)}=max{f(a)，g(b)}e)重复b)~d)直到过程收敛。如果重复过程中有一个值大于2n，则表明该算符优先文法不存在算符优先函数。第四十八页，共五十四页，2022年，8月28日由关系图构造优先函数a对所有终结符a(包括‘#’)用有下脚标的fa，gb为结点名，画出2n个结点。b若ai⋗aj；或ai≖aj

，则从fai到gaj画一条箭弧。c若ai⋖aj；或ai≖aj，则从gaj到fai画一条箭弧。d给每个结点赋一个数，此数等于从该结点出发所能到达的结点(包括该结点自身在内)的个数。赋结结点fai的数，就是函数f(ai)的值，赋给gaj的数，就是函数g(aj)