※ 引述《Matz (void (*一資米)())》之銘言： : 各位前輩大神好。 : 本魯最近想自己寫一個精簡C語言的編譯器。 : 看惹很多書，但都感覺有點拿以下手，中間卡住超多次。 : 最近看到C4 C in four function，程式碼很少大概500多行而已。 : 想問C4拿來入門合適嗎??? 安安 小弟私立科大學店生，誤信對岸知乎 「程序員的三大浪漫」 https://www.zhihu.com/question/27323148 抄了jserv大大的MazuCC，然後到處抄，什麼都抄一點，然後再加上自己的劣化，最後生 出了一陀不三不四的東西，然後我還拿去騙惹畢業專題 雖然我八成以後不會再寫編譯器惹，但還是整理一下抄編譯的流程八 首先實作編譯器很簡單，分三個部份，詞彙分析器、語法分析器、程式碼產生器 概念的部份可以看這個 https://www.youtube.com/watch?v=4LZkf64APx8 完全不懂的情況下「編譯器概念」這一節能大概知道什麼是編譯器 然後看完這個，詞彙分析器大概就完成了，反正我的程式最後開放四個函式 int is_punct(token *tok, int c); /*判斷tok是否是punct且符合c*/ void unget_token(token *tok); /*將tok還回去*/ token *peek_token(void); /*預先得知下個token，但不讀入*/ token *read_token(void); /*讀入下個token*/ 細節和功能邊做邊想就好了 然後語法分析器，可以跳著看和邊看邊睡對岸的開放式課程，作為參考 https://www.bilibili.com/video/av17404276/ 然後語法當然不可能自己設計，所以繼續抄，有人已經整理好了C語言的BNF 既然是從The C programming language, 2nd整理出來的，那應該和C89差不遠 https://reurl.cc/V6Z22Y 再來就是看jserv大大的MazuCC https://github.com/jserv/MazuCC 可以跪著看，如果膝蓋會痛，可以休息一下再繼續跪 我自己寫的編譯器，list.h直接抄，typedef struct __Ast也直接抄 其他部份雖然名義上沒抄，但實際上大概就像寫數學想半天寫不出來，然後去看後面解答 一樣 如果前面看開放式課程沒有睡的很死，那應該會知道，裡面實作解析運算子的方法是LR的 運算子優先序解析器 static int priority(const Token tok) { switch (get_punct(tok)) { case '[': case '.': case PUNCT_ARROW: return 1; case PUNCT_INC: case PUNCT_DEC: return 2; case '*': case '/': return 3; case '+': case '-': return 4; case PUNCT_LSHIFT: case PUNCT_RSHIFT: return 5; case '<': case '>': return 6; case '&': return 8; case '|': return 10; case PUNCT_EQ: return 7; case PUNCT_LOGAND: return 11; case PUNCT_LOGOR: return 12; case '?': return 13; case '=': return 14; default: return -1; } } 因為LR解析器我從來都沒有看懂過，所以去瞄了一眼放在MazuCC簡介的8cc原始碼 https://github.com/rui314/8cc 好的，是LL的遞迴下降解析器 基本上就是把BNF的C語法直接轉成程式碼，一層一層的遞迴下去 恩，看的懂，那就選這個八，所以全部改寫成遞迴下降的形式(原來連這個都是抄的) 像是 <conditional-expression> ::= <logical-or-expression> | <logical-or-expression> ? <expression> : <conditional-expression> <logical-or-expression> ::= <logical-and-expression> | <logical-or-expression> || <logical-and-expression> <logical-and-expression> ::= <inclusive-or-expression> | <logical-and-expression> && <inclusive-or-expression> <inclusive-or-expression> ::= <exclusive-or-expression> | <inclusive-or-expression> | <exclusive-or-expression> <exclusive-or-expression> ::= <and-expression> | <exclusive-or-expression> ^ <and-expression> <and-expression> ::= <equality-expression> | <and-expression> & <equality-expression> <equality-expression> ::= <relational-expression> | <equality-expression> == <relational-expression> | <equality-expression> != <relational-expression> 給個圖 https://i.imgur.com/NtOmOxL.png 就能寫成 static Ast *conditional_expr() { Ast *ast = logical_or_expr(); token *tok = read_token(); if(is_punct(tok, '?')) { Ast *r = expr(); token *rtok = read_token(); if(!is_punct(rtok, ':')) error("next is ':' "); Ast *l = conditional_expr(); r = ast_binop(rtok->punct, r, l); return ast_binop(tok->punct, ast, r); } unget_token(tok); return ast; } static Ast *logical_or_expr() { Ast *ast = logical_and_expr(); token *tok = read_token(); while(is_punct(tok, PUNCT_LOGOR)) { ast = ast_binop(tok->punct, ast, logical_and_expr()); tok = read_token(); } unget_token(tok); return ast; } static Ast *logical_and_expr() { Ast *ast = inclusive_or_expr(); token *tok = read_token(); while(is_punct(tok, PUNCT_LOGAND)) { ast = ast_binop(tok->punct, ast, inclusive_or_expr()); tok = read_token(); } unget_token(tok); return ast; } static Ast *inclusive_or_expr() { Ast *ast = exclusive_or_expr(); token *tok = read_token(); while(is_punct(tok, '|')) { ast = ast_binop(tok->punct, ast, exclusive_or_expr()); tok = read_token(); } unget_token(tok); return ast; } static Ast *exclusive_or_expr() { Ast *ast = and_expr(); token *tok = read_token(); while(is_punct(tok, '^')) { ast = ast_binop(tok->punct, ast, and_expr()); tok = read_token(); } unget_token(tok); return ast; } static Ast *and_expr() { Ast *ast = equality_expr(); token *tok = read_token(); while(is_punct(tok, '&')) { ast = ast_binop(tok->punct, ast, equality_expr()); tok = read_token(); } unget_token(tok); return ast; } static Ast *equality_expr() { Ast *ast = relational_expr(); token *tok = read_token(); while(is_punct(tok, PUNCT_EQ) || is_punct(tok, PUNCT_NE)) { ast = ast_binop(tok->punct, ast, relational_expr()); tok = read_token(); } unget_token(tok); return ast; } 484簡單很多 然後寫到這裡大概會發現，恩，全部都能用Lex和yacc完成呢～，原理一樣，成果一樣， 不一樣的只是他是自動的，你是手動的(笑 然後陷入了某種無力感，隔了幾天接受了這個事實，然後繼續寫八 再來就是C語言的精隨指標和陣列拉 因為是精隨，所以你要懂一點點C語言才能寫出來 建議去看jserv大大的「你所不知道的C語言」系列講座 https://hackmd.io/@sysprog/c-prog/%2F%40sysprog%2Fc-programming 通常我是聽不懂，但只要開著直播，就能感受到經驗值往上漲 然後是《C專家編程》(Expert C Programming: Deep C Secrets) 因為英文很爛，所以我就看簡中版，可以當故事書看，輕鬆有趣 其中的一些故事可以對C的指標有更深入的理解 看完之後有總結出一些規律拉，大概是這樣 https://i.imgur.com/dXluSNc.png 指標解析方向由中間開始，然後是右邊、左邊 不知道對不對拉，不過目前都還能當人肉cdecl還蠻爽的 然後你會發現一件事，就是關於type的問題 陣列在運算式中會強制表示為指標+偏移的形式，但偏移的單位是「指標指向type的大小 」 例如 int a[2][3]; 在運算式中a[1][1]會表示成 *(*(a + 1) + 2)_ a就會加上sizeof(int) * 3 * 1個單位再加上sizeof(int) * 1 * 2個單位 也就是說在AST中表示成這樣 * | + / \ * 2 | + / \ a 1 但是a和1相加的時候，可以明確知道a的type，但*和2相加的時候，就不知道a的type了 所以需要將type往上傳讓其他節點也擁有type的資訊，這樣在*與2相加的時候，就能知道 要偏移sizeof(int) * 1 * 2 那要如何將變數往上傳？喔，首先你要在運算的時候得知他當初宣告時的type，這需要一 個symbol table，然後其他的我直接抄MazuCC了嘻嘻 然後就是程式碼產生器，我的程式碼產生器產生兩種目標語言 一種是Mano machine的組合語言，另一種是S-expression Mano machine是一個教學用的計算機結構 https://en.wikipedia.org/wiki/Mano_machine 為什麼選這個？因為我在舊書店買到了這本書阿 https://i.imgur.com/emCYran.jpg 然後自己學了好幾章 我一直覺得組合語言不是人寫的，所以一直想要一個編譯器，難得有機會當然要做做看 然後是S-expression，這是我又聽信知乎 https://www.zhihu.com/question/26549715/answer/34336593 跑去買了SICP的中譯本，然後看了幾節SICP的影片，雖然最後還是沒學會 只學會了 https://i.imgur.com/BBHdDlN.jpg 不過還是有所啟發，所以寫了S表達式的程式碼產生器 例如 int main() { int sum = 0; for(int i = 0; i < 10; i++) sum = sum + i; return sum; } 可以產生出這樣的形式 (AST_FUNC (main (int)) (AST_DECL (= ((int) sum) 0)) (AST_FOR (INIT (AST_DECL (= ((int) i) 0))) (COND (< ((int) i) 10)) (STEP (++ ((int) i))) (BODY (= ((int) sum) (+ ((int) sum) ((int) i))))) (AST_RETURN ((int) sum))) 當然輸出的都是沒排版的，這時可以寫一個簡單的排版程式，和編譯器有點像 然後組合語言產生器嗎.......就組合語言產生器阿 選的組合語言不要太簡單，像是我選的就太簡單的，很多指令要另外寫副程式 像是PUSH和POP要自己寫，還因為沒辦法把PC的值抓出來(只有呼叫副程式的只能碰到PC) ，所以要用很迂迴的手法才能抓到PC 然後也要有symbol table，因為你前面宣告，後面要用，除了要判斷變數是否存在，還要 知道區域變數與BP的偏移位置 再來要對lvalue有概念，第一次寫的時候以為我有概念，但寫出來的扣說我沒概念 重寫的時候我以為我有概念了，但寫到後來發現我好像搞錯了什麼？因為扣比第一次簡單 很多，而且快到deadline了，所以我現在還在想我搞錯什麼？ 大概是這樣 這版的大大的程度應該都高我很多，我的學習歷程應該沒什麼參考性 如果有錯或冒犯到大大，請多見諒 會寫出來只是報告還沒做完+深夜情緒 做這個花了我七、八個月，前面幾個月常常「陷入我是誰？我要做什麼？」的狀態 然後中間遇到問題沒人可以問，只能自己找資料，也不知道找到的資料有沒有用(當然也 是我個性的問題拉，不擅長社交，只在討論區問問題，強者我朋友遇到同樣的問題可能會 直接私訊大大八:P) 還有沒人監督+沒明確截止日+糟糕的時間管理的隨意浪費時間 雖然對未來找工作沒什麼幫助，沒有強到不看學歷那就只看學歷，以我私立科大的學歷， 第一份工作八成不到30K 業界最多工作還是web，對我這種能拿出來現的只有一點計算機冷知識和C語言，還是去學 比較實用的技術八:P 最後人還是要腳踏實地，不要被浪漫衝昏頭，雖然真的很浪漫就是了 https://www.zhihu.com/question/27323148/answer/36153626 -- https://youtu.be/o6-na8AVSqI 天.....天才 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.126.202.172 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/CompilerDev/M.1592682144.A.C8B.html ※ 編輯: wei115 (59.126.202.172 臺灣), 06/21/2020 03:59:40 ※ 編輯: wei115 (59.126.202.172 臺灣), 06/21/2020 04:06:49