資源描述：
《編譯原理清華大學(xué)陳英》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、ch5語法分析與自下而上分析第五章語法分析（自下而上）1.自下而上分析的關(guān)鍵：確定歸約條件（句柄）和歸約原則(選擇歸約的產(chǎn)生式)。2.算符優(yōu)先分析法：?條件：OGOPG結(jié)構(gòu)：優(yōu)先表；stack;總控程序；?構(gòu)造思想：VT間優(yōu)先關(guān)系FIRSTVT優(yōu)先規(guī)約條件—最左素短語出現(xiàn)LASTVT關(guān)系表優(yōu)先函數(shù)表第1頁ch5語法分析與自下而上分析3.LR(0)SLR(0)LR(1)LALR(1)分析、相應(yīng)LR文法與分析器的構(gòu)造。結(jié)構(gòu)：LR分析表；stack;總控程序；?構(gòu)造思想：歸約條件(句柄最左性)?句柄、活前綴關(guān)系?活前綴識(shí)別C(Si)+GO(分析動(dòng)作)=D
2、FA?LR分析表4.LR對(duì)二義文法的分析與應(yīng)用。5.語法分析器自動(dòng)生成思想與YACC。第2頁Ch5語法分析5.7LALR(1)分析5.7.2LALR(1)分析表構(gòu)造NYG不是二義文法LR文法構(gòu)造G的LR(0)的C判斷一個(gè)N有沖突？G為L(zhǎng)R(0)文法Y屬于SLR（1）方法那Y能解決？G為SLR(1)一類NLR文構(gòu)造G的LR(1)的C法的Y步驟:有沖突？G為非四類LRN構(gòu)造G的LALR(1)的CY沖突？G為L(zhǎng)R(1)NendG為L(zhǎng)ALR(1)第3頁ch5語法分析與自下而上分析(ch5_5.8)5－8：設(shè)有下列文法:A→a
3、(R)T→A,T
4、AR→T(1
5、)計(jì)算該文法的FIRSTVT和LASTVT。拓廣文法:S→＃A＃A→a
6、(R)T→A,T
7、AR→TFIRSTVT(A)={a,(}LASTVT(A)={a,)}FIRSTVT(T)={a,(,,}LASTVT(T)={a,),,}FIRSTVT(R)={a,(,,}LASTVT(R)={a,),,}第4頁ch5語法分析與自下而上分析(ch5_5.8)(2)計(jì)算該文法的優(yōu)先關(guān)系并產(chǎn)生優(yōu)先關(guān)系表。a(),＃a>>>(<<=<)>>>,<<><＃<<=S→＃A＃A→a
8、(R)T→A,T
9、AR→TFIRSTVT(A)={a,(}LASTVT(A)={a,)
10、}FIRSTVT(T)={a,(,,}LASTVT(T)={a,),,}FIRSTVT(R)={a,(,,}LASTVT(R)={a,),,}第5頁ch5語法分析與自下而上分析(ch5_P150_4.9)(3)計(jì)算該文法的優(yōu)先函數(shù)。fg畫圖aaa(),＃fg(f51521(g44131g)f)a(),＃a>>>(<<=>>,<<>11、(R)AT→A,T
12、A算符優(yōu)先分析每一次(R)R→T歸約的短語（即最T左素短語）。A,T1、a(R)2
13、、aA3、A,AT4、(T)aA,T5、aaA6、A,A7、（T）a第7頁ch5語法分析與自下而上分析(ch5_5.9)5－9考慮對(duì)文法G，若其中某項(xiàng)目集為：Ｉ＝｛A→α·Xβ，B→α·，C→α·｝當(dāng)X∈V時(shí)，如何構(gòu)造文法G的SLR(1)分析表。N設(shè)Follow(B)＝S，F(xiàn)ollow(C)=T，F(xiàn)IRST(X)－{ε}=R，則對(duì)?a∈S，Action(I,a)=RB→α則對(duì)?a∈T，Action(I,a)=RC→α則對(duì)?a∈R，Action(I,a)＝“移進(jìn)”第8頁ch5語法分析與自下而上分析(ch5_5.10(3))5－10設(shè)有下列文法：(3)
14、S→cA
15、ccBB→ccB
16、bA→cA
17、a試構(gòu)造上述文法的LR(0)項(xiàng)目集規(guī)范族并構(gòu)造LR（0）分析表。解：首先拓廣文法：S’→SS→cA
18、ccBB→ccB
19、bA→cA
20、a第9頁ch5語法分析與自下而上分析(ch5_5.10(3))S’→S{S’→?S;S→?cA
21、?ccB}=I0S→cA①
22、ccB②{S’→S?}=I1B→ccB③
23、b④{S→c?A
24、c?cB;A→?cA
25、?a}=I2A→cA⑤
26、a⑥{S→cA?}=I3{S→cc?B;A→c?A;B→?ccB
27、?b;A→?cA
28、?a}=I4{A→a?}=I5abcSAB{S→ccB?}=I6021
29、2543{A→cA?}=I7459876{B→c?cB;A→c?A;A→?cA
30、?a}=I885107{B→b?}=I910598711{B→cc?B;A→c?A;B→?ccB
31、?b;A→?cA
32、?a}=I10{B→ccB?}=I11第10頁ch5語法分析與自下而上分析(ch5_5.10(3))LR（0）分析表:{S’→S?}=I1S’→SS→cA①
33、ccB②ActionGoto{S→cA?}=I3B→ccB③
34、b④abc#SAB{A→a?}=I5A→cA⑤
35、a⑥0S21{S→ccB?}=I61acc{A→cA?}=I72S5S43{B→b?}=I
36、93r1r1r1r1{B→ccB?}=I114S5S9S876abcSAB5r6r6r6r66r2r2r2r20217r5
