編譯原理及實現(xiàn)技術(shù)：20-中間代碼生成-表示形式、語法制導(dǎo)方法

第五章：中間代碼生成(1)

1.生成中間代碼的目的便于優(yōu)化讓生成的目標代碼效率更高優(yōu)化不等同于對代碼的精簡和算法的優(yōu)化便于移植編譯前端：與目標機無關(guān)編譯后端：與目標機相關(guān)2.中間代碼結(jié)構(gòu)2.1三元式2.2逆波蘭式2.3抽象語法樹2.4四元式2.1三元式由三個部分組成：操作符，運算分量，運算分量如：x+y可以表示成（+,x,y）例如語句:a:=b*c+b/d(1)(*,b,c)(2)(/,b,d)(3)(+,(1),(2))(4)(:=,(3),a)2.2逆波蘭式（后綴表達式）將運算對象寫在前面，把運算符寫在后面，因而也稱后綴式。最大特點是排好了計算順序，而不是根據(jù)運算符的優(yōu)先級。程序設(shè)計語言中的表示逆波蘭表示a+bab+a+b*cabc*+(a+b)*cab+c*2.3抽象語法樹抽象語法樹AGT（AbstractGrammarTree）可以顯示地表示源程序的結(jié)構(gòu)，是常用的一種標準中間代碼形式。

例如：

c:=a*b+a*b:=c+**abab2.4四元式四元式:(算符op，ARG1，ARG2，運算結(jié)果RESULT）例如：a:=b*c+b/d

(1)(*,b,c,t1)(2)(/,b,d,t2)(3)(+,t1,t2,t3)(4)(:=,t3,-,a)四元式的特點：都是一些簡單的運算，每一條四元式都是一個簡單運算，更接近于匯編程序和機器指令，生成目標代碼的時候更方便，順序是排好的，按照四元式的順序來進行計算就可以，而不是按照運算符的優(yōu)先級。2.4四元式算術(shù)、邏輯、關(guān)系運算符

ADDI、ADDF、SUBI、SUBF、MULTI、

MULTF、DIVI、DIVF、MOD、AND、

OR、EQ、NE、GT、GE、LT、LEREADI,READF,FLOAT,ASSIG,AADD...遇到時隨時解釋3.語法制導(dǎo)方法語法制導(dǎo)技術(shù)在處理和規(guī)則相關(guān)聯(lián)的任務(wù)中有著重要的應(yīng)用語法制導(dǎo)就是在進行語法分析的同時要完成相應(yīng)的語義動作，這些語義動作都是由一些程序組成的，要完成和用戶的需求相關(guān)聯(lián)的任務(wù)編譯器對一個串進行語法檢查的同時，可以按照語法分析的程序的結(jié)構(gòu)對程序進行我們所需要的操作，從而解決我們想要解決的問題。3.語法制導(dǎo)方法例如：有文法GSABAaA│bBbB│c要求對輸入G的任意句子L，輸出b串的長度，例如abbbbc，輸出43.語法制導(dǎo)方法則有:S#Init#AB

A

aA│b#Add#

B

b#Add#B│c#Out#其中：Init：m=0;Add

:m++;Out：print(m);#Init#m=0

#init#AB#替換對給定的終極符串a(chǎn)bbbc，分析過程：S

#

abbbc#替換Match基于LL(1)的語法制導(dǎo)的實現(xiàn)過程（1）

abbbc#

AB#

aAB#

b#Add#B#替換#Add#m++Match

abbbc#

abbbc#

AB#

bbbc#

bbbc#

bbc#

#Add#B#

B#

bbc#例G[s]:[1]S

#init#AB

[2]AaA

[3]Ab#Add#

[4]Bb#Add#B

[5]Bc#Out_Val#

{a,b}{c}{a}符號棧輸入流動作替換Success對給定的終極符串a(chǎn)bbbc，分析過程(續(xù)）：基于LL(1)的語法制導(dǎo)的實現(xiàn)過程（2）例G[s]:[1]S

#init#AB

[2]AaA

[3]Ab#Add#

[4]Bb#Add#B

[5]Bc#Out_Val#

{a,b}{c}{a}替換

B#

bbc#

b#Add#

B#

bbc#Match#Add#

m++

#Add#

B#

bc#

B#

bc#

b#Add#

B#

bc#替換Match

#Add#B#

c##Add#

m++

B#

c#替換

c#Out##

c#Match

#Out##

##Out#print(m)

#

#符號棧輸入流動作4.中間代碼生成中的幾個問題語義信息的提取與保存：四元式:(算符op，ARG1，ARG2，運算結(jié)果RESULT）ARG1，ARG2，

RESULT為操作分量和運算結(jié)果的抽象地址表示，應(yīng)包含相應(yīng)語義信息。如：3.5+i(ADDF,3.5,(i.level,i.off,dir),(-1,t3,dir))語義信息的兩種表示方式：指向相應(yīng)符號表的指針把對應(yīng)分量的語義信息放在此處4.中間代碼生成中的幾個問題語義棧Sem及其操作：在語法制導(dǎo)生成中間代碼的過程中，要用到一個語義棧，把相關(guān)的分析程序的一些中間結(jié)果都要存放到語義棧中。進棧、退棧、棧的結(jié)構(gòu)可自行定義5.表達式的中間代碼生成【1】ET【2】EE+T【3】EE-T【4】TF【5】TT*F【6】TT/F【7】F(E)【8】Fi算數(shù)表達式文法：5.1基于LR(1)方法【1】ET空【2】EE+T#inc【3】EE-T#dec#inc中要執(zhí)行的動作：對sem(s-1)和sem(s-2)進行類型檢查（是否相同、是否相容、是否需要類型轉(zhuǎn)換_必要的話產(chǎn)生轉(zhuǎn)換四元式）new(t);Gen(+,sem(s-2),sem(s-1),t)//dec為'-'號退棧：s=s-1;或者是pop(2)進棧:sem(s-1)=t;或者是push(t)5.1基于LR(1)方法【4】TF空【5】TT*F#MUL【6】TT/F#Dev#MUL中要執(zhí)行的動作：對sem(s-1)和sem(s-2)進行類型檢查（是否相同、是否相容、是否需