自作コンパイラ

\[ \newcommand{dn}[3]{\frac{\mathrm{d}^{#3} #1}{\mathrm{d} #2^{#3}}} \newcommand{\d}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}} \newcommand{\dd}[2]{\frac{\mathrm{d}^2 #1}{\mathrm{d} {#2}^2}} \newcommand{\ddd}[2]{\frac{\mathrm{d}^3 #1}{\mathrm{d} {#2}^3}} \newcommand{\pdn}[3]{\frac{\partial^{#3} #1}{\partial {#2}^{#3}}} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\pdd}[2]{\frac{\partial^2 #1}{\partial {#2}^2}} \newcommand{\pddd}[2]{\frac{\partial^3 #1}{\partial {#2}^3}} \newcommand{\p}{\partial} \newcommand{\D}[2]{\frac{\mathrm{D} #1}{\mathrm{D} #2}} \newcommand{\Re}{\mathrm{Re}} \newcommand{\Im}{\mathrm{Im}} \newcommand{\bra}[1]{\left\langle #1 \right|} \newcommand{\ket}[1]{\left|#1 \right\rangle} \newcommand{\braket}[2]{\left\langle #1 \middle|#2 \right\rangle} \newcommand{\inner}[2]{\left\langle #1 ,#2 \right\rangle} \newcommand{\l}{\left} \newcommand{\m}{\middle} \newcommand{\r}{\right} \newcommand{\f}[2]{\frac{#1}{#2}} \newcommand{\eps}{\varepsilon} \newcommand{\ra}{\rightarrow} \newcommand{\F}{\mathcal{F}} \newcommand{\L}{\mathcal{L}} \newcommand{\t}{\quad} \newcommand{\intinf}{\int_{-\infty}^{+\infty}} \newcommand{\R}{\mathcal{R}} \newcommand{\C}{\mathcal{C}} \newcommand{\Z}{\mathcal{Z}} \newcommand{\bm}[1]{\boldsymbol{#1}} \]

トークン化

文字列をトークン列に変換します。

抽象構文木の構築

抽象構文木 (Abstract Syntax Tree : AST)

Func Node::Type childs
type TypeFunc arg[] ret
TypeStruct member[]
TypeArray base size
TypePointer base
TypePrim ident
program Program defs
FuncDef name type compound
GVarDef name type
TypeDef name type
compound Compound stmt[]
stmt VoidStmt
ExprStmt expr
LVarDef name type
Assign expr expr
UAssign expr
If cond true_node
IfElse cond true_node false_node
Goto name
Label name
Return expr
While cond body
DoWhile cond body
For cond body init iterate
Continue
Break
expr
cond Cond cond true_node false_node
or Or : :
xor Xor : :
and And : :
equality EQ : :
NEQ : :
relational LT : :
LEQ : :
GT : :
GEQ : :
shift RShift : :
LShift : :
add Add : :
Sub : :
mul Mul : :
Div : :
Mod : :
post Cast ident type
Ref ident
Addr ident
Array ident expr
Member ident ident
FuncCall ident
prim Num int
Ident str
SizeOf type

シンボルテーブル生成

種類 名前 型 アドレス 関数本体 ローカル
Func name type addr (テキスト領域) body lsymbol
GVar name type addr (静的領域)
LVar name type addr (スタック相対)
Type name type

ASTの再帰的評価

ASTを再帰的に評価することで、コード生成に必要なさまざまな情報を得ることができます。

型のサイズ

変数に必要なメモリを知るために型のサイズを計算します。

変数

アドレス

代入文の左辺を評価します。

定数値

コンパイル時に値が決まっているべき部分を評価します。

アセンブラコードの生成

グローバル変数の配置

グローバル変数はデータ領域に配置されます。

関数のコード生成

実行環境メモ

現在の位置を保持しながらコード生成をする。

関数 ループ
main null / for_1 / for_1

return, break, continue に必要な情報。

関数のバイナリはテキスト領域に配置されます。

低レイヤの世界では「テキスト」は実行可能なバイナリのことを指します。

ローカル変数の配置

スタックのアドレスはフレームポインタからの相対アドレスです。

作業日誌

expr =  mul ("+" mul | "-" mul)*
mul = primary ("*" primary | "/" primary | "%" primary)*
primary = num | "(" expr ")"
prim = num | ident | "(" expr ")"
program = stmt*
stmt = ";"
     | "{" stmt* "}"
     | "if" "(" expr ")" stmt ("else" stmt)?
     | "while" "(" expr ")" stmt
     | "do" stmt "while" ( expr ) ";"
     | "for" "(" expr? ";" expr? ";" expr? ")" stmt
     | expr ";"
program = func*
func = ident "(" ident % "," ")" compound
compound = "{" stmt* "}"

参考

https://github.com/DoctorWkt/acwj

https://github.com/rui314/chibicc

https://www.sigbus.info/compilerbook

https://github.com/season1618/books/blob/main/c-compiler/index.md