第八節習題
一、單項選擇題
1、將編譯程式分成若干個「遍」是為了 。
a．提高程式的執行效率
b．使程式的結構更加清晰
c．利用有限的機器記憶體並提高機器的執行效率
d．利用有限的機器記憶體但降低了機器的執行效率
2、構造編譯程式應掌握
a．源程式b．目標語言
c．編譯方法d．以上三項都是
3、變數應當 。
a．持有左值b．持有右值
c．既持有左值又持有右值 d．既不持有左值也不持有右值
4、編譯程式絕大多數時間花在上
a．出錯處理b．詞法分析
c．目標**生成d．管理**
5、 不可能是目標**
a．彙編指令**b．可重定位指令**
c．絕對指令**d．中間**
6、使用可以定義乙個程式的意義。
a．語義規則b．詞法規則
c．產生規則d．詞法規則
7、詞法分析器的輸入是 。
a．單詞符號串b．源程式
c．語法單位d．目標程式
8、中間**生成時所遵循的是- 。
a．語法規則b．詞法規則
c．語義規則d．等價變換規則
9、編譯程式是對 。
a．匯程式設計序的翻譯 b．高階語言程式的解釋執行
c．機器語言的執行 d．高階語言的翻譯
10、語法分析應遵循
a．語義規則b．語法規則
c．構詞規則d．等價變換規則
解答1、將編譯程式分成若干個「遍」是為了使編譯程式的結構更加清晰，故選b。
2、構造編譯程式應掌握源程式、目標語言及編譯方法等三方面的知識，故選d。
3、對編譯而言，變數既持有左值又持有右值，故選c。
4、編譯程式打交道最多的就是各種**，因此選d。
5、目標**包括彙編指令**、可重定位指令**和絕對指令**3種，因此不是目標**的只能選d。
6、詞法分析遵循的是構詞規則，語法分析遵循的是語法規則，中間**生成遵循的是語義規則，並且語義規則可以定義乙個程式的意義。因此選a。
7、b 8、c 9、d 10、c
二、多項選擇題
1、編譯程式各階段的工作都涉及到
a．語法分析b．**管理c．出錯處理
d．語義分析e．詞法分析
2、編譯程式工作時，通常有階段
a．詞法分析b．語法分析c．中間**生成
d．語義檢查e．目標**生成
解答1．b、c 2. a、b、c、e
三、填空題
1、解釋程式和編譯程式的區別在於 。
2、編譯過程通常可分為5個階段，分別是 、語法分析 、**優化和目標**生成。 3、編譯程式工作過程中，第一段輸入是 ，最後階段的輸出為程式。
4、編譯程式是指將程式翻譯成程式的程式解答
是否生成目標程式 2、詞法分析中間**生成 3、源程式目標**生成 4、源程式目標語言
一、單項選擇題
1、文法g：s→xsx|y所識別的語言是
a. xyx b. (xyxc. xnyxn(n≥0) d. x*yx*
2、文法g描述的語言l(g)是指 。
a. l(g)=
c. l(g)= d. l(g)=
3、有限狀態自動機能識別 。
a. 上下文無關文法 b. 上下文有關文法
c.正規文法d. 短語文法
4、設g為算符優先文法，g的任意終結符對a、b有以下關係成立 。
a. 若f(a)>g(b)，則a>b b.若f(a)c. a~b都不一定成立 d. a~b一定成立
5、如果文法g是無二義的，則它的任何句子
a. 最左推導和最右推導對應的語法樹必定相同
b. 最左推導和最右推導對應的語法樹可能不同
c. 最左推導和最右推導必定相同
d. 可能存在兩個不同的最左推導，但它們對應的語法樹相同
6、由文法的開始符經0步或多步推導產生的文法符號串行是 。
a. 短語 b.控制代碼 c. 句型 d. 句子
7、文法g：e→e+t|t
t→t*p|p
p→(e)|i
則句型p+t+i的控制代碼和最左素短語為 。
和i b. p和p+t c. i和p+t+i 和t
8、設文法為：s→sa|a
a→a|b
則對句子aba，下面是規範推導。
a. ssasaaaaaaaaabaaba
b. ssasaaaaaaaaabaaba
c. ssasaasaasbaabaaba
d. ssasasaasbaabaaba
9、文法g：s→b|∧(t)
t→t,s|s
則firstvt(t) 。
a.10、產生正規語言的文法為 。
a. 0型b. 1型c. 2型d. 3型
11、採用自上而下分析，必須 。
a. 消除左遞迴 b. 消除右遞迴 c. 消除回溯d. 提取公共左因子
12、在規範歸約中，用來刻畫可歸約串。
a. 直接短語b. 控制代碼c. 最左素短語 d. 素短語
13、有文法g：e→e*t|t
t→t+i|i
句子1+2*8+6按該文法g歸約，其值為 。
a. 23 b. 42 c. 30 d. 17
14、規範歸約指 。
a. 最左推導的逆過程b. 最右推導的逆過程
c. 規範推導d. 最左歸約的逆過程
[解答]
1、選c。
2、選a。
3、選c。
4、雖然a與b沒有優先關係，但構造優先函式後，a與b就一定存在優先關係了。所以，由f(a)>g)(b)或f(a)5、如果文法g無二義性，則最左推導是先生長右邊的枝葉：對於d，如果有兩個不同的是了左推導，則必然有二義性。
故選a。
6、選c。
7、由圖2-8-1的語法樹和優先關係可以看出應選b。
8、規範推導是最左推導，故選d。
9、由t→t,…和t→(… 得firstvt(t
由t→s得firstvt(s)firstvt(t)，而firstvt(s)=；即
firstvt(t)={b因此選c。
10、d 11、c 12、b 13、b 14、b
三、填空題
1、文法中的終結符和非終結符的交集是 。詞法分析器交給語法分析器的文法符號一定是 ，它一定只出現在產生式的部。
2、最左推導是指每次都對句型中的非終結符進行擴充套件。
3、在語法分析中，最常見的兩種方法一定是分析法，另一是分析法。
4、採用語法分析時，必須消除文法的左遞迴。
5、 樹代表推導過程， 樹代表歸約過程。
6、自下而上分析法採用 、歸約、錯誤處理、 等四種操作。
7、chomsky把文法分為種型別，編譯器構造中採用和文法，它們分別產生和語言，並分別用和自動機識別所產生的語言。
解答 1、空集終結符右
2、最左
3、自上而上自下而上
4、自上而上
5、語法分析
6、移進接受
7、4 2 型 3型上下文無關語言正規語言下推自動機有限
四、判斷題
1、文法 s→as|br|ε描述的語言是(a|bc
r→cs
2、在自下而上的語法分析中，語法樹與分析樹一定相同
3、二義文法不是上下文無關文法
4、語法分析時必須先消除文法中的左遞迴
5、規範歸約和規範推導是互逆的兩個過程
6、乙個文法所有句型的集合形成該文法所能接受的語言
解答 1、對 2、錯 3、錯 4、錯 5、錯 6、錯
五、簡答題
1、控制代碼 2、素短語 3、語法樹 4、歸約 5、推導
[解答]
1、控制代碼：乙個句型的最左直接短語稱為該句型的控制代碼。
2、素短語：至少含有乙個終結符的素短語，並且除它自身之外不再含任何更小的素短語。
3、語法樹：滿足下面4個條件的樹稱之為文法g[s]的一棵語法樹。
①每一終結均有一標記，此標記為vn∪vt中的乙個符號；
②樹的根結點以文法g[s]的開始符s標記；
③若一結點至少有乙個直接後繼，則此結點上的標記為vn中的乙個符號；
④若乙個以a為標記的結點有k個直接後繼，且按從左至右的順序，這些結點的標記分別為x1,x2,…,xk，則a→x1,x2,…,xk，必然是g的乙個產生式。
4、歸約：我們稱αγβ直接歸約出αaβ，僅當a→γ 是乙個產生式，且α、β∈(vn∪vt)*。歸約過程就是從輸入串開始，反覆用產生式右部的符號替換成產生式左部符號，直至文法開始符。
5、推導：我們稱αaβ直接推出αγβ，即αaβαγβ，僅當a→ γ 是乙個產生式，且α、β∈(vn∪vt)*。如果α1α2…αn，則我們稱這個序列是從α1至α2的乙個推導。
若存在乙個從α1αn的推導，則稱α1可推導出αn。推導是歸約的逆過程。
六、問答題
1、給出上下文無關文法的定義。
[解答]
乙個上下文無關文法g是乙個四元式（vt,vn,s, p），其中：
●vt是乙個非空有限集，它的每個元素稱為終結符號；
●vn是乙個非空有限集，它的每個元素稱為非終結符號，vt∩vn=φ；
●s是乙個非終結符號，稱為開始符號；
●p是乙個產生式集合（有限），每個產生式的形式是p→α，其中，p∈vn，
α∈(vt∪vn)*。開始符號s至少必須在某個產生式的左部出現一次。
編譯原理複習題 手打
編譯原理複習提綱 1.編譯程式是對高階語言的翻譯。2.詞法分析器輸出的單詞符號常常表示成二元式。3.編譯技術中常用屬性文法描述程式語言的語義。4.dfa是五元組 有限狀態集合，有窮字母表，轉換函式，初始狀態，終止狀態集合 5.如果文法g是無二義的，則它的任何句子最左推導和最右推導對應的語法樹必定相同...
編譯原理期末複習總結
一 簡答題 1.什麼是編譯程式？答 編譯程式是一種將高階語言程式 源程式 翻譯成低階語言 目標程式 的程式 將高階程式語言程式翻譯成邏輯上等價的低階語言 組合語言,機器語言 程式的翻譯程式。2.請寫出文法的形式定義？答 乙個文法g抽象地表示為四元組g vn,vt,p,s 其中vn表示非終結符號 vt...
管理學原理期末複習題
1.管理 2.決策 3.部門化 4.集中化戰略 5.組織結構 6.參謀職權 7.人員配備 8.領導生命週期 9.命令統一原則與權責一致原則 10.9.9型管理與9.1型管理 11.保健因素 12.激勵 13.控制 14.流動比率 15.經濟環境 16.獎賞權力與專家權力 17.非正式組織 18.固定...