計算機科学実験及演習3 (ソフトウェア) - 競技プログラミング+αなブログ

3回生前期の実験が今日終わった。
実験のページはこれ→http://ecs.kuis.kyoto-u.ac.jp/isle/le3b/index.html
bisonとflex使ってTinyC用コンパイラを作りましょうということ。

６月

実装言語は何でもいいということだったので、使い慣れている?C++で実装しようとした。
普通はCで実装するのでC以外で実装する人は席を固められることに。
案の定C以外で実装しようとする人がうちのチームの3人しかいなかったので3人横一列で並ぶことになる。
環境設定したりbisonとflexのC++での使い方を調べる作業で2日くらい過ぎる。
結局C++での使い方の情報が少なくよく分からなかったのでCで実装することになる。
emacsのyaccモードやbisonモードの設定に四苦八苦しながら、課題５くらいまでさくさく終える。（課題６は随意課題）
~~ICPC国内予選も近かったので適当にAOJをする。~~
ICPC国内予選が終わる。
意味解析部に入る。資料通りやればいい。構文木の表示のインデントあたりが一番面倒。課題７終わり。

７月

コード生成に入る。１日半くらいで終わる。とりあえず課題８終わり。
できれば拡張＆最適化しましょうということだったので、拡張＆最適化をやっていたら意外と時間が余らず実験終了。

拡張

剰余%
+=, -=
インクリメント、デクリメント(前置)
for文（expression省略可）
局所変数宣言での代入

最適化

オペランドが変数または定数のときのeaxへの代入の省略
条件分岐の簡略化
0の加減算、1の乗算の削除
1の加減算をそれぞれinc, dec 命令で置き換え
無条件分岐の分岐先が直後のラベルである場合の無条件分岐削除
無条件分岐を飛び越すためだけの条件分岐があるとき分岐を１つ削除
無条件分岐から次のラベルまでの命令の削除
2連続で完全に同じ命令（ただし、movもしくは分岐命令のときのみ）を１つ削除
mov A, B -> mov B, A のパターンで2個目を削除
2連続のラベルの削除
参照されていないラベルの削除

おまけ

最適化の1〜2はコード生成部で、それ以外はコード生成したあとNASMのコードのリストに対して行う。
正直最適化の３以降はポインタで無駄に苦しむ割に成果がそこまでないので、こっちやるくらいなら最適化１と最適化２をやるべき。
１は、オペランドが変数や定数かを判断して頑張る。第１オペランドが変数や定数のとき、第2オペランドが変数や定数のとき、どちらも変数や定数のとき、などと場合分けする。
２は、コードを生成する関数の引数に、真ならばこのラベルへジャンプするという文字列（char*）、偽ならばこのラベルへジャンプするという文字列を加えて実装した。ジャンプはしない（通常）場合はどちらもNULLが入る。例えばif文なら、条件式のexpressionをコード生成するときに偽ならばelseラベルに飛ぶように引数で指定すればよい。この最適化を実装する時は
return 3<4;
なんかでちゃんと1が返るよう注意する。
yaccファイルについては
http://www.bookshelf.jp/texi/bison/bison-ja_6.html#SEC34
を見るといい。特に「3.5.5 規則の途中のアクション」を見るべき。
あと、bisonモード、yaccモードは、
bison_mode.el
flex_mode.el
make_regexp.el(多分必要)
をどこかからDLして適当なフォルダに入れて、.emacsに

;; bison-mode / flex-mode
;; *.y *.yy ファイルを 自動的に bison-mode にする
(setq load-path (cons "~/emacs" load-path))
(setq auto-mode-alist
      (cons (cons "\\.yy?$" 'bison-mode) auto-mode-alist))
(autoload 'bison-mode "bison-mode" "Major mode for yacc files." t)
;; *.l *.ll ファイルを 自動的に flex-mode にする
(setq auto-mode-alist
      (cons (cons "\\.ll?$" 'flex-mode) auto-mode-alist))
(autoload 'flex-mode "flex-mode" "Major mode for lex files." t)

と書いたらできた。"~/emacs"のところは自分がelファイルを入れたフォルダに設定する。