sxarp / c_compiler_go Goto Github PK
View Code? Open in Web Editor NEWLicense: MIT License
License: MIT License
GoでCのコンパイラを書いてる
現在フィボナッチ関数くらいが書けるようになった(以下をコンパイルして実行できる)
main(){
x = 10;
return fib(x);
}
fib(x){
if (x == 1) { return 1;}
if (x== 2) { return 2;}
return fib(x-1) + fib(x-2);
}
小さなコンパイラを作りそれをDSLを使い組み合わせていく。
一つ一つのコンパイラモジュール(小さなコンパイラ)はそれぞれ単体テストで保護していく。
[]tok.Token
=> トークンの配列psr.Parser#Call([]tok.Token) (ast.AST, []tok.Token)
=> トークン列を消費してast.AST
を返すasm.Code
アセンブリコード。ast.AST#Eval(asm.Code)
=> アセンブリコードをasm.Code
に書き出すpsr.Parser
を使って以下のようにしてトークン列をアセンブリコードに変換できる:
var psr psr.Parser
psr = compiler
ast, _ := psr.Call(tokens)
ast.Eval(code) // codeにアセンブラが書き込まれている。
したがってpsr.Parser
がコンパイラとなっている。
psr.Parser
の定義。実態は関数Call
。
type Parser struct {
Call func([]tok.Token) (ast.AST, []tok.Token)
}
何故structに入れているかと言うと、メソッドを生やしてメソッドチェーンしたかったから。
Parser.Call
はトークン列を消費してast.AST
を吐き出す。
ast.AST
の定義
type AST struct {
nodes []*AST
Token *tok.Token
atype *ASTType
eval Eval
}
子としてast.AST
の配列を持つ。
AST#Eval
はasm.Code
を受け取りそれにアセンブリコードを書き出す:
func (a AST) Eval(code asm.Code) {
if a.eval == nil {
for _, node := range a.nodes {
node.Eval(code)
}
} else {
a.eval(a.nodes, code)
}
}
AST.eval
がnil
じゃなければAST.eval
を評価。さもなければ子のノード(AST)のEval
を再帰的に呼び出す。
eval
として、例えば足し算だと以下のような関数が対応している。
(+ (+ 1 2) 1)
的なASTが作られてたと仮定する(つまり子ノードとして(+ 1 2)
と1
を持っている)。
func eval(nodes []ast.AST, code asm.Code) {
nodes[0].Eval(code) // (+ 1 2)に対応するコードの書き出し。実行時に評価されるとstackに3をpushする
nodes[1].Eval(code) // 1に対応するコードの書き出し。実行時に評価されるとstackに1をpushする
// このコードパスに来た段階でstackに3と2が積まれいるはず。
// その2つをpopして足して再びstackにpushするコードを`code`に書き込んでいく
code.
Ins(asm.I().Pop().Rax()).
Ins(asm.I().Pop().Rdi()).
Ins(asm.I().Add().Rax().Rdi()).
Ins(asm.I().Push().Rax())
}
DSLを使うと足し算(int + int)の実装は以下のようにできる:
var numInt = andId().And(psr.Int, true).
SetEval(func(nodes []*ast.AST, code asm.Code) {
i := nodes[0].Token.Vali()
code.Ins(asm.I().Push().Val(i)) // intをstackにpushする
})
var add = andId().And(psr.Int, true).And(psr.Plus, false).And(psr.Int, true).
SetEval(func(nodes []*ast.AST, code asm.Code) {
// ノードの数は2つ(+リテラルはASTへの追加をしていない)
nodes[0].Eval(code)
nodes[1].Eval(code)
code.
Ins(asm.I().Pop().Rax()).
Ins(asm.I().Pop().Rdi()).
Ins(asm.I().Add().Rax().Rdi()).
Ins(asm.I().Push().Rax())
})
ここでpsr.Parser#And
はパーサーコンビネーターである(前回の話を参照)。
DSLによって生成されたadd
を使うと以下のようにしてコードを生成できる:
tokens := tok.Tokenize("1 + 2")
ast, _ := add.Call(tokens)
ast.Eval(code) // codeにアセンブリが書き込まれている。
つまりadd
は極めて小さいコンパイラと言える。
また、numInt
はもっと小さなコンパイラで、一つの数字からなるコードを変換して、stackにその数字にpushするようなアセンブリを吐く。
なお、DSL内で使われているpsr.Parser#SetEval
はpsr.Parser
が吐くast.AST
にast.AST.eval
をアタッチしている(説明用の雰囲気実装):
func (psr Parser) SetEval(eval func(nodes []ast.AST, code asm.Code)) Parser {
call := func(tokens []tok.Token) (ast.AST, []tok.Token) {
if ast, tokens := psr.Call(tokens); ast.Fail() {
return ast.Fail, tokens
} else {
// psrが吐くASTにevalをアタッチしてる
ast.SetEval(eval)
return ast, tokens
}
}
return Parser{Call: call}
}
ところでadd
はint + int
のようなコードをコンパイル出来るが、引数がint
ではないパターンにも応したい。例えば((int + int) + int)
みたいな。
結局のところ、add
が期待してるのは子のAST(nodes
)が吐いたコードが実行時に評価された結果stackに値が2つ突っ込まれれてれ良いのである。
そのために以下のようにコードを変える:
func adder(expr *psr.Parser) psr.Parser{
add := andId().And(expr, true).And(psr.Plus, false).And(expr, true).
SetEval(func(nodes []*ast.AST, code asm.Code) {
// ノードの数は2つ(+リテラルはASTへの追加をしていない)
nodes[0].Eval(code)
nodes[1].Eval(code)
code.
Ins(asm.I().Pop().Rax()).
Ins(asm.I().Pop().Rdi()).
Ins(asm.I().Add().Rax().Rdi()).
Ins(asm.I().Push().Rax())
})
return add
}
これまで固定値でpsr.Int
を使っていたところを引数expr *psr.Parser
として受け取れるようにしている。
expr
はコード実行時にstackに何らかの値を一つpushするものなら何でも良い。
adder
に適当なexpr *psr.Parser
を突っ込むことで、足し算のコンパイラがインスタンス化される。
adder
の単体テストの際は、単純なpsr.Parser
をモック的に突っ込んで挙動を確認できる。
この調子でひたすらコンパイラを生成する関数(func(*psr.Parser) psr.Parser
的なもの)をを実装していく(足し算や掛け算や代入など):
https://github.com/sxarp/c_compiler_go/blob/master/src/gen/generator.go
出来た関数はつど、モック(主にpsr.Int
)を突っ込んでインスタンス化して単体テストしていく:
https://github.com/sxarp/c_compiler_go/blob/master/src/gen/generator_test.go
出来た部品を組み合わせて、最終版なpsr.Parser
(コンパイラを作る)
func Generator() psr.Parser {
body := func(st *SymTable) psr.Parser {
lvIdent := lvIdenter(st)
rvIdent := rvIdenter(&lvIdent)
var term, muls, adds, expr, eqs, call, ifex psr.Parser
num := orId().Or(&numInt).Or(&call).Or(&rvIdent)
eqs, adds, muls = eqneqs(&adds), addsubs(&muls), muldivs(&term)
parTerm := andId().And(psr.LPar, false).And(&adds, true).And(psr.RPar, false).Trans(ast.PopSingle)
term = orId().Or(&num).Or(&parTerm)
assign := assigner(&lvIdent, &expr)
expr = orId().Or(&assign).Or(&eqs)
call = funcCaller(&expr)
semi := andId().And(&expr, true).And(psr.Semi, false)
line := andId().And(&semi, true).And(&popRax, true)
ret := returner(&semi)
retIfLine := orId().Or(&ifex).Or(&ret).Or(&line)
lines := andId().Rep(&retIfLine)
ifex = ifer(&expr, &lines)
return andId().And(&lines, true)
}
function := funcDefiner(body)
functions := andId().Rep(&function)
return andId().And(&functions, true).And(psr.EOF, false)
}
GolangでCのコンパイラを書いてる
低レイヤを知りたい人のためのCコンパイラ作成入門に触発された
低レイヤーの勉強&Golangを手に馴染ませたい
コードを書いて開発してるとき、ほとんどの時間はバグとの戦いに費やされている(気がする)。
体感的には、5%コードが書いてる時間で、残りの95%がデバッグ。
しかし、最善手を打つと、デバッグにかかる時間を抑えられる=>5%でコードを書く、15%でバグりにくい設計を考える、15%でテストを書く、残りの15%がデバッグ=>トータルで50%の所要時間に!
つまるところ、テストや設計でバグを事前に捻り潰すのが大事。
バグの予防としてこのレポジトリ内で行ったていることをいくつか揚げる:
string
などを使わない。アセンブリコードを吐く部分を例に上げて説明する。
アセンブリコードを書く部分を、素朴にやると、↓のような書き方となる。
asmCode := " mov rax, 42"
asmCode += " ret"
でも、この書き方は脆弱でぶっ壊れやすい。例えば↓のようになるとただちにバグってしまう:
asmCode := " mob rax, 42"
なので↓のように書けるようにした:
acode.Ins(asm.I().Mov().Rax().Val(42))
ここで、各メソッドのシグネチャーはそれぞれ以下のようになっている:
asm.I => func() Ini
Ini#Mov => func() Oped
Oped#Rax => func() Dested
Dested#Val=> func() Fin
code#Ins => func(Fin)
code.Ins
は、完成されたインストラクション(Fin
型)しか引数として受け付けないので、不完全なインストラクション、例えばasm.I().Mov().Rax()
をcode.Ins
を突っ込んでも、コンパイラに弾かれる。
データ駆動とは、ロジックを出来るだけ薄くして出来るだけデータを使ってコードを書くことを指す。
データ駆動が良い理由は、機能の追加や変更をするとき、データの修正だけで済むので安全だからである。
一方で機能追加の際にロジックを弄る場合は、ロジックはある種何でもありなので、コードを壊す危険がある。
データ駆動は表現出来ることが抑えられているので事故が起きにくい。
for {
if len(s) == 0 {
break
}
if s[0] == "+" {
tokens = append(tokens, PlusToken)
s = s[1:]
continue
}
if s[0] == "-" {
tokens = append(tokens, MinusToken)
s = s[1:]
continue
}
}
新しいトークンのタイプを追加する場合、if
文を追加していくことになるが、それ以外なんでも追加しようと思えば出来るので危険。例えば微妙に間違った形のif
文とか、あるいはおもむろに無限に終わらないfor
文を回し始めることだって可能。
一方でデータ駆動だと↓のような書き方となる。
var TPlus TokenType = TokenType{literal: "+"}
var TMinus TokenType = TokenType{literal: "-"}
var TLPar TokenType = TokenType{literal: "("}
var TRPar TokenType = TokenType{literal: ")"}
var TMul TokenType = TokenType{literal: "*"}
var TDiv TokenType = TokenType{literal: "/"}
var TokenTypes = []*TokenType{&TPlus, &TMinus, &TInt, &TLPar, &TRPar, &TMul, &TDiv}
func Tokenize(s string) []Token {
return tokenize(TokenTypes, s)
}
https://github.com/sxarp/c_compiler_go/blob/master/src/tok/tokenizer.go#L96
var TPlus TokenType = TokenType{literal: "+"}
を追加していく定形作業なので事故が起きる余地が少ない。
また、TokenTypes
から、トークンナイザーを生成する関数tokenize
は、単体テスト可能な点に注意。
if
文を追加する場合と違い、トークンタイプを追加するたびにテストを追加しなくても良い(追加しても良い)。
ロジックにデータを流し込むことで、処理を構成出来れば、ロジックを薄く出来て単体テストもしやすくなり、結果として壊れにくいコードとなる。
データ駆動と考え方は同じで、表現力を絞ることにより事故が起きにくくなるようにする。
コード上に、必要な自由度のみが残り、余計なものが入らないので事故が起きにくくなる。
ただし、対象となるドメインの本質的な難しさは無くならない(本質的な難しさに集中できるとも言える。)
このリポジトリの例として、パーサーコンビネーターを使ったパーサーを生成するDSLを紹介する:
パーサーを以下のような感じで定義できる(実際は少し違うが/ノードをASTに追加するかどうかもオプションで取る)
mul := OrId()
add := OrId()
term := OrId()
termPlusMul := AndId().And(&term).And(Plus).And(&mul)
termMinusMul := AndId().And(&term).And(Minus).And(&mul)
add = add.Or(&termPlusMul).Or(&termMinusMul).Or(&term)
// add = term + mul | term - mul | term
termMulMul := AndId().And(&term).And(Mul).And(&mul)
termDivMul := AndId().And(&term).And(Div).And(&mul)
mul = mul.Or(&termMulMul).Or(&termDivMul).Or(&add)
// mul = term * mul | term / mul | add
parTerm := AndId().And(LPar).And(&mul).And(RPar)
term = term.Or(&parTerm).Or(num)
// term = ( term ) | num
return AndId().And(&mul).And(EOF)
// mul EOF
再帰を表現するために、And
とOr
にはパーサーのポインターを渡すようにしている。
このDSLは正しく書かないと、すぐ無限ループに入ったり、トークン列を最後までパースできなくなったりするので、DSL化したことで、問題が簡単になったわけではない(正しい生成規則を見つけるは難しい)。
ちょっとでもおかしなことが起きてたら、直ちに例外(panic)を投げるようにしている。
これは本番のコードでも同様にやるべきだと考えていて、できるだけ早い段階で分かりやすい例外を吐いてクラッシュさせる方が、テスト時やデプロイ後の早い段階で検知/修正できるので、良いと思っている。
パーサーを書く際には型的には以下のような感じにするのが自然:
func([]token) (Fail | AST, []token)
しかし、Goだと、Fail | AST
のような型は素朴には定義できない。
ワークアラウンドとして、AST
型で定数としてFail
を定義してお茶をにごした。
var TFail ASTType = ASTType{}
var Fail = AST{atype: &TFail}
https://github.com/sxarp/c_compiler_go/blob/master/src/psr/parser.go#L21-L22
これでそんなに困っていはいない。
dockerの中に全てを封じ込めている。
git pullし、make startし、make testでテストが回るようになっている。
GOPATHがない環境でも安心。
タイトル案:
目次と記事の構成を書く
基本的な戦略
足し算をコンパイルするモジュールはDSLを使って以下のように書けます:
todo: 解説を分割する
// 足し算(`expr + expr`)の形のコードをコンパイルするコンパイラを生成する関数
// @param expr 足し算の引数部分(expr)をコンパイルするコンパイラ
// @return 戻り値として引数2つを取る足し算のコンパイラが返る
func adder(expr *psr.Parser) psr.Parser {
// `expr + expr`という形の構文をパースする
return andId().And(expr, true).And(psr.Plus, false).And(expr, true).
// コード生成の定義を以下に書いていく
SetEval(func(nodes []*ast.AST, code asm.Code) {
// 左側のexprをアセンブリコードとして書き出す
nodes[0].Eval(code)
// 右側のexprをアセンブリコードとして書き出す
nodes[1].Eval(code)
// 生成されたアセンブリコードが実行されてこのコードに到達した時、
// 2つのexprが評価された結果、値が2つスタックに積まれているはずである
// なので、その2つの値をpopし、足し合わせて結果をスタックに積むコードを
// 以下で書き込んでいく:
code.
// スタックをpopして値をraxレジスタに乘せる
Ins(asm.I().Pop().Rax()).
// スタックをpopして値をrdiレジスタに乘せる
Ins(asm.I().Pop().Rdi()).
// raxとrdiレジスタの値を足す、結果はraxに乗る
Ins(asm.I().Add().Rax().Rdi()).
// raxレジスタの値をスタックに積む
Ins(asm.I().Push().Rax())
})
}
ここで引数expr
として、足される要素(intや変数など)をコンパイルするコンパイラを渡しています。
expr
として渡すコンパイラが満たすべき条件は、生成するアセンブリコードが実行時に評価されるとスタックに評価値された値を一つ積む事です。
逆にその条件が満たされているなら、どんなコンパイラでもexpr
として渡してコンパイラを組み立てる事ができます。
このコンパイラモジュール(モジュールとは言ってもこれ自体コンパイラとしてちゃんと挙動する)を動かす場合は以下のような手順になります:
// 文字列をトークンナイズする
tokens := Tokenize("1 + 2")
// 整数一文字をコンパイルするコンパイラ(`Int`)を渡して、足し算コンパイラをインスタンス化する
add := adder(&Int)
// トークン列をパースしてAST(抽象構文木)を返す
ast, _ := add.Call(tokens)
// ASTを評価してアセンブリコードを`code`に書き出す
ast.Eval(code)
参考までに整数一文字をコンパイルするInt
コンパイラの定義:
var Int = andId().And(psr.Int, true).
SetEval(func(nodes []*ast.AST, code asm.Code) {
// トークンに入っている値を取り出す
i := nodes[0].Token.Vali()
// 取り出された値をstackにpushする
code.Ins(asm.I().Push().Val(i))
})
最終的に各モジュールを組み合わせてコンパイラを生成する。
解説は難しいのですが、DSLの書き味を見てもらいたく
func Generator() psr.Parser {
body := func(st *SymTable) psr.Parser {
lvIdent := lvIdenter(st)
ptrDeRef := ptrDeRefer(st, &lvIdent)
rvAddr := rvAddrer(&lvIdent)
rvIdent := rvIdenter(&ptrDeRef)
rvVal := orId().Or(&rvAddr).Or(&rvIdent)
var term, muls, adds, expr, eqs, call, ifex, while, forex psr.Parser
num := orId().Or(&numInt).Or(&call).Or(&rvVal)
eqs, adds, muls = eqneqs(&adds), addsubs(&muls), muldivs(&term)
parTerm := andId().And(psr.LPar, false).And(&adds, true).And(psr.RPar, false).Trans(ast.PopSingle)
term = orId().Or(&num).Or(&parTerm)
assign := assigner(&ptrDeRef, &expr)
expr = orId().Or(&assign).Or(&eqs)
call = funcCaller(&expr)
semi := andId().And(&expr, true).And(psr.Semi, false)
varDeclare := varDeclarer(st, psr.Semi)
line := andId().And(&semi, true).And(&popRax, true)
ret := returner(&semi)
body := orId().Or(&ifex).Or(&forex).Or(&while).Or(&ret).Or(&varDeclare).Or(&line)
bodies := andId().Rep(&body)
ifex, forex, while = ifer(&expr, &bodies), forer(&expr, &bodies), whiler(&expr, &bodies)
return andId().And(&bodies, true)
}
function := funcDefiner(body)
functions := andId().Rep(&function)
return andId().And(&functions, true).And(psr.EOF, false)
}
ビルディングブロックは以下のようになります:
#And
と#Or
)#SetEval
)code#Ins
)#And
と#Or
)#SetEval
)#Ins
)コンパイラは文字列を機械語(あるいはアセンブリコード)に変換するプログラムです。
変換として、例えば以下のように入力された文字列を変換します:
入力
1+2
出力
mov rax 1
mov rdi 2
add rax rdi
コンパイラのステップ
コンパイラの処理は以下のようになります:
それぞれを簡単に説明していきます
トークンナイザーの役割は文字列をリスト(トークン列)に変換することです。
この変換によって後続の処理がしやすくなります。
例えば以下のような変換を行います:
// 入力される文字列
var input = "1+2"
// 出力されるトークン列
var output = []struct {
tokenType string
value string
}{
{tokenType: "Integer", value: "1"},
{tokenType: "Opetator", value: "+"},
{tokenType: "Integer", value: "2"},
}
パーサーの役割は、トークン列を木構造に変換することです。
この木構造は、入力されるコードの意味的な構造を表現しています。
例えば以下のような変換を行います:
// 入力されるトークン列
var output = []struct {
tokenType string
value string
}{
{tokenType: "Integer", value: "1"},
{tokenType: "Opetator", value: "+"},
{tokenType: "Integer", value: "2"},
}
// 構文木を表現する構造体
type Tree struct {
treeType string
value int
children []Tree
}
var one = Tree{treeType: "integer", value: 1} // "1"を表現する構文木
var two = Tree{treeType: "integer", value: 2} // "2"を表現する構文木
// 出力される構文木("1+2"を表現する)
var output = Tree{treeType: "add", children: []Tree{one, two}}
もう少し複雑な例で1+(1+2)
だと以下のようになります:
// 入力されるトークン列
var input2 = []struct {
tokenType string
value string
}{
{tokenType: "Integer", value: "1"},
{tokenType: "Opetator", value: "+"},
{tokenType: "Brace", value: "("},
{tokenType: "Integer", value: "2"},
{tokenType: "Opetator", value: "+"},
{tokenType: "Integer", value: "3"},
{tokenType: "Brace", value: ")"},
}
var one = Tree{treeType: "integer", value: 1} // "1"を表現する構文木
var two = Tree{treeType: "integer", value: 2} // "2"を表現する構文木
var three = Tree{treeType: "integer", value: 3} // "3"を表現する構文木
// "2+3"を表現する構文木
var onePlusTwo = Tree{treeType: "add", children: []Tree{two, three}}
// 出力される構文木("1+(2+3)"を表現)
var output = Tree{treeType: "add", children: []Tree{one, onePlusTwo}}
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.