Generator:將剖析樹轉換為 CPU0 的組合語言 -- 以 C 語言實作

程式作品

C 語言

Java

C#

JavaScript

常用函數

文字處理

遊戲程式

衛星定位

系統程式

資料結構

網路程式

自然語言

人工智慧

機率統計

資訊安全

等待完成

訊息

相關網站

參考文獻

最新修改

簡體版

English

檔案:Generator.h

#ifndef GENERATOR_H
#define GENERATOR_H

#include "Tree.h"
#include "HashTable.h"

typedef struct {                                        // 程式碼產生器物件
  HashTable *symTable;                                  //   符號表
  Tree *tree;                                           //   剖析樹
  FILE *asmFile;                                        //   輸出的CPU0組合語言檔
  int forCount, varCount;                               //   For迴圈與臨時變數的數量
} Generator;

void generate(Tree *tree, char *asmFile);               // 程式碼產生器的主函數

Generator *GenNew();                                    // Generator 的建構函數
void GenFree(Generator *g);                             // Generator 的解構函數
Tree* GenCode(Generator *g, Tree *node, char *rzVar);   // 產生組合語言程式碼
void GenData(Generator *g);                             // 產生資料宣告
void GenPcode(Generator *g, char* label, char* op,      // 輸出虛擬碼 pcode
              char* p1, char* p2, char* pTo);
void GenPcodeToAsm(Generator *g, char* label, char* op, // 將虛擬碼轉為組合語言
              char* p1, char* p2, char* pTo);
void GenAsmCode(Generator *g, char* label, char* op,    // 輸出組合語言指令
              char* p1, char* p2, char* pTo);
void GenTempVar(Generator *g, char *tempVar);           // 取得下一個臨時變數名稱
void negateOp(char *condOp, char *negOp);               // 取比較運算的互補運算
                                                        // 例如: < 變 >=
#endif

檔案:Generator.c

#include "Generator.h"

// 程式產生器的主要函數。
void generate(Tree *tree, char *asmFile) {      // 將剖析樹 tree 轉為組合語言檔 asmFile
  char nullVar[100]="";
  Generator *g = GenNew();                      // 開啟組合語言檔以便輸出
  g->asmFile = fopen(asmFile, "w");
  printf("=====PCODE=====\n");                  // 產生程式碼
  GenCode(g, tree, nullVar);                    // 產生資料宣告
  GenData(g);                                   // 關閉組合語言檔
  fclose(g->asmFile);                           // 釋放記憶體
  GenFree(g);                                   // 讀入組合語言檔並印出
  char *asmText = newFileStr(asmFile);
  printf("=====AsmFile:%s======\n", asmFile);
  printf("%s\n", asmText);                      // 釋放記憶體
  freeMemory(asmText);
}

Generator *GenNew() {
  Generator *g = ObjNew(Generator, 1);
  g->symTable = HashTableNew(127);
  return g;
}

void GenFree(Generator *g) {
  HashTableFree(g->symTable);
  ObjFree(g);
}

char nullVar[100]="";

Tree* GenCode(Generator *g, Tree *node, char *rzVar) {        // 遞迴產生節點 node 的程式碼
  strcpy(nullVar, "");
  strcpy(rzVar, "");
  if (node == NULL) return NULL;                              // 遞迴終止條件。

  if (strEqual(node->type, "FOR")) {                          // 處理 FOR 節點
    // FOR ::= 'for' '(' STMT ';' COND ';' STMT ')' BLOCK
    char forBeginLabel[100], forEndLabel[100], condOp[100];
    Tree *stmt1 = node->childs->item[2],                      // 取得子節點
         *cond  = node->childs->item[4],
         *stmt2 = node->childs->item[6],
         *block = node->childs->item[8];
    GenCode(g, stmt1, nullVar);                               // 遞迴產生 STMT
    int tempForCount = g->forCount++;                         // 設定FOR迴圈的
    sprintf(forBeginLabel, "FOR%d", tempForCount);            //   進入標記
    sprintf(forEndLabel, "_FOR%d", tempForCount);             //   離開標記
    GenPcode(g, forBeginLabel, "", "", "", "");               // 中間碼:例如 FOR1:
    GenCode(g, cond, condOp);                                 // 遞迴產生 COND
    char negOp[100];
    negateOp(condOp, negOp);                                  // 互補運算negOp
    GenPcode(g, "", "J", negOp, "", forEndLabel);             // 中間碼:例如J > _FOR1
    GenCode(g, block, nullVar);                               // 遞迴產生 BLOCK
    GenCode(g, stmt2, nullVar);                               // 遞迴產生 STMT
    GenPcode(g, "", "J", "", "", forBeginLabel);              // 中間碼:例如J FOR1
    GenPcode(g, forEndLabel, "", "", "", "");                 // 中間碼:例如 _FOR1
    return NULL;
  } else if (strEqual(node->type, "STMT")) {                  // 處理 STMT 節點
    //   STMT = return id | id '=' EXP | id ('++'|'--')
    Tree *c1 = node->childs->item[0];                         //   取得子節點
    if (strEqual(c1->type, "return")) {                       // 處理 return 指令
      Tree *id = node->childs->item[1];
      GenPcode(g, "", "RET", "", "", id->value);              // 中間碼: 例如 RET sum
    } else {
      Tree *id = node->childs->item[0];                       //   取得子節點
      Tree *op = node->childs->item[1];
      if (strEqual(op->type, "=")) {                          // 處理 id= EXP
        // STMT 是 id '=' EXP                                 //  取得子節點
        Tree *exp = node->childs->item[2];
        char expVar[100];
        GenCode(g, exp, expVar);                              //  遞迴產生 EXP
        GenPcode(g, "", "=", expVar, "", id->value);          //  中間碼:例如 = 0 sum
        HashTablePut(g->symTable, id->value, id->value);      //  將 id 加入到符號表中
        strcpy(rzVar, expVar);                                //  傳回 EXP 的變數,例如 T0
      } else { // STMT 是 id++ 或 id--,--> id OP1            // 處理 id++ 或 id--
        char addsub[100];
        if (strEqual(op->value, "++"))                        //  如果是 id++
          strcpy(addsub, "+");                                //   設定運算為 + 法
        else                                                  //  否則
          strcpy(addsub, "-");                                //   設定運算為 - 法
        GenPcode(g, "", addsub, id->value, "1", id->value);   //  中間碼:例如 ADD i, 1, i
        strcpy(rzVar, id->value);                             //  傳回id,例如 i
      }
    }
  } else if (strEqual(node->type, "COND")) {                  // 處理 COND 節點
    // 處理判斷式 COND = EXP ('=='|'!='|'<='|'>='|'<'|'>') EXP
    Tree* op = node->childs->item[1];                         // 取得子節點
    char expVar1[100], expVar2[100];
    GenCode(g, node->childs->item[0], expVar1);               //  遞迴產生 EXP
    GenCode(g, node->childs->item[2], expVar2);               //  遞迴產生 EXP
    GenPcode(g, "", "CMP", expVar1, expVar2, nullVar);        //  中間碼:例如 CMP i,10
    strcpy(rzVar, op->value); // 傳回布林運算子               //  傳回op,例如 >
  } else if (strPartOf(node->type, "|EXP|")) {                // 處理 EXP
    // 處理運算式 EXP = ITEM ([+-*/] ITEM)*
    Tree *item1 = node->childs->item[0];                      // 取得子節點
    char var1[100], var2[100], tempVar[100];
    GenCode(g, item1, var1);                                  // 遞迴產生 ITEM
    if (node->childs->count > 1) {
      Tree* op = node->childs->item[1];                       / 連續取得 (op ITEM)?
      Tree* item2 = node->childs->item[2];
      GenCode(g, item2, var2);                                // 遞迴產生 ITEM
      GenTempVar(g, tempVar);                                 // 取得臨時變數,例如T0
      GenPcode(g, "", op->value, var1, var2, tempVar);        // 中間碼:例如 + sum i T0
      strcpy(var1, tempVar);                                  // 傳回臨時變數,例如 T0
    }
    strcpy(rzVar, var1);                                      // 傳回臨時變數,例如 T0
  } else if (strPartOf(node->type, "|number|id|")) {          // 處理 number, id 節點
    // 遇到變數或常數,傳回其 value 名稱。
    strcpy(rzVar, node->value);                               // 直接傳回 id 或 number
  } else if (node->childs != NULL) {                          // 其他情況
    // 其他狀況,若有子代則遞回處理
    int i;
    for (i=0; i<node->childs->count; i++)                     // 遞迴處理所有子節點
      GenCode(g, node->childs->item[i], nullVar);
  }
  return NULL;
}

void GenData(Generator *g) { // 產生組合語言的變數宣告
  Array *symArray = HashTableToArray(g->symTable);
  int i;
  for (i=0; i<symArray->count; i++) { // 產生符號表
    char *varName = symArray->item[i];
    char varLabel[100];
    sprintf(varLabel, "%s:", varName);
    GenAsmCode(g, varLabel, "RESW", "1", "", "");
  }
  for (i=0; i<g->varCount; i++) { // 產生臨時變數
    char tVarLabel[100];
    sprintf(tVarLabel, "T%d:", i);
    GenAsmCode(g, tVarLabel, "RESW", "1", "", "");
  }
  ArrayFree(symArray, NULL);
}

void GenPcode(Generator *g, char* label, char* op, // 輸出pcode後再轉為組合語言
              char* p1, char* p2, char* pTo) {
  char labelTemp[100];
  if (strlen(label)>0)
    sprintf(labelTemp, "%s:", label);
  else
    strcpy(labelTemp, "");
  printf("%-8s %-4s %-4s %-4s %-4s\n", labelTemp, op, p1, p2, pTo); // 印出 pcode
  GenPcodeToAsm(g, labelTemp, op, p1, p2, pTo);                     // 將 pcode 轉為組合語言
}

void GenPcodeToAsm(Generator *g, char* label, char* op, // 將 pcode 轉為組合語言的函數
                   char* p1, char* p2, char* pTo) {
  if (strlen(label)>0)                                      // 如果有標記
    GenAsmCode(g, label, "", "", "", "");                   //  輸出標記
  if (strEqual(op, "=")) { // pTo = p1                      // 處理等號 (= 0 sum)
    GenAsmCode(g, "", "LD", "R1", p1, "");                  // 轉成 LDI R1, 0
    GenAsmCode(g, "", "ST", "R1", pTo, "");                 //      ST R1, sum
  } else if (strPartOf(op, "|+|-|*|/|")) { // pTo=p1 op p2  // 處理運算(+ sum i sum)
    char asmOp[100];
    if (strEqual(op, "+")) strcpy(asmOp, "ADD");            // 根據 op 設定運算指令
    else if (strEqual(op, "-")) strcpy(asmOp, "SUB");
    else if (strEqual(op, "*")) strcpy(asmOp, "MUL");
    else if (strEqual(op, "/")) strcpy(asmOp, "DIV");
    GenAsmCode(g, "", "LD", "R1", p1, "");                  // 轉成 LD R1, sum
    GenAsmCode(g, "", "LD", "R2", p2, "");                  //      LD R2, i
    GenAsmCode(g, "", asmOp,"R3", "R1", "R2");              //      ADD R3, R1, R2
    GenAsmCode(g, "", "ST", "R3", pTo, "");                 //      ST R3, sum
  } else if (strEqual(op, "CMP")) { // CMP p1, p2           // 處理 CMP (cmp i 10)
    GenAsmCode(g, "", "LD", "R1", p1, "");                  // 轉成 LD R1, i
    GenAsmCode(g, "", "LD", "R2", p2, "");                  //      LDI R2, 10
    GenAsmCode(g, "", "CMP", "R1", "R2", "");               //      CMP R1, R2
  } else if (strEqual(op, "J")) { // J op label             // 處理 J (J > _FOR)
    char asmOp[100];                                        // 根據 op 設定跳躍指令
    if (strEqual(p1, "=")) strcpy(asmOp, "JEQ");
    else if (strEqual(p1, "!=")) strcpy(asmOp, "JNE");
    else if (strEqual(p1, "<")) strcpy(asmOp, "JLT");
    else if (strEqual(p1, ">")) strcpy(asmOp, "JGT");
    else if (strEqual(p1, "<=")) strcpy(asmOp, "JLE");
    else if (strEqual(p1, ">=")) strcpy(asmOp, "JGE");
    else strcpy(asmOp, "JMP");
    GenAsmCode(g, "", asmOp, pTo, "", "");
  } else if (strEqual(op, "RET")) {                         // 處理 RET sum
    GenAsmCode(g, "", "LD", "R1", pTo, "");                 // 轉成 LD R1, sum
    GenAsmCode(g, "", "RET", "", "", "");                   //      RET
  }
}

void GenAsmCode(Generator *g, char* label, char* op,         // 輸出組合語言指令
                char* p1, char* p2, char* pTo) {
  char *realOp = op;
  if (strEqual(op, "LD"))                                    // 如果指令是 LD,而且
    if (isdigit(p2[0]))                                      //   p2 為常數, 改用 LDI 指令
      realOp = "LDI";
  fprintf(g->asmFile, "%-8s %-4s %-4s %-4s %-4s\n",          // 輸出組合語言指令
                      label, realOp, p1, p2, pTo);
}

void GenTempVar(Generator *g, char *tempVar) {
  sprintf(tempVar, "T%d", g->varCount++);
}

void negateOp(char *condOp, char *negOp) {
  if (strEqual(condOp, "==")) strcpy(negOp, "!=");
  if (strEqual(condOp, "!=")) strcpy(negOp, "==");
  if (strEqual(condOp, ">=")) strcpy(negOp, "<");
  if (strEqual(condOp, "<=")) strcpy(negOp, ">");
  if (strEqual(condOp, ">")) strcpy(negOp, "<=");
  if (strEqual(condOp, "<")) strcpy(negOp, ">=");
}

Facebook

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License