通過詞法分析，語法分析，語義分析，最后產生了四元式。而代碼生成則是通過四元式來完成。我們先從簡單開始做起。

編譯實驗項目下載鏈接：http://download.csdn.net/download/supersmart_dong/10224159

例如四元式(j,0,0,7)這樣的，代碼生成只需要一個goto語句；(j=,A,B,7)代碼生成為:

CMP A,B

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	無條件轉移

CMP 為比較，實際上是兩個變量相減只影響標志位。

所以當(J<,A,B,7)這樣的只需要一個比較語句和一個跳轉語句就行。跳轉到哪？當然是跳轉到對應四元式所對應的代碼了，我們需要引進基本塊的概念，塊也就是一堆順序執行的語句序列。首先要就四元式進行劃分基本塊。

(1)程序第一個四元式為基本塊入口

(2)跳轉四元式的下一個四元式為基本塊入口

(3)跳轉語句要跳轉到的四元式，該四元式為基本塊入口

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

首先第一步，設置基本塊路口，我們四元式需要一個屬性來標記是否為某基本塊入口(0為否，1為是)，按照上面的三步驟，遍歷四元式判斷是不是第一個四元式，是不是跳轉語句的四元式，是的話相應四元式屬性置為1就可以。

第二步就是初始化基本塊集合。遍歷四元式將四元式加入基本塊，直到下一個入口四元式為止，再把基本塊加到集合中。

做完這些，所有跳轉語句就可以完成了，跳轉目的地也就是四元式對應的基本塊名稱。

接下來完成加減乘除的四元式代碼生成。假如有ax，bx，dx寄存器可用

像(+,A,B,T1) (:=,T1,0,A)對應匯編代碼應該是:

MOV? AX，A

ADD? ?AX,B

MOV? C,AX?

假如B的值存在了bx寄存器中：

MOV? AX，A

ADD? ?AX,BX

MOV? C,AX?

首先定義寄存器的數據結構，起碼要有name(寄存器名稱)，Rvalue(寄存器存放的值)，例如上面的代碼，AX寄存器最后存放了T1和C的值。

struct registers {string name;vector<string> Rvalue;registers(string n){ name = n; }registers(){};void clearPush(string n){Rvalue.clear();Rvalue.push_back(n);}bool isinReg(string n){bool flag = false;for (int i = 0; i < Rvalue.size(); i++){if (Rvalue[i] == n)flag = true;}return flag;} }; vector<registers> regs = { registers("AX"), registers("BX"), registers("DX") }; registers M("M"); registers findreg(string arg,int &index) {//如果找到原本有的for (int i = 0; i < regs.size(); i++){if (regs[i].isinReg(arg)){index = i;return regs[i];}}//沒有則返回空寄存器for (int i = 0; i < regs.size(); i++){if (regs[i].Rvalue.size()==0){index = i;return regs[i];}}return NULL; } bool isExistRvalue(string arg) {for (int i = 0; i < regs.size(); i++){ if (regs[i].isinReg(arg))return true; }return false; }
在進行加減乘除的代碼生成的時候，首先遍歷所有寄存器的Rvalue查詢是否存在Rvalue中，是的話返回對應寄存器。

例如進行計算A+B時，對應四元式 (+,A,B,T)，如果A和B分別在ax，bx寄存器中，對應代碼：

ADD ax，bx

如果A在寄存器ax中b不在寄存器，則：

ADD ax，B

如果A在不在寄存器b在寄存器bx，則：

ADD bx，A

A和B都不在寄存器中時，返回空寄存器(假如是AX)：

mov? ax，A

add ax ,B

目標代碼生成參考代碼：

#include <string> #include <vector> #include "register.h" //定義基本塊的數據結構，定義代碼表的基本結構，找到四元式的入口，劃分基本塊，遍歷基本塊進行代碼生成（首先完成根據四元式地址找到基本塊，完成操作符代碼表），精化代碼表用到寄存器分配 static int nameNum; struct basicBlock {string name;vector<GenStruct> gens; vector <string> codes;basicBlock(){string str;int2str(nameNum,str);name = "L" + str;nameNum++;}void add(GenStruct g){gens.push_back(g);} }; class codeTable { private:vector<basicBlock> block; //基本塊void initblock(); //初始化基本塊int findblocknameByGen(int index); //根據四元式地址找到基本塊string findblocknameByGen(string index){int i = stoi(index);i=findblocknameByGen(i);if (i >= block.size()) return "End";return block[i].name; }vector<string> createcode(GenStruct);void initblockcodes();bool stringisinGen(string,int); //判斷string 是否在index后四元式中存在 public: vector<basicBlock> getBasicBlock(){ return block; }codeTable(){ initblock(); initblockcodes(); }void clearNotUse(GenStruct);void printcodes(); }; void codeTable::initblock() {for (int i = 0; i < genStructs.size()-1; i++){if (i == 0) { //程序第一條為入口changeOut_port(0); }if (genStructs[i].code <= 58 && genStructs[i].code >= 52) //跳轉語句{changeOut_port(genStructs[i].result);//跳轉到的語句為入口語句changeOut_port(i+1); //跳轉語句的下一行,為入口語句}}for (int i = 0; i < genStructs.size() ; ) //把入口語句加入到基本塊{basicBlock bl;bl.add(genStructs[i]);i++;for (; i < genStructs.size(); i++){if (genStructs[i].out_port == 1){block.push_back(bl);break;}else bl.add(genStructs[i]);}if (i==genStructs.size())block.push_back(bl);} } int codeTable::findblocknameByGen(int index) {for (int i = 0; i < block.size(); i++) //i為block索引{for (int j = 0; j < block[i].gens.size(); j++){if (block[i].gens[j].label == index){return i;}}}return -1; } void codeTable::initblockcodes() {for (int blockindex = 0; blockindex < block.size(); blockindex++){for (int i = 0; i < block[blockindex].gens.size(); i++){block[blockindex].codes = merge(block[blockindex].codes, createcode(block[blockindex].gens[i]));}} } void codeTable::printcodes() {for (int blockindex = 0; blockindex < block.size(); blockindex++){cout << block[blockindex].name << ":\n";for (int i = 0; i < block[blockindex].codes.size(); i++){cout << " "<<block[blockindex].codes[i] << endl;}} } vector<string> codeTable::createcode(GenStruct gen) {vector<string> codes;int code = gen.code;clearNotUse(gen);registers reg; int regindex,temp;switch (code){case 41://op = "*";if (isExistRvalue(gen.addr1) && isExistRvalue(gen.addr2)){codes.push_back("MUL " + findreg(gen.addr1, regindex).name + "," + findreg(gen.addr2, temp).name);regs[regindex].clearPush(gen.result);}else if (isExistRvalue(gen.addr1) && !isExistRvalue(gen.addr2)){codes.push_back("MUL " + findreg(gen.addr1, regindex).name + "," + gen.addr2);regs[regindex].clearPush(gen.result);}else if (!isExistRvalue(gen.addr1) && isExistRvalue(gen.addr2)){codes.push_back("MUL " + findreg(gen.addr2, regindex).name + "," + gen.addr1);regs[regindex].clearPush(gen.result);}else{reg = findreg(gen.addr1, regindex);codes.push_back("MOV " + reg.name + "," + gen.addr1);codes.push_back("MUL " + reg.name + "," + gen.addr2);regs[regindex].clearPush(gen.result);}break;case 43://op = "+"; if (isExistRvalue(gen.addr1) && isExistRvalue(gen.addr2)){codes.push_back("ADD " + findreg(gen.addr1, regindex).name + "," + findreg(gen.addr2, temp).name);regs[regindex].clearPush(gen.result);}else if (isExistRvalue(gen.addr1) && !isExistRvalue(gen.addr2)){codes.push_back("ADD " + findreg(gen.addr1, regindex).name + "," + gen.addr2);regs[regindex].clearPush(gen.result);}else if (!isExistRvalue(gen.addr1) && isExistRvalue(gen.addr2)){codes.push_back("ADD " + findreg(gen.addr2, regindex).name + "," + gen.addr1);regs[regindex].clearPush(gen.result);}else{reg = findreg(gen.addr1, regindex);codes.push_back("MOV " + reg.name + "," + gen.addr1);codes.push_back("Add " + reg.name + "," + gen.addr2);regs[regindex].clearPush(gen.result);}break;case 45://op = "-";codes.push_back("MOV " + findreg(gen.addr1, regindex).name + ",-" + gen.addr2);regs[regindex].clearPush(gen.result);break;case 48://op = "/"; 沒有這個文法codes.push_back("DIV " + gen.addr1 + "," + gen.addr2);break;case 51://op = ":="; reg = findreg(gen.addr1, regindex);codes.push_back("MOV " + gen.result + "," + reg.name);regs[regindex].Rvalue.push_back(gen.result);break;case 52://op = "j";codes.push_back("GOTO " + findblocknameByGen(gen.result));break;case 53://op = "j<"; codes.push_back("CMP " + gen.addr1 + "," + gen.addr2);codes.push_back("JL " + findblocknameByGen(gen.result));break;case 54://op = "j<=";codes.push_back("CMP " + gen.addr1 + "," + gen.addr2);codes.push_back("JLE " + findblocknameByGen(gen.result));break;case 55://op = "j<>";codes.push_back("CMP " + gen.addr1 + "," + gen.addr2);codes.push_back("JNE " + findblocknameByGen(gen.result));break;case 56://op = "j="; codes.push_back("CMP " + gen.addr1 + "," + gen.addr2);codes.push_back("JE " + findblocknameByGen(gen.result));break;case 57://op = "j>";codes.push_back("CMP " + gen.addr1 + "," + gen.addr2);codes.push_back("JG " + findblocknameByGen(gen.result));break;case 58://op = "j>=";codes.push_back("CMP " + gen.addr1 + "," + gen.addr2);codes.push_back("JGE " + findblocknameByGen(gen.result));break;default:break;}return codes; } bool codeTable::stringisinGen(string str,int index) {for (int i = genStructs.size() - 1; i >= index; i--) //因為先刪除后操作，所以要把iindex是加進去{if (genStructs[i].addr1 == str || genStructs[i].addr2 == str)return true;}return false; } //遍歷所有基本塊，把非待用的寄存器里值給刪了,把基本塊里的Rvalue void codeTable::clearNotUse(GenStruct gen)//運行到四元式的值 {int index = gen.label;//遍歷所有寄存器的Rvalue 看看后沒有在index之后的四元式出現for (int i = 0; i < regs.size(); i++){for (int j = 0; j < regs[i].Rvalue.size(); j++){if (!stringisinGen(regs[i].Rvalue[j], index)){//刪除regs[i].Rvalue.erase(regs[i].Rvalue.begin() + j);}}} }
到此為止，差不多就結束了。不過有個缺陷，就是計算一旦多起來寄存器可能就不夠用了，所以在每次生成代碼前還要把寄存器里非待用的給刪了。何為非待用？例如：

1：? T1 ：=A+B

2：? ?C :=T1+A

當執行完第一句時此時T1 和A是待用的因為之后的運算用到了他們，B是非待用的因為之后的運算沒用到B。

實現非待用判斷不難，首先從尾至當前，遍歷四元式看看第二元素，第三元素是否與之相等。

實現非待用的刪除，遍歷每個寄存的RValue中的值，判斷該值是否非待用，是則刪除。

總結

以上是生活随笔為你收集整理的编译实验(三)目标代码生成的全部內容，希望文章能夠幫你解決所遇到的問題。

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