南航計(jì)算機(jī)考研復(fù)試

1、2009 年編譯部分。（一）簡(jiǎn)答，每題 5 分。1.何謂編譯程序的前端和后端，為什么要分前端和后端。2.結(jié)合 C 語(yǔ)言說(shuō)明程序運(yùn)行時(shí)如何組織內(nèi)存空間3.編譯各階段對(duì)符號(hào)表進(jìn)行什么操作4.一道考最右推導(dǎo)，和短語(yǔ)，直接短語(yǔ)，句柄的題，很容易（二）將一個(gè)文法改為 LL(1)方法，并寫(xiě)出其（三）給出一個(gè)正規(guī)式，畫(huà)出相應(yīng)的最小 DFA（四）分析表。（可以參照往年的試卷，題型差不多）給出一文法，構(gòu)造該方R（0）項(xiàng)目族的 DFA，寫(xiě)出該文法的 SLR（1）分析表，問(wèn)該文法是否為 SLR（1）方法。（這道題的文法不是 SLR（1）的）（五） S-(L)|a L-L,S|S文法差不多就這樣，要求寫(xiě)出一程序，打印

2、出 a 的嵌套層數(shù)。（六）原題給了一個(gè)賦值序列1.畫(huà)出 DAG 圖2.寫(xiě)出優(yōu)化后的四元式序列。序列形式：（形式就這樣，具體的記不清了）A=B/C D=B+C. L=B/C.2010 年編譯原理部分簡(jiǎn)答題 解釋符號(hào)表在編譯過(guò)程各個(gè)階段的作用；描述 C 語(yǔ)言在不允許遞歸的情況下，是否必須為動(dòng)態(tài)分配寫(xiě)一個(gè)文法使語(yǔ)言為 L（G）=1n a 0n 1m a 0m|n 為偶數(shù)，m 為奇數(shù)已知 r=(a*|b*)*b(ba)*,畫(huà)出最小 DFA4）E-FE|FF-i|Fi改寫(xiě)成 LL(1)；并畫(huà)出 5)已知 S-bTc|aT-RR-R/S|S構(gòu)造活前綴的 DFA，及畫(huà)出 SLR 分析表6）文法如下：P-D|

3、D;D|id：T|proc id；D；S分析表寫(xiě)一個(gè)語(yǔ)導(dǎo)定義，打印改程序一共了多少個(gè) id；寫(xiě)一個(gè)翻譯方案，打印該程序每個(gè)變量 id 的嵌套深度。7）給出了一段程序，劃分基本塊并畫(huà)出程序流圖；畫(huà)出 DAG 圖編譯原理的題目都比較主流，比較容易，但第 6 題，可能大家復(fù)習(xí)的時(shí)候并不是很注意語(yǔ)法制導(dǎo)翻譯那塊，我這里給出這題的參考：6）1：為 D 設(shè)置一個(gè)綜合屬性 i，用于計(jì)算 D 中含 id 的個(gè)數(shù)，語(yǔ)導(dǎo)定義如下：產(chǎn)生式P-DD-D1;D2 D-id:TD-proc id;D1;S語(yǔ)義規(guī)則prf(D.i) D.i:=D1.i+D2.i D.i:=1D.i:=D1.i+12：為 D 設(shè)置一個(gè)繼承屬性

4、 h，用以計(jì)算 D 所在的嵌套深度，翻譯方案如下：P-D.h:=1 DD-D1.h:=D.h D1 ; D2.h:=D.h D2D-id: T pr(，D.h)D-proc id；D1.h:=D.h+1 D1；S2011 年編譯：（編譯的題目總體來(lái)說(shuō)比較主流）一：解釋編譯程序的前端和后端，為什么？二：內(nèi)存分配策略三: 給出 aianbnbj,其中 i,j0,n=0四：a(ab)*b 寫(xiě)出最小 DFA五：LL（1）文法的改寫(xiě)，分析表，常規(guī)題目，不過(guò)要注意提取左因子六：SLR 分析器的分析表構(gòu)造，具體文法記不得了，可以參考類似提醒，每年不同七：語(yǔ)導(dǎo)，具體文法也記不得了，每年都不同，不

5、過(guò)看這趨勢(shì)，應(yīng)該每年都考的八：給了一串賦值序列給出 DAG 圖，然后優(yōu)化12 年開(kāi)始考編譯原理和離散數(shù)學(xué)，之前都不考離散數(shù)學(xué)的編譯：一1（5 分）編譯程序包含的主要過(guò)程，每一個(gè)過(guò)程主要工作2.（5 分）根據(jù) c 語(yǔ)言的特點(diǎn)，說(shuō)明其需要采用哪些運(yùn)行時(shí)空間分配策略，并說(shuō)明 c 語(yǔ)言如何實(shí)現(xiàn)非局部變量的。3.（10 分）文法 G(S) saTb|+ TR RR/S|S（1） 句型aR/aR/Sb/+b(2)寫(xiě)出上面句型的短語(yǔ)，直接短語(yǔ)，句柄，素短語(yǔ)。二（5 分）文法語(yǔ)言 L(G)=0i1j|ij=0三(10 分)求 R=a(a|ba)*b 最小 DFA四(10 分)G(E)EFE|FFi|Fi改寫(xiě)成

6、 LL（1），并畫(huà)出五(10 分)G(A)ABA|iBAB|j分析表(1)(2)活前綴 DFASLR 分析表，判斷是否是 SLR(1)六（10 分）三進(jìn)制文法 G(S) SL.L|LLLF|FF0|1|2令綜合屬性 S.val七（10 分） A:=B*C該數(shù)的十進(jìn)制值，試設(shè)計(jì)一翻譯模式，計(jì)算并打印輸出 S.valD:=B/C E:=A+D L:=B/C F:=L*E G:=B*C H:=G*F F:=H*E L:=FDAG優(yōu)化四元式、離散：一（20 分） 將下面命題寫(xiě)成謂詞邏輯公式，并證明每個(gè)科學(xué)工作者都是勤奮的，每個(gè)勤奮又聰明的人都能成功，是科學(xué)工作者并且是聰明的，那么能成功。二（20 分）設(shè) f：AA 是，P(A)是冪集，定義C：P(A)P(A) 對(duì) XP（A），令 C(X)= BP(A)|X B 且對(duì)于任意 aB，都有 f(a) B證明：對(duì)任意 XP(A)，YP(A)1).XC(X)2）C(C(X) C(X)3）如果 XY，則 C(X) C(Y)。三 20）無(wú)向圖，頂點(diǎn)集 a,b,c,d,e,f,g（, a,b）,(a,d),(b,e)(b,c)(b,f)(d,e)(b