目錄

一、概念

二、詞法分析

三。自上而下分析語法——LL語法

1）消除左遞歸

? ?2) 消除回溯、提左因子? 、 FIRST集 和 FOLLOW 集

?3）預測分析法 與 FIRST集 和 FOLLOW 集的構建。

4)預測分析法中 預測分析表M的構建

四、自下而上的分析語法——算符優先分析法

1）對每個非終結符構建FIRSTVT 集 和LASTVT 集

2）構造算符優先關系表

五、語義分析

1）賦值語句和的簡單算數運算表達式的翻譯

2)布爾表達式的翻譯方法

3)典型控制語句的翻譯方法

六、目標代碼生成

1）基本塊劃分

2）寄存器選擇——寄存器的待用信息與活躍信息的確定

七、中間代碼的優化

(1) 基于DAG圖的優化方法?

---

一、概念

1）字母表、字符串、字符串和運算

• 字母表用 Σ 表示，是字符的非空有窮集合，字符是字母表Σ的元素
• 字符串，是字母表Σ中字符組成的有窮序列，其長度用? ?|<字符串>|? 表示。空串用是ε表示， |ε| = 0
• Σ* 指包括空串在內的Σ上所有字符串的集合。稱之為字母表的閉包。
• 字符串的方冪： 例如??? ?，指 連續n個a字符?
• 對于集合A的正則閉包 +? ?
• 對于集合A的閉包 * ,?

文法分類分為0型文法，1型文法，2型文法，3型文法，分別又稱為短語文法，上下文有關文法，上下文無關文法，正規文法 。

• 0型文法，短語文法： 每個產生式? α ->β? 左部α中至少又一個非終結符
• 1型文法，上下文有關文法： 在0型文法的基礎上，還滿足? |α|? <= |β|?
• 2型文法： 每個產生式? A->β? ?,其中A 是非終結符? ，? ?β是終結符和非終結符的閉包。
• 3型文法：每個產生式? A->αB? 或 A ->α 的形式，其中A和B 是非終結符，α是終結符

四元式：是?( op ,arg1,arg2,result) 形式的一個對象，其中op 表示中間代碼的操作符，result 表示 運算結果的臨時變量。

后綴式、逆波蘭式：在抽象語法樹中的后續遍歷得到的式子。例如a+b(中序)改寫成后綴式為ab+

二、詞法分析

單詞分為關鍵字、算符、標識符、常數、介符。詞法分析的目標是為了將代碼分解成對應的單詞，并對單詞打上些有意義的編碼，給后續的語法分析和語義分析使用。

單詞	編碼	單詞	編碼	單詞	編碼	單詞	編碼
end	1	or	11	（	21	:=	31
begin	2	program	12	）	22	=	32
bool	3	real	13	+	23	<=	33
do	4	then	14	-	24	<	34
else	5	true	15	*	25	<>	35
end	6	var	16	/	26	>	36
false	7	while	17	.	27	>=	37
if	8	標識符	18	，	28
integer	9	整數	19	:	29
not	10	實數	20	；	30

對代碼進行按行讀取，判斷每個單詞是否屬于關鍵字，或者介詞、標識符還是標識符等。大致方式

為：按行讀取，逐各讀取字符并將每個字符假如一個字符緩存變量中，讀取的字符如果是空格、換行、或者介詞、運算符（對應表格代碼是21~37）的話，則緩存變量中是一個完整的單詞。對著單詞表對單詞打上編碼，如果不存在則為標識符..

三。自上而下分析語法——LL語法

1）消除左遞歸

? ? ? ? 對于類似的產生式 “ A ->Aα | β ”都可以化簡成

????????????????????????????????A ->?βA'

????????????????????????????????A' ->?αA'? |?ε

? ? ? ? 實際上對于產生式都可以化簡成

? ?? ? ? ? ? 和? ? ? ?

?

? ?2) 消除回溯、提左因子? 、 FIRST集 和 FOLLOW 集

? ? ? 對所有非終結符的A的每個候選是α，定義其終結首符集，FIRST

? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ?對所有非終結符的A的每個候選是α，定義其后隨符號集，FOLLOW

? ? ? ? ? ? ? ? ? ? ? ? ?

?3）預測分析法 與 FIRST集 和 FOLLOW 集的構建。

? ? ? ?統計每個非終結符的 FIRST? ?和FOLLOW 集 ，并構建預測分析表。

?例如：對應文法G[E]：

? ? ? ? ? ? ? ? ? ? ? ? E →? E? +? ?T? |? ?T

? ? ? ? ? ? ? ? ? ? ? ? T? → T * F? | F?

? ? ? ? ? ? ? ? ? ? ? ? F? →( E ) | i

現有輸入串? ? i? *(i + i) ，判斷其語法是否正確？

? ? ? 首先先消除左遞歸，得到新文法如下?

? ? ? ? ? ? ? ? ? ? ? ? ?E?→ T E'? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?.....①

? ? ? ? ? ? ? ? ? ? ? ? E'?→ + T E' |?ε? ? ? ? ? ? ? ? ? ? ? ? ? ?.....②

? ? ? ? ? ? ? ? ? ? ? ? T? → F T'? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ....③

? ? ? ? ? ? ? ? ? ? ? ? T' →*FT' |ε? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ....④

? ? ? ? ? ? ? ? ? ? ? ? F? →( E ) | i? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?.....⑤

因此，有非終結符? E, E',T, T', F.構建FIRST集的過程為

• ?自下而上遍歷對應的產生式，把產生式右邊的首終結符加入到產生式左邊的FIRST中因此

? ? ? ? FIRST(F) = { ( , i ...}? ? ?FIRST(T')? = { * , ε ...}? ? FIRST(E’) =?{? ?+ ,?ε ....}?

• ?對于? ? A →B....類似的文法應該把 FIRST(B) 也加入到? FIRST(A)中因此

? FIRST(F) = { ( , i? }? ? ?FIRST(T')? = { * , ε}? ? FIRST(E‘) =?{? ?+ ,?ε}?

? FIRST(T)? ={ ( , i? }? ? FIRST (E) ={ ( , i? }?

構建FOLLOW集的過程為:自上而下遍歷對應的產生式形如? S? → ABC，

• 把FIRST(C) / {ε}加入到FOLLOW(B)中，如果C是終結符， 那么終結符的FIRST集就是它自身，即FIRST(C) ={ C }，
• 把 FOLLOW(S)加入到 FOLLOW(C)中，如果C 可以間接推出?ε ，即ε∈ FIRST(C),那么把 FOLLOW(S)也加入到FOLLOW(B)中，
• 往起始產生式的FOLLOW加入 ‘#’ 起始符。?

因此上述文法的

? ? ? ? FOLLOW (E) = {? # ,? )? }? ? ?....（第3個條件、⑤式匹配第一條件）

? ? ? ? FOLLOW(E') = FOLLOW(E)? = {? # ,? )? }? ? ? ? (①式匹配第4個條件)

? ? ? ? FOLLOW(T)? =FIRST(E')/{ε} ∪? FOLLOW(E) ={ + ，），# }? ? （②式匹配第一條件，①式匹配第二條件）

? ? ? ? 同理：

? ? ? FOLLOW (T' ) = FOLLOW(T)? =?{ + ，），# }

? ? ? FOLLOW(F) =?FIRST(T')/{ε} ∪? FOLLOW(T) ∪? FOLLOW(T')={ * , + ，），#}

4)預測分析法中 預測分析表M的構建

• ? ? 遍歷每個產生式 A ->α，對每個終結符 a? ∈ FIRST(A)? , 將 A->α 加入到 M[A,a]中，
• ? ? 如果 ε? ∈ FIRST(A)，則對任何終結符b?∈ FOLLOW(A），將 A->ε?加入到 M[A,B]中

因此，預測分析表如下:

	i	+	*	(	)	#
E	E?→ T E'			E?→ T E'
E'		E'?→ + T E'			E' →ε	E' →ε
T	T? → F T'			T? → F T'
T'		T' →ε	T' →*FT'		T' →ε	T' →ε
F	i?			F? →( E )

語法分析過程：

分析棧的起始狀態為? #<起始非終結符>? ，如果分析棧的輸入串的待匹配字符 和 分析棧頂元素按照預測分析表進行化簡，如果棧頂和待匹配字符一致則匹配，如果都不滿足則輸入串語法錯誤。

步驟?	分析棧	輸入串	備注
1	#E	i? *(i + i)#	E?→ T E'
2	#E'T	i? *(i + i)#	T? → F T'
3	#E'T'F	i? *(i + i)#	F? →i?
4	#E'T'i	i? *(i + i)#	匹配
5	#E'T'	*(i + i)#	T' →*FT'
6	#E'T'F*	*(i + i)#	匹配
7	#E'T'F	(i + i)#	F? →( E )
8	#E'T')E(	(i + i)#	匹配
9	#E'T')E	i + i)#	E?→ T E'
10	#E'T')E'T	i + i)#	T? → F T'
11	#E'T')E'T'F	i + i)#	F? →i?
12	#E'T')E'T'i	i + i)#	匹配
13	#E'T')E'T'	+ i)#	T' →ε
14	#E'T')E'	+ i)#	E'?→ + T E'
15	#E'T')E'T+	+ i)#	匹配
16	#E'T')E'T	i)#	T? → F T'
17	#E'T')E'T'F	i)#	F? →i?
18	#E'T')E'T'i	i)#	匹配
19	#E'T')E'T'	)#	T' →ε
17	#E'T')E'	)#	E' →ε
18	#E'T')	)#	匹配
16	#E'T'	#	T' →ε
17	#E'	#	E' →ε
18	#	#	匹配
19			語法正確

? ? ? ? ? ? ? ?

四、自下而上的分析語法——算符優先分析法

對于一個文法，如果其每個產生式的右部都不含兩個相鄰的非終結符，形如：S->.....QR....，則為算符文法。

假如G 是一個不含?ε 的算符文法

?a =·?b : 當且僅當文法G含有? S? ->? ...ab... 或?? S? ->? ...aQb...?

?a <·?b : 當且僅當文法G含有? S? ->? ...aQ... 且 Q ->b... 或 Q ->Rb

?a >·?b :?當且僅當文法G含有? S? ->? ...Qb... 且 Q ->...s 或 Q ->....aR?

當一個算符文法的任意終結符(a,b) 最多只滿足a =·?b，a <·?b，a >·?b 關系之一，則該文法為算符優先文法。也就是說，任意一對終結符，最多只有一種優先關系成立。

例如、對于文法

? ? ? ? E'? ->? #E#? ? ? .......①

? ? ? ? E -> E+T |T? ? ........②

? ? ? ? T -> T * F | F? ........③

? ? ? ? F->P ↑ F? | P .........④

? ? ? ? P -> (E) | i? ?...........⑤

用算法優先分析輸入串為? ( i+i )*i

1）對每個非終結符構建FIRSTVT 集 和LASTVT 集

? ? FIRSTVT(P) 和?LASTVT (P)表示 非終結符P可推出產生式的第一個終結符和最后一個終結符集合??

? ? ?FIRSTVT (P )? =? { a | P => a...? 或 P => Qa....? ，a ∈ 終結符， Q∈非終結符}

? ? ?LASTVT (P )? =? { a | P => ....a? 或 P =>.....aQ? ，a ∈ 終結符， Q∈非終結符}

因此可以自下而上的用下面的規則構造FIRSTVT，

• 若有產生式? ?P->a.?或 P -> Qa....? ，則 a∈FIRSTVT (P )?
• 若有 a∈FIRSTVT (Q)? 且有產生式? ?P->?Q... 則，a∈FIRSTVT (P )

同理，可以自下而上的用下面的規則構造LASTVT，

• 若有產生式? ?P->....a? ?或 P ->.....aQ? ，則 a∈LASTVT (P )?
• 若有 a∈LASTVT (Q)? 且有產生式? ?P-> ....Q?則，a∈LASTVT(P )

? ? FIRSTVT (P)? = { (,i }? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? LASTVT(P') ={ ),i}

? ? FIRSTVT (F) = {↑,(, i}? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?LASTVT(F) = {↑, ),i}

? ? FIRSTVT (T) = {*,↑,(, i}? ? ? ? ? ? ? ? ? ? ? ? ? ? LASTVT (T) = {*,↑,), i}

? ? FIRSTVT (E) = {+,*,↑,(, i}???????????????????????? LASTVT (E) = {+,*,↑,), i}

? ? FIRSTCT (E') = {#}? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??LASTVT (E') = {#}

2）構造算符優先關系表

? 形如有產生式? ....aP.....,那么對任何 b ∈ FIRSTVT(P) ,都有 a <· b

? 形如有產生式? ....Pb.....,那么對任何 a?∈ LASTVT(P) ,都有 a? >· b

? 遍歷每個產生式因此算符優先關系表如下

	+	*	↑	i	(	)	#
+	>·	<·	<·	<·	<·	>·	>·
*	>·	>·	<·	<·	<·	>·	>·
↑	>·	>·	<·	<·	<·	>·	>·
i	>·	>·	>·			>·	>·
(	<·	<·	<·	<·	<·	=·
)	>·	>·	>·			>·	>·
#	<·	<·	<·	<·	<·		=·

當分析棧頂元素與輸入緩沖區的第一個字符作優先對比，如果是<· 則將緩沖區的第一個字符移進分析棧中即push分析棧，如果是>·則進行規約，即pop分析棧。如果是=·那么緩沖區的第一個字符和分析棧頂同時移除

步驟	分析棧	輸入緩沖區	備注
1	#	( i+i )*i#	#<·(,移進
2	#(	i+i )*i#	(<·i,移進
3	#(i	+i )*i#	i>·+,規約
4	#(	+i )*i#	(<·+移進
5	#(+	i )*i#	+<·i,移進
6	#(+i	)*i#	i>·),規約
7	#(+	)*i#	+>·),規約
8	#(	)*i#	( =· ) ,同時移出
9	#	*i#	#<·*，移進
10	#*	i#	*<·i,移進
11	#*i	#	i>· #，規約
12	#*	#	*>· #，規約
13	#	#	# =·# ,同時移出
			語法正確

五、語義分析

? ? ? ?語義分析的主要目的是為了在語法分析中規約、匹配、接受等時執行相應的動作指令，最終生成一組四元式，四元式可以為接下來的中間代碼生成中解析。

對于算符文法語法語義分析的流程圖大致如下

在文法翻譯可以粗略地分為：聲明語句的翻譯、賦值語句的翻譯、簡單算數運算表達式的翻譯，布爾表達式的翻譯、控制語句的翻譯。其中聲明語句的翻譯涉及符號表相關動作，非本文重點。

動作函數及屬性說明如下：

• Entry(id) :在符號表中標識符id的位置
• S.code : 語句S對應的后綴式代碼序列
• E.place : 與非終結符E相聯系的臨時變量地址
• E.true : 當E的表達式為真時，控制流轉向的語句編號(四元式編號)
• E.false : 當E的表達式為假時，控制流轉向的語句編號(四元式編號)
• Gen(op,arg1,arg2,result) ： 創建四元式，屬性result默認值為空。
• nextquad：下一個生成的四元式編號，即比當前最大的四元式編號多1。執行一次Gen，nextquad就加1，
• E.quad：E對應的四元式編號，
• S.next : S對應的代填轉移鏈，通常在S規約后，回填S.next集合中對應的跳轉四元式
• Merg(P1,P2), 把四元式鏈表P1 和鏈P2，并返回新鏈的鏈首指針
• Backpatch (p,t) ：把t回填到四元式鏈表P中每一個節點(四元式)中的result項。
• Newtemp() : 生成一個臨時變量

注：產生式S統一計為語句；E計為表達式，L計為語句塊 , A 為賦值語句,M為語句塊的起始四元式編號，N語句塊的結束四元式編號

1）賦值語句和的簡單算數運算表達式的翻譯

產生式	語義動作
? ? A->id := E? ? ?	{Gen(":=" , E.place, "_" , Entry(id))? }
E -> E1? + E2	{E.place = Newtemp() ; GEN("+",E1.place,E2.place,E.place) }
E -> E1? * E2	{E.place = Newtemp() ; GEN("*",E1.place,E2.place,E.place) }
E -> -E1??	{E.place = Newtemp() ; GEN("minus",E1.place,"_",E.place) }
E-> ( E1 )	E.place =E1.place?
E -> id?	E.place = Entry(id)

2)布爾表達式的翻譯方法

注:rel_op為布爾運算符

產生式	語義動作
? E -> E1?or ME2 ?	{backpatch(E1.false, M.quad) ; E.true := merge(E1.true , E2.true); E.false := E2.false}
E -> E1? and? ME2	{backpatch(E1.true, M.quad) ; E.true := E2.true?;? E.false := merge(E1.false,E2.false)}
E -> not E1?	E.true := E1.false ;?E.false := E1.true?;?
E-> ( E1 )	E.true :=E1.true ;? ?E.false :=E.1false?
E->? id? rel_op? ?id?	{E.true :=nextquad ;? E.false :=??nextquad+1 ； Gen( "j <rel_op>"? , id1.place? ,? id2.place ,0?); Gen("j" ,"_" ,"_",0); }
E -> id?	{E.true :=nexquad ;? E.false :=??nexquad+1 ； Gen( "jnz"? , id1.place? ,?"_" ,0?); Gen("j" ,"_" ,"_",0); }
M ->ε	M.xq =nextquad

? ? ? ? ? ? ?

例如：布爾表達式 “?a<b or c<d? and e<f ”的四元式序列?設序列起始值為100

因為對于自下而上的語法分析中，語義動作是在產生式規約的時候發生的，所以語義執行順序是按照逆波蘭式順序執行的

????????

首先發生規約的是? ? E ->? a <b 產生式；對照的語義動作表得到的控制流鏈號見上圖，得到的四元式為；

100 :("j<" , a,b,0)

101: (j,_,_0)

接下來發生規約的是M ->ε ,此時nextquad下一個四元式編號是102，再接下來發生規約是E ->c < d

102 :("j<" , c,d,0)

103: (j,_,_0)

接下來發生規約的是M ->ε ,此時nextquad下一個四元式編號是104，再接下來發生規約是E ->e < f

104 :("j<" , e,f,0)

105: (j,_,_0)

接下來發生規約的是??E -> E1? and? ME2? ,見上表對應的語義動作是把?M.quad回填到E1.true控制流四元式的跳轉值。即backpatch(102, 104)，修改編號102的四元式成? ?102 :("j<" , c,d,104)

接下來發生規約的是??? E -> E1?or ME2 ? ,見上表對應的語義動作是把?M.quad回填到E1.false控制流四元式的跳轉值。即backpatch(101, 102)，修改編號101的四元式成? ?101: (j,_,_102)

因此 此布爾表達式得到的最終序列是：

100 :("j<" , a,b,0)

101: (j,_,_102)

102 :("j<" , c,d,104)

103: (j,_,_0)

104 :("j<" , e,f,0)

105: (j,_,_0)

上述四元式的含義是

100：如果 a<b 為真時，跳轉到第0個四元式(即退出程序)，否則繼續往下執行

101：直接跳轉到102號四元式

102：如果 c <d? 為真時跳轉到第104號四元式，否則繼續往下執行

........

3)典型控制語句的翻譯方法

產生式	語義動作
? S -> if E then MS1??	{backpatch(E.true, M.quad) ; S.next?:= merge(E1.false?, S1.next); }
S -> if E then M1 S1 N else M2 S2	{backpatch(E.true, M1.quad) ; backpatch(E.false, M2.quad) ; S.next:= merge(S1.next,N.next,S2.next)}
E -> while M1 E do M2 S1	{backpatch(S.next, M1.quad) ; backpatch(E.true, M2.quad) ; S.next:=E.false; Gen(" j?",_ , _ M1.quad)}
S-> Begin L end?	S.next = L.next
S -> A	S.next 初始化
L -> L1? ;? MS	backpatch(L1.next, M.quad) ; L.next =S.next
L? -> S	L.next =S.next
M ->ε	M.quad =nextquad
N->ε	N.next =nextquad ; Gen(" j ", _ ,_ ,0)

?例如：程序語句

while a > 0 and x < 0 do begin x := x +1 ;if a > 0 or b <0 then a := a-1 else b := b -1end

的四元式序列?設序列起始值為100

：還是畫語法樹并自下而上按照逆波蘭式順序規約填寫控制流

?總結一下：

• 四則運算會生成一個四元式
• 賦值語句會生成一個四元式
• 布爾比較運算符會生成兩個跳轉四元式，跳轉目標待回填
• 條件控制語句，如果布爾比較是真值則跳轉到控制語句塊的起始位置M中。每一個分支語句結束(規約)時N會產生一個直接跳轉四元式，最后一個分支應省略。這些直接跳轉四元式的目標地址是整個控制語句結束后編碼。即 L -> L1; MS中的M
• 循環控制語句：如果布爾比較是真值則跳轉到控制語句塊的起始位置M中，控制語句塊結束時會產生一個直接跳轉四元式，直接到布爾比較中。如果布爾比較是假值，則跳轉到控制語句結束后編碼。
• 語句S的語法子樹的結束入口通常需要S自身規約時才可以確定，所以用S.next存儲S的語法子樹中的待回填的退出地址。

因此：得到下述四元式，用T來表示臨時變量

100:? ("j>" ,a,0,102)

101: (" j " ,_,_,0)

102:(" j<" ,x,0,104);

103: (" j " ,_,_,0)

104:(" +" ,x,1,T1)

105:(":=",T1,_,x )

106:(" j>" ,a,0,110)

107:(" j " ,_,_,108)

108:(" j<",b,0,110)

109:(" j ",_,_113)

110:(" - ",a,1,T2)

111:(":=",T2,_,x)

112: (" j ",_,_,100)

113:( " - " ,b,1,T3)

114:(" :=",T3,_ ,b)

115"(" j ",_,_,100)

0: 程序結束

六、目標代碼生成

? ? ? ? 目標代碼生成的任務是為了把四元式序列轉化成對應的代碼。而這個轉化后的代碼通常是匯編語言。在上例中的的偽Pascal文法下的代碼片段，其每一個四元式都有對應的含義。例如四元式102:(" j<" ,x,0,104)? 對應的意義是當 x<0 時跳轉到104號四元式。對應的匯編代碼是：

CMP x,0

JE? <代碼塊標簽名稱>?

類似的

指令碼	意義	條件
JZ, JE	結果為0或相等則轉	Z=1，(A) = (B)
JNZ, JNE	結果不為0或不相等則轉	Z=0，(A)≠(B)
JNL, JGE	大于等于轉(不小于)	(S∨O)=0，(A)≥(B)
JL, JNGE	小于轉(不大于等于)	(S∨O)=1，(A)<(B)
JG, JNLE	大于轉(不小于等于)	(S∨O∨Z)=0，(A)>(B)
JMP	無條件轉移

那么 <代碼塊標簽名稱> 該怎么確定呢？

1）基本塊劃分

? ? ? ? 代碼塊標簽名稱通常是自定義的，通常是當作 goto語句的跳轉代碼位置。而四元式的基本塊相當于程序語言的語句塊，就是一堆順序執行的語句序列。而基本塊入口的確定滿足以下條件的其中一個就行：

• 程序第一個四元式為基本塊入口
• 跳轉四元式的下一個四元式為基本塊入口
• 跳轉語句要跳轉到的四元式，該四元式為基本塊入口

最后，相鄰兩個基本塊入口之間的四元式構成一個基本塊(其中包含前者入口，不包含后者入口)。跳轉語句的跳轉位置也就是基本塊的名字。

對于上例的四元式序列劃分的基本塊如下：

---------GOTOBLOCK1------------ 100:("j>" ,a,0,102) ---------GOTOBLOCK2------------ 101:(" j " ,_,_,0) ---------GOTOBLOCK3------------ 102:(" j<" ,x,0,104) ---------GOTOBLOCK4------------ 103:(" j " ,_,_,0) ---------GOTOBLOCK5------------ 104:(" +" ,x,1,T1) 105:(":=",T1,_,x ) 106:(" j>" ,a,0,110) ---------GOTOBLOCK6------------ 107:(" j " ,_,_,108) ---------GOTOBLOCK7------------ 108:(" j<",b,0,110) ---------GOTOBLOCK8------------ 109:(" j ",_,_113) ---------GOTOBLOCK9------------ 110:(" - ",a,1,T2) 111:(":=",T2,_,x) 112:(" j ",_,_,100) ---------GOTOBLOCK10------------ 113:( " - " ,b,1,T3) 114:(" :=",T3,_ ,b) 115"(" j ",_,_,100) ---------END--------------------

因此：102:(" j<" ,x,0,104) 要跳轉的104四元式對應的的基本塊GOTOBLOCK5因此對應的目標代碼是：

CMP x,0 JE? GOTOBLOCK5

除了比較跳轉的四元式外,:還有四則運算和賦值語句

賦值語句對應的是:? ?MOV? 變量名 ,<寄存器名稱>? ，?

而四則運算對應的代碼則為? ?

• ADD?<寄存器名稱> ,<變量或寄存器名稱>?
• ADD?<寄存器名稱> ,<變量或寄存器名稱>?
• MUL <寄存器名稱> ,<變量或寄存器名稱>?
• DIV <寄存器名稱> ,<變量或寄存器名稱>?

每個寄存器只能存一個值，因此如何選擇寄存器是目標代碼生成的一個重點

2）寄存器選擇——寄存器的待用信息與活躍信息的確定

? ? ? ? 在同一個基本塊中，如果中間代碼(四元式) i?對 A 定值，中間代碼 j 引用了? A 值，且從 i 到 j 之間沒有 A 的其他定值，則 j 是代碼 i 中變量? A 的待用信息? ，且 A在 i 處是活躍的。

????????通俗來講，就是存在寄存器里的值還需要被后續代碼 j 引用到，那么就 j 使用的寄存器就應該是 A ，且? i 到 j 之間的代碼不能使用寄存器A。 即 代碼 j 待使用 A 的值 ，A的值是來源于代碼 i。

? ? ? ? 對于變量待用信息的計算：

(1)開始時，把基本塊中各個變量在符號表中的待用信息域初始化為“非待用”，根據基本塊出口之后是否活躍(變量生命周期是否結束)來初始化活躍信息域 "活躍" 或 "非活躍"。

(2)由后向前遍歷從基本塊出口至基本塊入口中的每一行中間代碼形如? ( op , B , C, A) 或??( := , B ,_, A)形式的依次執行以下步驟:

把符號表中變量A的待用信息和活躍信息附加在中間代碼i上

把符號表中變量A的待用信息和活躍信息分別置為 "非待用" 和 "非活躍"

把符號表中變量B 和 變量 C 的待用信息和活躍信息?附加在中間代碼i上

把符號表中的 B 和 C 的待用信息均置為 i? ， 活躍信息都置為 "活躍"

例如：某一個基本塊的中間代碼序列如下，假設基本塊結束后W時活躍變量,假設由R1,R2,R3寄存器，寫出目標代碼；

①? T :=? A +B

②? U := A? - C

③? V := T? + U

④? W := V? + U

由④遍歷到①代碼得到待用信息與活躍信息表

序號	中間代碼?	T	A	B	C	U	V	W
④	W := V? + U					非待用 非活躍	非待用 非活躍	非待用 活躍
③	V := T? + U	非待用 非活躍				4，活躍	4，活躍	非待用 活躍
②	U := A? - C	3,活躍	非待用 非活躍		非待用 非活躍	3，活躍	4，活躍	非待用 活躍
①	T :=? A +B	3,活躍	2,活躍	非待用 非活躍	2,活躍	3，活躍	4，活躍	非待用 活躍

所以當代碼執行到 ①時，存放值B的寄存器使用完了可以直接釋放，存放A值的寄存器要等代碼②執行完，才可以釋放，存放值T的寄存器要等代碼③執行完才變成"非待用"后可以釋放。

同理類推....得到目標代碼

MOV R1 , A MOV R2 , B ADD R2 , R1 --B值以后用不到了R2釋放,R2用來存T MOV R3 , C SUB R1 , R3 -- C以后用不到了R3釋放 ，A值以后用不到了R1釋放,R1用來存U ADD R2 , R3 -- T值以后用不到了R2釋放，R2用來存 V ADD R1 , R2 -- U值以后用不到了R1釋放,V值以后用不到了R2釋放,R1用來存W

最后：五-3 示例中得到的目標代碼為

CODEBLOCK1:CMP a , 0JG CODEBLOCK3 CODEBLOCK2:JMP CODEEND CODEBLOCK3:CMP x , 0 JL CODEBLOCK5 CODEBLOCK4:JMP CODEEND CODEBLOCK5:MOL AX , xADD AX , 1MOV x ,AXCMP a , 0 JG CODEBLOCK9 CODEBLOCK6:JMP CODEBLOCK8 CODEBLOCK7:CMP b,0JL CODEBLOCK9 CODEBLOCK8:JMP CODEBLOCK10: CODEBLOCK9:MOL AX , aSUB AX , 1MOV x ,AXJMP CODEBLOCK1 CODEBLOCK10:MOL AX , bSUB AX , 1MOV b ,AXJMP CODEBLOCK1 CODEEND:

七、中間代碼的優化

? ? ? ? 中間代碼的優化有三個原則:等價原則，有效原則，合算原則。即優化后的效果必須要和原來一致，不會增加無效代碼，并且對性能有提高的。每個對于不可達代碼，可以畫流圖來確認哪些基本塊是永遠沒機會執行的，對于這些不可達的基本塊可以直接從代碼中刪除。對于算數計算的優化可以用有向無環圖(DAG)進行代碼優化。原理大致是，每一個節點代表一個值可以被一個或多個變量引用。然后重寫語句。

(1) 基于DAG圖的優化方法?

例如、給定某個基本塊代碼如下：

?T0 := 3.14

?T1 :=? 2 * T

?T2 := R + r

?A? ?:=? T1 * T2

?B? :=? A

?T3 := 2? *? T0

?T4 := R + r

?T5 := T3 * T4

?T6 :=? R - r

?B? ?:=? T5 *? T6?

常量是葉子節點，計算符是內部節點

?

? ? ?最后得到的DAG圖是

確認哪個是基本塊退出后的活躍變量,(假設是 B)，以活躍變量為根節點，刪除非活躍變量的引用，但是每個內部節點要保留至少一個引用，葉子節點保留值就行。

假設基本塊退出后的只有一個活躍變量，優化后的中間代碼可以為：

T2 := R - r

T6 := R + r

A := 6.18 * T2

B := A * T6

?

總結

以上是生活随笔為你收集整理的编译原理：全片知识难点总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。