編譯原理復(fù)習(xí)題

1、1、 （10分）下面的文法GS是否是LL（1）文法，說(shuō)明理由，構(gòu)造LL（1）分析表SaBc|bAB AaAb|Bb BcB|e2、 （5分）消除下列文法的左遞歸，消除左遞歸后判斷是否是LL（1）文法。 SSaB|bB AS|a BAc3、 （5分）構(gòu)造下面算符文法的優(yōu)先矩陣，判斷是否是算符優(yōu)先文法SA A AaA AB Ba4、 （10分）將表達(dá)式A+B*(C-D)-E/FG分別表示為三元式、四元式、逆波蘭式序列5、 （10分）現(xiàn)有文法如下：SaS|bS|a 判斷該文法是哪一類(lèi)LR文法，說(shuō)明理由，并構(gòu)造相應(yīng)的分析表。1、 已知文法G A:=aABe|a B:=Bb|d（1） 給出與上述文法等價(jià)

2、的LL（1）文法G。（2） 構(gòu)造預(yù)測(cè)分析表并給出輸入串a(chǎn)ade#分析過(guò)程。（10分）2、 設(shè)已給文法G: E:=E+T E:=T T:=T*F T:=F F:=PF F:=P P:=(E) P:=i構(gòu)造此文法的算符優(yōu)先矩陣。（10分）3、 有正規(guī)式b*abb*(abb*)*（1） 構(gòu)造該正規(guī)式所對(duì)應(yīng)的NFA（畫(huà)出狀態(tài)轉(zhuǎn)換圖）。（2） 將所求的NFA確定化。（畫(huà)出確定化的狀態(tài)轉(zhuǎn)換圖）。（3） 將所求的NFA最小化。（畫(huà)出最小化后的狀態(tài)轉(zhuǎn)換圖）。（10分）4、 若有文法G（S）的產(chǎn)生式如下：S:=L=R S:=R L:=*R L:=i R:=L,構(gòu)造識(shí)別所有項(xiàng)目集規(guī)范族的DFA。（15分）（1）

3、判斷該文法是否是LR（0）文法，說(shuō)明理由。（2） 判斷該文法是否是SLR（1）文法，說(shuō)明理由。（3） 判斷該文法是否是LR（1）文法，說(shuō)明理由。（4） 判斷該文法是否是LALR（1）文法，說(shuō)明理由1、（10分）將表達(dá)式（B*D+A）/E+D）*F+G分別表示為三元式、四元式、逆波蘭式序列2、（10分）對(duì)基本塊P畫(huà)出DAG圖B:=3D:=A+CE:=A*CF:=E+DG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L假定只有L在基本塊出口之后活躍，寫(xiě)出優(yōu)化后的四元式序列。3、（10分）對(duì)于文法GS：SaBb | aAa |bAb|bBa Ax Bx （1）判斷該文法

4、是否是LR（1）文法，構(gòu)造LR（1）分析表（2）判斷該文法是否是LALR（1）文法，說(shuō)明理由三、問(wèn)答題：(共50分)1、已知文法G S:=bBc|aAB A:=bAa|a B:=a|e寫(xiě)出所有非終結(jié)符號(hào)的First集和Follow集，構(gòu)造預(yù)測(cè)分析表并給出輸入串a(chǎn)bbaaa分析過(guò)程。（10分） 2、正規(guī)式0（0|1）*1構(gòu)造該正規(guī)式所對(duì)應(yīng)的NFA（畫(huà)出狀態(tài)轉(zhuǎn)換圖）。將所求的NFA確定化和最小化。（分別畫(huà)出確定化和最小化的狀態(tài)轉(zhuǎn)換圖）。（10分）3、若有文法G（S）的產(chǎn)生式如下：S:=bASB|bA A:=dSa|b B:=cAa|c構(gòu)造識(shí)別所有項(xiàng)目集規(guī)范族的DFA。（20分）判斷該文法是否是LR

5、（0）文法，說(shuō)明理由。判斷該文法是否是SLR（1）文法，說(shuō)明理由。判斷該文法是否是LR（1）文法，說(shuō)明理由。判斷該文法是否是LALR（1）文法，說(shuō)明理由。4、簡(jiǎn)述編譯的整個(gè)過(guò)程（10分）。1、已知文法GS SeT|RT TDR| e RdR|e Da|bd寫(xiě)出所有非終結(jié)符號(hào)的First集和Follow集，構(gòu)造LL(1)分析表，判斷此文法是否是LL（1）文法。（10分） 2、給出正規(guī)式 (a|b)*bb(a|b)*構(gòu)造該正規(guī)式所對(duì)應(yīng)的NFA（畫(huà)出狀態(tài)轉(zhuǎn)換圖）。將所求的NFA確定化和最小化。（分別畫(huà)出確定化和最小化的狀態(tài)轉(zhuǎn)換圖）。（10分）3、若有文法G（S）的產(chǎn)生式如下：SaAD|aBe|bBS

6、|bAe Ag Bg Dd|e，構(gòu)造識(shí)別所有LR(1)項(xiàng)目集規(guī)范族的DFA。（20分）判斷該文法是否是LR（1）文法，說(shuō)明理由，構(gòu)造LR（1）表。判斷該文法是否是LALR（1）文法，說(shuō)明理由。4、簡(jiǎn)述編譯的整個(gè)過(guò)程（10分）。1、 把下圖確定化和最小化：（15分）0baaabbbbbaaa2、 已知文法G S:=bBc|aAB A:=bAa|a B:=a|e寫(xiě)出所有非終結(jié)符號(hào)的First集和Follow集，構(gòu)造預(yù)測(cè)分析表并給出輸入串a(chǎn)bbaaa分析過(guò)程。（15分）3、 若有文法G（S）的產(chǎn)生式如下：S:=bASB|bA A:=dSa|b B:=cAa|c構(gòu)造識(shí)別所有項(xiàng)目集規(guī)范族的DFA。（20

7、分）判斷該文法是否是LR（0）文法，說(shuō)明理由。判斷該文法是否是SLR（1）文法，說(shuō)明理由。判斷該文法是否是LR（1）文法，說(shuō)明理由。判斷該文法是否是LALR（1）文法，說(shuō)明理由。三、問(wèn)答題：（共計(jì)50分）5、 已知文法G A:=aABe|a B:=Bb|d（1） 給出與上述文法等價(jià)的LL（1）文法G。（2） 構(gòu)造預(yù)測(cè)分析表并給出輸入串a(chǎn)ade#分析過(guò)程。（10分）6、 設(shè)S=0，1上的正規(guī)集S由倒數(shù)第二個(gè)字符為1的所有字符串組成，請(qǐng)給出該字集對(duì)應(yīng)的正規(guī)式，并構(gòu)造一個(gè)識(shí)別該正規(guī)集的DFA。(15分)3、設(shè)文法G(S)：(10分)構(gòu)造算符優(yōu)先關(guān)系表和優(yōu)先函數(shù)。4、構(gòu)造文法G(S)：(1) S &#

8、174; BB(2) B ® aB(3) B® b的LR分析表。假定輸入串為abab，請(qǐng)給出LR分析過(guò)程(即按照步驟給出狀態(tài)，符號(hào)，輸入串的變化過(guò)程)（15分）。四、綜合題（共45分）1、(10分)計(jì)算文法G(M)的每個(gè)非終結(jié)符的FIRST和FOLLOW集合，并判斷該文法是否是LL(1)的，請(qǐng)說(shuō)明理由。G(M)：a) M TBb) T Ba | ec) B Db | eT | ed) D d | e2、(15分)對(duì)文法G(S)：S a | | (T)T T，S | S(1) 構(gòu)造算符優(yōu)先表;(2) 判斷是算符優(yōu)先文法嗎?(3) 構(gòu)造優(yōu)先函數(shù)。3、（10分）將表達(dá)式A-B*(

9、C+D)+E/FG分別表示為三元式、四元式、逆波蘭式序列4、（10分）設(shè)有文法GS SBa|Bb|c BBd|Se|f判斷該文法是哪一類(lèi)LR文法，說(shuō)明理由，并構(gòu)造相應(yīng)的分析表1、已知文法G S:=aBc|bAB A:=aAb|b B:=b|e構(gòu)造預(yù)測(cè)分析表并給出輸入串baabbb分析過(guò)程。（10分）2、構(gòu)造正規(guī)式 (0|1)*00 相應(yīng)的DFA并進(jìn)行化簡(jiǎn)。(15分) 7、 若有文法G（S）的產(chǎn)生式如下：S:=bASB|bA A:=dSa|b B:=cAa|c構(gòu)造識(shí)別所有項(xiàng)目集規(guī)范族的DFA。（15分）（1） 判斷該文法是否是LR（0）文法，說(shuō)明理由。（2） 判斷該文法是否是SLR（1）文法，說(shuō)

10、明理由。（3） 判斷該文法是否是LR（1）文法，說(shuō)明理由。（4） 判斷該文法是否是LALR（1）文法，說(shuō)明理由。8、 （10分）對(duì)文法G(S)：S ® S Ú a T | a T | Ú a TT ® Ù a T | Ù a(1) 消除該文法的左遞歸和提取左公因子；(2) 構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合；(3) 構(gòu)造該文法的LL(1)分析表，并判斷該文法是否是LL(1)的。三、已知文法G S:=aBc|bAB A:=aAb|b B:=b|e構(gòu)造預(yù)測(cè)分析表并給出輸入串baabbb分析過(guò)程。（10分） 四、正規(guī)式（0*|1）（1*0）*（10分）（1） 構(gòu)造該正規(guī)式所對(duì)應(yīng)的NFA（畫(huà)出狀態(tài)轉(zhuǎn)換圖）。（2） 將所求的NFA確定化。（畫(huà)出確定化的狀態(tài)轉(zhuǎn)換圖）。五、若有文法G（S）的產(chǎn)生式如下：S:=bASB|bA A:=dSa|b B:=cAa|c構(gòu)造識(shí)別所有項(xiàng)目集規(guī)范族的DFA。（15分）i