Re: [問題] C4拿來入門適合嗎?
※ 引述《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://www.ptt.cc/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
推
06/21 09:43,
3年前
, 1F
06/21 09:43, 1F
→
06/21 09:45,
3年前
, 2F
06/21 09:45, 2F
推
06/21 12:17,
3年前
, 3F
06/21 12:17, 3F
推
06/24 22:13,
3年前
, 4F
06/24 22:13, 4F
推
07/04 20:57,
3年前
, 5F
07/04 20:57, 5F
討論串 (同標題文章)