西電軟院編譯原理試題

1、Xidian University Li Huan 編譯原理題目解 詩(shī)云： 太初有道，道曰全真。全真七子，星聚軟院 此處作者指的是目前西電軟件學(xué)院七位有德道長(zhǎng)：總掌教大護(hù)法武道長(zhǎng)、首席副掌教顧道長(zhǎng)、劉道長(zhǎng)諱西洋、沈道長(zhǎng)諱沛意、王道長(zhǎng)諱獻(xiàn)青、高道長(zhǎng)諱海昌、陳道婆諱靜玉。此乃huan說，另有其他版本。不再贅述。 。 重陽(yáng)歸天 此處指軟件學(xué)院開山祖師陳真人諱平。歸天意本離世，此處特指升仙為四大護(hù)校法尊之一。 ，分道七篇。各執(zhí)一篇，授業(yè)終南。 當(dāng)是時(shí)也，正乃王道長(zhǎng)獻(xiàn)青真人講道西電，秘授編譯原理心法一篇，以饗眾生。 無量壽佛！ 今晚 Li Huan 1、填空題（30 分） 1.1 以階段劃分的編譯器中，

2、 語法分析 階段以記號(hào)流為輸入， 語義分析 階段以語法樹為輸入。 1.2 有 正 規(guī) 式 P=a|b 和 Q=cd 則 L(QP)=cda,cdb ， L(P|Q)Q)= acd,bcd,cdcd 。 1.3 有兩個(gè)因素使得有限自動(dòng)機(jī)是不確定的，一個(gè)是 具有 狀態(tài)轉(zhuǎn)移 ，另一個(gè)是 對(duì)同一字符，可能有多于一個(gè)的下一狀態(tài)轉(zhuǎn)移 。 1.4 詞法分析器有四個(gè)作用，請(qǐng)給出其中的任意兩個(gè)： 識(shí)別記號(hào)并交給語法分析器/濾掉源程序中的無用成分/處理與具體平臺(tái)有關(guān)的輸入/調(diào)用符號(hào)表管理器或出錯(cuò)管理器 。 1.5 一個(gè)定義正確的上下文無關(guān)文法，非終結(jié)符集合和終結(jié)符集合的交集為空，所有出現(xiàn)在產(chǎn)生式左部的文法符號(hào)均是

3、 非終結(jié)符 ，僅出現(xiàn)在產(chǎn)生式右部的文法符號(hào)均是 終結(jié)符 。 1.6 編譯源程序的過程中，發(fā)現(xiàn)函數(shù)定義末尾缺少花括號(hào)，該情況是 語法 錯(cuò)誤；發(fā)現(xiàn)除數(shù)為 0，該情況是 語義 錯(cuò)誤。 1.7 推導(dǎo) S=>?H=>?FTP =>?FTc=>?Fbc=>?abc 是 最右/規(guī)范 推導(dǎo)。 1.8 產(chǎn)生式 FA*F|A 提取左因子的結(jié)果為 F->AF' F'->*F| 。 1.9 對(duì)于算術(shù)表達(dá)式 “a*b+c”，當(dāng)采用預(yù)測(cè)分析方法時(shí)，接受格局中的“當(dāng)前剩余輸入”應(yīng)該 為空 ，初始格局中的“當(dāng)前剩余輸入”應(yīng)該是 a*b+c 。 1.10 最左歸約是 最

4、右推導(dǎo)/規(guī)范推導(dǎo) 的逆過程，每步直接歸約均是用 產(chǎn)生式左部非終結(jié)符 替換右句型中的 句柄 ，直到歸約為文法開始符號(hào)。 1.11 在引用調(diào)用的參數(shù)傳遞方式中，調(diào)用時(shí)傳遞的是實(shí)參的 地址 ，要求實(shí)參必須是 左值 ，過程內(nèi)部對(duì)形參的修改等價(jià)于 對(duì)實(shí)參的修改 。 1.12 假定運(yùn)算+與*都是左結(jié)合的，且運(yùn)算*比運(yùn)算+優(yōu)先級(jí)高，則算術(shù)表達(dá)式 x+y*(u+v)的后綴式是 xyuv+*+ 。 1.13 拉鏈-回填技術(shù)是語法制導(dǎo)翻譯過程中使用的一種基本技術(shù)，其基本思想是當(dāng)三地址碼中的轉(zhuǎn)向不確定時(shí) 將所有轉(zhuǎn)向同一地址的三地址碼拉成一個(gè)鏈 ，而一旦所轉(zhuǎn)向的地址被確定，則 為此鏈上所有的三地址碼回填入此地址 。

5、2、簡(jiǎn)答題（20 分） 2.1 簡(jiǎn)述語言的語法和語義，并舉一個(gè)實(shí)際的例子加以說明。 答：語法規(guī)定了句子形成的規(guī)則，表述了語言的形式，或者說語言的樣子和結(jié)構(gòu)，也被稱為語法規(guī)則。根據(jù)語法規(guī)則可以識(shí)別記號(hào)流中的語言結(jié)構(gòu)，也被稱為語法分析。語義揭示了語言本身的含義、施加于語言結(jié)構(gòu)上的限制或要執(zhí)行的動(dòng)作。例如“貓吃老鼠”和“老鼠吃貓”都是語法正確的句子，但后者表述的語義不對(duì)。（自己組織語言即可） 2.2 如果一個(gè)集合中的元素都是長(zhǎng)度不小于 1 且均不以 ab 開始的 a、 b 串，請(qǐng)給出描述該集合的正規(guī)式。 答：a|（aa|b）（a|b）* 2.3 語法分析器在編譯器中應(yīng)完成什么任務(wù)？答：語法分析器根據(jù)

6、語法規(guī)則識(shí)別出記號(hào)流中的結(jié)構(gòu)，并構(gòu)造一棵能夠正確反映該結(jié)構(gòu)的語法樹。檢查輸入中的錯(cuò)誤，調(diào)用出錯(cuò)管理器進(jìn)行適當(dāng)處理。 2.4 給定文法 G：CC h T|T TT a F|F Fv 請(qǐng)給出該文法的終結(jié)符集合、非終結(jié)符集合，并指出文法的開始符號(hào)。 答：終結(jié)符：h、a、v 非終結(jié)符：C、T、F 開始符號(hào)：C 2.5 給出下圖中的樹對(duì)應(yīng)的三地址碼序列。 解： 2.6 假設(shè)數(shù)組下標(biāo)從 0 開始，對(duì)于有 5 行 6 列的數(shù)組 a56，已知該數(shù)組的存儲(chǔ)空間首地址為 a，每個(gè)元素占用存儲(chǔ)空間大小為 w，請(qǐng)給出數(shù)組以行為主存放時(shí)元素 a23的地址。 答：a+（2*6+3）* w =15w+a 3、計(jì)算題（50

7、分） 3.1 給定正規(guī)式 R = a(a|b)* <1> 用 Thompson 算法構(gòu)造識(shí)別 L(R)的 NFA N； <2> 用“子集法”把 N 確定化（寫出完整過程），得到識(shí)別 L(R)的 DFA D； <3> 如果 D 不是最簡(jiǎn) DFA，請(qǐng)找出最簡(jiǎn) DFA D。答：<1>筆誤：紅線一端從 1 開始。 <2> E_閉包（0）=0 A E_閉包（smove(A,a)）=1,2,3,5,8 B E_閉包（smove(B,a)）=2,3,4,5,7,8 C E_閉包（smove(B,b)）=2,3,5,6,7,8 D E_閉包（smov

8、e(C,a)）=2,3,4,5,7,8 C E_閉包（smove(C,b)）=2,3,5,6,7,8 D E_閉包（smove(D,a)）=2,3,4,5,7,8 C E_閉包（smove(D,b)）=2,3,5,6,7,8 D a b A B - B C D C C D D C D DFA: <3> Move(C,a)=C Move(C,b)=D Move(D,a)=C Move(D,b)=D B、C、D 不可分。合并為一。 DFA A: 3.2 給定文法 G： BB & C | C CE < E | E EE | n 和右句型“B & n < n”

9、。 <1>畫出該句型對(duì)應(yīng)的分析樹； <2>指出句型中的所有短語、直接短語和句柄。 解： <1> <2> 短語：B & n < n(B1)、n < n(C)、n(E2)、n(E1)、n(E3) 直接短語：n(E1)、n(E3) 句柄：n(E1) 3.3 給定文法 G 的拓廣文法如下: S S S E $ E id E id ( E ) E E + id <1>構(gòu)造識(shí)別 G 所有活前綴的 DFA； <2>G 是 SLR(1)文法嗎？為什么？ <3>G 是 LL(1)文法嗎？為什么？若不是，請(qǐng)改寫

10、為等價(jià)的 LL(1)文法。解： <1> <2>是 I3 中存在移進(jìn)規(guī)約沖突。 FOLLOW(E) ( = Ø,則沖突可解決。因此，是SLR(1)文法。 <3>不是因?yàn)榇嬖谧筮f歸和左因子。EàE+id|id|id(E) 消除左遞歸：EàidE|id(E)E E=+idE| 消除左因子：EàidF FàE|(E)E 3.4 給定上下文無關(guān)文法和語義規(guī)則如下： S aS1a S.count := S1.count + 2; | bS1b S.count := S1.count + 2; | C S.count := C.count; C cC1 C.count := C1.count + 1; | c C.count := 1; <1> 畫出輸入序列 aabbccbbaa 的分析樹； <2> 根據(jù)語義規(guī)則標(biāo)注分析樹上對(duì)應(yīng)文法符號(hào)的.count 值；解： <1> 注：.c 就是.count，此處為簡(jiǎn)略表示。 <2> 如上圖示。 3.5 忽略過程參數(shù)的快排序的部分 Pascal 聲明代碼如下： program sort; var a:array10of integer; x:integer; procedure quicksort; var