自作Cコンパイラ
2019-05-28版がベース
現時点で追記/修正
考えている流れ
まずは入門に従ってCで進める
そのあとにRustで書いてみる
メモ
tokenizeしたやつから、
生成規則で構文を定義する
EBNFは生成規則を記述するための記法
Cは大体が左結合(左側を先に計算する)演算子
=は右結合
ポインタのデリファレンス*も右結合
パーサ
入力: フラットなトークン列
出力: 抽象構文木
再帰下降構文解析
1つの生成規則を1つの関数にマップするという構文解析の手法
LL(1)パーサと
トークンを1つだけ先読みする再帰下降パーサのこと
LL(1)パーサが書ける文法のことをLL(1)文法という
スタックマシン
ここのgen関数を追加する辺りで、tokenize関数のトークン判定の条件分岐に以下の4つを導入する必要がある
*p == '*' || *p == '/' || *p == '(' || *p == ')'
関数呼び出しごとに確保されるメモリ領域
関数フレーム
アクティベーションレコード
初めて見た
今までスタックフレームと呼んでいた
プロローグ
コンパイラが関数の先頭に出力する定型の命令
末尾はエピローグ
tokenizerでやること、parserでやること、code generatorでやることの区別がまだうまくついていない
tokenizer
入力文字列をトークン列に変換する
トークンは構文の上での最小単位でいいか?
+= や is_hogeなど
トークン列が構文的に正しいかはこの時点ではわからなくてもいい
ただし、存在しないトークンが来たかどうかはここで弾く
Cならば=>や!==などは存在しない演算子
parser
トークン列を抽象構文木に変換する
意味的におかしいものはここで弾く
&(a) = 1など
code generator
抽象構文木をアセンブラに変換をする
Rob Pikeのプログラミングの5つのルール/Rob Pike's 5 Rules of Programming
わかる
制御構文の追加からは特に執筆中の内容になるらしい
ASTを常に2分木にする必要はあるか?
ミニマルにはじめているのはいいが、ブロックを導入した辺りで最後の式が評価される、というのはやめたほうがいいかもしれない
if/whileなどの構造を入れた辺りでスタック操作をミスってデバッグに手間取った
前半は丁寧なので加筆が進めばその辺りも考慮されそう
関数定義の実装後に軽くリファクタをした
あまりしすぎても本文と乖離しそうなので程々に
1+pはOKだが、1-PはNG
配列型とポインタ型は大体同じ
違いは
配列型変数をそのまま使うと先頭のアドレスが返る
ポインタ型変数をそのまま使うと指す先のアドレスが返る
code:c
int* p = &x;
p == &x
ここで変数p自体のアドレスは返らないが、変数a自体のアドレスを返す
ブロック({})による変数のshadowingは特にスタックを切り替えているわけではなさそうだった
なので、Cのスコープは関数ローカル、ファイルローカル、グローバル、だけ?
一通りやっての感想
低レイヤを知りたい人、という部分がいまいちよくわからなかった
#includeという文字列に反応するのがウケた
ループが雑すぎた
大方針として、一個のノードを処理したらスタックに何かが積まれる、というのが守られていない
副作用のみでもpush 0の必要がある
左辺値/右辺値
名前の通り、基本的にそちらの辺で使用される値
ただし、左辺値を右辺値として扱うこともある
e.g., i = x
右辺値は左辺には来られない
a[0] は *(a + 0 * N)
derefは左辺値にも右辺値にもなれる
セルフホスト前の実装のTODOs
関数呼び出しの引数の無限ループを回避し、適切にエラーを出すこと
大丈夫になっていた
が、関数の括弧が閉じられていないというエラーは出ない
エラーは指示する文言にする
tokensのスコープを狭める
関数引数でポインタを使えるようにする
関数引数と変数の宣言を統合する
ローカル変数のオフセット計算を型のサイズに合わせて行う
try 0 'int main() { int* p; int** q; q = &p; return (q+1)-(1+&p);}' が通るようにする
ND_RETURNにも型情報を入れる
関数テーブルを作ればterm()での関数かどうかの判定が直ぐにできる
Contextに入れる
型テーブルも作る
consumeとは違う、現在トークンを判定する関数を作る
コードジェネレータに渡すためにstruct programとかでまとめる
代入時に型検査したい
三項演算子
bool型
内部的にはcharでよさそう
size_t型
ちゃんとやるならlong型へのtypedef?
マクロの入れ子
関数の再帰呼び出しで実行するのがよさそう
int i = 1 != NULL && 1 < 10; return i; が動かない
セルフホストする
++と--
前置/後置で微妙に異なるのに注意
これも作っておきたい
&&と||
これは必須
ローカル変数の初期化
グローバルは少し手間だが、ローカルは欲しい
const/static
構文的に受け入れて無視、でよさそう
struct
流石にこれをなしにするのはきびしい
enum
これも無くてもできるがあったほうが嬉しい
union
これは少しむずいかもしれない?
無名unionを使っている部分をどうするか
構造体に入れるが同じオフセットになるようにしてやる
型のサイズ計算は?
switch
if文で代替可能だが、作ってもよさそう
caseが定数しか取れない
"switch" "(" expr ")" "{" ("case" constant ":" (expr ";")? )? ("default:" (expr";")? ) }"
こんな感じか?
思ったよりも手間
構造体のメンバへのアクセス
入れ子も
構造体メンバへの操作
++, --
+=, *=, -=, /=
void型の認識
関数の引数/返り値でvoidを使えるようにする
opaque構造体
プロトタイプ宣言
とりあえず読み捨てでよい
あとから関数テーブルを作る
外部変数宣言
グローバル変数として扱う
キャスト
マクロ
ifdef, ifndef, define, else, endif
include
文字列連結で対応できそう?
システムパスのものは読まない
!演算子
break文
文字リテラル
'a', '\0'
文字列リテラルのバッククオート処理
"%zd\n"
size_t型
continue
ローカル変数の破棄
ブロック末尾で毎回破棄する
関数テーブルを持って置かないと戻り値のサイズがわからない…
とりあえず代入先の変数の型を優先する
関数を呼び出すときに引数のサイズに合わせてレジスタに値を設定する必要がある
実装のTODO
エラー文言の改善
デバッグしやすいようにする
コンパイルしているコードを指し示す
関数テーブルを作る
term()での関数かどうかの判定が直ぐにできる
不正な関数呼び出しを避けられる
コードジェネレータに渡すためにstruct programとかでまとめる
型検査
代入のとき
三項演算子
bool型
内部的にはcharでよさそう
マクロの入れ子
関数の再帰呼び出しで実行するのがよさそう
union
これは少しむずいかもしれない?
無名unionを使っている部分をどうするか
構造体に入れるが同じオフセットになるようにしてやる
型のサイズ計算は?
switch
if文で代替可能だが、作ってもよさそう
caseが定数しか取れない
"switch" "(" expr ")" "{" ("case" constant ":" (expr ";")? )? ("default:" (expr";")? ) }"
こんな感じか?
思ったよりも手間
continue
システムヘッダーのinclude
#include<stdio.h>
文字列の扱いの修正
要検討
型テーブルを作る
consumeとは違う、現在トークンを判定する関数を作る
ローカル変数の破棄
ブロック末尾で毎回破棄する
GDB
set disassembly-flavor intel