Cコンパイラ自作チャレンジ（その1・字句解析編）
2018/06/05追記
続き書きました。
Cコンパイラの自作に挑戦してみる
C言語のプログラムを書き始めたのはたしか僕が中学生か高校生の頃でした。 あの頃からなんとな〜く「プログラミング言語というのはどうやってできているんだろう」と思っていました。 どう考えてもあんな複雑なルールを持ったプログラムの構文を解釈するなんて無理やろ、既存のコンパイラはどうしているんだと思わずにいられませんでした。
そんな疑問が解決されたのは、大学に入って言語処理系の講義を受けた時でした。 字句解析や構文解析について教わりとても感動しました。 最適化の話はあんまり理解できませんでしたが。
というわけで、今ならそれなりにコンパイラの自作ができそうな気がするのでCコンパイラの自作に挑戦してみたいと思います。 最近は言語処理系の自作が流行っているみたい(？)ですし。
作るにあたって名前があったほうがいいなと思ったのですが、だいたいCコンパイラって「なんとかcc」みたいな名前がついているイメージがあるので、僕のイニシャルをとってskccという名前をつけることにします。
C言語の規格
C言語の正式な規格はANSIやISOから購入する必要があるみたいなのですが、Committee Draftであれば自由に閲覧することができます。 Committee Draftは最終決定された規格と違う部分もあるかもしれないのですが、どれくらい違うものなんですかね？
今回はC11のCommittee Draftに沿ってコンパイラを作っていこうと思います。
コンパイルの処理の流れ
規格の5.1.1.2 Translation phasesに処理の流れが8つのフェーズに分かれて記述されています。 ざっくり要約してまとめると以下のような感じになります。
- トライグラフを置換する。
- 改行の直前にあるバックスラッシュを削除して前後の行を1つにつなげる。
- 字句解析をしてソースファイルをpreprocessing-tokenに分解する。
- プリプロセッサの実行、マクロを展開、
_Pragmaの実行を行う。 - 文字定数と文字列リテラルの文字を対応する実行環境用に変換する。
- 隣接する文字列リテラルを連結する。
- preprocessing-tokenをtokenに変換、構文解析をする。
- あんまり読んでないですが、リンクの話をしているっぽそう(？)。
フェーズ2で行われる処理は、複数行にわたる#defineなどの行末に置かれるバックスラッシュの処理ですね。
preprocessing-tokenはフェーズ3〜6で使われる字句要素、tokenはフェーズ7の構文解析で使われる字句要素です。
ふたつは若干内容が異なっている点に注意です。
イメージとしては、preprocessing-tokenはざっくりとしたトークン分けで、プリプロセッシングが行われた後により細くtokenに分けるという感じです。
例えば、数値は整数と浮動小数点をすべて含むpp-numberという字句要素に分解され、プリプロセッシングの後で整数と浮動小数点に分けられて値と型が解析されます。
余談ですが、pp-numberは0xe-8のようなinteger-constantでもfloating-constantでもないトークンを含んでおり、これらは値と型を解析するタイミングでエラーとすればよさそうです。
preprocessing-tokenの字句解析器
まずはフェーズ3の処理をする字句解析器を作っていきます。
6.4 Lexical elementsにpreprocessing-tokenの構文が書かれています。 トークンの種類はheader-name, identifier, pp-number, character-constant, string-literal, punctuator, これらのいずれにもマッチしない1文字です。
入力文字列のうちで構文に一致する最長の箇所までがひとつのトークンとなります。
例えば、x+++++yはx, ++, +, ++, yと区切ると正しいプログラムになりますが、この規則に則って字句解析が行われるのでx, ++, ++, +, yと区切られます。
字句解析器を作る際にはflexなどのツールを利用することが多いと思うのですが、今回はそういった便利なものを使わずに頑張ります。 というわけで、基本的にはpreprocessing-tokenの構文を手でオートマトンに変換し、1文字ずつ読み取りながらどのトークンにマッチするのか調べていきます。
このオートマトンを作る部分が結構大変で苦労しました。 例えば、文字定数を受理するオートマトンは以下のような感じになるんですが、初めて見るプレフィックスやエスケープシーケンスが意外と多くその辺で手こずりました。
その他の種類のトークンを受理するオートマトンはGitHubに置いておくので気になる方はどうぞ。 間違いがあれば指摘していただけると助かります。
skcc/diagrams at c85779b7150b75f8aef604f56dc7a7950633c479 · ShinyaKato/skcc · GitHub
あとはこの図を見ながらひたすらif文を書いていきます。 こんな感じ。
skcc/lex.c at 6a7ed86c64717b31517f5a5633fa7fbc5b784a43 · ShinyaKato/skcc · GitHub
また、これは自分の解釈があってるか自信がないのですが、最長の一致箇所を見るので途中でどこにも遷移できない場合は最後に通った受理状態まで戻ることになると思われます。
例えば、...(可変引数のアレ)を受理する途中にドットふたつという状態があるのですが、この状態は受理状態になりません。
なので仮に..というドットがふたつ連続した入力が与えられた場合は、最後に通った受理状態であるドットひとつまで戻って.と.という形に分割されます。
もし途中でひとつも受理状態を通っていなければ、先頭の1文字をどのトークンにもマッチしない文字としてトークンにします。
規格をよく読むと、"や'がこのような1文字のトークンとして切り出された場合の挙動は未定義とされています。
このような"や'が現れるのはクォーテーションの間に改行が入る場合やエスケープシーケンスが不正な場合ぐらいだと思いますが。
もう一点忘れないように書いておくと、header-nameは行頭の#, defineの後に続く場合にのみ認識されます。
すなわち、字句解析器は文脈に依存します。
正直かなり衝撃的だったのですが、規格にもそう書いてあるので仕方ないですね。
次はプリプロセッサ
次はプリプロセッサを作っていきたいと思います。
といってもある程度サボって構文解析に進んでいくつもりではありますが。
字句解析とかプリプロセッサとかあんまりTwitter映えしないし。
