大連海事大學(xué)《編譯原理》期末總復(fù)習(xí).ppt

《大連海事大學(xué)《編譯原理》期末總復(fù)習(xí).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《大連海事大學(xué)《編譯原理》期末總復(fù)習(xí).ppt（91頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

《編譯原理》 期末總復(fù)習(xí),考試題型及分?jǐn)?shù)分布,填空題(10分） 單選題（20分） 判斷題（10分） 解析題（60分）,第二章 文法與形式語(yǔ)言簡(jiǎn)介,（1）給出句型或句子最左推導(dǎo)或最右推導(dǎo)（規(guī)范推導(dǎo)）； （2）畫(huà)出句型或句子的語(yǔ)法樹(shù)； （3）求句型的短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄； （4）判斷一個(gè)文法是二義性的文法,P28#3,規(guī)范推導(dǎo)： aa+a*,S∷=SS*|SS+|a,S=,aa+a*,Sa+a*=,SS+a*=,Sa*=,SS*=,語(yǔ)法樹(shù)：,P28#4,只含有4個(gè)符號(hào)的句子：,Z∷=U0∣V1,U∷=Z1∣1,V∷=Z0∣0,U0=,Z10=,U010=,1010,Z=,0100,Z=,V1=,U000=,Z00 =,1000,U0=,Z10=,V110=,0110,Z=,Z=,V1=,Z00=,V100=,P28#5,S∷=AB A∷=aA︱ε B∷=bBc︱bc,A∷=aA︱ε描述的語(yǔ)言: {an|n=0},B∷=bBc︱bc描述的語(yǔ)言:{bncn|n=1},L(G[S])={anbmcm|n=0,m=1},P28#7,E∷=T∣E+T∣E-T T∷=F∣T*F∣T/F F∷=(E)∣i，,句型T+T*F+i的語(yǔ)法樹(shù)：,E,,,,E,+,T,,T,,,,E,+,,T,,,,T,*,F,F,,i,短語(yǔ)：,T+T*F+i,,T+T*F,簡(jiǎn)單短語(yǔ)：,T*F，,T ，,i,句柄：,T,已知文法G[E]: E::=E+T|T T::=T*F|F F::=(E)|i 1、試給出句子i*(i+i)的規(guī)范推導(dǎo)； 2、畫(huà)出相應(yīng)的語(yǔ)法樹(shù)；(注意：相同的葉子節(jié)點(diǎn)用不同的下標(biāo)加以區(qū)分，如：i1、i2、i3…) 3、指出該句子所有的短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄。,存在的問(wèn)題,給出的推導(dǎo)不是規(guī)范推導(dǎo)； 一次使用多條規(guī)則； 沒(méi)有標(biāo)明句柄所在的位置； 不是從文法的開(kāi)始符號(hào)進(jìn)行推導(dǎo)；,句子i*(i+i)的規(guī)范推導(dǎo),E?T? T*F? T*(E) ? T*(E+T) ? T*(E+F) ? T*(E+i) ? T*(T+ i) ? T*(F + i) ? T*(i + i) ?F* (i + i) ?i * (i + i),句子i*(i+i)的語(yǔ)法樹(shù),短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄,為了區(qū)分相同的短語(yǔ)，可以采用加下標(biāo)的方法。 i1、i3是相對(duì)于非終結(jié)符號(hào)F、T的短語(yǔ)、簡(jiǎn)單短語(yǔ); i2是相對(duì)于非終結(jié)符號(hào)F、T、E的短語(yǔ)、簡(jiǎn)單短語(yǔ); i2+i3是相對(duì)于非終結(jié)符號(hào)E的短語(yǔ); (i2+i3)是相對(duì)于非終結(jié)符號(hào)F的短語(yǔ); i1*(i2+i3)是相對(duì)于非終結(jié)符號(hào)T、E的短語(yǔ); i1是句柄;,P28#8,S∷=S*S|S+S|(S)|a,給出句子a+a*a 兩棵不同的語(yǔ)法樹(shù),已知文法G[S]: S::=iSeS|iS|i 試說(shuō)明該文法是二義性的文法。,句子iiiei兩棵不同的語(yǔ)法樹(shù),S::=iSeS|iS|i,第三章 詞法分析,1、正規(guī)文法和有限自動(dòng)機(jī)的等價(jià)性 2、正規(guī)式和有限自動(dòng)機(jī)的等價(jià)性 3、 NFA到DFA轉(zhuǎn)換的子集法及最小化,,正則文法的狀態(tài)圖畫(huà)法如下：,1、文法中的每個(gè)非終結(jié)符號(hào)對(duì)應(yīng)狀態(tài)圖中的一個(gè)結(jié)點(diǎn)，即圖中的每個(gè)結(jié)點(diǎn)代表一個(gè)非終結(jié)符號(hào)。,2、增設(shè)一個(gè)結(jié)點(diǎn)代表開(kāi)始狀態(tài)S，而文法中的識(shí)別符號(hào)對(duì)應(yīng)的結(jié)點(diǎn)為終結(jié)狀態(tài),3、對(duì)于文法中的每一條形如U→a的規(guī)則，畫(huà)一條從結(jié)點(diǎn)S指向結(jié)點(diǎn)U的弧線，并在弧上標(biāo)記a。,4、對(duì)于文法中每一條形如U∷=Wa的規(guī)則，畫(huà)一條從結(jié)點(diǎn)W指向結(jié)點(diǎn)U的弧線，并在弧上標(biāo)記a。,S,U,,a,,開(kāi)始狀態(tài),W,U,,a,有正則文法G[Z]：Z::=Ua|Vb，U::=Zb|b，V::=Za|a ，畫(huà)出該文法的狀態(tài)圖，并檢查句子abba是否合法。,S,U,V,Z,,,,,,,,a,a,a,b,b,b,P60#1,句子abba合法。,Z::=Ua|Vb,U::=Zb|b,V::=Za|a,Z::=Ua|Vb， U::=Zb|b， V::=Za|a,從正規(guī)式R構(gòu)造NFA M的步驟1,1、把正規(guī)式R表示為：,初態(tài),終態(tài),,x,,R,從∑上的正規(guī)式R構(gòu)造NFA M的步驟2,2、把R分裂并加進(jìn)新的結(jié)點(diǎn),每條弧標(biāo)記為∑上的一個(gè)字符或ε,,結(jié)點(diǎn)分裂規(guī)則①,,加入k結(jié)點(diǎn),1弧變2弧,結(jié)點(diǎn)分裂規(guī)則②,,1弧變2弧,結(jié)點(diǎn)分裂規(guī)則③,,加入k結(jié)點(diǎn),閉包去掉變閉環(huán),前后各1條空弧,k,,,ε,ε,R1,子集法的基本思想,NFA,基本思想：,NFA的一組狀態(tài),DFA的一個(gè)狀態(tài),對(duì)應(yīng),,等價(jià)的DFA,子集法,,轉(zhuǎn) 換,子集法,設(shè)已給具有ε動(dòng)作的NFA M=（K,∑,f,S0,Z),構(gòu)造相應(yīng)的確定的有限自動(dòng)機(jī): DFA M′ =（K′,∑,f′,q0,Z′ ),構(gòu)造K ′及f ′的步驟可遞歸地描述如下：,（1）給出M′的初態(tài) ：,遞歸描述步驟（1）,K′=,{q0 },q0 =,ε-closure(S0),遞歸描述步驟（2）,（2）對(duì)于K′中尚未標(biāo)記的狀態(tài) qi ={Si1 ,Si2 ,…,Sim}, Sik ?K做 ：,①標(biāo)記qi ；,②對(duì)于每一個(gè)a∈∑，置：,③若qj不在K′中,則將qj,f′(qi , a)=qj,,K′,,M′,J=move({Si1 ,Si2 ,…,Sim},a)，,qj = ε-closure(J)= Ia,遞歸描述步驟（3）,（3）重復(fù)（2）直到M′中不再有未標(biāo)記的狀態(tài)為止。,至少含有一個(gè)Z中元素的qi作為M′的終態(tài),構(gòu)造正規(guī)式b(ab|bb)*ab的DFA,（1）NFA,初態(tài),終態(tài),,x,,b(ab|bb)*ab,初態(tài),終態(tài),,x,a,1,,b,2,,ε,3,,ε,,ab|bb,4,,b,初態(tài),終態(tài),,x,a,1,,b,2,,ε,3,,ε,,4,,b,bb,初態(tài),終態(tài),,x,a,1,,b,2,,ε,3,,ε,,a,4,,b,b,5,6,b,b,ab,（2）DFA,1、ε-closure(x)={x},=q0,K′＝｛ q0 ｝,2、對(duì)K′中未標(biāo)記狀態(tài)q0做：,move(q0,a)=move({x},a)=Φ,move(q0,b)=move({x},b)= {1},ε-closure({1})={1,2,3}=q1,f′(q0,b)= q1,K′＝｛ q0,q1｝,3、對(duì)K′中未標(biāo)記狀態(tài)q1做：,move(q1,a)=,move({1,2,3},a)={4,6},ε-closure({4,6})= {4,6} =q2,f′(q1,a) =q2,move(q1,b)=,move({1,2,3},b)={5},ε-closure({5})= {5} =q3,f′(q1,b) =q3,K′＝｛ q0,q1,q2,q3｝,4、對(duì)K′中未標(biāo)記狀態(tài)q2做：,move(q2,a)=,move({4,6},a)=Φ,move(q2,b)=,move({4,6},b)={2,y},ε-closure({2,y})= {2,3,y} =q4,f′(q2,b) =q4,K′＝｛ q0,q1,q2,q3,q4｝,5、對(duì)K′中未標(biāo)記狀態(tài)q3做：,move(q3,a)=,move({5},a)=Φ,move(q3,b)=,move({5},b)={2},ε-closure({2})= {2,3} =q5,f′(q3,b) =q5,K′＝｛ q0,q1,q2,q3,q4,q5｝,6、對(duì)K′中未標(biāo)記狀態(tài)q4做：,move(q4,a)=,move({2,3,y},a)={4,6},ε-closure({4,6})= {4,6} =q2,f′(q4,a) =q2,move(q4,b)=,move({2,3,y},b)={5},ε-closure({5})= {5} =q3,f′(q4,b) =q3,K′＝｛ q0,q1,q2,q3,q4,q5｝,7、對(duì)K′中未標(biāo)記狀態(tài)q5做：,move(q5,a)=,move({2,3},a)={4,6},ε-closure({4,6})= {4,6} =q2,f′(q5,a) =q2,move(q5,b)=,move({2,3},b)={5},ε-closure({5})= {5} =q3,f′(q5,b) =q3,K′＝｛ q0,q1,q2,q3,q4,q5｝,等價(jià)的DFA M ′如下,K′＝｛ q0 , q1 , q2 ,q3 , q4 ,q5｝,f′(q0,a) = Φ , f′(q0,b) =q1,f′(q1,a) =q2, f′(q1,b) =q3,f′(q2,a) = Φ, f′(q2,b) =q4,f′(q3,a) = Φ, f′(q3,b) =q5,f′(q4,a) =q2, f′(q4,b) =q3,Z′＝｛ q4 ｝,f′(q5,a) =q2, f′(q5,b) =q3,NFA M轉(zhuǎn)換為DFA M ′的過(guò)程,q0={x},q1 ={1,2,3},q2 ={4,6},q3 ={5},q4 ={2,3,y},q1 ={1,2,3},q2 ={4,6},q3 ={5},q2 ={2,3,y},q5={2,3},q3 ={5},f′(q0,b) =q1,f′(q1,a) =q2, f′(q1,b) =q3,f′(q2,b) =q4,f′(q3,b) =q5,f′(q4,a) =q2, f′(q4,b) =q3,f′(q5,a) =q2, f′(q5,b) =q3,q5 ={2,3},q2 ={4,6},q2 ={4,6},q3 ={5},DFA M ′的狀態(tài)圖,f′(q0,a) = Φ , f′(q0,b) =q1, f′(q1,a) =q2, f′(q1,b) =q3, f′(q2,a) = Φ, f′(q2,b) =q4, f′(q3,a) = Φ, f′(q3,b) =q5, f′(q4,a) =q2, f′(q4,b) =q3, f′(q5,a) =q2, f′(q5,b) =q3,b,最小化,1、初始劃分由兩個(gè)子集組成，即：,∏：,,｛q0,q1,q2,q3，q5｝(非終態(tài)）,｛q4｝（終態(tài)）,b,2、考查子集｛q0,q1,q2,q3,q5｝,｛ q0,q1,q2,q3,q5 ｝a：,={q2 ｝,? ｛ q0,q1,q2,q3,q5 ｝,｛ q0,q1,q2,q3,q5 ｝b：,={q1,q3,q4,q5 ｝,? ｛q0,q1,q2,q3,q5｝,?｛q4｝,b,｛ q0,q1,q2,q3,q5 ｝：,,｛ q0,q1,q3,q5 ｝,{q2 ｝,∏={｛ q0,q1,q3,q5 ｝,｛q2｝，｛q4｝},b,3、考查子集｛q0,q1,q3,q5｝,｛ q1,q5 ｝a：,={q2 ｝,｛ q0,q1,q3,q5 ｝b：,={q1,q3,q5 ｝,? ｛ q0,q1,q3,q5 ｝,子集｛ q0,q1,q3,q5 ｝再分割:,f′(q0,a) = Φ,f′(q3,a) = Φ,｛ q0,q3,｝a：,= Φ,｛ q0,q3,｝,｛ q1,q5 ｝,b,,q0,初態(tài),b,,q2,,a,b,,｛ q0,q3,｝,｛ q1,q5 ｝,{q2 ｝,{q4 ｝,q1,a,,b,b,b,考察字符串：bab,,左圖識(shí)別過(guò)程：q0---q1---q2---q4,右圖識(shí)別過(guò)程：q0---q1---q2---q4,考察字符串：bbbab,左圖識(shí)別過(guò)程：q0---q1---q3---q5---q2---q4,右圖識(shí)別過(guò)程：q0---q1---q0---q1---q2---q4,b,設(shè)字母表∑＝{a,b}上的正規(guī)式R=(a|ba)* 1、構(gòu)造NFA M′ ,使得L(M′ )=L(R) ; 2、將NFA M′確定化，得到DFA M 使得L(M′ )=L(M); 3、將DFA M最小化。,構(gòu)造NFA M′,x,1,,ε,,ε,a,R=(a|ba)*,2,b,a,將NFA M′確定化,1、ε-closure({x})={x,1,y}=q0,K′＝｛ q0 ｝,2、對(duì)K′中未標(biāo)記狀態(tài)q0做：,(1)標(biāo)記q0,(2)move(q0,a)=move({x,1,y},a)={1},ε-closure({1})= {1,y}=q1,f′(q0,a)=q1,move(q0,b)=,move({x,1,y},b)=,{2},ε-closure({2})= {2}=q2,q0 ={x,1,y}， q1 ={1,y},f′(q0,b)=q2,K′＝｛ q0 , q1 , q2 ｝,3、對(duì)K′中未標(biāo)記狀態(tài)q1做：,(1)標(biāo)記q1,(2)move(q1,a)=,move({1,y},a)=,{1},ε-closure({1})= {1,y}=q1,f′(q1,a)=q1,q0 ={x,1,y}， q1 ={1,y}， q2={2},move(q1,b)=,move({1,y},b)=,{2},f′(q1,b)=q2,K′＝｛ q0 , q1 , q2 ｝,4、對(duì)K′中未標(biāo)記狀態(tài)q2做：,(1)標(biāo)記q2,(2)move(q2,a)=,move({2},a)=,{1},ε-closure({1})= {1,y}=q1,f′(q2,a)=q1,move(q2,b)=,move({2},b)=,Φ,等價(jià)的DFA M 如下,f′(q0,a)=q1,f′(q0,b)=q2,f′(q1,a)=q1,f′(q1,b)=q2,f′(q2,a)=q1,NFA M ′轉(zhuǎn)換為DFA M 的過(guò)程,f′(q0,a)=q1,f′(q0,b)=q2,f′(q1,a)=q1,f′(q1,b)=q2,f′(q2,a)=q1,DFA M 的狀態(tài)圖,f′(q0,a)=q1,f′(q0,b)=q2,f′(q1,a)=q1,f′(q1,b)=q2,f′(q2,a)=q1,q2,,初態(tài),,a,b,a,,b,a,將DFA M最小化,1、初始劃分由兩個(gè)子集組成，即：,∏：,,｛q0,q1｝(終態(tài)）,｛q2｝（非終態(tài)）,｛q0,q1｝a=,{q1},｛q0,q1｝b=,{q2},2、考查子集｛q0,q1｝,｛q0,q1｝a=,{q1},｛q0,q1｝b=,{q2},子集｛q0,q2｝不能再分割，即q0,q1為等價(jià)狀態(tài)進(jìn)行合并,q2,,初態(tài),終態(tài),a,,b,a,第四章 自頂向下的語(yǔ)法分析,（1）消除直接左遞歸 （2）消除間接左遞歸的算法 （3）First集合和Follow集合的求解方法 （4）避免回溯的判斷方法 （5）簡(jiǎn)單回溯的消除方法 （6）LL(1)分析表的構(gòu)造算法 （7）LL(1)分析方法,一、消除左遞歸,消除間接左遞歸的算法,消除直接左遞歸,,引進(jìn)新的非終結(jié)符,提公因子,1. 引進(jìn)新的非終結(jié)符的方法,U::=Ux1|Ux2|…|Uxm|y1|y2|…|yn,左遞歸規(guī)則形如：,U′::=x1 U′| x2 U′|…| xm U′|ε,,,,左遞歸規(guī)則,,,,不以U開(kāi)頭,方法：,引進(jìn)新的非終結(jié)符號(hào)U′,改 寫(xiě),,U::= y1 U ′| y2 U ′|…| yn U ′,2.提公因子的方法,U::=(y1|y2|…|yn),U::=Ux1|Ux2|…|Uxm|y1|y2|…|yn,左遞歸規(guī)則形如：,,,,左遞歸規(guī)則,,,,不以U開(kāi)頭,改 寫(xiě),,{x1|x2|…|xm},3.消除間接左遞歸的算法步驟（1）,(1)將文法中所有的非終結(jié)符號(hào)排序:,U1,U2,…,Un;,消除間接左遞歸的算法步驟（2）,i=2,,i=n?,,j=1,,Y,j=i-1?,Y,,存在Ui ::=Ujy?,Y,,如果Uj::= x1 | x2 | … | xk 則Ui::= x1 y| x2 y | … | xk y,,消除Ui 規(guī)則中的直接左遞歸,,,j=j+1,,,N,,N,,,i=i+1,,,N,結(jié)束,,,考查是否存在排在后面的非終結(jié)符（ Ui ）定義為（：：=）以排在Ui 前面的非終結(jié)符號(hào)（Uj）開(kāi)頭的規(guī)則。,消除間接左遞歸的算法步驟（3）,(3)消去多余規(guī)則(壓縮文法),此算法要求,,1）文法沒(méi)有回路(U,2）文法不存在規(guī)則U::=ε,U),FIRST集的定義,符號(hào)串x,推導(dǎo),,終結(jié)頭符號(hào)集,FIRST(x)=,{a,|x,a… },,a∈VT,x,ε,,ε∈FIRST(x),文法避免回溯的條件,多選規(guī)則：U::=x1|x2|…|xn,文法避免回溯的條件:,,不含空規(guī)則,FIRST(xi ),∩,FIRST( xj ) =,Φ,,,(i≠j),FOLLOW(U)的定義,非終結(jié)符號(hào)U的后繼終結(jié)符號(hào)集。,FOLLOW(U)= {a,|Z,…Ua…},,a∈VT,,識(shí)別符號(hào),特別地：,Z,…U,,# ∈ FOLLOW(U),,輸入結(jié)束符,求FOLLOW(U)的算法步驟1),1) #∈FOLLOW(Z);,,識(shí)別符號(hào),求FOLLOW(U)的算法步驟2),2) A::=αUβ,FIRST(β)-{ε},,FOLLOW(U),,文法滿足避免回溯的條件,U::=x1|x2|…|xn,1)FIRST(xi)∩FIRST(xj)=Φ (i≠j),2)若xj,ε,FIRST(xi)∩FOLLOW(U)=Φ (i≠j),,非空規(guī)則,消除回溯的簡(jiǎn)單方法,U::=xi|xj,FIRST(xi)∩FIRST(xj) ≠ Φ,={a},U::=xi|xj,改寫(xiě),,U::=aW|aV,提取a,,U::=a(W|V),引入X,,U::=aX,,X::=W|V,LL(1)分析表M的結(jié)構(gòu),行標(biāo)題,,非終結(jié)符號(hào)U,列標(biāo)題,,,終結(jié)符號(hào)a,結(jié)束符#,,,M[U,a],,規(guī)則,,,當(dāng)U面臨輸入符號(hào)a時(shí)應(yīng)選擇的規(guī)則,出錯(cuò)標(biāo)志,,,構(gòu)造LL(1)分析表M的算法,(3)其它均置ERROR,規(guī)則U::=x,(1)a∈FIRST(x),,,U::=x,,M[U,a],(2)ε∈FIRST(x),,,U::=x,M[U,b],,,M[U,#],,∈,FOLLOW(U),空,,LL(1)分析方法基本思想,從左到右掃描源程序,從識(shí)別符號(hào)開(kāi)始生成句子的最左推導(dǎo),只要向前查看一個(gè)輸入符號(hào),便能確定當(dāng)前應(yīng)選擇的規(guī)則,,LL(1)方法,LL(1)分析方法的實(shí)現(xiàn),LL(1)方法,,LL(1)分析表M,符號(hào)棧S,K:,符號(hào)棧S的棧頂指針,J:,輸入串R的指針,實(shí)現(xiàn)步驟,(3)棧頂元素=,(1),棧頂元素,當(dāng)前符號(hào),,匹配,,,k:=k-1,j:=j+1,(2),棧頂元素S[k]∈VN,當(dāng)前輸入符號(hào)為R[j],,查M表,,M[S[k],R[j]]元素,S[k]::=x1x2…xn,,,x1x2…xn,代替,,S[k],,入棧順序,由右向左,輸入符號(hào)=,#,成功,,,,,S棧,…,S[k],,xn,…,x2,x1,,棧頂元素出棧,,輸入下一符號(hào),出棧,P78#4,A → aABe|ε B → Bb|b,（1）FIRST(A)={a, ε},FIRST(B)=,A → aABe,A 為識(shí)別符號(hào),,FOLLOW(A)={b, #},A → aABe,B → Bb,,FOLLOW(B)={b, e},P78#4(續(xù)),（2）不是LL(1)文法，文法中有直接左遞歸的規(guī)則：,B → Bb|b,A → aABe|ε B → Bb|b,（3）消除直接左遞歸：,引進(jìn)新的非終結(jié)符號(hào)B’,B → bB’,B’ → bB’ |ε,改寫(xiě)后的文法：,A → aABe|ε,B → bB’,B’ → bB’ |ε,P78#4(續(xù)),（4）構(gòu)造LL(1)分析表,FOLLOW(A) ={b, #},FOLLOW(B’)= FOLLOW(B)={ e},FOLLOW(B)={e},A → aABe,A→ ε,A→ ε,B → bB’,B’ → bB’,B’→ ε,對(duì)文法G[S]: S → a| ∧|(T) T → T,S|S （1）給出(a,(a,a))的最左推導(dǎo)； （2）該文法是LL(1)文法嗎？為什么？ （3）改寫(xiě)成與之等價(jià)的LL(1)文法，構(gòu)造LL(1)分析表。 （4）給出輸入串(a,a)#的分析過(guò)程，并說(shuō)明該串是否為G的句子。,(1)句子(a,(a,a))的最左推導(dǎo)： S ?(T) (T,S) ?(S,S) (a,S) ?(a,(T)) (a,(T,S)) ?(a,(S,S)) (a,(a,S)) ? (a,(a,a)),S → a| ∧|(T) T → T,S|S,（2）改寫(xiě)文法： 消除直接左遞歸T → T,S|S引入新的非終結(jié)符號(hào)T’ T → ST’ T’ → ,ST’|ε 改寫(xiě)后的文法： S → a| ∧|(T) T → ST’ T’ → ,ST’|ε 消除間接左遞歸后： S → a| ∧|(T) T → a T’ | ∧T’|(T)T’ T’ → ,ST’|ε,消除間接左遞歸,（3）判斷改寫(xiě)后的文法是否是LL(1)文法： 求FOLLOW(T’)=FOLLOW(T)={)} FILLOW(T’)∩First(,ST’)={)} ∩{,}=Φ 改寫(xiě)后的文法是LL(1)文法,S → a| ∧|(T) T → a T’ | ∧T’|(T)T’ T’ → ,ST’|ε,（4）LL（1）分析表,(5)給出句子（a,a）的分析過(guò)程,#S,（a,a）#,S → (T),#）T（,（a,a）#,匹配,#）T,a,a）#,T → a T’,#）T’a,a,a）#,匹配,#）T’,,a）#,T’ → ,ST’,#）T’S,,,a）#,匹配,#）T’S,a）#,S → a,#）T’a,a）#,匹配,#）T’,）#,T’ → ε,#）,）#,匹配,#,#,成功,第5章 LR分析法,1、LR(0)分析法 2、SLR(1)分析法 3、LR（1）分析法 4、LALR（1）分析法,文法G(Z)如下： S’ →S S → (SR |a R → *SR|) （1）判斷該文法是LR(0)還是SLR(1)文法？并說(shuō)明理由。 （2）構(gòu)造相應(yīng)的分析表,S’ →S S → (SR |a R → *SR|),（1）判斷：,S’ →·S S → ·(SR S → ·a,I0,,S,S′::=S?,I1,,（,,S → (·SR,S → ·(SR S → ·a,I2,,a,S::=a?,I3,,S,,S → (S·R,R → ·*SR R → ·),（,,,a,I4,,R,S → (SR·,I5,,*,,R → *·SR,S → ·(SR S → ·a,I6,,),R →) ·,I7,,S,,R → *S·R,R → ·*SR R → ·),I8,,,,（,,,,a,,R,R → *SR ·,I9,,*,,),,沒(méi)有沖突項(xiàng)目子集，是LR（0）文法,（2）構(gòu)造LR（0）分析表,1,S2,S3,acc,4,S2,S3,(0)S’ →S (1)S → (SR (2)S → a (3)R → *SR (4)R → ),r2,r2,r2,r2,r2,5,S6,S7,r1,r1,r1,r1,r1,8,S2,S3,r4,r4,r4,r4,r4,9,S6,S7,r3,r3,r3,r3,r3,文法G(S)如下： S →AB A → aBa|ε B → bAb|ε （1）判斷該文法是LR(0)還是SLR(1) 文法？并說(shuō)明理由。 （2）構(gòu)造相應(yīng)的分析表,（1）判斷是LR(0)或SLR(1)文法：,S →·AB A → ·aBa A → ·,S →AB A → aBa|ε B → bAb|ε,I0,,A,S →A · B B → ·bAb B → ·,I1,,a,A → a · Ba B → ·bAb B → ·,I2,,B,S →A B ·,I3,,b,B → b · Ab A → ·aBa A → ·,I4,,B,A → a B · a,I5,,b,,A,B → b A · b,I6,,a,,a,A → a B a ·,I7,,b,B → b A b ·,I8,I0,I1,I2,I4有沖突項(xiàng)目，所以不是LR(0)文法,求follow集,FOLLOW(S)={#} 由S →AB得到：#∈ FOLLOW(B) 由A → aBa得到：a∈ FOLLOW(B) 所以： FOLLOW(B)={a,#} 由B → bAb得到：b∈ FOLLOW(A) 由S →AB得到： #∈ FOLLOW(A) 所以： FOLLOW(A)={b,#},S →AB A → aBa|ε B → bAb|ε,S →A · B B → ·bAb B → ·,S →·AB A → ·aBa A → ·,B → b · Ab A → ·aBa A → ·,A → a · Ba B → ·bAb B → ·,是SLR(1)文法,（2）構(gòu)造SLR（1）分析表,1,S2,3,S4,(0)S →AB (1)A → aBa (2)A → ε (3)B → bAb (4)B → ε,FOLLOW(A)={b,#},FOLLOW(B)={a,#},r2,r2,r4,r4,5,S4,r4,r4,acc,6,S2,r2,r2,S7,S8,r1,r1,r3,r3,