編譯原理試題

《編譯原理試題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、//東南大學(xué)一、文法G1：　　E→ET+

2、T　　T→TF*

3、F　　F→FP↑

4、P　　P→E

5、i　　1、試證明符號串TET+*i↑是G1的一個(gè)句型（要求畫出語法樹）?！　?、寫出該句型的所有短語，簡單短句和句柄。三、　　1、試寫出一個(gè)上下文無關(guān)文法G3，它能產(chǎn)生配對的圓括號串（例如，（），（（）），（）（（））等，甚至包含0對括號）?！　?、使用文法G3給出輸入串（（））（）#的自上而下分析過程。四、已知文法G4：　　S→aAb

6、Sc

7、ε　　A→aAb

8、ε　　1、給出G4文法的LR（0）項(xiàng)目集規(guī)范族；　　2、構(gòu)造SLR分析表；　　3、G4文法所定義的語言；　　

9、4、已知有如下文法及相應(yīng)的LR分析表，試給出語句01001#的LR分析過程（填寫下表）。　　S→AAA　　A→1A　　A→0五、　　1、翻譯下面語句成四元式中間代碼序列和后綴式（逆波蘭式）；　　whilex+y>ado　　ifa<10thena：=a+1elsex：=x-1；　　2、翻譯布爾表達(dá)式　?。╝>b）or（c=d）andnot（e

10、、LL（1）分析必須對原有文法提取左因子和消除左遞歸?！　?、算符優(yōu)先分析法采用“移近-歸約”技術(shù)，其歸約過程是規(guī)范的?！　?、文法S→aA；A→Ab；A→b是LR（0）文法（S為文法的開始符號）。　　5、一個(gè)BASIC解釋程序和編譯程序的不同在于，解釋程序由語法制導(dǎo)翻譯成目標(biāo)代碼并立即執(zhí)行之，而編譯程序需產(chǎn)生中間代碼及優(yōu)化。　　二、設(shè)計(jì)一個(gè)最小狀態(tài)有窮自動機(jī)，識別由下列子串組成的任意字符串。（20分）　　GO，GOTO，TOO，ON　　例如：GOTOONGOTOOGOON是合法字符串。　　三、構(gòu)造一個(gè)LL（1）文法G，識別語言L：（20分）　　L={ω

11、ω

12、為{0，1}上不包括兩個(gè)相鄰的1的非空串}　　并證明你的結(jié)論。六、設(shè)有一個(gè)子程序的四元式序列為：（20分）　　（1）I：=1　　（2）ifI>20GOTO（16）　?。?）T1：=2*J　?。?）T2：=20*I　　（5）T3：=T1+T2　?。?）T4：=addr（A）-22　?。?）T5：=2*I　?。?）T6：=T5*20　?。?）T7：=2*J　?。?0）T8：=T6+T7　?。?1）T9：=addr（A）-22　?。?2）T10：=T9[T8]　?。?3）T4[T3]：=T10+J　?。?4）I：=I+1　?。?5）goto（2）　?。?6）ret

13、　　1、分劃基本塊?！　?、對代碼施行各種可能的優(yōu)化，并寫出優(yōu)化過程中采用了何種優(yōu)化策略。一、已知文法G1：　　S→aB

14、ε　　B→bC

15、bD　　C→cB

16、c　　D→d　　1、試構(gòu)造一個(gè)最小DFA，畫出狀態(tài)轉(zhuǎn)換圖?！　?、由該DFA給出它所識別的語言（用正規(guī)式表示）。二、已知正規(guī)式α=ab*c*d，　　1、試構(gòu)造一個(gè)DFAM，其接受的語言為此α（畫出圖）；　　2、由該DFAM寫出對應(yīng)的正規(guī)文法（古線性）。三、文法G3：　　S→A[B]　　A→[B]

17、Aa　　B→a　　1、求出各非終結(jié)符N的Firstvt（N）和Lastvt（N），構(gòu)造包括語句括號‘#’在內(nèi)的

18、算符優(yōu)先表；四、已知文法G4：　　T→T*F

19、F　　F→（T）

20、i　　1、試給出語句（i*i）#的自上而下分析過程（填下表）；　　2、畫出對應(yīng)的語法樹，指出每一步歸納的句柄?！　〔襟E│棧內(nèi)│輸入│動作五、已知文法G5：　　0、E‘→E　　1、E→E+T　　2、E→T　　3、T→i　　列出LR（0）項(xiàng)目集規(guī)范族，求出各非終結(jié)符N的Follow集合，構(gòu)造SLR分析表。六、翻譯如下語句成四元式序列（由語法制導(dǎo)生成）　　whilea>banda=d；七、按語法制導(dǎo)翻譯

21、下段程序成四元式序列（不要優(yōu)化），設(shè)數(shù)組A：array[1……10，1……10]ofint；每個(gè)下標(biāo)變量占1字編址，數(shù)組按行存放，Z為函數(shù)名。　　begin　　A[i，j]：=A[i，j]+2；　　B：=Z（A[i，j]）*5　　end　八、將如下一段四元式序列進(jìn)行塊內(nèi)優(yōu)化和循環(huán)優(yōu)化（強(qiáng)度減弱及刪除基本歸納變量），寫出優(yōu)化后的四元式序列。（要求先劃分基本塊）　?。?）i：=1　?。?）ifi>100goto（10）　?。?）T1：=20*i　?。?）M：=J+T1　?。?）T2：=20*i　?。?）N：=K+T2　　（7）O：=M+N　?。?）i：=i+1　

22、?。?）goto（2）　　（10）……一、已知正規(guī)文