※ 引述《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/cn.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