コンパイラを作るためのメモ

かつお

2020年9月14日 09:32

コンパイラを作る作業をググりつつ書いていきます。
事前の知識ゼロから作業して形だけでも理解していく感じで進めていきます。

作業環境:

PC: Dell Latitude D830(メルカリで買った2008年位のPC)

OS: Manjaro Linux , デスクトップ環境 = xfce

参考にした本:

技術書典の本

arm、armアーキテクチャとは

https://www.dospara.co.jp/5info/cts_str_pc_arm

アセンブリ言語とは

https://agency-star.co.jp/column/assembly-language

使用する言語

Ocaml: MLという関数型言語。様々なプログラミング言語をつくるために利用されている言語。

MLとは

https://esumii.github.io/min-caml/index2.html

C99とは

ISOで定められているＣ言語の規格のこと。1999年くらいなのでｃ99かも。

静的型付けと動的型付けの違い

下記の記事が神レベルでとても参考になりました。

コード書く段階で型をちゃんと宣言しないといけないのが静的型付けで、動的に自動で型付けしてくれる機能が付いている言語が動的型付けとざっくり理解しとけば忘れなさそう。

Menhirとは
yaccと呼ばれている伝統的なツールがあり、それのocaml版。

yaccとは
文法を定義するために独自の構文で作成したファイル、要は自分が独自に定義した構文のファイルをターゲット言語のソースに変換するためのツール。

自分が作ったhoge言語の構文で書かれた言語をｃ言語のプログラムに変換するみたいな感じかも。

ocamlのインストール

とりあえず公式サイト。読むとそれだけで時間が取られてしまうし難しそうなので必要なとき参照する感じで良さげ。

opamというocamlのパッケージ管理ツールをインストールするとocamlもセットでインストールされ使える。

まずはopamを検索。

$ pacman -Ss opam

あることを確認したらインストール。

$ pacman -S opam

次は、プログラミング言語ocamlのためのコンパイラや依存ライブラリをインストールしていく。

ocamlのパッケージ管理ツールopamで環境構築

ocamlのバージョン確認

$ ocaml --version
The OCaml toplevel, version 4.11.1

opamのヘルプを確認

わかりやすいヘルプなので見ておいたほうが良さげ。

$ opam --help

初期化

$ opam init --comp  4.11.1
[NOTE] Will configure from built-in defaults.
Checking for available remotes: rsync and local, git.
 - you won't be able to use mercurial repositories unless you install the hg command on your
   system.
 - you won't be able to use darcs repositories unless you install the darcs command on your
   system.

[WARNING] Recommended dependencies -- most packages rely on these:
 - make
 - m4
 - cc
[ERROR] Missing dependencies -- the following commands are required for opam to operate:
 - patch

上記のようにwarningとerrorメッセージが出てきました。

hg、darcsコマンドがないと言っているので、インストールします。

hgと検索してもみつからないので、おそらくpython-hglibのことだと思い下記のようにインストールしました。あとでうまくいったのでこれでokみたいです。

$ pacman -S python-hglib darcs

make、m4、ccパッケージが足らないと言ってるので、インストールします。

$ pacman -S make m4 gcc

さらに、patchコマンドがないと言っているので、patchコマンドもインストールします。

$ pacman -S patch

再度initを実行します。

$ opam init --comp 4.11.1

するとinitが進みます。途中でメッセージが2回ほど出てきますがy(yes)で進めます。

最後にまたエラーメッセージが出ました。

[ERROR] Compiler selection '4.11.1' is ambiguous. matching packages: {
       ocaml-base-compiler.4.11.1, ocaml-system.4.11.1 }

iopam init --comp 4.11.1の4.11.1が、ocaml-base-compiler.4.11.1, ocaml-system.4.11.1のどっちなのかあいまいだと言っています。

ocaml-system.4.11.1と明示して再度initしてみると成功しました。

$ opam init --comp ocaml-system.4.11.1

この辺、勘で選択したので、また調べてみます。

ここまでで、初期化できました。

opam switchする
opam switchという概念があり、複数のocamlコンパイラをインストールしている場合、opam switchすることでコンパイラを切り替えられる。

$ opam switch
#   switch    compiler    description

上記のように、何も表示されていないので、下記のコマンドを実行

$ opam switch create ocaml-base-compiler.4.11.1

opam switch createでインストールされている特定のコンパイラをswitchの切り替え対象にできる。

無事に成功したら再度opam switchを実行

$ opam switch
#   switch                      compiler                    description
->  ocaml-base-compiler.4.11.1  ocaml-base-compiler.4.11.1
         ocaml-base-compiler.4.11.1
         
[WARNING] The environment is not in sync with the current switch.
         You should run: eval $(opam env)

上記のように、ocaml-base-compiler.4.11.1がswitchに登録されアクティブになっている。

warningがでているので、文言のとおりのコマンドを実行する

$ eval $(opam env)

evalコマンド

eval [引数 ...]という書式で引数を一つの文字列に連結しその結果をシェルへの入力として使用し、コマンドとして実行するコマンド。

opam envはopam config envと同等のコマンド。現在有効なocamlコンパイラswitchの環境変数へバインドしリターンする。

ヘルプは$ opam env --helpで確認できる。

ocamlのコンパイラや依存パッケージをインストール

$ opam install menhir ppx_deriving batteries -y

loop言語のソースのダウンロード

$ git clone http://github/nomaddo/loop.git

ソースをビルド

$ cd loop
$ make
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot parsing/pident.ml
make: ocamlfind: そのようなファイルやディレクトリはありません
make: *** [Makefile:45: parsing/pident.cmo] エラー 127

エラーが出たのでgithubのreadmeを読むと必要なパッケージをインストールしてないのがあったのでインストール

$ opam install ppx_sexp_conv
The following actions will be performed:
 - install   csexp             1.3.2            [required by
                                                dune-configurator]
 - downgrade ppxlib            0.22.0 to 0.21.0 [required by ppx_sexp_conv]
 - install   dune-configurator 2.8.2            [required by base]
 - recompile ppx_deriving      5.2.1            [uses ppxlib]
 - install   base              v0.14.1          [required by ppx_sexp_conv]
 - install   ppx_sexp_conv     v0.14.2
===== 4 to install | 1 to recompile | 1 to downgrade =====
Do you want to continue? [Y/n] y

<><> Gathering sources ><><><><><><><><><><><><><><><><><><><><><><><><><><><><>
[dune-configurator.2.8.2] found in cache
[ppx_deriving.5.2.1] found in cache
[csexp.1.3.2] downloaded from cache at https://opam.ocaml.org/cache
[ppx_sexp_conv.v0.14.2] downloaded from cache at https://opam.ocaml.org/cache
[base.v0.14.1] downloaded from cache at https://opam.ocaml.org/cache
[ppxlib.0.21.0] downloaded from cache at https://opam.ocaml.org/cache

<><> Processing actions <><><><><><><><><><><><><><><><><><><><><><><><><><><><>
-> removed   ppx_deriving.5.2.1
-> removed   ppxlib.0.22.0
-> installed csexp.1.3.2
-> installed dune-configurator.2.8.2
-> installed base.v0.14.1
-> installed ppxlib.0.21.0
-> installed ppx_deriving.5.2.1
-> installed ppx_sexp_conv.v0.14.2
Done.
# Run eval $(opam env) to update the current shell environment

再度反映

$ eval $(opam env)

ビルド

$ make
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot parsing/pident.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot parsing/ast.ml
menhir --infer -v --ocamlc 'ocamlc -I parsing' parsing/parser.mly
Warning: one state has shift/reduce conflicts.
Warning: one shift/reduce conflict was arbitrarily resolved.
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot parsing/parser.mli
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot etc/etc.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot etc/flags.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot parsing/parser.ml
ocamllex parsing/lexer.mll
26 states, 638 transitions, table size 2708 bytes
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot parsing/lexer.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot typing/btypes.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot typing/tident.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot typing/intf_mod.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot typing/typed_ast.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot typing/tyenv.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot typing/typing.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot ir/typ.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot ir/operand.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot ir/ir.ml
File "ir/ir.ml", line 261, characters 11-50:
261 | let add op [x; y] = [new_instr ++ Add (op, x, y) ]
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(_::_::_::_|_::[]|[])
File "ir/ir.ml", line 262, characters 11-50:
262 | let sub op [x; y] = [new_instr ++ Sub (op, x, y) ]
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(_::_::_::_|_::[]|[])
File "ir/ir.ml", line 263, characters 11-50:
263 | let mul op [x; y] = [new_instr ++ Mul (op, x, y) ]
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(_::_::_::_|_::[]|[])
File "ir/ir.ml", line 264, characters 11-50:
264 | let div op [x; y] = [new_instr ++ Div (op, x, y) ]
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(_::_::_::_|_::[]|[])
File "ir/ir.ml", lines 265-266, characters 11-51:
265 | ...........[x; y] = [new_bmov Le op true_op  x  y ;
266 |                      new_bmov Gt op false_op x  y ]
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(_::_::_::_|_::[]|[])
File "ir/ir.ml", lines 267-268, characters 11-51:
267 | ...........[x; y] = [new_bmov Lt op true_op  x  y ;
268 |                      new_bmov Ge op false_op x  y ]
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(_::_::_::_|_::[]|[])
File "ir/ir.ml", lines 269-270, characters 11-51:
269 | ...........[x; y] = [new_bmov Ge op true_op  x  y ;
270 |                      new_bmov Lt op false_op x  y ]
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(_::_::_::_|_::[]|[])
File "ir/ir.ml", lines 271-272, characters 11-51:
271 | ...........[x; y] = [new_bmov Gt op true_op  x  y ;
272 |                      new_bmov Le op false_op x  y ]
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(_::_::_::_|_::[]|[])
File "ir/ir.ml", lines 273-274, characters 11-51:
273 | ...........[x; y] = [new_bmov Eq op true_op  x  y ;
274 |                      new_bmov Ne op false_op x  y ]
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(_::_::_::_|_::[]|[])
File "ir/ir.ml", lines 275-276, characters 11-51:
275 | ...........[x; y] = [new_bmov Ne op true_op  x  y ;
276 |                      new_bmov Eq op false_op x  y ]
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(_::_::_::_|_::[]|[])
File "ir/ir.ml", line 277, characters 12-45:
277 | let conv op [x] = [new_instr ++ Conv (op, x)]
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(_::_::_|[])
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot ir/ir_util.ml
File "ir/ir_util.ml", line 88, characters 8-16:
88 |     let set_info term loop succ =
            ^^^^^^^^
Warning 26: unused variable set_info.
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot ir/dump.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot ir/ila_check.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot ir/transl.ml
File "ir/transl.ml", lines 156-163, characters 6-9:
156 | ......let [x; y] = List.map expr_sizeof_static es in
157 |       begin match Tyenv.find_prim id with
158 |       | Some "plus" -> x + y
159 |       | Some "minus" -> x - y
160 |       | Some "mul" -> x * y
161 |       | Some "div" -> x / y
162 |       | _ -> failwith "expr_sizeof_static: 1"
163 |       end
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(_::_::_::_|_::[]|[])
File "ir/transl.ml", lines 236-247, characters 16-19:
236 | ................let [x; y] as ops = List.map (fun e -> new_tv (transl_typ e.expr_typ)) es in
237 |                 let instrs = List.map2 transl_expr  ops es |> List.flatten in
238 |                 let s = Tyenv.find_prim id |> Option.get in
239 |                 instrs, begin match s with
240 |                   | "gt" | "fgt" -> [Instr.new_branch Gt x y then_bc ]
...
244 |                   | "eq" | "feq" -> [Instr.new_branch Eq x y then_bc ]
245 |                   | "ne" | "fne" -> [Instr.new_branch Ne x y then_bc ]
246 |                   | _ -> assert false
247 |                 end
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(_::_::_::_|_::[]|[])
File "ir/transl.ml", lines 435-439, characters 10-13:
435 | ..........let [x] = bc.succs in
436 |           if List.length x.succs = 1 && List.length x.preds = 1 then begin
437 |             flag := true;
438 |             Bc.shrink bc x
439 |           end...
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
({loop=_; _ }::{loop=_; _ }::_|[])
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot ir/simplify.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot ir/ir_main.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot asmgen/ilb.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot asmgen/ilb_dump.ml
File "asmgen/ilb_dump.ml", lines 35-36, characters 8-64:
35 | ........let Arg j = List.find (function Arg i -> true | _ -> false) op.operand_attrs in
36 |         Format.fprintf fmt "@arg_%d(%d)(%a)" j i dump_typ op.typ
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(Ind|Bct|Tpath (Tident _)|Reg _)
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot asmgen/ilb_util.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot asmgen/ilb_simplify.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot asmgen/toilb.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot asmgen/sa.ml
File "asmgen/sa.ml", lines 185-197, characters 6-41:
185 | ......match arg.Operand.typ with
186 |       | I4 ->
187 |           if !r_cnt > 4 then begin    (* レジスタに乗り切らない *)
188 |             incr r_cnt;
189 |             let tv = Operand.new_tv arg.Operand.typ in
...
194 |             incr r_cnt;
195 |             let tv = Operand.new_tv arg.Operand.typ in
196 |             tv.Operand.operand_attrs <- Operand.Arg i :: tv.Operand.operand_attrs;
197 |             Map.add arg (`Reg tv) map end...................
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(I2|R8)
File "asmgen/sa.ml", line 183, characters 6-11:
183 |   let s_cnt = ref 0 in
           ^^^^^
Warning 26: unused variable s_cnt.
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot asmgen/ra.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot asmgen/asmgen.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot driver/options.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -I etc -I parsing -I typing -I ir -I asmgen -I driver -c -package ppx_deriving.show,batteries -g -bin-annot driver/main.ml
ocamlfind ocamlc -package ppx_deriving.show,batteries -package ppx_deriving.show,batteries -g -bin-annot -a -o libloop.cma etc/etc.cmo etc/flags.cmo parsing/pident.cmo parsing/ast.cmo parsing/parser.cmo parsing/lexer.cmo typing/btypes.cmo typing/tident.cmo typing/intf_mod.cmo typing/typed_ast.cmo typing/tyenv.cmo typing/typing.cmo ir/typ.cmo ir/operand.cmo ir/ir.cmo ir/ir_util.cmo ir/dump.cmo ir/ila_check.cmo ir/transl.cmo ir/simplify.cmo ir/ir_main.cmo asmgen/ilb.cmo asmgen/ilb_dump.cmo asmgen/ilb_util.cmo asmgen/ilb_simplify.cmo asmgen/toilb.cmo asmgen/sa.cmo asmgen/ra.cmo asmgen/asmgen.cmo driver/options.cmo driver/main.cmo
ocamlfind ocamlc -package ppx_deriving.show,batteries -package ppx_deriving.show,batteries -g -bin-annot -w -A -linkpkg -linkall -o loop etc/etc.cmo etc/flags.cmo parsing/pident.cmo parsing/ast.cmo parsing/parser.cmo parsing/lexer.cmo typing/btypes.cmo typing/tident.cmo typing/intf_mod.cmo typing/typed_ast.cmo typing/tyenv.cmo typing/typing.cmo ir/typ.cmo ir/operand.cmo ir/ir.cmo ir/ir_util.cmo ir/dump.cmo ir/ila_check.cmo ir/transl.cmo ir/simplify.cmo ir/ir_main.cmo asmgen/ilb.cmo asmgen/ilb_dump.cmo asmgen/ilb_util.cmo asmgen/ilb_simplify.cmo asmgen/toilb.cmo asmgen/sa.cmo asmgen/ra.cmo asmgen/asmgen.cmo driver/options.cmo driver/main.cmo
rm parsing/lexer.ml

warningがいっぱいでますがエラーまで行ってないのでいけたかも。

動作の確認(test/for.loopからfor.sを生成)

$ ./loop test/for.loop

for.sが生成されていないので、失敗。また詳細を調べていきます。

。。

また内容を追加していきます。