針對編譯器一次分析

# 針對編譯器一次分析實際上我們的編譯器要從高階語言到組合語言的過程要經過掃描器(Lexer) 剖析器(Parser) 語意分析 (Semarntic Analysis) 中間碼產生 (P-code) 最佳化(Optimziztion) 產生組合語言 (Asm Generator) 那麼我們來跟蹤一下老師的程式碼，來看看整個流程大致上是如何 # INPUT ```c0c sum = 0; for (i=0; i<=10; i++) { sum = sum + i; } return sum; ``` # Complier.c 這邊可以看到我們的主程式去讀檔，然後先交給 parser產生語法樹然後我們的generate 再把我們的語法樹給轉為 asm 。 ```C #include "Parser.h" #include "Generator.h" void compile(char *cFile, char *asmFile) { // 編譯器主程式 printf("compile file:%s\n", cFile, asmFile); char *cText = newFileStr(cFile); // 讀取檔案到 cText 字串中。 Parser *parser = parse(cText); // 剖析程式 (cText) 轉為語法樹 generate(parser->tree, asmFile); // 程式碼產生 ParserFree(parser); // 釋放記憶體 freeMemory(cText); } ``` # Parser.c 我們單看 Parser.c 這邊可以看到我們的新增了一個 p指標並調用 ParserNew 去初始化我們的指標 *p 並呼叫我們的ParserParse 開始解析 ```C #include "Parser.h" Parser *parse(char *text) { // 剖析器的主要函數 Parser *p=ParserNew(); // 建立剖析器 ParserParse(p, text); // 開始剖析 return p; // 傳回剖析器 } ``` # ParserNew() ParserFree() 這邊跟前一文章組譯器原理差不多新增一個串列，這邊看到我們的 stack 是我們的剖析堆疊。另一個則是釋放記憶體 ```C Parser *ParserNew() { Parser *parser = ObjNew(Parser, 1); parser->tokens = NULL; parser->tree = NULL; parser->stack = ArrayNew(10); return parser; } void ParserFree(Parser *parser) { ArrayFree(parser->tokens, strFree); ArrayFree(parser->stack, NULL); TreeFree(parser->tree); ObjFree(parser); } ``` # ParserParse 這邊目前看來是我們還不太清楚這邊要幹嘛先看tokenize ```C void ParserParse(Parser *p, char *text) { // 剖析物件的主函數 printf("======= tokenize =======\n"); // 首先呼叫掃描器的主函數 tokenize() 將程式轉換為詞彙串列 p->tokens = tokenize(text); printTokens(p->tokens); p->tokenIdx = 0; printf("======= parsing ========\n"); p->tree = parseProg(p); // 開始剖析 PROG = BaseList if (p->stack->count != 0) { // 如果剖析完成後堆疊是空的，那就是剖析成功 printf("parse fail:stack.count=%d", p->stack->count); // 否則就提示錯誤訊息 error(); } } ``` # Lexer 掃描器 # tokenize 這邊發現我們的tokenize 位於 Scanner.c 也就說在我們生成語法樹的時候，我們要先針對我們能不能判斷當前這個token 是變數是迴圈還是數字也就是說我們要把她給特殊標記也就是說 printf("%d",30) 就會被拆成上面第一排是 token 下面那一排是我們的 token 進行標記後詞彙標記後，這會有助與我們的剖析器作分析。 | token | ----- | ----- | ----- |----- |----- | | -------- | -------- | -------- | -------- | -------- | -------- | | printf | ( | "%d" |, | 30| )| | id | ( | string | , | number | ) | | **type** | ----- | ----- | ----- |----- |----- | 判斷是不是變數像我們的 c語言變數定義就是開頭不能是數字。可以接受 _ 這類作為開頭。可以看到我們這邊都是在判斷是不是特殊像是 Operator或是數字或是英文字母。所以我們首先來看 ```C Array *tokenize(char *text) { // 將程式轉換成一個一個的詞彙 Array *tokens = ArrayNew(10); Scanner *scanner = ScannerNew(text); char *token = NULL; while ((token = ScannerScan(scanner)) != NULL) { // 不斷取出下一個詞彙，直到程式字串結束為止 ArrayAdd(tokens, newStr(token)); // printf("token=%s\n", token); } ScannerFree(scanner); return tokens; } ``` 下面我們針對 ScannerScan 去做分析我們看到比較關鍵的 next() 和 ch(); ```C #define ch() (scanner->text[scanner->textIdx]) #define next() (scanner->textIdx++) ``` 實際上就是 Scanner.c 裡面定義好的函數，主要就是對我們讀入的當前 text 去做拆分假設遇到是數字，英文也可能會遇到運算子假設符合規則就繼續讀下一個字元，當讀完一個串一個 token將會返回加入我們的 tokens 裡面的 list。 ```c char *ScannerScan(Scanner *scanner) { // 掃描下一個詞彙 while (strMember(ch(), SPACE)) // 忽略空白 next(); if (scanner->textIdx >= scanner->textLen) // 檢查是否超過範圍 return NULL; char c = ch(); // 取得下一個字元 int begin = scanner->textIdx; // 記住詞彙開始點 if (c == '\"') { // string = ".." // 如果是 "，代表字串開頭， next(); // skip begin quote " while (ch() != '\"') next(); // 一直讀到下一個 " 符號為止。 next(); // skip end quote " } else if (strMember(c, OP)) { // OP , ex : ++, --, <=, >=, ... // 如果是OP(+-*/<=>!等符號) while (strMember(ch(), OP)) next(); // 一直讀到不是OP為止 } else if (strMember(c, DIGIT)) { // number, ex : 312, 77568, ... // 如果是數字 while (strMember(ch(), DIGIT)) next(); // 一直讀到不是數字為止 } else if (strMember(c, ALPHA)) { // name, ex : int, sum, i, for, if, .... // 如果是英文字母 while (strMember(ch(), ALPHA) || strMember(ch(), DIGIT)) next(); // 一直讀到不是英文字母 (或數字)為止 (ex: x1y2z) } else // some other symbol, such as # next(); // 否則，傳回單一字元 strSubstr(scanner->token, scanner->text, begin, scanner->textIdx-begin); // 設定token為(begin…textIdx) 之間的子字串 return scanner->token; // 傳回token詞彙 } ``` 仔細觀察的話， ![](https://i.imgur.com/KNCzAHV.png) 可以看到我們的這個部分其實就是在做把我的token 額外給他設定一個 type 的屬性也就是 token=sum , type=id token== , type== token=0 , type=number token=; , type=; token=return , type=return token=sum , type=id token=; , type=; ```C char *tokenToType(char *token) { // 判斷並取得 token的型態 if (strPartOf(token, KEYWORDS)) // 如果是關鍵字 if, for, … return token; // 型態即為該關鍵字 else if (token[0] == '\"') // 如果以符號 " 開頭，則 return STRING; // 型態為 STRING else if (strMember(token[0], DIGIT)) // 如果是數字開頭，則 return NUMBER; // 型態為 NUMBER else if (strMember(token[0], ALPHA)) // 如果是英文字母開頭，則 return ID; // 型態為 ID else // 否則 (像是 +,-,*,/,>,<,….) return token; // 型態即為該 token } void printTokens(Array *tokens) { //printf("tokens->count = %d\n", tokens->count); int i; for (i = 0; i < tokens->count; i++) { char *token = tokens->item[i]; printf("token=%s , type=%s\n", token, tokenToType(token)); } } ``` # Parser 剖析器在經過了我們的掃描器之後我們要來把我們的 TOKEN 掃成 list 後現在要把它再次處理成一棵語法樹假設處理過後我們的 list 最終輸出會長成這樣，仔細看的話可以看到他是有level的也就是縮排的格式。那麼我們就已我們最上面開始的 **input** 去進行處理。 ``` ======= tokenize ======= token=sum , type=id token== , type== token=0 , type=number token=; , type=; token=for , type=for token=( , type=( token=i , type=id token== , type== token=0 , type=number token=; , type=; token=i , type=id token=<= , type=<= token=10 , type=number token=; , type=; token=i , type=id token=++ , type=++ token=) , type=) token={ , type={ token=sum , type=id token== , type== token=sum , type=id token=+ , type=+ token=i , type=id token=; , type=; token=} , type=} token=return , type=return token=sum , type=id token=; , type=; ======= parsing ======== +PROG +BaseList +BASE +STMT idx=0, token=sum, type=id idx=1, token==, type== +EXP idx=2, token=0, type=number -EXP -STMT idx=3, token=;, type=; -BASE +BASE +FOR idx=4, token=for, type=for idx=5, token=(, type=( +STMT idx=6, token=i, type=id idx=7, token==, type== +EXP idx=8, token=0, type=number -EXP -STMT idx=9, token=;, type=; +COND +EXP idx=10, token=i, type=id -EXP idx=11, token=<=, type=<= +EXP idx=12, token=10, type=number -EXP -COND idx=13, token=;, type=; +STMT idx=14, token=i, type=id idx=15, token=++, type=++ -STMT idx=16, token=), type=) +BLOCK idx=17, token={, type={ +BaseList +BASE +STMT idx=18, token=sum, type=id idx=19, token==, type== +EXP idx=20, token=sum, type=id idx=21, token=+, type=+ idx=22, token=i, type=id -EXP -STMT idx=23, token=;, type=; -BASE -BaseList idx=24, token=}, type=} -BLOCK -FOR -BASE +BASE +STMT idx=25, token=return, type=return idx=26, token=sum, type=id -STMT idx=27, token=;, type=; -BASE -BaseList -PROG ``` # parseProg 一開始進入點我們算是最開始的語法樹根到 parseBaseList ->parseBase 可以看到我們目前只有編寫兩種一個是變數賦予值和 For 我們先以變數來 sum=0; 看看會發生什麼事，假設以這種情況就是從ParseStmt (p) 開始跑。 ```C // PROG = BaseList Tree *parseProg(Parser *p) { // 剖析 PROG=BaseList 規則 push(p, "PROG"); parseBaseList(p); // 建立 PROG 的樹根 return pop(p, "PROG"); // 剖析 BaseList， } // 取出 PROG 的剖析樹 // BaseList= (BASE)* // 剖析 BaseList =(BASE)* 規則 void parseBaseList(Parser *p) { push(p, "BaseList"); // 建立 BaseList 的樹根 while (!isEnd(p) && !isNext(p, "}")) // 剖析 BASE，直到程式結束或碰到 } 為止 parseBase(p); pop(p, "BaseList"); // 取出 BaseList 的剖析樹 } // BASE = FOR | STMT ';' void parseBase(Parser *p) { // 剖析 BASE = FOR|STMT 規則 push(p, "BASE"); if (isNext(p, "for")) // 建立 BASE 的樹根 parseFor(p); // 如果下一個詞彙是 for else { // 根據 FOR 規則進行剖析 parseStmt(p); // 否則 next(p, ";"); // 根據 STMT 規則進行剖析 } pop(p, "BASE"); // 取出 BASE 的剖析樹 } ``` # parseStmt 這邊可以看到我們tokenize list 裡面的 type 是 id 所以會走 else 那個條件，可以知道我們需要走next 這個函數才能進到下一層 parserExp(p) 這時候我們把這個 next() 拿出來看一下。 ```C // STMT = return id | id '=' EXP | id OP1 void parseStmt(Parser *p) { push(p, "STMT"); if (isNext(p, "return")) { next(p, "return"); next(p, "id"); } else { next(p, "id"); if (isNext(p, "=")) { // id '=' EXP --> ASSIGN next(p, "="); parseExp(p); } else // id OP1 next(p, OP1); } pop(p, "STMT"); } ``` # next() 可以看到假設在上述剛剛的情況下可以得知我們的傳入的p 中間的最主要判斷 isNext(p, "id") 這邊可以看 ![](https://i.imgur.com/MmctHBd.png) ```C char *next(Parser *p, char *pTypes) { // 檢查下一個詞彙的型態 char *token = nextToken(p); // 取得下一個詞彙 if (isNext(p, pTypes)) { // 如果是pTypes型態之一 char *type = tokenToType(token); // 取得型態 Tree *child = TreeNew(type, token); // 建立詞彙節點(token,type) Tree *parentTree = ArrayPeek(p->stack); // 取得父節點， TreeAddChild(parentTree, child); // 加入父節點成為子樹 printf("%s idx=%d, token=%s, type=%s\n", // 印出詞彙以便觀察 level(p),p->tokenIdx,token,type); p->tokenIdx++; // 前進到下一個節點 return token; // 傳回該詞彙 } else { // 否則(下一個節點型態錯誤) printf("next():%s is not type(%s)\n", token, pTypes); // 印出錯誤訊息 error(); p->tokenIdx++; // 前進到下一個節點 return NULL; } } ``` 他其實是在判斷當前的p->tokenIdx 指向哪個 index 所以是 0 開始也就是 p->tokens->item[p->tokenIdx]; 那就是意味著第一個 tokens[0] 的型態是哪一個 type 和是否真的符合我們type 的格式。 ```C char* nextToken(Parser *p) { return (char*) p->tokens->item[p->tokenIdx]; } ``` ```C BOOL isNext(Parser *p, char *pTypes) { char *token = nextToken(p); if (token == NULL) return FALSE; char *type = tokenToType(token); char tTypes[MAX_LEN+1]; sprintf(tTypes, "|%s|", pTypes); if (strPartOf(type, tTypes)) return TRUE; else return FALSE; } ``` 再繼續往裡面看還可以看到strPartOf ASSERT 裡面就是寫假設有其中一個條件發生錯誤好像可以讓程式強制停止也就是假設我們的 item 裡面的值是為空 strstr 這個函式會在 str 中尋找 substr，一樣回傳 substr 的第一個出現位址，如果沒找到的話則是 NULL。這樣的話就是去檢查我們傳進來的的 token 被校正成 |%s| 也就可能變成 |EXP| |STMT| ...，後續再講語意分析和產生中間碼會有關係格式化後回到剛剛的 ```C BOOL strPartOf(char *token, char *set) { ASSERT(token != NULL && set != NULL); ASSERT(strlen(token) < 100); char ttoken[100]; sprintf(ttoken, "|%s|", token); return (strstr(set, ttoken)!=NULL); } ``` isNext () 這邊我們大概就知道意思了我們直接去讀當前這個 p->token->item 裡面的 type 然後假設找的到就往下，找不到就 return; 然後我們的產生一個臨時的變數 type 然後校正格式為 |%s| 因為我們傳過來的是 id 所以可能最終輸出就是 |id| ```C BOOL isNext(Parser *p, char *pTypes) { char *token = nextToken(p); if (token == NULL) return FALSE; char *type = tokenToType(token); char tTypes[MAX_LEN+1]; sprintf(tTypes, "|%s|", pTypes); if (strPartOf(type, tTypes)) return TRUE; else return FALSE; } ``` 這邊可以看到我們把我們的 type 他又跑去呼叫tokenToType(token); 這邊檢查型態也就是 Scanner.c ```C char STRING[] = "string"; char NUMBER[] = "number"; char ID[] = "id"; char KEYWORDS[] = "|if|for|while|return|"; char OP1[] = "|++|--|"; char OP2[] = "|+|-|*|/|"; char COND_OP[] = "|==|!=|<=|>=|<|>|"; char ITEM[] = "|id|number|string|"; char OP[] = "+-*/<=>!"; char *tokenToType(char *token) { // 判斷並取得 token的型態 if (strPartOf(token, KEYWORDS)) // 如果是關鍵字 if, for, … return token; // 型態即為該關鍵字 else if (token[0] == '\"') // 如果以符號 " 開頭，則 return STRING; // 型態為 STRING else if (strMember(token[0], DIGIT)) // 如果是數字開頭，則 return NUMBER; // 型態為 NUMBER else if (strMember(token[0], ALPHA)) // 如果是英文字母開頭，則 return ID; // 型態為 ID else // 否則 (像是 +,-,*,/,>,<,….) return token; // 型態即為該 token } ``` 最終他呼叫了strPartOf ()函數去做可能在編譯的過程中，出現異常的檢查ASSERT和用 strstr() 這個函數去查我們的 (type, tTypes) type有沒有tTypes在裡面當然他裡面還做了格式化一次也就是包起來 sprintf(ttoken, "|%s|", token); 最後只有兩種情況就是找的到我們的函數型態和找不到我們函數型態也就是 ```C if (strPartOf(type, tTypes)) return TRUE; else return FALSE; ``` 這樣的話我們的又要回到主函數 next了 # 返回next 那麼我們知道返回是 true 和 false 我們就來分析一下會發生什麼事。 ```C char *next(Parser *p, char *pTypes) { // 檢查下一個詞彙的型態 char *token = nextToken(p); // 取得下一個詞彙 if (isNext(p, pTypes)) { // 如果是pTypes型態之一 char *type = tokenToType(token); // 取得型態 Tree *child = TreeNew(type, token); // 建立詞彙節點(token,type) Tree *parentTree = ArrayPeek(p->stack); // 取得父節點， TreeAddChild(parentTree, child); // 加入父節點成為子樹 printf("%s idx=%d, token=%s, type=%s\n", // 印出詞彙以便觀察 level(p),p->tokenIdx,token,type); p->tokenIdx++; // 前進到下一個節點 return token; // 傳回該詞彙 } else { // 否則(下一個節點型態錯誤) printf("next():%s is not type(%s)\n", token, pTypes); // 印出錯誤訊息 error(); p->tokenIdx++; // 前進到下一個節點 return NULL; } } ``` # true 返回成功後，就是代表當前這個 token 是符合我們傳進去的參數 id 也就是 next(p, "id"); ，下面它們還有提到節點也就是我們要生成 ![](https://i.imgur.com/MDydLHi.png) 類似這樣的語法樹 ```C if (isNext(p, pTypes)) { // 如果是pTypes型態之一 char *type = tokenToType(token); // 取得型態 Tree *child = TreeNew(type, token); // 建立詞彙節點(token,type) Tree *parentTree = ArrayPeek(p->stack); // 取得父節點， TreeAddChild(parentTree, child); // 加入父節點成為子樹 printf("%s idx=%d, token=%s, type=%s\n", // 印出詞彙以便觀察 level(p),p->tokenIdx,token,type); p->tokenIdx++; // 前進到下一個節點 return token; // 傳回該詞彙 } ``` 不過目前這個例子只是 sum = 0;這個情況也就是這一塊，這邊可能要去買一下書才知道 xdd，目前只能靠慢慢分析 ``` ======= parsing ======== +PROG +BaseList +BASE +STMT idx=0, token=sum, type=id idx=1, token==, type== +EXP idx=2, token=0, type=number -EXP -STMT ------------------------- ``` 可能是目前累積在 stack 的深度? ```C char* level(Parser *p) { return strSpaces(p->stack->count); } ``` 因為他一直附加在主節點應該是 ```C Tree *parentTree = ArrayPeek(p->stack); // 取得父節點， TreeAddChild(parentTree, child); // 加入父節點成為子樹 ``` 也可以看到他有print分層 level(p) ，這邊跟我用 gcc plugin 分析跑的東西很像 xd # false 不是直接略 ```C else { // 否則(下一個節點型態錯誤) printf("next():%s is not type(%s)\n", token, pTypes); // 印出錯誤訊息 error(); p->tokenIdx++; // 前進到下一個節點 return NULL; } ``` # 返回parseStmt 過總而言之無論如何 p->tokenIdx++ 勢必會往下一個 item 移動那我們的目前 item index = 1 也就是 ``` ======= tokenize ======= token=sum , type=id token== , type== ``` 第二個 = ```C // STMT = return id | id '=' EXP | id OP1 void parseStmt(Parser *p) { push(p, "STMT"); if (isNext(p, "return")) { next(p, "return"); next(p, "id"); } else { next(p, "id"); if (isNext(p, "=")) { // id '=' EXP --> ASSIGN next(p, "="); parseExp(p); } else // id OP1 next(p, OP1); } pop(p, "STMT"); } ``` push 可以知道他其實就是在對我們的 stack 去做堆疊回到我們主程式就明瞭了 ```C Tree* push(Parser *p, char* pType) { // 建立 pType 型態的子樹，推入堆疊中 printf("%s+%s\n", level(p), pType); Tree* tree = TreeNew(pType, ""); ArrayPush(p->stack, tree); return tree; } ``` 判斷目前是不是 return 不是結束的話就判斷是不是 id 無論是不是id 都往下一個 token 前進 ```C // STMT = return id | id '=' EXP | id OP1 void parseStmt(Parser *p) { push(p, "STMT"); if (isNext(p, "return")) { next(p, "return"); next(p, "id"); } else { next(p, "id"); if (isNext(p, "=")) { // id '=' EXP --> ASSIGN next(p, "="); parseExp(p); } else // id OP1 next(p, OP1); } pop(p, "STMT"); } ``` 這邊可以看到老師就直接檢查是不是 "=" 了在呼叫我們的parseExp(p); ```C if (isNext(p, "=")) { // id '=' EXP --> ASSIGN next(p, "="); parseExp(p); } else // id OP1 next(p, OP1); ``` # true ```C next(p, "id"); if (isNext(p, "=")) { // id '=' EXP --> ASSIGN next(p, "="); parseExp(p); } ``` 假設是的話再往下一個推也就意味著目前已經到我們的 number index = 2 ``` ======= tokenize ======= token=sum , type=id token== , type== token=0 , type=number ``` # parseExp 可以看他他就在往下一個移動 ``` char OP2[] = "|+|-|*|/|"; char ITEM[]= "|id|number|string|"; ``` 假設是是不是 item 也就是是不是等於變數或者 string id之類的無論如何都往前推下一個 token index 並且將 index 的 token 和 type 給印出來他又判斷是否是 Operator ```C // EXP = ITEM [+-*/] ITEM | ITEM void parseExp(Parser *p) { push(p, "EXP"); next(p, ITEM); if (isNext(p, OP2)) { next(p, OP2); next(p, ITEM); } pop(p, "EXP"); } ``` ``` ======= parsing ======== +PROG +BaseList +BASE +STMT idx=0, token=sum, type=id idx=1, token==, type== +EXP idx=2, token=0, type=number ``` ## false 他這邊只是單純判斷 ```C else // id OP1 next(p, OP1); ``` ```C char OP1[] = "|++|--|"; ``` 到這邊我們已經可以生成一棵語法樹了, For 我就不分析了大同小異整體長起來會像這樣 ``` ======= parsing ======== +PROG +BaseList +BASE +STMT idx=0, token=sum, type=id idx=1, token==, type== +EXP idx=2, token=0, type=number -EXP -STMT idx=3, token=;, type=; -BASE +BASE +FOR idx=4, token=for, type=for idx=5, token=(, type=( +STMT idx=6, token=i, type=id idx=7, token==, type== +EXP idx=8, token=0, type=number -EXP -STMT idx=9, token=;, type=; +COND +EXP idx=10, token=i, type=id -EXP idx=11, token=<=, type=<= +EXP idx=12, token=10, type=number -EXP -COND idx=13, token=;, type=; +STMT idx=14, token=i, type=id idx=15, token=++, type=++ -STMT idx=16, token=), type=) +BLOCK idx=17, token={, type={ +BaseList +BASE +STMT idx=18, token=sum, type=id idx=19, token==, type== +EXP idx=20, token=sum, type=id idx=21, token=+, type=+ idx=22, token=i, type=id -EXP -STMT idx=23, token=;, type=; -BASE -BaseList idx=24, token=}, type=} -BLOCK -FOR -BASE +BASE +STMT idx=25, token=return, type=return idx=26, token=sum, type=id -STMT idx=27, token=;, type=; -BASE -BaseList -PROG ``` # 語意分析 Semarntic Analysis 在經過了上述兩個階段後我們要來分析最後一個 generate(parser->tree, asmFile); ```C void compile(char *cFile, char *asmFile) { // 編譯器主程式 printf("compile file:%s\n", cFile, asmFile); char *cText = newFileStr(cFile); // 讀取檔案到 cText 字串中。 Parser *parser = parse(cText); // 剖析程式 (cText) 轉為語法樹 generate(parser->tree, asmFile); // 程式碼產生 ParserFree(parser); // 釋放記憶體 freeMemory(cText); } ``` # generate 可以看到他最主要的GenCode 我們直接看過去吧 ```C // 程式產生器的主要函數。 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); } ``` # GenCode 可能會覺得這怎麼看，我們先縮小範圍 ``` 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 printf("ha%s\n",expVar) ; printf("ha%s\n",id->value) ; 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]; printf("%s\n" ,item1->value); 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 名稱。 printf("strha%s\n",node->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; } ``` 以 sum = 0 ; 來看這例子 ``` ======= tokenize ======= token=sum , type=id token== , type== token=0 , type=number token=; , type=; ======= parsing ======== +PROG +BaseList +BASE +STMT idx=0, token=sum, type=id idx=1, token==, type== +EXP idx=2, token=0, type=number -EXP -STMT idx=3, token=;, type=; -BASE ``` 我們上次執行階段到這邊在看我們的 GenCode裡面可以得知我們剛剛處理的宣告 sum = 0 ; 其實是在 STMT 節點 ```C 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 ```C 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 } ``` 我有加了幾行註解方便分析 ```C 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 printf("number or id name : %s\n",expVar) ; printf("value %s\n",id->value) ; 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]; printf("EXP :%s\n" ,item1->value); printf("EXP type:%s\n" ,item1->type); 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 名稱。 printf("number or id :%s\n",node->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; } ``` 整體輸出就會變這樣因為我們要從語意分析再來才是中間碼再轉為 asm 組合語言，所以 ``` =====PCODE===== EXP :0 EXP type:number number or id :0 number or id name : 0 value sum = 0 sum ``` 我們可以在分析生成中間碼之前看看發生了什麼事 ``` = 0 sum ``` 我們來分析 ```C else { Tree *id = node->childs->item[0]; // 取得子節點 Tree *op = node->childs->item[1]; ``` 看到這邊可以知道我們其實是去抓我們 tee index = 0 和 1 ```C +PROG +BaseList +BASE +STMT idx=0, token=sum, type=id <<<childs->item[0]; idx=1, token==, type== <<<childs->item[1]; ``` 我們針對我們 op tree 他的 type == "=" 的情況下會發生什麼事 ```C if (strEqual(op->type, "=")) { // 處理 id= EXP // STMT 是 id '=' EXP // 取得子節點 Tree *exp = node->childs->item[2]; char expVar[100]; GenCode(g, exp, expVar); // 遞迴產生 EXP printf("number or id name : %s\n",expVar) ; printf("value %s\n",id->value) ; GenPcode(g, "", "=", expVar, "", id->value); // 中間碼：例如 = 0 sum HashTablePut(g->symTable, id->value, id->value); // 將 id 加入到符號表中 strcpy(rzVar, expVar); // 傳回 EXP 的變數，例如 T0 } ``` 可以看到我們的程式又往下一層去找了 Tree *exp = node->childs->item[2]; 這時候就是代表我們 tree index = 2 ``` +PROG +BaseList +BASE +STMT idx=0, token=sum, type=id idx=1, token==, type== +EXP idx=2, token=0, type=number <<< 就是我 ``` 那他又把 GenCode(g, exp, expVar); 我們這棵額外的 tree 又丟給自己那他下一次會跑去哪裡咧可以知道他下一次走的節點是 EXP ``` C else if (strPartOf(node->type, "|EXP|")) { // 處理 EXP // 處理運算式 EXP = ITEM ([+-*/] ITEM)* Tree *item1 = node->childs->item[0]; // 取得子節點 char var1[100], var2[100], tempVar[100]; printf("EXP :%s\n" ,item1->value); printf("EXP type:%s\n" ,item1->type); 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 } ``` 那麼這邊又做了什麼事第一我們的樹其實是從上一層傳遞過來的所以是子節點 ```C Tree *item1 = node->childs->item[0]; ``` 這一行他直接上一層的子節點在遞迴一次也就是下面這個狀態 ```C GenCode(g, item1, var1); ``` ``` =====PCODE===== EXP :0 EXP type:number number or id :0 number or id name : 0 value sum = 0 sum ``` 所以最後他還是跟前幾個分析的程式依樣判斷是否合法然後真的合法的變數名稱就這層 tree 的值給返回 number or id :0 number or id name : 0 ```C else if (strPartOf(node->type, "|number|id|")) { // 處理 number, id 節點 // 遇到變數或常數，傳回其 value 名稱。 printf("number or id :%s\n",node->value) ; strcpy(rzVar, node->value); // 直接傳回 id 或 number } ``` 可以看到他是直接 strcpy(rzVar, node->value); 取得值往上一層丟 "|number|id|" strcpy(rzVar, var1); 取得值往上一層丟 "|EXP|" strcpy(rzVar, expVar); 取得值往上一層丟 "|STMT|" 所以到這邊就可以攔截的到值 ```C if (strEqual(op->type, "=")) { // 處理 id= EXP // STMT 是 id '=' EXP // 取得子節點 Tree *exp = node->childs->item[2]; char expVar[100]; GenCode(g, exp, expVar); // 遞迴產生 EXP printf("number or id name : %s\n",expVar) ; printf("value %s\n",id->value) ; ``` 往下面看 # 中間碼 P-CODE # GenPcode 這邊快速帶過因為我們已經知道我們傳過來的值是 ``` =====PCODE===== ... number or id :0 number or id name : 0 value sum --------------------------------下面才是真正的中間碼 = 0 sum ``` ``` GenPcode(g, "", "=", expVar, "", id->value); // 中間碼：例如 = 0 sum ``` # 產生組合語言 Asm Generator 那麼這邊要來轉為 ASM 就有 ```C void GenPcode(Generator *g, char* label, char* op, char* p1, char* p2, char* pTo) { // 輸出pcode後再轉為組合語言 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 轉為組合語言 } ``` 值照塞 ```C void GenPcodeToAsm(Generator *g, char* label, char* op, char* p1, char* p2, char* pTo) { // 將 pcode 轉為組合語言的函數 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 } } ``` 對印到我們的一個CASE ```C if (strEqual(op, "=")) { // pTo = p1 // 處理等號 (= 0 sum) GenAsmCode(g, "", "LD", "R1", p1, ""); // 轉成 LDI R1, 0 GenAsmCode(g, "", "ST", "R1", pTo, ""); // ST R1, sum ``` 寫入 ASM FILE ```C void GenAsmCode(Generator *g, char* label, char* op, char* p1, char* p2, char* pTo) { // 輸出組合語言指令 char *realOp = op; if (strEqual(op, "LD")) if (isdigit(p2[0])) // 如果指令是 LD，而且 realOp = "LDI"; // p2 為常數 fprintf(g->asmFile, "%-8s %-4s %-4s %-4s %-4s\n", label, realOp, p1, p2, pTo); // 改用 LDI 指令 } ``` # 最終OUTPUT ``` =====AsmFile:test2.asmmake====== LDI R1 0 ST R1 sum LDI R1 0 ST R1 i FOR0: LD R1 i LDI R2 10 CMP R1 R2 JGT _FOR0 LD R1 sum LD R2 i ADD R3 R1 R2 ST R3 T0 LD R1 T0 ST R1 sum LD R1 i LDI R2 1 ADD R3 R1 R2 ST R3 i JMP FOR0 _FOR0: LD R1 sum RET sum: RESW 1 i: RESW 1 T0: RESW 1 ``` 累，今天又要來分析虛擬機，小例子QQ FOR 就不多做分析囉，以後買書再來補足 GOOGLE 搜尋規則要改了!??? 工程師生態直接大改變 (希望不會。

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.