編譯原理清華第三版答案黃賢英
Ⅰ 編譯原理題目關於判斷LL(1)文法的
A 不是，因為含有左公共引子a
B 和D不是，因為含有左遞歸
C是，因為SELECT(S→aS) 與SELECT(S→b)的交集為空，符合LL(1)文法的定義。
Ⅱ 編譯原理：靜態數組的存儲空間可以在編譯時確定。這句話為什麼是錯的。請給出詳細原因，謝謝。
靜態數組指的是寫代碼期間就知道大小的數組，比如int a[10];
char s[] = "hello";
這個靜態和動態分配相區別，不要和static弄混了，static/extern/auto是用於說明變數的存儲方式——也就是說，靜態數組也可以是static的，也可以是extern的，也可以是auto的。
舉個例子，下面就是一個靜態數組，但是存儲方式是auto的。
voidtest()
{
inta[10];
}
這個數組的存儲空間無法在編譯時候確定，只能在運行期間確定，原因是：盡管可以確定數組的大小，但是不能確定它的首地址。
再比如：
static int sa[10] = {0};
這個數組的存儲空間在編譯時，就可以確定了。
Ⅲ 編譯原理題：分別構造下列語言的文法（4個題） 200分獻上。。。
（3）任何不是以0打頭的所有奇整數所組成的集合
解：G(S)
=
({S,A,B,I,J},{-,0,1,2,3,4,5,6,7,8,9},{S→J|IBJ,B→0B|IB|e,
I→J|2|4|6|8,
Jà1|3|5|7|9},S)
（4）所有偶數個0和偶數個1所組成的符號串集合
解：對應文法為
S→0A|1B|e，A→0S|1C
B→0C|1S
C→1A|0B
Ⅳ 編譯原理 設文法G[S] 求答案！
·消除左遞歸 S→aAS'|∧aAS'
S'→VaAS'|ε對A的產生式提取左因子 A→∧aA' A'→A|ε
· 非終結符合 First Follow
S a∧ #
S』 V ε #
A ∧ #
A『 ∧ #
Select（S→aAS'）=a
Select(S→∧aAS')=∧
Select(S'→VaAS')=V
Select(S'→ε)=#
Select(A→∧aA')=∧
Select(A'→A)=∧
Select(A'→ε)=#
符合LL（1）文法
a ∧ V #
S S→aAS' S→∧aAS'
S' S'→VaAS' S'→ε
A A→∧aA'
A' A'→A A'→ε
Ⅳ 編譯原理問題，高手進。
回答下列問題：(30分)
(6分)對於下面程序段
program test (input, output)
var i, j: integer;
procere CAL(x, y: integer);
begin
y:=y*y; x:=x-y; y:=y-x
end;
begin
i:=2; j:=3; CAL(i, j)
writeln(j)
end.
若參數傳遞的方法分別為(1)傳值、(2)傳地址，(3)傳名，請寫出程序執行的輸出結果。
答： (1) 3 (2) 16 (3) 16 (每個值2分)
(6分)計算文法G(M)的每個非終結符的FIRST和FOLLOW集合，並判斷該文法是否是LL(1)的，請說明理由。
G(M)：
M → TB
T → Ba |
B → Db | eT |
D → d |
解答：
計算文法的FIRST和FOLLOW集合：(4分)
FIRST(M) = { a，b，e，d， } FIRST(T) = { a，b，e，d， }
FIRST(B) = {b，e，d， } FIRST(D) = {d，}
FOLLOW (M) = {#} FOLLOW (T) = { a，b，e，d，#}
FOLLOW (B) = {a，# } FOLLOW (D) = { b}
檢查文法的所有產生式，我們可以得到：
1. 該文法不含左遞歸，
2. 該文法中每一個非終結符M，T，B，D的各個產生式的候選首符集兩兩不相交。
3. 該文法的非終結符T、B和D，它們都有候選式，而且
FIRST(T)∩FOLLOW(T)={ a，b，e，d }≠
所以該文法不是LL(1)文法。(2分)
(4分)考慮下面的屬性文法
產 生 式 語 義 規 則
S→ABC
A→a
B→b
C→c B.u := S.u
A.u := B.v + C.v
S.v := A.v
A.v :=3*A.u
B.v := B.u
C.v := 1
畫出字元串abc的語法樹;
對於該語法樹，假設S.u的初始值為5，屬性計算完成後，S.v的值為多少。
答：(1) (2分)
(2) S.v的值為18 (2分)
(4分)運行時的DISPLAY表的內容是什麼？它的作用是什麼？
答：DISPLAY表是嵌套層次顯示表。每當進入一個過程後，在建立它的活動記錄區的同時建立一張嵌套層次顯示表diaplay.假定現在進入的過程層次為i，則它的diaplay表含有i+1個單元，自頂向下每個單元依次存放著現行層、直接外層、…、直至最外層(主程序，0層)等每層過程的最新活動記錄的起始地址。通過DISPLAY表可以訪問其外層過程的變數。
(5分)對下列四元式序列生成目標代碼：
A:=B*C
D:=E+A
G:=B+C
H:=G*D
其中，H在基本塊出口之後是活躍變數， R0和R1是可用寄存器。
答: 目標代碼序列
LD R0 B
MUL R0 C
LD R1 E
ADD R1 R0
LD R0 B
ADD R0 C
MUL R0 R1
ST R0 H
(5分)寫出表達式a+b*(c-d)對應的逆波蘭式、三元式序列和抽象語法樹。
答：
逆波蘭式：(abcd-*+) (1分)
三元式序列: (2分)
OP ARG1 ARG2
(1) - c d
(2) * b (1)
(3) + a (2)
抽象語法樹：(2分)
(8分)構造一個DFA，它接受={a，b}上所有包含ab的字元串。
答：
(2分)構造相應的正規式：(a|b)*ab(a|b)*
(3分)
a a
a b
b b
(3分)確定化：
I
{0,1,2} {1,2,3} {1,2}
{1,2,3} {1,2,3} {1,2,4,5,6}
{1,2} {1,2,3} {1,2}
{1,2,4,5,6} {1,2,3,5,6} {1,2,5,6}
{1,2,3,5,6} {1,2,3,5,6} {1,2,4,5,6}
{1,2,5,6} {1,2,3,5,6} {1,2,5,6}
b b
b a
a a a a
a b b
b
最小化：
{0，1，2} {3，4，5}
{0， 2}，1， {3，4，5}
(6分)寫一個文法使其語言為L(G)={anbncm| m,n≥1，n為奇數，m為偶數}。
答：
文法G(S):
(8分)對於文法G(S):
1. 寫出句型b(Ma)b的最右推導並畫出語法樹。
2. 寫出上述句型的短語，直接短語和句柄。
答：
1. (4分)
2. (4分)
短語: Ma)， (Ma)， b(Ma)b
直接短語: Ma)
句柄: Ma)
(12分)對文法G(S)：
S → a | ^ | (T)
T → T，S | S
(1) 構造各非終結符的FIRSTVT和LASTVT集合;
(2) 構造算符優先表;
(3) 是算符優先文法嗎?
(4) 構造優先函數。
答：
(1) (4分)
(2) (4分)
a ^ ( ) ,
a > >
^ > >
( < < < = <
) > >
, < < < > >
(3) 是算符優先文法，因為任何兩個終結符之間至多隻有一種優先關系。 (1分)
(4) 優先函數(3分)
a ^ ( ) ,
F 4 4 2 4 4
G 5 5 5 2 3
(8分)設某語言的do-while語句的語法形式為
S do S(1) While E
其語義解釋為：
針對自下而上的語法分析器，按如下要求構造該語句的翻譯模式，將該語句翻譯成四元式：
(1) 寫出適合語法制導翻譯的產生式；
(2) 寫出每個產生式對應的語義動作。
答：(1). 適合語法制導翻譯的文法(4分)
G(S):
R do
UR S(1) While
SU E
(2). (4分)
R do
{ R.QUAD:=NXQ }
UR S(1) While
{ U.QUAD:=R.QUAD;
BACKPATCH(S.CHAIN, NXQ) }
SU E
{ BACKPATCH(E.TC, U.QUAD);
S.CHAIN:=E.FC }
答案二：
(1) S do M1 S(1) While M2 E
M ε (4分)
(2) M ε { M.QUAD := NXQ } (4分)
S do M1 S(1) While M2 E
{
BACKPATCH(S(1).CHAIN, M2.QUAD);
BACKPATCH(E.TC, M1.QUAD);
S.CHAIN:=E. FC
}
(10分)將語句
while C>0 do if A B=0 then C:=C+D else C:=C*D
翻譯成四元式。
答：
100 (j>， C， 0， 102)
101 (j， -， -， 112)
102 (jnz， A， -， 106)
103 (j， -， -， 104)
104 (j=， B， 0， 106)
105 (j， -， -， 109)
106 (+， C， D， T1)
107 (:=， T1， -， C)
108 (j， -， -， 100)
109 (*， C， D， T2)
110 (:=， T2， -， C)
111 (j， -， -， 100)
112
(10分)設有基本塊如下：
T1:=3
T2:=A*B
T3:=9+T1
M:=A*B
T4:=C-D
L:=T3*T4
T2:=C+D
N:=T2
畫出DAG圖；
設L，M，N 是出基本塊後的活躍變數，請給出優化後的四元式序列。
答：
1. (6分)
L
*
T2,M T4 T2,N
* - +
T1 T3
3 A B 12 C D
2. (4分)
M:=A*B
S1:=C-D
L:=12*S1
N:=C+D
(8分)文法G(S)及其LR分析表如下，請給出串baba#的分析過程。
(1) S → DbB (2) D → d (3) D → ε
(4) B → a (5) B → Bba (6) B → ε
LR分析表
ACTION GOTO
b D a # S B D
0 r3 s3 1 2
1 acc
2 s4
3 r2
4 r6 S5 r6 6
5 r4 r4
6 s7 r1
7 S8
8 r5 r5
解答：
步驟 狀態 符號 輸入串
0 0 # baba#
1 02 #D baba#
2 024 #Db aba#
3 0245 #Dba ba#
4 0246 #DbB ba#
5 02467 #DbBb a#
6 024678 #DbBba #
7 0246 #DbB #
8 01 #S # acc
哈哈，估計認識！！
Ⅵ 編譯原理follow集怎麼求例：s->xSNy|Nx;N->zN|空 答案：follow（S）={y,z,#},follw(N)={x,y}什麼時候有#
求某一非終結符的follow集，主要看產生式右端（含有該非終結符的右端）。
因為S是該文法的開始符，所以#在follow（S）中。在產生式S->xSNy的右端，S的後跟符號是first（Ny），即z和y。這樣follow（S）={y,z,#}
求follw(N)時，看產生式S->xSNy和S->Nx，在它們的右端都含有N，根據S->xSNy可知，y在follw(N)中；根據S->Nx可知，x在follw(N)中；這樣follw(N)={x,y}
雖然產生式N->zN的右端也含有N，但根據follow集合的定義，將follw(N)加入follw(N)中沒有意義，所以不用計算。
對於不是開始符的其他非終結符，其follow集合有沒有#，要看產生式的結構（產生式右端）。
Ⅶ 編譯原理 設有文法G（S） 這題怎麼做求答案
G[S] S→%A A→mAn A→% 1)准確指出文法屬於chomsy哪一型文法 2)首先要做這題你要知道判別文法類型包括四個層次： 0-型文法（無限制文法或