第四章語法分析

語法分析是編譯過程的核心部分，它以詞法分析輸出的單詞串形式的源程序作為輸入和分析的對象,它的主要任務(wù)是按照程序語言的語法規(guī)則，分析源程序的語法結(jié)構(gòu)，即分析如何由這些單詞組成各種語法成分，同時(shí)進(jìn)行語法檢查，為語義分析和代碼生成作準(zhǔn)備。執(zhí)行語法分析任務(wù)的程序叫語法分析程序或語法分析器。語法分析程序以詞法分析輸出的符號串作為輸入，在分析過程中檢查這個(gè)符號串是否為該程序語言的句子。若是，輸出該句子的分析樹；若不是，則表示源程序存在語法錯(cuò)誤，需要報(bào)告錯(cuò)誤的性質(zhì)和位置。例如，對于C程序語句“IF(a<10)b=5；”，詞法分析識別出了IF、(、標(biāo)識符、…等單詞符號，而語法分析則要檢查這些單詞之間的搭配、結(jié)構(gòu)是否正確。IF后面是否為(，(后面是否為正確的表達(dá)式等等。常用的語法分析方法大體上可以分成自頂向下和自底向上兩大類：自頂向下分析方法：語法分析從頂部(樹根、語言的識別符號)到底部(葉子、語言的終結(jié)符號)為輸入的符號串建立分析樹。本章介紹的遞歸下降分析方法和LL分析方法就屬于自頂向下分析方法。自底向上分析方法：語法分析從底部到頂部為輸入的符號串建立分析樹。最常見的LR分析方法采用的就是自底向上分析方法。無論采用哪種分析方法，語法分析都是自左向右地讀入符號。4.1自頂向下的分析方法自頂向下的分析方法就是從文法的開始符號出發(fā)，按最左推導(dǎo)方式向下推導(dǎo)，試圖推出要分析的輸入串。自頂向下分析常用的方法有：遞歸下降分析(recursive-descentparsing)和LL(1)分析(LL(1)parsing)。一般而言,為了給w尋找一個(gè)最左推導(dǎo),須對每一步直接推導(dǎo)應(yīng)使用的產(chǎn)生式進(jìn)行判斷,即反復(fù)用各候選式進(jìn)行試探,以便得到正確的選擇。例如,文法G[E]:1.E→T|EAT2.T→F|TMF3.F→(E)|i4.A→＋|－

5.M→*|/給w=i+i*i建立最左推導(dǎo)。E=>T=>F=>(E)錯(cuò)誤,退回到F,選用其他候選式E=>T=>F=>i錯(cuò)誤,退回到T,選用其他候選式E=>T=>TMF錯(cuò)誤,退回到E,選用其他候選式E=>EAT4.1自頂向下的分析方法上述自頂向下的分析過程有如下基本特點(diǎn):由于采用了最左推導(dǎo),故如果文法是左遞歸的,便會使語法分析過程陷入循環(huán)不已的狀態(tài)。例如E=>EAT=>EATAT=>EATATAT=>…采用最左推導(dǎo)以實(shí)現(xiàn)對符號串w的匹配,實(shí)際上是用文法產(chǎn)生式的諸候選式反復(fù)進(jìn)行試探的過程,這勢必會出現(xiàn)大量的回溯,從而導(dǎo)致語法分析效率的大幅下降。當(dāng)報(bào)告分析失敗時(shí),分析程序一般僅能給出輸入串w不是句子這一結(jié)論,而難于指出出錯(cuò)的具體情況(錯(cuò)誤性質(zhì)和出錯(cuò)位置等)。因此,欲實(shí)現(xiàn)自頂向下的語法分析,其首要任務(wù)時(shí)改造程序設(shè)計(jì)語言的文法,以消除其中的左遞歸和避免回溯的出現(xiàn)。4.1.1消除文法的左遞歸另一種方法是對A引入一個(gè)新的非終結(jié)符號A’,改寫為A→βA’A’→αA’|ε例如，前面文法的規(guī)則：E→EAT|T，T→TMF|F，消除左遞歸：方法一：E→T{AT}T→F{MF}方法二:E→TE’T→FT’E’→ATE’|εT’→MFT’|ε一般的,設(shè)文法中全部A-產(chǎn)生式為A→Aα1|Aα2|…|Aαn

|β1|β2|…|βm

改寫為A→β1A’|β2A’|…|βmA’

A’→α1A’|α2A’|…|αnA’

|ε我們在第二章提到，不同的文法可描述相同的語言，這些文法稱為等價(jià)文法。對于左遞歸問題，我們就是用等價(jià)文法來解決，即將文法中的左遞歸去掉。消除直接左遞歸的方法如下：對形如A→Aα|β的直接左遞歸文法規(guī)則，用擴(kuò)充BNF表示來改寫規(guī)則，即利用元符號“{”和“}”來改寫規(guī)則，將規(guī)則改寫成A→β{α}4.1.1消除文法的左遞歸

下面，再給出一種通過將文法G=(Vn,Vt,P,S)表示成矩陣形式而一次消除G的全部左遞歸的方法。首先,令Vn={X1,X2,…,Xn},且對G中的每個(gè)產(chǎn)生式

Xi→y1|y2|…|ym可將其寫成

Xi=X1α1i+X2α2i+…Xnαni+βi于是,文法G的諸產(chǎn)生式便可寫成如下的矩陣方程(X1,X2,…,Xn)=(X1,X2,…,Xn)α11

α12…α1n+(β1,β2,…,βn)

α21

α22…α2n…………αn1

αn2…αnn

如果一個(gè)非終結(jié)符號A是經(jīng)兩步或多步推導(dǎo)而出現(xiàn)的左遞歸,則可對相關(guān)產(chǎn)生式作代入操作，將A-產(chǎn)生式化成直接左遞歸的，再按上面的方法將左遞歸消除。例如，對于文法S→Aβ|yA→Sα代入后得到(見引理2.1)S→Sαβ|y消除直接左遞歸得到

S→yS’S’→αβS’|ε4.1.1消除文法的左遞歸或X=XA+B此方程有形如X=BA*的最小解,由于A*=I+AA*其中I=ε

ΦΦ…ΦΦεΦ…Φ……ΦΦΦ…ε若設(shè)A*=Z=z11z12…z1n

z21z22…z2n…………zn1zn2…znn則有

X=BZZ=I+AZ將上述兩矩陣式寫成分量式,便得到了一組等價(jià)的新的產(chǎn)生式,且消除了原文法的一切左遞歸。4.1.1消除文法的左遞歸例4.1考慮文法S→Sa|Ab|aA→Sc顯然,S,A都是左遞歸的非終結(jié)符。首先寫出文法的矩陣表示

(SA)=(SA)a

c+(aΦ)bΦ

設(shè)ac*=Z=z11z12

bΦ

z21z22

則有

(SA)=(aΦ)z11z12z21z22z11z12=εΦ+acz11z12z21z22ΦεbΦz21z22

于是得到新的等價(jià)文法S→az11A→az12z11→az11|cz21|εz12→az12|cz22z21→bz11z22→bz12|ε

刪除無用產(chǎn)生式S→az11z11→az11|cz21|εz21→bz114.1.2回溯的消除及LL(1)文法對于給定的文法G[S]=(Vn,Vt,P,S)和給定的輸入符號串w=a1a2…an(ai∈Vt)，為判斷w是否為L(G)中的句子，現(xiàn)試圖為w建立一個(gè)從S出發(fā)的最左推導(dǎo)，設(shè)經(jīng)過若干步推導(dǎo)后得到

S=*>w1Aβ

A∈Vn，β∈(Vn∪Vt)*其中w1=a1a2…ai-1，即w的一個(gè)前綴w1已從上面的推導(dǎo)得到匹配，現(xiàn)須對Aβ繼續(xù)進(jìn)行推導(dǎo)，現(xiàn)設(shè)G中的全部A-產(chǎn)生式為

A→y1|y2|…|ym且對這m個(gè)候選式y(tǒng)k(1≤k≤m)，要么全部ykβ均不能推導(dǎo)出以ai打頭的符號串(此時(shí)w不是句子)，要么存在一個(gè)yj，能使yjβ推導(dǎo)出以ai打頭的符號串，而其余的ykβ則不能推出，這樣上述推導(dǎo)過程在產(chǎn)生式選擇上的試探將可避免。如果文法G中的全部產(chǎn)生式均滿足上述要求,則消除回溯的問題自然就解決了。4.1.2回溯的消除及LL(1)文法可見,要實(shí)現(xiàn)無回溯的自頂向下分析,對相應(yīng)文法須有一定的要求。為導(dǎo)出文法應(yīng)滿足的條件,需定義候選式y(tǒng)的終結(jié)首符集和非終結(jié)符號A的后繼終結(jié)符號集如下:FIRST(y)={a|y=*>a…，a∈Vt}

當(dāng)y=*>ε時(shí),約定ε∈FIRST(y)

FIRST(y)就是從y可能推導(dǎo)出的句型的所有開頭終結(jié)符和可能的ε。FOLLOW(A)={a|S#=*>…Aa…,a∈Vt}

當(dāng)S=*>…A,約定#∈FOLLOW(A)FOLLOW(A)就是在所有的句型這緊接A之后的終結(jié)符或#。于是,對于一個(gè)已化簡的非左遞歸文法G,在進(jìn)行自頂向下語法分析時(shí),不出現(xiàn)回溯的充分條件是對于G中的每個(gè)產(chǎn)生式A→y1|y2|…|ym,其各候選式均應(yīng)滿足:(1)不同的候選式不能推出以同一終結(jié)符號打頭的符號串,即

FIRST(yi)∩FIRST(yj)=Φ1≤i,j≤m;i≠j(2)若有yj=>ε,則其余候選式y(tǒng)i所能推導(dǎo)出的符號串不能以FOLLOW(A)中的終結(jié)符號開頭,即

FIRST(yi)∩FOLLOW(A)

=Φi≤1,2,…,m;i≠j通常,我們將滿足上述條件的文法稱為LL(1)文法。即對于此種文法,可采用從左到右掃視源程序P,并按最左推導(dǎo)的方式求得與P中各符號的匹配,而且每步推導(dǎo)只需向前查看一個(gè)輸入符號,就可準(zhǔn)確的選擇所用的產(chǎn)生式。4.1.2回溯的消除及LL(1)文法下面,給出對給定文法G求各個(gè)FIRST集FOLLOW集的算法。由于每個(gè)產(chǎn)生式的各個(gè)候選式均是一個(gè)由文法符號所組成的符號串,因此僅須給出對單個(gè)文法符號求這兩個(gè)集合的方法即可。文法符號的FIRST集合構(gòu)造方法：對于文法中的符號X∈Vn∪Vt，其FIRST(X)集合可反復(fù)應(yīng)用下列規(guī)則計(jì)算，直到其FIRST(X)集合不再增大為止：

1)若X∈Vt，則FIRST(X)={X}2)若X∈Vn，且具有形如X→aα的產(chǎn)生式(a∈Vt)，或具有形如X→ε的產(chǎn)生式，則把a(bǔ)或ε加進(jìn)FIRST(X)。3)設(shè)G中有形如X→Y1Y2…Yk的產(chǎn)生式，若Y1∈Vn，則把FIRST(Y1)中的一切非ε符號加進(jìn)FIRST(X)；對于一切2≤i≤k，若Y1，Y2，…，Yi-1均為非終結(jié)符號，且ε∈FIRST(Yj)，1≤j≤i-1，則將FIRST(Yi)中的一切非ε符號加進(jìn)FIRST(X)；但若對一切1≤i≤k，均有ε∈FIRST(Yj)，則將ε符號加進(jìn)FIRST(X)。

若X→Y1|Y2|…|Yk∈P,且Y1∈Vn,則把FIRST(Y1)\ε加進(jìn)FIRST(X);若ε∈FIRST(Y1),則把FIRST(Y2)\ε加進(jìn)FIRST(X);若ε∈FIRST(Y1)和FIRST(Y2),則把FIRST(Y3)\ε加進(jìn)FIRST(X)…以此類推;但若對一切1≤i≤k,均有ε∈FIRST(Yi),則把ε加進(jìn)FIRST(X)4.1.2回溯的消除及LL(1)文法例4.2設(shè)有文法S→abBA→SC|εB→AbAC→B|c求所有非終結(jié)符和符號串AABcab的FIRST集合。解:FIRST(S)={a}

FIRST(A)=FIRST(SC)∪{ε}=FIRST(S)∪{ε}={a,ε}FIRST(B)=FIRST(AbA)=FIRST(A)\ε∪FIRST(bA)={a,b}FIRST(C)=FIRST(B)∪c={a,b,c}FIRST(AABcab)=FIRST(A)\ε∪FIRST(A)\ε∪FIRST(Bcab)={a}∪FIRST(B)={a,b}4.1.2回溯的消除及LL(1)文法對于文法中的符號A∈Vn，其FOLLOW(A)集合可反復(fù)應(yīng)用下列規(guī)則計(jì)算，直到其FOLLOW(A)集合不再增大為止：1)對于文法的開始符號，令#∈FOLLOW(S)2)若G中有形如A→αBβ的產(chǎn)生式，且β≠ε，則將FIRST(β)中的一切非ε符號加進(jìn)FOLLOW(B)。3)若G中有形如A→αB或A→αBβ的產(chǎn)生式，且ε∈FIRST(β)，則FOLLOW(A)中的全部元素均屬于FOLLOW(B)。注意：在FOLLOW集合中無ε。

4.1.2回溯的消除及LL(1)文法例4.3，有文法E→TE’，E’→+TE’，E’→ε，

T→FT’，

T’→*FT’，T’→ε，F(xiàn)→(E)|i，求各非終結(jié)符號的FOLLOW集。解：首先，我們需要求出某些符號的FIRST集：

FIRST(E)=FIRST(T)=FIRST(F)={(，i}FIRST(E’)={+，ε}，F(xiàn)IRST(T’)={*，ε}

接下來，按FOLLOW集定義求各非終結(jié)符號的FOLLOW集：

FOLLOW(E)={)，#}，F(xiàn)OLLOW(E’)=FOLLOW(E)={)，#}FOLLOW(T)=FIRST(E’)∪FOLLOW(E)∪FOLLOW(E’)={+，)，#}FOLLOW(F)=FIRST(T’)∪FOLLOW(T)∪FOLLOW(T’)={+，*，)，#}FOLLOW(T’)=FOLLOW(T)={+，)，#}前進(jìn)4.1.3遞歸下降分析法

4.3.1遞歸下降分析的基本方法遞歸下降分析的概念極為簡單，其方法是將文法中的每一個(gè)非終結(jié)符U的文法規(guī)則看作是識別U的一個(gè)過程定義，為每個(gè)非終結(jié)符號構(gòu)造一個(gè)子程序，以完成該非終結(jié)符號所對應(yīng)的語法成分的分析和識別任務(wù)。如果U的文法規(guī)則的右部只有一個(gè)侯選式，則按從左向右的順序依次構(gòu)造規(guī)則U的識別過程代碼。如果有終結(jié)符號，判斷能否與輸入的符號相等，如果相等，表示識別成功，讀入指針指向下一個(gè)輸入符號；如果不等，則意味著輸入串此時(shí)有語法錯(cuò)誤。如果是非終結(jié)符號，則簡單調(diào)用這個(gè)非終結(jié)符號的子程序，由這個(gè)子程序完成該非終結(jié)符號所對應(yīng)的語法成分的分析和識別任務(wù)。當(dāng)一條規(guī)則右部有多個(gè)侯選式時(shí)，則根據(jù)每個(gè)侯選式的第一個(gè)符號確定該侯選式分支。只有被調(diào)用的分析和識別某語法成分的子程序匹配輸入串成功，且正確返回時(shí)，該語法成分才算真正獲得識別。

例4.4，考慮文法Z::=(U)|aUb

，U::=dZ|e，為其構(gòu)造遞歸下降分析子程序。并對輸入串a(chǎn)eb進(jìn)行語法分析。解：文法中有兩個(gè)非終結(jié)符號Z和U，那么我們需要分別編兩個(gè)過程來完成Z和U規(guī)則的識別。對于規(guī)則Z::=(U)|aUb，右部有兩個(gè)候選式，因此，U的識別過程有兩個(gè)分支，分別根據(jù)符號(和a來判別。同理對規(guī)則U::=dZ|e設(shè)計(jì)的過程也分為兩個(gè)分支。見圖4.1(a)和(b)所示。4.1.3遞歸下降分析法Z::=(U)|aUb過程ZINPUTSYM=下一個(gè)符號U出口語法錯(cuò)誤：輸入串少‘)’INPUTSYM=‘a(chǎn)’YNNNNYY語法錯(cuò)誤：輸入串少‘(’、‘a(chǎn)’語法錯(cuò)誤：輸入串少‘b’INPUTSYM=‘(’INPUTSYM=‘)’INPUTSYM=‘b’INPUTSYM=下一個(gè)符號INPUTSYM=下一個(gè)符號UY圖4.1(a)非終結(jié)符號Z的分析程序過程UINPUTSYM=下一個(gè)符號Z出口INPUTSYM=‘e’YNNY語法錯(cuò)誤：輸入串少‘d’、‘e’INPUTSYM=‘d’INPUTSYM=下一個(gè)符號YU::=dZ|e圖4.1(b)非終結(jié)符號U的分析程序4.1.3遞歸下降分析法每個(gè)非終結(jié)符號的子程序設(shè)計(jì)好后，就可以對輸入串進(jìn)行語法分析。假設(shè)輸入串為aeb,從Z子程序開始識別，INPUTSYM

=a,由于INPUTSYM不等于(，等于a，所以選擇Z子程序的右邊分支，表示選擇了Z::=aUb規(guī)則。讀下一個(gè)符號，使INPUTSYM

=e，調(diào)U子程序，因INPUTSYM=e，所以，讀下一個(gè)符號，使INPUTSYM

=b，表示使用U::=e規(guī)則，并返回調(diào)用程序Z子程序右邊分支U的下方，接著判斷INPUTSYM=b，讀下一個(gè)符號，并退出Z，分析過程結(jié)束，從而判定輸入串a(chǎn)eb語法分析成功。這個(gè)過程相當(dāng)于構(gòu)造了如下推導(dǎo)過程：

Z=>aUb=>aeb

4.1.3遞歸下降分析法E→T|E+T|E-TE→T{+T|-T}T→F|T*F|T/FT→F{*F|/F}ETYN出口INPUTSYM=下一個(gè)符號INPUTSYM=‘+’INPUTSYM=‘-’NYTFYN出口INPUTSYM=下一個(gè)符號INPUTSYM=‘*’INPUTSYM=‘/’NY圖4.2

E和T的分析程序4.1.4預(yù)測分析法LL(1)分析方法也是常見的自頂向下分析，LL(1)分析使用一個(gè)下推棧而不是遞歸調(diào)用來完成分析。名稱中第一個(gè)L表示自左向右順序掃描輸入符號串，第二個(gè)L表示分析過程產(chǎn)生一個(gè)句子的最左推導(dǎo)。括號中的1表示每進(jìn)行一步推導(dǎo)，只需要向前查看一個(gè)輸入符號，便能確定當(dāng)前所應(yīng)選用的規(guī)則。

LL(1)分析的基本方法LL(1)分析器由一個(gè)總控程序、一張分析表和一個(gè)分析棧組成，如圖4.4所示。輸入符號串：分析棧a1a2…………an#

XZS#LL（1）總控程序分析表輸出流圖4.4LL(1)分析器模型4.1.4預(yù)測分析法

輸入符號串:指要分析的輸入符號串。為了分析算法的統(tǒng)一，我們需要在輸入串的末尾放置一個(gè)特殊符號#，這個(gè)符號不屬于終結(jié)符號集。

分析表M:是一個(gè)二維表，可用一個(gè)二維數(shù)組M[A，a]來表示，它概括了文法的全部信息。分析表中的每一行與文法的一個(gè)非終結(jié)符號關(guān)聯(lián)，即A可以是文法中的一個(gè)非終結(jié)符號；而每一列則與文法的一個(gè)終結(jié)符號或#關(guān)聯(lián)，即a是文法的一個(gè)終結(jié)符號或#。分析表元素M[A，a]，指出了分析器應(yīng)采取的動作:或是指出當(dāng)前推導(dǎo)應(yīng)使用的產(chǎn)生式,或是指出輸入符號串存在語法錯(cuò)誤。對于不同的LL(1)文法，LL(1)的分析算法是相同的，不同的僅僅是分析表。顯然，如何根據(jù)文法來構(gòu)造分析表是LL(1)分析的關(guān)鍵。對于任意給定的已化簡的文法G，為了構(gòu)造分析表，首先我們要求出每個(gè)非終結(jié)符號的FOLLOW集合和每個(gè)后選式的FIRST集合。然后對文法G中的每個(gè)產(chǎn)生式A→y1|y2|…|ym，按下列規(guī)則確定分析表中的元素M：1)若a∈FIRST(yi)，則置M[A，a]=“yi”。2)若ε∈FIRST(yj)，且a∈FOLLOW(A)，則置M[A，a]=“yj”。3)除上述兩種情況外其余一切表元素均置為“ERROR”。

分析棧：用來存放一系列文法符號。分析開始時(shí)，先將#入棧，然后再將文法的開始符號入棧。

輸出流：分析過程中使用的產(chǎn)生式序列?？偪爻绦颍悍治銎鲗斎氪姆治隹靠偪爻绦蛲瓿?根據(jù)分析棧的棧頂符號X和當(dāng)前的輸入符號a，總控程序按照分析表的指示來決定分析器的動作.工作過程如下：第一步初始化:分析開始時(shí)，首先將符號#及文法的開始符號S依次置于分析棧的底部，并把各指示器調(diào)整至起始位置，如圖4.5所示。然后，反復(fù)執(zhí)行第二步的操作。輸入符號串：

a1a2…………an#分析棧：

S#圖4.5分析開始時(shí)狀況第二步假設(shè)分析的某一步，分析棧及余留的符號串如圖4.6，則根據(jù)棧頂?shù)姆朮m，采取下列動作：aiai+1…………an##X1X2…Xm-1Xm

圖4.6分析進(jìn)行中的狀況4.1.4預(yù)測分析法(1)若Xm∈Vn，則查分析表的Xm行ai列，假設(shè)M[Xm，ai]為產(chǎn)生式Xm→Y1Y2…Yk，則將Xm出棧，并將Y1Y2…Yk反序入棧，如圖4.7；若M[Xm，ai]為ERROR，則出錯(cuò)。aiai+1…………an##X1X2…Xm-1YkYk-1…Y1

圖4.7反序入棧(2)若Xm=ai≠#，表示棧頂與掃描的符號匹配，則棧頂符號Xm出棧，輸入指示器指向下一個(gè)符號，否則(即Xm≠ai)出錯(cuò)。(3)若Xm=ai=#，表示輸入串完全匹配，分析成功。

4.1.4預(yù)測分析法4.1.4預(yù)測分析法例4.5考慮算術(shù)表達(dá)式文法E→TE’，E’→+TE’，E’→ε，T→FT’，T’→*FT’，T’→ε，F(xiàn)→(E)|i對規(guī)則E→TE’：FIRST(TE’)={(，i}，那么在分析表的符號E所在的行、符號(和i所在的列對應(yīng)的位置分別填入TE’,見表4.1的E行。對規(guī)則E’→+TE’：FIRST(+TE’)={+}，所以在分析表E’行+列對應(yīng)的位置填入+TE’，見表4.1的E’行。對規(guī)則E’→ε：FOLLOW(E’)={)，#}，所以在分析表E’行)和#列對應(yīng)的位置填入ε，見表4.1的E’行?！瓕τ谝粋€(gè)文法，若按上述方法構(gòu)造的分析表M不含多重定義，則稱它是一個(gè)LL(1)文法。返回表4.1算術(shù)表達(dá)式分析表符號輸入符號i+*()#EE’TT’FTE’

FT’

i

+TE’ε

*FT’

TE’

FT’

(E)

ε

ε

ε

ε

表4.1算術(shù)表達(dá)式分析表4.1.4預(yù)測分析法根據(jù)表4.1給出的分析表，對符號串i+i*i進(jìn)行分析。表4.2符號串i+i*i的分析過程步驟分析棧余留輸入串所用產(chǎn)生式1234567891011121314151617#E#E’T#E’T’F#E’T’i#E’T’#E’#E’T+#E’T#E’T’F#E’T’i#E’T’#E’T’F*#E’T’F#E’T’i#E’T’#E’#i+i*i#i+i*i#i+i*i#i+i*i#+i*i#+i*i#+i*i#i*i#i*i#i*i#*i#*i#i#i####E→TE’T→FT’F→i

T’→εE’→+TE’

T→FT’F→i

T’→*FT’

F→i

T’→εE’→ε表4.2中輸出的產(chǎn)生式序列構(gòu)成對輸入符號串的最左推導(dǎo)。按此產(chǎn)生式序列構(gòu)造輸入符號串i+i*i的最左推導(dǎo)過程如下：E=>TE’

=>FT’E’

=>iT’E’

=>iE’

=>i+TE’

=>i+FT’E’=>

i+iT’E’

i+i*FT’E’

i+i*iT’E’

i+i*iE’

i+i*i

4.1.4預(yù)測分析法4.1.5某些非LL(1)文法的改造

對于任何LL(1)文法G,我們總能按上述方法為G構(gòu)造一個(gè)預(yù)測分析表,且構(gòu)造出的分析表決不會含有多重定義的元素.然而,對于非LL(1)文法,或因?yàn)樗鼈兒凶筮f歸,或因?yàn)樗鼈兇嬖诙x性,歸根結(jié)底因?yàn)樗鼈儾粷M足無回溯條件,則構(gòu)造出的分析表必然會出現(xiàn)多重定義的元素.例如,S→abBA→SC|BAA|εB→AbAC→B|cFIRST(S)={a}FOLLOW(S)={a,b,c,#}FIRST(A)={a,b,ε}FOLLOW(A)={a,b,c,#}FIRST(B)={a,b}FOLLOW(B)={a,b,c,#}FIRST(C)={a,b,c}FOLLOW(C)={a,b,c,#}M[A,a]={A→SC,A→BAA}M[A,b]={A→BAA,A→ε}可見分析表含有多重定義元素,2、解決二義性問題這個(gè)問題有時(shí)可通過反復(fù)提取公因子解決。對形如A→αβ1|αβ2|…|αβm的產(chǎn)生式,可改寫為A→αA’

A’→β1|β2|…|βm例如，規(guī)則：T→(E)|a(E)|a可改成：T→(E)|aT’，T’→(E)|ε

4.1.5某些非LL(1)文法的改造1、左遞轉(zhuǎn)成右遞歸

LL(1)分析不能處理左遞歸文法，但也不能像遞歸下降分析那樣將左遞歸改為采用擴(kuò)充BNF表示。在LL(1)分析中，必須將左遞歸文法變成右遞歸文法。例如，對左遞歸規(guī)則E→E+T|T，如果像遞歸下降分析那樣改成E→T{+T}無法形成逆序入棧，但可改成右遞歸：令E’為新的非終結(jié)符號，則等價(jià)的右遞歸規(guī)則為：E→TE’，E’→+TE’|ε實(shí)際上，在遞歸下降分析方法中，也可將左遞歸規(guī)則改成右遞歸進(jìn)行處理。4.1.5某些非LL(1)文法的改造但并非所有的文法都可用此法解決分析表的多重定義?？紤]有文法G[S]：S→AU|BR,A→aAU|b,B→aBR|b,U→c,R→d對于規(guī)則S→AU|BR，因?yàn)镕IRST(AU)∩FIRST(BR)≠φ，故該文法不是LL(1)文法。為了能夠提取公因子，必須將非終結(jié)符號A、B的產(chǎn)生式帶入S的產(chǎn)生式中，得到：S→aAUU|bU|aBRR|bR經(jīng)提取公因子后，得到S→a(AUU|BRR)|b(U|R),令S’、S”分別代替括號中的左右部分，得如下等價(jià)文法：S→aS’|bS”,S’→AUU|BRR,S”→U|R,A→aAU|b,B→aBR|b,U→c,R→d顯然，對于規(guī)則S’→AUU|BRR，因?yàn)镕IRST(AUU)∩FIRST(BRR)≠φ，故它仍然不是LL(1)文法。且無論重復(fù)多少次提取公因子，都不能把它變成LL(1)文法。由于遞歸下降分析法也存在這類問題，所以，自頂向下分析方法無法對這類文法進(jìn)行語法分析。4.1.5某些非LL(1)文法的改造我們把能由某一LL(1)文法產(chǎn)生的語言稱為LL(1)語言。LL(1)文法具有下列性質(zhì)：1)任何LL(1)文法都是無二義的。2)若文法中有左遞歸，肯定不是LL(1)文法。但有些左遞歸文法可轉(zhuǎn)換成右遞歸文法，從而滿足LL(1)文法的要求。3)存在一種算法，能判定文法是否為LL(1)文法。4)存在一種算法，能判定任意兩個(gè)LL(1)文法是否產(chǎn)生相同的語言。5)不存在這樣的算法，判定任意上下文無關(guān)語言能否由LL(1)文法產(chǎn)生。6)非LL(1)語言是存在的。在LL系列分析方法中，若每一步推導(dǎo)不是向前看一個(gè)字符，而是看K個(gè)字符才能確定要選用的產(chǎn)生式，則稱為LL(K)分析，能滿足LL(K)分析條件的文法叫LL(K)文法。習(xí)題4.1對下面文法，設(shè)計(jì)遞歸下降分析程序。

S→aAS|(A),A→Ab|c4.2設(shè)有文法G[Z]：

Z∷=(A),A∷=a|Bb,B∷=Aab若采用遞歸下降分析方法，對此文法來說，在分析過程中，能否避免回溯？為什么？4.3若有文法如下，設(shè)計(jì)遞歸下降分析程序。

<語句>→<語句><賦值語句>|ε<賦值語句>→Id=<表達(dá)式>；

<表達(dá)式>→<項(xiàng)>|<表達(dá)式>+<項(xiàng)>|<表達(dá)式>-<項(xiàng)><項(xiàng)>→<因子>|<項(xiàng)>*<因子>|<項(xiàng)>/<因子><因子>→ID|NUM|(<表達(dá)式>)4.4有文法G[A]：A::=aABe|εB::=Bb|b1)求每個(gè)非終結(jié)符號的FOLLOW集。

2)該文法是LL(1)文法嗎？

3)構(gòu)造LL(1)分析表。4.5若有文法A→(A)A|ε，

1)為非終結(jié)符A構(gòu)造First集合和Follow集合。

2)說明該文法是LL(1)的文法。4.6利用分析表4.1識別以下算術(shù)表達(dá)式，請寫出分析過程：

1)i+i*i+i2)i*(i+i+i)習(xí)題4.7考慮下面簡化了的C聲明文法：

<聲明語句>→<類型><變量表>；

<類型>→int|float|char<變量表>→ID,<變量表>|ID1）

在該文法中提取左因子。2）

為所得的文法的非終結(jié)符構(gòu)造First集合和Follow集合。3）

說明所得的文法是LL(1)文法。4）

為所得的文法構(gòu)造LL(1)分析表。5）

假設(shè)有輸入串為:charx,y,z，寫出相對應(yīng)的LL(1)分析過程。習(xí)題4.8修改語法分析程序，使該程序能分析do語句和邏輯表達(dá)式,有關(guān)文法規(guī)則如下：

<statement>::=if_stat>|<while_stat>|<do_stat>|<for_stat>|<read_stat>

|<write_stat>|<command_stat>|<expression_stat><do_stat>::=do<statement>while<expression>;<expression>::=ID=<log_expr>|<log_expr><log_expr>::=<log_expr>(&&|||)<bool_expr>|!<log_expr>|<bool_expr>&&、||、!為邏輯運(yùn)算符。習(xí)題4.2自底向上的語法分析主要內(nèi)容：概述簡單優(yōu)先分析法算符優(yōu)先分析法優(yōu)先函數(shù)LR分析法自頂向下語法分析：對給定的輸入符號串，從方法的開始符號出發(fā)，為其構(gòu)造一個(gè)推導(dǎo)過程，試圖自上而下地構(gòu)造一棵語法樹。最常用的推導(dǎo)方法最左推導(dǎo)，即對于一個(gè)推導(dǎo)過程中的每一步，被替換的總是當(dāng)前句型中最左端的非終結(jié)符號。常用的自頂向下的語法分析方法：１）遞歸下降法２）LL(1)分析法概述

例：有文法G[S]：

(1)S→

aAcBe(2)A→

b(3)A→

Ab(4)B→

d試分析符號串a(chǎn)bbcde是否為該文法的句子。

解：首先，我們從文法的開始符號進(jìn)行規(guī)范推導(dǎo)，依次使用1、4、3、2規(guī)則，就可得到符號串a(chǎn)bbcde。規(guī)范推導(dǎo)過程如下：S=>aAcBe=>aAcde=>aAbcde=>abbcde

概述從符號串開始，向上歸約，如果最終能夠規(guī)約到文法的開始符號S，則同樣可以說明該輸入符號串是這個(gè)文法的句子。其歸約過程如下圖所示。ScBcAaAbdbScBcAaAbdScBcAadScBcAaS

(a)b歸約為A(b)Ab歸約為A(c)d歸約為B(d)aAcBe歸約為S(e)歸約過程概述自底向上語法分析：從輸入符號串開始，通過反復(fù)查找當(dāng)前句型的句柄，并使用規(guī)則，將找到的句柄歸約成相應(yīng)的非終結(jié)符號，直到歸約到開始符號，從而自底向上地為輸入符號串構(gòu)造一棵語法分析樹。自底向上分析方法，也可稱為移進(jìn)-歸約法

(1)四個(gè)動作：移進(jìn)，歸約，接受，報(bào)錯(cuò)

(2)分析棧：用于存放從輸入符號串移進(jìn)或歸約生成的符號。

(3)從左到右讀入輸入符號串的各個(gè)符號，并依次入棧，當(dāng)棧頂符號串形成一個(gè)句柄時(shí)，就進(jìn)行一次歸約，即把棧頂構(gòu)成句柄的若干符號用相應(yīng)產(chǎn)生式左部的非終結(jié)符號來代替，也就是把句柄符號串從出棧，再把產(chǎn)生式左部的非終結(jié)符入棧。

(4)最后，其分析棧里只有界符#及方法的開始符號，則所分析的符號串為合法的句子，報(bào)告成功；否則，輸入串非法，報(bào)告錯(cuò)誤。概述步驟

分析棧

余留符號串

下步動作

０123456*7*89101112##b#bb#bba#bbA#bA#A#Aa#Aac#AaS#AaSb#AB#Sbbaacb#baacb#aacb#acb#acb#acb#acb#cb#b#b####移進(jìn)移進(jìn)移進(jìn)按A→a歸約用A→bA歸約用A→bA歸約移進(jìn)移進(jìn)用S→c歸約移進(jìn)用B→aSb歸約用S→AB歸約分析成功表4.４輸入串bbaacb的“移進(jìn)-歸約“分析過程通過上述分析可看出，每次歸約的句柄都出現(xiàn)在符號棧的棧頂，不會出現(xiàn)在棧的中間，因?yàn)槲覀兊乃惴ㄊ亲宰笙蛴覓呙栎斎敕柎?，進(jìn)行的是最左歸約。概述

方法G[S]:(1)S→

AB(2)S→

c(3)A→

bA(4)A→

a(5)B→

aSb(6)B→

c兩個(gè)關(guān)鍵問題：１）如何確定句柄２）句柄確定后，如何確定選用哪一條規(guī)則，即產(chǎn)生式兩種常用的自底向上語法分析方法：１）優(yōu)先分析法（簡單優(yōu)先分析法、算符優(yōu)先分析法）２）LR分析法概述4.2.1簡單優(yōu)先分析法

優(yōu)先法的基本思想是根據(jù)歸約的先后次序?yàn)橥痪湫椭械南噜徫姆ǚ栆?guī)定相應(yīng)的優(yōu)先關(guān)系(<,=,>），從而構(gòu)造一個(gè)優(yōu)先矩陣。以后在分析一個(gè)句型(指規(guī)范句型)

α=X1X2…Xi-1XiXi+1…Xi+kXi+k+1…Xm

時(shí)，將從左到右一次掃視α中的符號，且每掃視一個(gè)符號Xi都以其后繼符號Xi+1查優(yōu)先矩陣，判明它們之間的優(yōu)先關(guān)系，以期找到α的句柄之尾符號，然后再從尾符號開始進(jìn)行反向掃描，直至找到α的句柄之頭符號為止?？梢宰C明，此時(shí)α中滿足Xi-1<XiXi=Xi+1=…Xi+kXi+k>Xi+k+1的最左子串XiXi+1…Xi+k便是規(guī)范句型α的句柄。于是按相應(yīng)產(chǎn)生式A→XiXi+1…Xi+k將句柄規(guī)約為A，則得到新的句型

α’=X1X2…Xi-1AXi+k+1…Xm再對α’重復(fù)上述操作，并最終將其歸約為文法的開始符號。簡單優(yōu)先文法：

(1)每一對文法符號U和R之間，至多只有一種優(yōu)先關(guān)系;

(2)任意兩個(gè)不同的產(chǎn)生式均無相同的右部。4.2.1簡單優(yōu)先分析法設(shè)G=(VN,VT,P,S)是一已化簡的文法，V=VN

∪VT，并設(shè)Si和Sj是V中的任意兩個(gè)符號，若G中存在這樣的規(guī)范句型

α=…SiSj…則此相鄰符號Si，Sj和α的句柄之間的關(guān)系必然是下述情況之一:(1)若Si在句柄中，而Sj不在句柄中(如圖(a)所示)，則Si顯然為句柄的尾符號，故G中必有形如A→…Si的產(chǎn)生式，使Si先于Sj被歸約。記為Si>Sj。

(2)若Si與Sj同時(shí)處于句柄中(如圖(b)所示)，則G中必有形如A→…SiSj…的產(chǎn)生式，使Si和Sj同時(shí)被歸約。記為Si=Sj。當(dāng)且僅當(dāng)G中有形如U→…ASj…的產(chǎn)生式,且有A=+>…Si當(dāng)且僅當(dāng)G中有形如U→…SiSj…的產(chǎn)生式4.2.1簡單優(yōu)先分析法(3)若Sj在句柄中，而Si不在句柄中(如圖(c)所示)，則Sj顯然為句柄的頭符號，故G中必有形如A→Sj…的產(chǎn)生式，使Sj先于Si被歸約。記為Si<Sj。(a)(b)(c)ASiSj………ASiSj……ASiSj………當(dāng)且僅當(dāng)G中有形如U→…SiA…的產(chǎn)生式,且有A=+>Sj…需要注意的是：上述三種優(yōu)先關(guān)系都是對方法中的符號序偶來定義的，都不具有對稱性，即若Sr>St，并不一定有St<Sr，即使存在Sr＝St，也并不意味著St<Sr4.2.1簡單優(yōu)先分析法

解:顯然有E1=++=T1T=**=F(=EE=)

考慮E1→E1+T1∵E1=+>E1+T1E1=+>T1

E1=+>TE1=+>T*FE1=+>FE1=+>(E)E1=+>i

∴T1,T,F,),i>+∵T1=+>TE1=+>T*FE1=+>FE1=+>(E)E1=+>i

∴+<T,F,(,i

考慮T→T*F∵T=+>T*FT=+>FT=+>(E)T=+>i∴F,),i>*∵F=+>(E)F=+>i

∴*<(,i

考慮F→(E)∵E=+>E1E=+>E1+T1E=+>T1E=+>TE=+>T*FE=+>FE=+>(E)E=+>i∴(<E1,T1,T,F,(,i∴E1,T1,T,F,),i>)例4.4給出文法G’[E]的全部優(yōu)先關(guān)系和符號串i+i*i的分析過程

E→E1E1→E1+T1∣T1T1→TT→T*F∣FF→(E)∣i按照這種方式建立的優(yōu)先矩陣如圖4-4所示。需要指出的是用這種方式優(yōu)先矩陣雖然直觀，但對于規(guī)模稍大的方法而言顯然是不可行的。4.2.1簡單優(yōu)先分析法

在簡單優(yōu)先方法中，進(jìn)行語法分析時(shí)，為了尋找一個(gè)句型的句柄的頭符號和尾符號，只須逐次查看相鄰兩個(gè)符號間的優(yōu)先關(guān)系即可。具體方法：從左至右依次掃描句型中的符號X1X2…Xm，并在掃描過程中檢查相信兩符號間的優(yōu)先關(guān)系，一旦出現(xiàn)Xi+k>Xi+k+1時(shí)，此Xi+k即為句柄的尾符號。接下來從Xi+k開始，從右至左逐個(gè)查看已掃過的符號，直到某相鄰兩個(gè)符號間有優(yōu)先關(guān)系Xi-1<Xi時(shí)，此Xi為句柄的頭符號。即對于簡單優(yōu)先方法的任何規(guī)范句型X1X2…Xm而言，其句柄是該句型中，滿足：

Xi-1<Xi

Xi=Xi+1=…=Xi+k

Xi+k>Xi+k+1的最左子串XiXi+1…Xi+k具體算法如程序4-4所示4.2.1簡單優(yōu)先分析法

程序4-4簡單優(yōu)先分析驅(qū)動程序#defineSUCCESS1#defineERROR0#defineMAXINPUT300#defineMAXSTACK100#defineSTARTSYMBOL‘S’int

stack[MAXSTACK],a[MAXINPUT];int

IsHigherThan(int,int);int

IsLowerThan(int,int);int

RightSideOfAProduction(int

begin,int

end,int

len);int

parser(void){int

i,k,r;i=0;k=0;stack[0]=‘#’;r=a[k++];

do{int

j,LeftSide;

while(!IsHigherThan(stack[i],r)){stack[++i]=r;r=a[k++];}j=i;while(!IsLowerThan(stack[j-1],stack[j]))j--;

LeftSide=RightSideOfAProduction(stack[j],stack[i],i-j+1);

if(LeftSide){i=j;stack[i]=LeftSide;}elseifi==1&&r==‘#’&&stack[i]==STARTSYMBOL)returnSUCCESS;elsereturnERROR;}while(1);}4.2.1簡單優(yōu)先分析法表4.５符號串i+i*i的移進(jìn)-歸約分析過程步驟分析棧優(yōu)先關(guān)系r余留輸入串句柄歸約產(chǎn)生式0#<i+i*i#1#i>+i*i#iF→i2#F>+i*i#FT→F3#T>+i*i#TT1→T4#T1>+i*i#T1E1→T15#E1=+i*i#6#E1+<i*i#7#E1+i>*i#iF→i8#E1+F>*i#FT→F9#E1+T=*i#10#E1+T*<i#11#E1+T*i>#iF→i12#E1+T*F>#T*FT→T*F13#E1+T>#TT1→T14#E1+T1>#E1+T1E1→E1+T115#E1>#E1E→E116#E>#(分析成功)4.2.1簡單優(yōu)先分析法

簡單優(yōu)先分析的局限性簡單優(yōu)先分析對文法有較強(qiáng)的要求，通常文法的符號對間的優(yōu)先關(guān)系會多于一種，特別是遞歸文法。例如，文法中同時(shí)存在形如

U→…SiSj…Sj→Sj…的產(chǎn)生式，在符號Si和Sj之間，便同時(shí)存在Si=Sj和Si<Sj兩種關(guān)系。有的文法可通過分層法(析出法)來消除多重優(yōu)先關(guān)系。改寫為

U→…SiW…W→Sj…但當(dāng)兩者間既有“<”關(guān)系也有“>”關(guān)系，上述方法就不能奏效。簡單優(yōu)先分析局限性的根本原因在于局限于考察相鄰兩個(gè)符號的優(yōu)先關(guān)系，如果我們查看更多的符號(如LR(K)分析)，或者考察不相鄰的兩個(gè)符號(如算府優(yōu)先分析)，則上述矛盾的情況將會得到改善。4.2.2算符優(yōu)先分析法算符優(yōu)先分析法，僅在廣義運(yùn)算符(即文法的終結(jié)符號)間定義優(yōu)先關(guān)系。定義4.2

若在一個(gè)文法G中，不含有形如

U→…AB…的產(chǎn)生式，其中A，B∈VN

，則稱G為算符文法?？梢?算符文法G的任何產(chǎn)生式右部,都不會出現(xiàn)兩非終結(jié)符號相鄰的情況。在算符文法的任何句型中,兩相鄰終結(jié)符之間的非終結(jié)符至多只有一個(gè)。中綴表達(dá)式是滿足這一條件的一種廣義運(yùn)算，事實(shí)上程序設(shè)計(jì)語言中廣泛使用的也恰是中綴表達(dá)式，但也有些語法成分的定義不滿足這一條件。定義4.3

當(dāng)且僅當(dāng)G中有形如

U→…ab…或U→…aAb…的產(chǎn)生式時(shí)，a=b。4.2.2算符優(yōu)先分析法定義4.4

當(dāng)且僅當(dāng)G中有形如U→…aA…的產(chǎn)生式,且有

A=+>b…或A=+>Bb…時(shí)，

a<b。定義4.5

當(dāng)且僅當(dāng)G中有形如U→…Ab…的產(chǎn)生式,且有

A=+>…a或A=+>…aB時(shí)，a>b。定義4.6

設(shè)G為一算符文法，若G的任何一對終結(jié)符號之間，至多只有三種算符優(yōu)先關(guān)系=、<和>之一成立，則稱G為算符優(yōu)先文法。FIRSTVT(A)={b∣A=+>b…或A=+>Bb…}LASTVT(A)={a∣A=+>…a或A=+>…aB}4.2.2算符優(yōu)先分析法

在用算符優(yōu)先分析法進(jìn)行語法分析時(shí)，每次歸約的不再是句型的句柄，而是它的最左素短語。所謂素短語，是指其中至少還有一個(gè)終結(jié)符號,且不再含有其他素短語的短語。例如EE+TE+TTT*FFi句型T+T*F+i的語法樹對于句型T+T*F+i：短語：T,T*F,T+T*F,T+T*F+i,i素短語：T*F,I句柄：T4.2.2算符優(yōu)先分析法

可以證明，對于G的句型

α=#N1a1N2a2…NjajNj+1aj+1…Nj+kaj+k…NnanNn+1#其中#為界符，ai∈VT，Ni∈VN，它的最左素短語是滿足關(guān)系

aj-1<ajaj=aj+1=…aj+kaj+k>aj+k+1的最左子串NjajNi+1aj+1…Nj+kaj+kNj+k+1。因此，可按與簡單優(yōu)先分析相似的過程找到一個(gè)句型的最左素短語。算符優(yōu)先文法僅在終結(jié)符號之間定義優(yōu)先關(guān)系，完全不考慮非終結(jié)符號，故顯然不能識別句型中只由一個(gè)非終結(jié)符號組成的句柄，也就是全然不考慮按單產(chǎn)生式進(jìn)行歸約，因此，每次找到的最左素短語就不一定是句型的句柄，因而此最左素短語也就可能不是相應(yīng)文法的任何產(chǎn)生式的右部。所以,我們按“同形即可歸約”的策略來歸約。4.2.2算符優(yōu)先分析法構(gòu)造算符優(yōu)先矩陣的一般方法(1)對文法的每一非終結(jié)符號構(gòu)造FIRSTVT集和LASTVT集，算法分別如下

ⅰ)構(gòu)造FIRSTVT集，置FIRSTVT(A)=φ

若文法中有形如A→b…或A→Bb…的規(guī)則，則b∈FIRSTVT(A)

若文法中有形如A→B…的規(guī)則，則FIRSTVT(B)∈FIRSTVT(A)ⅱ)構(gòu)造LASTVT集，置LASTVT(A)=φ

若文法中有形如A→…a或A→…aB的規(guī)則，則a∈LASTVT(A)

若文法中有形如A→…B的規(guī)則，則LASTVT(B)∈LASTVT(A)(2)ⅰ)形如…aA…的規(guī)則右部，a<FIRSTVT(A)ⅱ)形如…Ab…的規(guī)則右部，LASTVT(A)>bⅲ)形如…ab…或…aAb…的規(guī)則右部，a=b(3)#<FIRSTVT(S)LASTVT(S)>#4.2.2算符優(yōu)先分析法考慮E→E+T

+,*,),i>++<*,(,i考慮T→T*F*,(,i>**<(,i考慮F→(E)(<+,*,(,I+,*,),i>)(=)考慮##<+,*,(,i+,*,),i>#例：構(gòu)造文法G[E]的算符優(yōu)先矩陣和符號串i+i*i的分析過程

E→E+T∣TT→T*F∣FF→(E)∣i解:首先求各非終結(jié)符號的FIRSTVT集和LASTVT集FIRSTVT(F)={(,i}FIRSTVT(T)={*}∪FIRSTVT(F)={*,(,i}FIRSTVT(E)={+}∪FIRSTVT(T)={+,*,(,i}LASTVT(F)={),i}LASTVT(T)={*}∪LASTVT(F)={*,),i}LASTVT(E)={+}∪LASTVT(T)={+,*,),i}+*()i#+><<><>*>><><>(<<<=<)>>>>i>>>>#<<<<表4.8G[E]的算符優(yōu)先矩陣4.2.2算符優(yōu)先分析法表4.6符號串i+i*i的算符優(yōu)先分析過程步驟當(dāng)前句型及優(yōu)先關(guān)系當(dāng)前應(yīng)被歸約的最左子串歸約所得到符號1#<i>+i*i#iF2#<F+<i>*i#iF3#<F+<F*<i>#iF4#<F+<F*F>#F*FT5#<F+T>#F+TE6#E#分析成功4.2.2算符優(yōu)先分析法算符優(yōu)先分析中的重要事實(shí)：１）按算符優(yōu)先關(guān)系所確定的應(yīng)被歸約的子串恰好是當(dāng)前句型的最左素短語。２）盡管算符優(yōu)先分析也屬于自底向上語法分析的范疇，但卻不嚴(yán)格從左至右的規(guī)范分析，每步所得的句型自然也不是一個(gè)規(guī)范句型３）盡管分析時(shí)，指出了每一個(gè)最左素短語應(yīng)歸約到的非終結(jié)符號，但每次在查找最左素短語時(shí)，起主導(dǎo)作用的是終結(jié)符號間的優(yōu)先關(guān)系，兩終結(jié)符號間空間是哪種優(yōu)先關(guān)系與非終結(jié)符號并無關(guān)聯(lián)，故在進(jìn)行算符優(yōu)先分析時(shí)，隨意給歸約到的非終結(jié)符號命名也是可以的。４）具體算法如程序4-5所示。4.2.3優(yōu)先函數(shù)為了節(jié)省存儲空間，同時(shí)便于比較，我們將優(yōu)先矩陣線性化，構(gòu)造兩個(gè)離散函數(shù)f和g，滿足

當(dāng)Si<Sj時(shí)，f(Si)<g(Sj)

當(dāng)Si=Sj時(shí)，f(Si)=g(Sj)

當(dāng)Si>Sj時(shí)，f(Si)>g(Sj)f和g分別稱為入棧(前)優(yōu)先函數(shù)和比較(后)優(yōu)先函數(shù)。(1)不是所有的優(yōu)先矩陣都能線性化。(2)若優(yōu)先函數(shù)存在，則不唯一。(3)當(dāng)一個(gè)優(yōu)先矩陣線性化后，就對每一對符號都賦予了一對優(yōu)先數(shù)。這樣，對于原先不存在優(yōu)先關(guān)系的符號對，也可以比較優(yōu)先關(guān)系了,就可能掩蓋(至少推遲發(fā)現(xiàn))輸入串中的語法錯(cuò)誤。對此問題，需通過其他語法檢查手段解決。4.2.3優(yōu)先函數(shù)下面介紹兩種優(yōu)先矩陣線性化的方法。一.有向圖法(Bell方法)設(shè)已給的優(yōu)先文法G[S]有n個(gè)符號S1

，S2

，…Sn

，如果優(yōu)先函數(shù)存在，則可如下構(gòu)造:(1)對于每一Si

，分別作以fi和gi為標(biāo)記的結(jié)點(diǎn)，并按如下方式構(gòu)造以f1

，f2

，…fn及g1

，g2

，…gn為結(jié)點(diǎn)的有向圖:

若有Si>Sj或Si=Sj

，則從結(jié)點(diǎn)fi引一條至結(jié)點(diǎn)gj的矢線;若有Si<Sj或Si=Sj，則從結(jié)點(diǎn)gj引一條至結(jié)點(diǎn)fi的矢線。(2)對每個(gè)結(jié)點(diǎn)都賦予一個(gè)整數(shù)，此整數(shù)就是從該結(jié)點(diǎn)出發(fā)，沿著矢線所能到達(dá)的結(jié)點(diǎn)個(gè)數(shù)(包括出發(fā)結(jié)點(diǎn)在內(nèi))

，賦給結(jié)點(diǎn)fi的整數(shù)就是f(Si)

;賦給結(jié)點(diǎn)gi的整數(shù)就是g(Si)。(3)對f和g進(jìn)行檢驗(yàn)，若它們與原優(yōu)先關(guān)系相容，則f和g即為所求的優(yōu)先函數(shù);否則，原優(yōu)先矩陣就不能線性化。4.2.3優(yōu)先函數(shù)二.構(gòu)造優(yōu)先函數(shù)的Floyd方法(1)首先，給f和g賦初值，即對每一符號Si

，置

f(Si)=g(Si)=1(2)進(jìn)行迭代，即對每一符號對(Si,Sj):ⅰ)若有Si>Sj，但有f(Si)≤f(Sj)，則執(zhí)行f(Si)=g(Sj)+1;ⅱ)若有Si<Sj，但有f(Si)≥f(Sj)，則執(zhí)行g(shù)(Sj)=f(Si)+1;ⅲ)若有Si=Sj

，但有f(Si)≠f(Sj)，則令f(Si)和g(Sj)中的最小者等于最大者

。(3)重復(fù)步驟(2)，直到過程收