第5章自底向上的自頂向下(TopDown)的分析自底向上(BottomUp)的分析1PAGEPAGE7自底向上分 文法為 句子分析句子分析 abbcd回憶幾個概短語如果Ｓ*αAβandA+γ，則稱γ是句型αγβ的相對于直接(簡單)如果Ｓ*αAβandAγ，則稱γ是句型αγβ的相對于變量A的直接(簡單)短語(immediatephrase)句柄回憶幾個概規范歸設α為文法G的句子，如①α=αnαn-每個i(1<i≤n)，αi-1是將句型αi中的句則稱序列αn，...，α1為α的規范歸約語法分析樹的生成再演——SA

A

B abbcdeB→d A→bbA→Ab

是什么關

abbcde

B→dd A→b A→Ab d

棧內容特點：不含當前句型棧內容特點：不含當前句型的句柄后的任何符

棧+棧+輸入緩沖區剩余=#當前“句?棧中內分析設想——分析器框控制分析進程，輸出分析結果——產生式序保存輸入符號(token)保存語法符號——已經處理的部分結果(前綴棧棧內容+輸入緩沖區內容＝前“句型”#棧內不含當前句型的句柄后的任何符分析控制分析控制程棧輸入緩沖區(符號序列idid+id＊id控制程棧內容+輸入緩沖區內容＝前“句型”#棧內不含當前句型的句柄后的任何符分析設想——系統運開始格棧：#；輸入棧壓入棧移進歸約正常結束格#S，輸入緩沖區系系統如何發現句柄已經在棧頂E→idE→(E)E→E+E→EE→idE→(E)E→E+E→E*EEE→E→idEE→E→idE→E→E*EE→E+ 例分析過程動 輸入緩沖初始 移 歸約 移 移 歸約 移 移 歸約 歸約 歸約

Eid1

E→idE→E→idE→E→E+E→E*E id2E

EEE id3分析器的四種動移進：將下一輸入符號移入接受：分析成出錯：出錯處回回頭想想——決定移進和歸約的依據是什編譯原(Principlesof 講：上次課主要內+T語法+T記的語法符號可以看 0T3邊，表示處理程序對0T36ε6作上次課主要內**0T3ε6E7F7F T(E)上次課主要內遞歸子程序上次課主要內自底向上的分“句柄”是否在棧頂形上次課主要內系統框

控制程id+控制程

例分析過程動 輸入緩沖初始 移 歸約 移 移 歸約 移 移 歸約 歸約 歸約E→E+E

Eid1

EEE→idE→E→EEE→idE→E→E+E→E*

EEE id3

移進歸約分析中的問第6步#E+id2據E→id對id2歸約之 移第7步可以移進移 也可以按產生式E→E+E歸歸 移進歸約分析中的問歸約歸約存在兩個可用的產生AabbcAabbcdeAabbcd不同分析方法處理方法不如何識別句柄利用

根據歸約的先后次序為句型中相鄰的符號規定優先關a1…ai-1≮ai≡ai+1≡…≡aj-狀態

E→idE→(E)E→E+E→E*句柄是否形成=例如：E→E+E 等待歸約出 等待移進 等待歸約出 句柄已經形成，歸約出新的 算符優先分析算術表達式分析的啟算符優先關系的直觀意 +的優先級低于 的優先級等于+ +(左邊)的優先級高于+(右邊方算術表達式文法的再分句型句型的特征(E+E)*(E-這些算符之間存在優先算符文如果文法G=(V,T,P,S)中不存在形的產生式，則稱之為算符文法(OGOperator即：如果文法G中不存在具有相鄰非終結符算符間的優先關間(a，b在后)的優先關系如下a≡bA→…ab…∈Pa≮bA→…aB…∈P且(B+b…或者a≯bA→…Bb…∈P且(B+…a或者算符優先文對OGG=(V，T，P，S)，如果a,b∈T,a≡b,a≮b,a≯b至多有一個成立，則稱之為算符優先文法(OPG—OperatorPrecedenceGrammar)在無ε產生式的算符文法中，如果任意兩個終結符之間至多有一種優先關系，則稱為算符優先文法存在優先+≮存在優先+≮*id≯+≮id≯+≯*≯↑≯*id≯*#≮≯E→E+｜E-｜E*｜E/｜｜(E｜例直觀的算符優先

≮≮??≮≮≮??≮≮≮得到這張表≯≯≮≮≮

≮≮≮ 算符優先關系的確優先關系的確a≮bB→…aA…∈P且(A+b…或者需求出非終結符A派生出的a≯bB→…Ab…∈P且(A+…a或者需求出非終結符A派生出的最后一個終結符構成的集對于OGG=(V,T,P,S)，定FIRSTOP(A)={b|A+b…或者LASTOP(Ab|A+…b或者求FIRSTOP和初值(掃描所有產生式ifA→a…∈P或A→Ba…∈P

ifA→…a∈P或AaB迭代(掃描所有產生式

ifA→B…∈P

將FIRSTOP(B)ifA→…B∈Pthen將LASTOP(B)設設計程序：求FIRSTOP、E→E+T|E-T|TT→T*F|T/F|F量量E+ - id / * )E+-id/* )/*F()F())*id/*T具體)*id/*T算符優先關系的確如果A→…ab；A→…aBb…，如果則對如果則對算符優先關系表的構造如果XiXi+1∈TT則如果XiXi+1Xi+2∈TVT則如果XiXi+1∈TV則如果XiXi+1∈VT則a∈LASTOP(Xi)，E→E+T|E-T|TT→T*F|T/F|F語法變 +,-,*,/,(, +,-,*,/,), *,/,(, *,/,), (, ),

≯≯≮≮≮

id

id

E→E+T|E-例分E→E+T|E-#≮id≯+id*id#≮F+≮id≯*id#≮F+≮F*≮id#≮F+≮F*≮id≯#≮F+≮F*F#≮F+≮F*F≯#≮F+T≯#E問有時未歸約真正的句柄不是嚴格最左歸歸約的符號串有時與產生式右部仍能正確識別句子的原OP未定義非終結符之間的優先關系，不能識別由單一非終結符組成的句柄算符優先分析過程識別的“句柄”為最短(LPP：LeftmostPrime素短語與最短素短語(Primeγ是短語：S*αAβandγ至少含一個終結且不含更小的含終結符的短稱γ是句型αγβ的相對于變量A的素短E→E+T|TT→T*F|F 句型F+T*F+id的短語有 T*F為最短語，是

歸約的對 F+T*F EEEEEEEEEEid+E*id+文法間句型”的 素短語與最短設句型的一般形#N1a1N2a2…Nnan#(Ni∈V∪{ε},ai它的最短語是滿足下列條件的最左子NiaiNi+1ai+1…Njaj其中：ai-ai≡ai+1≡…≡aj-1≡aj編譯原(Principlesof 講：上次課主要內基本動作——移進、歸約、接受、出處移進歸歸約歸上次課主要內優先a1…ai-1≮ai≡ai+1≡…≡aj-根據優先級比較的結果決定移近、歸上次課主要內算符優先文優先關系的定a≡bA→…ab…∈Pa≮bA→…aB…∈P且(B+b…或者a≯bA→…Bb…∈P且(B+…a或者上次課主要內算符優先文法(OPG)a≡b，a≮b，a≯b至對每個語法變量求FIRSTOP和ifA→a…∈P或A→Ba…∈PthenifA→…a∈P或A→…aBthenifA→B…∈PthenFIRSTOP(B)放入ifA→…B∈PthenLASTOP(B)放入上次課主要內對順序Xi≡Xi+1/Xi≡Xi+2(Xi+1是變量Xi+1是變量 aXi是變量 a算符的棧內/外優先級比上次課主要內被歸約對#N1a1N2a2…NiaiNi+1ai+1…NjajNj+1aj+1…Nnan其中：ai-ai≡ai+1≡…≡aj-1≡aj最短素短語：短語、含終極符、最算符優先函算符優先分析算原理：識別句柄并歸a1…ai-1≮ai≡ai+1≡…≡aj-首先利用≯找到“句柄”尾，再回頭利≮比較棧頂和下一輸入符號的關系，如果是找到后彈出“句柄”，歸約為非終結符算符優先分析的系統組移進歸約分析器+優先關系分析算法參照輸入串、優先關系表，完成一系列歸約，生成語法分析樹——輸出產生id+id*id的分析過id+id*id和運算符棧？是否有更簡單的比較優先級的

E→idE→idE→E→E*E→E+算符優先函f(a)<g(b)，如果af(a)=g(b)，如果af(a)>g(b)，如果a優點：節省空間(n2→2n)便于執行比較運如：id≯id不存在，但f(id)與g(id)算符優先函例E→E+E|E-ffg+21-21*43/43↑45(05)60構造優先函數的算法不是唯一aT{#},建立兩個結點fa和a，b 若ab或者ab則從fa至gb 若ab或者a≡b則從gb至fa畫一條弧若圖中無環，則存在優先函f(a)和g(b)等于從fa和gb+*#+≮≯≯≯≮≯≯*≮≯≯≯#≮≮≮+*#f4240g5130優

算符優先分析法優缺缺習題P2116、9.1、練習：給出布爾表達式的文法，構造其算優先關系BE→BEorBT|BT→BTandBF|BF→notBP→(BE)|true|算符優先分析法的改進必須是算符優先文法：文法書寫限制 如何根據希望設計分析文能否利用產生式去分析的“進程”——LR(Left-Right)例

S→

(ε-)閉(ε-)閉添加S'→S：S'→.S(分析開始，S'→S.(分析成功5.35.3LR(Left-Right)LR(k)分析從語言的文法描述入手，探討當前“規范L：從左R：最右推導對應的最左歸約k：超前讀入k個符號，以確定歸約用的產為語法分析器的自動生成提供了基文法G=(V,T,P,S)的(Augmented)文G'=(V∪{S'},T,P∪{S'→S},S'),S'→.S，例(續

接受項S待約項B

例 (3)形如A→α.β形如A→α.β項目刻畫了分析進展式式

歸約項 a一、基本概念一、基本概念——LR(0)項例 移進(Shift)待約(Reducing)項目 歸約(Reduce)項目項目A→X1…Xi-1.Xi…Xn表示分析進展程B

B (3)

b

abbab

Ba 規范族項目集規范族項目集(ε-閉包(ε-閉包形如A→α.β的形如A→α.β的項目集合

(2) (3)Ba一、基本概念——項目集閉項目集I的閉包算法：求J=J∪{B→.γ|A→α.Bβ∈J,untilJ不再擴例例 b項 Kernel

例(0)(1)b

(2) (3)

二二、LR(0)分析LR(0)、LR(0)、、LR(1)、動作表轉移表ab#SB01212536456

an

#………Xm-#………Xm-………Sm-

四、四、LR分析器主控程序(LR分析算法開始時分析棧中為和開始狀態0，置輸入指針ip指向w#的第一個符號……… ０#轉移動作LR主控程態并并 輸 動作說0#bab##bab#0#Bab##Bab##Bab##Bab##BaB##BaB#

babbab的分析過程#BB##BB#0 # #(s0s1…sm(s0s1…sm，#X1X2…Xm,初始情況：初始a1a2…an

一般情況：當前s0s1… #X ifaction[sm,aisj(shiftj)then格局變s0s1…sm 當前格當前格 ifaction[sm,airj(reducej)then表示用第j個產s0s1…sm-#X1…Xm-kＢ再查goto表，當goto[sm-k,Ｂ]=jthen格局變s0s1…sm-k#X1…Xm-kＢifaction[sm,ai]=accthen分析成s是棧頂狀態aipifaction[s,a]=si(shifti)使ip指向下一符號{把符號a和狀態使ip指向下一符號elseifaction[s,a]=rj(reduceA→β){2*|β|把A和goto[s',A]先后壓入棧中；輸出產生式A→β}elseifaction[s,a]=acc 輸 動作說0#bab##bab#0#Bab##Bab##Bab##Bab#

bab的分析過程中棧內容的#BB##BB#0#BaB#goto(3,B)=6#BaB#

# #(Canonical(CanonicalSentential六、棧內規范句型六、棧內…………

LR主控程

轉移轉移動作 (Canonical(CanonicalSentential規范句型的不含句柄右側任意符號的綴稱為規范句型的活前綴(Active例：idid*id的分析句型Eid*id和EE*活前 活前S*rmαAwrm (Canonical(CanonicalSentential換角度理活前綴與句柄的包含句柄： 項目集I的閉包七、LR(0)分析表的構造項目集I的閉包

b

a

Iε-閉

表達表達式文法的處文法

I I

F

F→(.E

F→

)

項目

閉

后繼項目(SuccessiveA→α.Xβ的后繼項目是七、后繼項目(SuccessiveA→α.Xβ的后繼項目是

b

a

I

a編譯原(Principlesof 講：LR分析思用LR分析思用形如A→α.β的項目構成狀LR(0)項目分移進項目待約項目：S→b.BB歸約項目:文法上次課

過項目“展開 I 4b項

IKernel

上次課主要內動作表轉移表ab#SB01212536456轉移：goto………Xm-………Sm-

上次課主要內 LR主控程

轉移轉移動作分析過

活前七、LR(0)分析表的構造——閉包之間的轉閉包之間的轉

b

a

I

aI I

F

F→(.E

F→

規范

)七、LR(0)分析表的構計算LR(0)項目集規范族C(分析器狀態集合設文法G=(V，T，P，S) 文法稱C為G'的LR(0)項目集規范族(Canonical七、LR(0)分析表的構——計算LR(0)項目集規范族C(分析器狀態集合C:={closure({S'→.S})};forI∈C，ifgo(I,X)≠Φ&go(I,X)CuntilC不變 表達式文法的項目集規C={{E'→.E{E'→E.,→E.+T},{E→T.T→T.*F},{F→(.E{F→id.},{T→T*.F,F→.(E),F→.id},{F→ I I

F

F→(.E

F→

)七、LR(0)分析表的構造——識 法所有規范句型活前綴的 的所有規范句型活前綴的DFA:M=(C,V∪T,go,I0,I0=CLOSURE({S'思考如何在計算機中一個文法的LR(0項目集規范族最節省空間？如果某文法有這些產生式的右部的最大長度為，問：你所給出的方案需要的空間與n和m什么樣的關系編譯原(Principlesof 講：上次課主要內分析器的運action[s,a]=si(shiftaction[s,a]=rj(reducebyproduct項目集閉CLOSURE(I)=I∪{B→.γ|A→α.Bβ∈I,后繼項目:A→α.Xβ上次課主要內閉包之間的轉移I0=CLOSURE({S'識別規范句型活前綴的M=(C,V∪T,go,I0,例按照LR(0)分析需求，分別構造識下列文法的所有規范句型活前綴 LR(0)方法能解決這個嗎文法為

語法樹 句子分析句子分析 abbcd句型活前綴的FA的狀態轉移圖， 七、LR(0)分析表構0為開始狀對ifA→α.aβ∈IiandifA→α.Bβ∈Iiand

thenaction[i,a]=sj;thengoto[i,B]=j;ifif

thenfora∈T∪{#}doaction[i,a]=rj;thenaction[i,#]=acc;所有空格置 I I

F

F→(.E

F→

(構造

)

狀態+*()#ETF012312348235存在移693歸789八、LR(0)不是總29項目集I的相歸約-歸約(Reduce/Reduce ):I中至移進-歸約(Shift/Reduce I相容(Consistent):既無歸約-歸約，又無移進-歸約I不相容I中有歸約-歸約或者移進-LR(0)文法：I∈C例例

0

I

I ab

I9: I7:I

0

I:

ab

如何構造分I9:

I7:動作表轉移表abcd#SAB012311223644r6/765673859九、SLR(1)分析表0為開始狀對ifA→α.aβ∈IiandifA→α.Bβ∈Iiand

thenaction[i,a]=sj;thengoto[i,B]=j;ifA→α.∈Iiif

thenforthen

cii,a]=j所有空格置例表達式文法的例表達式文法的SLR(1)分析(3)(4)(4)(5)(6)(6) I I

F

F→(.E

F→

)在狀態2、9出 )該文法不是LR(0)文法

構造表達式文法的SLR分析(1)(1)(2)(3)(4)(5)(6)FOLLOW(E)={),+,#FOLLOW(T)={),+,#,*FOLLOW(F)={),+,#,* I I

F

*

IFOLLOW(E)={),+,# TT F→(.E

F→

)

狀態狀態+*()#ETF012312348235693789E),E),+,T),+,#,F),+,#,狀態轉移圖SLR(1)分析的特描述能力強于LL(1SLR(1文法：SLR(1)分析表無SLR(1)分析的局限如果SLR(1)分析表仍有多重 約或歸約-歸約)，則說明該文法不是SLR(1)文法；說明僅使用LR(0項目集和FOLLOW集 =*

L→idSLR分析中的——更強的分析方I2={S→L.=R,R→L.輸入符號為=時，出現了移進歸約SL.=RI2且 action[2,=]=ShiftRLI2且=∈FOLLOW(R action[2,=]=ReduceR→要的信息

SS'→S.,#

S→.R

,=

R→.L

8'-L→.id,=

L→idII3

S→R.

*

L→.id

id I6''-II5'-L→id

L→idSLR(1)分析的基本步1、編寫文法，求Follow2、求識別所有活前綴的3、構造SLR(1)分析Yacc(YETANOTHERCOMPILER'SCOMPILER)簡%{%開始符詞匯表：% n1,n2,…(自動定義種別碼%tokenn1,i1(用戶指定種別碼%tokennh,ih(用戶指定種別碼類型說 其它說明%%規則部 給出文則的描%%程序部 掃描器和語義動作程輸出：LALR(1)分析yylex(yylex({intwhile((c=getchar())==‘‘if(isdigit(c))yylval=c–while(isdigit(c=getcharyylval=yylval*10+(c-'0'ungetc(c,stdinretun} return}/*表達式計算%%token :expr‘\n'{printf(“\n”,;expr:expr‘+' {$$=$1+$3;|expr‘-' {$$=$1-$3;| /*$$=$1;term:term‘*' {$$=$1*$3;|term‘/' {$$=$1/$3;| /*$$=$1;factor:‘(‘espr {$$=$2;| /*$$=$1;基本框控制算基于LR分析表(動作和狀態轉移

P21212、S ABA| BaB|2、已知文法AaAd|aAb|，判斷該文法是否