コンパイラ制作を始めました

10/05 2024

Category: news

Gompiler

一度は自分のコンパイラを作ってみたいと考えていた為，ぼちぼちコンパイラ制作に取り掛かりました．目的は自作によりコンパイラ全体に対する解像度を高めることです．

~ 以下，夢 ~
LLVMの様にフロントエンド，バックエンドを付け替えることでいろんな言語やアーキテクチャ，バイナリ出力かソース出力などを切り替えられるようにしたいです(果てしない)．
ゆくゆくは，自作言語を，自作チップ上の自作OS上の自作コンパイラで動かせたら楽しそう...
のんびり作っていけたらいいなと考えています．

フロントエンド

ひとまず，Lexerを組んでいる．その後Parserを経て中間言語に落とし込む想定．
Cのサブセット(ミニマルセット)でかまわないので，YaccやBisonを使わずに実装したい...

Lexer

字句解析器をつくりました．ソースコードをトークナイズ(字句の切り出し及び種類の解析)しています．

ドラゴンブックにもあるような，基本ブロックごとにトークンを分けて格納しています．

Parser

再帰下降型の構文解析器を作りました．
LL(1)文法の生成規則を逆順に走査し，トークン列を抽象構文木を生成します．
今回考えた文法Gは以下の通りです．YaccとかはLALR(1)の構文解析ルーチンを生成するらしいですが，今回はひとまず簡単なLL(1)を考えてみました．
例えば以下に，代表的な代入文の文法を記述します．(後で配列などにも対応させます...([] -> a, subscript))

Vは非終端記号，Σは終端記号，Rが生成規則で，<assign>は開始変数とする．
G = (V, Σ, R, <assign>)
V = {<assign>, <expr>, <mul>, <prim>}
Σ = {<num>, <var>}
R = {
<assign> → <var> = <expr>
<expr> → <mul> | (<mul> ± <mul>)*
<mul> → <prim> | (<prim> */ <prim>)*
<prim> → <num> | <var> | (<expr>)
}

以上の文法を再帰的に逆走することで，ASTを生成します．
さらに，今回今後の最適化を見据えて，生成したASTから三番地コードの生成も行いました．
(最適化には三番地コードが適しているとかいないとか...)
ASTの非終端記号はテンポラリ変数として扱います．

・入力したソースコードの例