《編譯原理 龍書 第二版 第5、6章》由會員分享，可在線閱讀，更多相關《編譯原理 龍書 第二版 第5、6章（6頁珍藏版）》請在裝配圖網上搜索。
1、第五章
練習5.1.1：
對于圖5-1中的SDD，給出下列表達式對應的注釋語法分析樹：
1）（3+4）*（5+6）n
練習5.2.4：
這個文法生成了含“小數點”的二進制數：
S->L.L|L L->LB|B B->0|1
設計一個L屬性的SDD來計算S.val，即輸入串的十進制數值。比如，串101.101應該被翻譯為十進制的5.625。提示：使用一個繼承屬性L.side來指明一個二進制位在小數點的哪一邊。
答：
元文法消除左遞歸后可得到文法：
S->L.L|L L->BL’ L’->BL’|ε B->0|1
使用繼承屬性L.side指明
2、一個二進制位數在小數點的哪一邊,2表示左邊，1表示右邊
使用繼承屬性m記錄B的冪次
非終結符號L和L’具有繼承屬性inh、side、m和綜合屬性syn
產生式
語義規(guī)則
1)S->L
S.val=L.syn;
L.side=2;L.m=1;L.inh=0
2)S->L1.L2
L1.side=2;L2.side=1; L1.inh=0;L1.m=1;L2.m=1/2;L2.inh=0
S.val=L1.syn+L2.syn;
3)L->BL’
L’.m=L.m*L.m;L’.side=L.side
L’.inh=L.inh*L.side+B
3、*L.m
L.syn=L’.syn
4)L’->BL1’
L1’.m=L’.m*L’.m;L1’.side=L’.side
L1’.inh=L’.inh*L’.side+B*L1’.m
L’.syn=L1’.syn
5)L’->ε
L’.syn=L’.inh
6)B->0
B.val=0
7)B->1
B.val=1
練習5.3.1：下面是涉及運算符+和整數或浮點運算分量的表達式文法。區(qū)分浮點數的方法是看它有無小數點。
E-〉E+T|T T-〉num.num|num
1）給出一個SDD來確定每個項T和表達式E的類型
2）擴展（1）中得到的SDD，使
4、得它可以把表達式轉換成為后綴表達式。使用一個單目運算符intToFloat把一個整數轉換為相等的浮點數
答：
(1)
產生式
語義規(guī)則
1)E->E1+T
If E1.type ==T.type then E.type=E1.type
else E.type=float
2)E->T
E.type=T.type
3)T->num
T.type=integer
4)T->num.num
T.type=float
(2)
產生式
語義規(guī)則
1)E->E1+T
If E1.type ==T.type then E.type=E1.type
El
5、se begin
E.type=float
If(E1.type==integer and T.type==float) then E1=intToFloat(E1)
Else if(T.type==integer and E1.type==float) then T=intToFloat(T)
END
E.val = E1.val T.val +
2)E->T
E.type=T.type ; E.val=T.val
3)T->num
T.type=integer; T.val=num
4)T->num.num
T.type=float ; T.val=num.nu
6、m
練習5.4.4：為下面的產生式寫出一個和例5.10類似的L屬性SDD。這里的每個產生式表示一個常見的C語言中的那樣的控制流結構。你可能需要生成一個三地址語句來跳轉到某個標號L，此時你可以生成語句goto L
1）S->if (C) S1 else S2
2）S->do S1 while (C)
3）S->’{’ L ‘}’; L -> LS|ε
請注意，列表中的任何語句都可以包含一條從它的內部跳轉到下一個語句的跳轉指令，因此簡單地為各個語句按序生成代碼是不夠的。
答：
產生式
語義規(guī)則
1) S->if (C) S1 else S2
C.false=Ne
7、wLable();C.true=NewLable()
S1.next=S2.next=S.next
S.code=C.code
|| Lable(C.true) || S1.code
|| gen(‘goto’ S.next)
|| Lable(C.false)|| S2.code
2) S->do S1 while (C)
Begin=NewLable()
C.false=NewLable(); C.true=NewLable()
S1.next=begin
S.code=Lable(begin)||S1.code
|
8、| Lable(C.true)
|| gen(‘goto’begin)
3) S->’{’ L ‘}’;
L -> L1S
L->ε
S.syn=L.syn;
S.inh=L1.syn; L.syn=S.syn
L.inh=L.syn
第六章
練習6.1.1：為下面的表達式構造DAG
（（x+y）-（（x+y）*（x-y）））+（（x+y）*（x-y））
答：DAG如下
*
+
-
-
+
Y
X
練習6.2.1：將算術表達式a+ - (b+c)翻譯成
1） 抽象語法樹
2） 四
9、元式序列
3） 三元式序列
4） 間接三元式序列
答：(1)抽象語法樹
c
b
+
+
minus
a
(2) 四元式序列
t1=b+c
t2=minus t1
t3=a+t2
op
Arg1
Arg2
result
0
+
b
c
T1
1
minus
T1
T2
2
+
a
T2
T3
(3)三元式序列
op
Arg1
Arg2
0
+
b
c
1
minus
(0)
2
+
a
(1)
(4)間接三元式序列
10
10、(0)
11
(1)
12
(2)
op
Arg1
Arg2
0
+
b
c
1
minus
(0)
2
+
a
(1)
instruction
練習6.4.3：使用圖6-22中的翻譯方案，來翻譯下列賦值語句
x=a[i][j]+b[i][j]
答：
假定數組a,b均為2*3規(guī)模的整型數組，且一個整數的寬度為4
x=a[i][j]+b[i][j]的注釋語法分析樹如下
S
X
E.addr=t8
11、E.addr=t4
E.addr=t9
=
+
L.addr=t7
L.array=b
L.type=integer
L.addr=t3
L.array=a
L.type=integer
L.addr=t5
L.array=b
L.type=array(3,integer)
L.addr=t1
L.type=array(3,integer)
L.array=a
[ E.addr= j ]
[ E.addr=j ]
j
a.type
=array(2,array(3,integer))
[
12、E.addr=i ]
b.type
=array(2,array(3,integer))
[ E.addr= i ]
i
j
i
x=a[i][j]+b[i][j]被翻譯成的三地址代碼如下如下
T1=i*12 T5=i*12
T2=j*4 t6=j*4
T3=t1+t1 t7=t5+t6
T4=a[t3] t8=b[t7]
T9=t4+t8
X=t9
練習6.6.4：使用圖6.6.5節(jié)中介紹的避免goto語句的翻譯方案，來翻譯下列表達式：
If （a==b && c
13、==d || e==f） x==1;
答：
If e==f goto L2
ifFalse a==b goto L1
ifFalse c==d goto L1
L2: x==1
L1:
練習6.7.1：使用圖6-43中的翻譯方案翻譯下列表達式。給出每個子表達式的truelist和falselist。你可以假設第一條被生成的指令地址是100.
a==b && (c==d || e==f)
答：
構造表達式的注釋語法分析樹如下
B.t={102,104}
B.f={101,105}
14、M.i={102}
)
(
B.t={102,104}
B.f={105}
B.t={102,104}
B.f={105}
&&
B.t={100}
B.f={101}
a == b
M.i={104}
||
B.t={102}
B.f={103}
B.t={104}
B.f={105}
ε&
ε&
c == d
e == f
各產生式進行歸約時產生的語義動作的相應指令如下
1) 按B->E1 rel E2 將a==b 歸約為B時語義動作相應的指令如下
100:
15、 if a==b goto –
101: goto –
2) 產生式 B->B1 && M B2中的標記非終結符號M記錄了nextinstr的值，該值為102
3) 按B->E1 rel E2 將c==d 歸約為B時語義動作相應的指令如下
102: if c==d goto –
103: goto –
4) 產生式 B->B1 || M B2中的標記非終結符號M記錄了nextinstr的值，該值為104
5) 按B->E1 rel E2 將e==f 歸約為B時語義動作相應的指令如下
104: if e==f goto –
105: goto –
6) 按照產生式B->B1 || M B2進行歸約
7) 按照產生式B->（B1）進行歸約
8) 按照產生式B->B1 && M B2進行歸約
9) 各子表達式的truelist和falselist在上圖中已標出
編譯原理 龍書 第二版 第5、6章
