編譯原理題-帶答案

一、判斷題（）
1．一個 LL(l)文法一定是無二義的。 ( N)
2．正規文法產生的語言都可以用上下文無關文法來描述。 ( N)
3．一張轉換圖只包含有限個狀態，其中有一個被認為是初態，最多只有一個終態。 ( Y)
4．目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。 ( N)
5．逆波蘭法錶示的錶達式亦稱前綴式 。 (Y )
6．如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。 (Y )
7．LR 法是自頂向下語法分析方法。 ( N)
8．數組元素的地址計算與數組的存儲方式有關。( N)
9．算符優先關系錶不一定存在對應的優先函數。 (N )
10．對於數據空間的存貯分配， FORTRAN 采用動態貯存分配策略。 (N )
參考答案：
1、× 2、× 3、√ 4、× 5、√
6、√ 7、× 8、× 9、× 10、×

二． 填空題（每空 2 分，共 20 分）

1. 不同的編譯程序關於數據空間的存儲分配策略可能不同，但大部分編譯中采用的方案有兩種：靜態存儲分配方案和動態存儲分配方案，而後者又分為（1） 和 （2） 。
2. 規範規約是最（3）規約。
3. 編譯程序的工作過程一般劃分為 5 個階段：詞法分析、（4） 、語義分析與中間代碼生成，代碼優化及（5） 。另外還有（6）和出錯處理。
   4．錶達式 x+yz/(a+b)的後綴式為 （7） 。
   5．文法符號的屬性有綜合屬性和 （8）。
   6．假設二比特數組按行存放，而且每個元素占用一個存儲單元，則數組 a[1…15,1…20]某個元素 a[i，j]的地址計算公式為（9）。
   7．局部優化是局限於一個（10）範圍內的一種優化。
   答案：
   (1) 棧式動態存儲分配
   (2) 堆式動態存儲分配
   (3) 左
   (4) 語法分析
   (5) 目標代碼生成
   (6) 錶格管理
   (7) xyzab+/+
   (8) 繼承屬性
   (9) a+(i-1)*20+j-1
   (10) 基本塊

三． 選擇題（每問 2 分，共 20 分）

1. 一個上下文無關文法 G 包括四個組成部分：一組終結符，一組非終結符，一個（C ），以及一組 產生式。
   A． 字符串 B． 產生式 C． 開始符號 D． 文法

2.程序的基本塊是指（D ）。
A． 一個子程序 B． 一個僅有一個入口和一個出口的語句
C． 一個沒有嵌套的程序段 D． 一組順序執行的程序段，僅有一個入口和一個出口

3. 高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬於（ B）分析方法。
   A． 自左向右 B． 自頂向下 C． 自底向上 D． 自右向左

4．在通常的語法分析方法中，（A ）特別適用於錶達式的分析。
A． 算符優先分析法 B． LR 分析法
C． 遞歸下降分析法 D． LL（1）分析法

5．經過編譯所得到的目標程序是（ D）。
A． 四元式序列 B． 間接三元式序列
C． 二元式序列 D． 機器語言程序或匯編語言程序
6. 設有文法 G[I]： I I → I1|I0|Ia|Ic|a|b|c
下列符號串中是該文法句子的有（ B）。
① ab0 ② a0c01 ③ aaa ④ bc10
可選項有：
A． ① B．②③④ C．③④ D．①②③④
7.程序的基本塊是指（ D）。
A． 一個子程序 B． 一個僅有一個入口和一個出口的語句
C． 一個沒有嵌套的程序段 D． 一組順序執行的程序段，僅有一個入口和一個出口
8. 高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬於（B ）分析方法。
A． 自左向右 B． 自頂向下 C． 自底向上 D． 自右向左
9．經過編譯所得到的目標程序是（ D）。
A． 四元式序列 B． 間接三元式序列
C． 二元式序列 D． 機器語言程序或匯編語言程序
10． 運行階段的存儲組織與管理的目的是（ C）。
① 提高編譯程序的運行速度 ② 節省編譯程序的存儲空間
③ 提高目標程序的運行速度 ④ 為運行階段的存儲分配做准備
可選項有：
A. ①② B. ②③ C. ③④ D. ④②
四、簡答題（每題10分，共30分）

1. 已知文法 G[S] 為：
   S→dAB
   A→aA|a
   B→Bb|ε
   G[S] 產生的語言是什麼？
   參考答案：
   答：G[S]產生的語言是L(G[S])={danbm│n≥1,m≥0}。

2. 簡述 DFA 與 NFA 有何區別 ?
   參考答案：
   答：DFA與NFA的區別錶現為兩個方面:一是NFA可以若幹個開始狀態，而DFA僅只一個開始狀態。 另一方面，DFA的映象M是從K×∑到K，而NFA的映象M是從K×∑到K的子集， 即映象M將產生一個狀態集合（可能為空集），而不是單個狀態。

3. 何謂優化？按所涉及的程序範圍可分為哪幾級優化？
   參考答案：
   (1)優化：對程序進行各種等價變換，使得從變換後的程序出發，能產生更有效的目標代碼。　　　 　　　　　
   (2) 三種級別：局部優化、循環優化、全局優化。

五、計算題（共20分）
考慮以下文法:
D →　T V
T →　int | float
V → id ,V | id
在該文法中提取左公因子。
為所得的文法的非終結符構造First集合和Follow集合。
說明所得的文法是LL(1)文法。
為所得的文法構造LL(1)分析錶
假設有輸入串 int x,y,z 寫出相應的LL(1)分析程序的動作
答案：
a. 文法存在左公因子，提取左公因子後的文法為：
　　 D →　T V
T →　int | float
V → id V’
V’→ ,V |ε

b.
非終結符
First集合
Follow集合

D
{ int , float }
{ $ }

T
{ int , float }
{ id }

V
{ id }
{ $ }

V’
{ , , ε }
{ $ }

c. (1) First ( TV ) = { int , float }
First(int) ∩ First(float)={int}∩{float}=φ;
First(id V’)={id}；
First(,V) ∩First(ε)={,} ∩{ ε}}=φ;
(2) V’=>ε,
First(V’)∩Follow(V’)= { , , ε }∩{ $ }=φ
根據LL(1)文法的定義判斷，此文法是LL(1)文法；