"ふつうのコンパイラをつくろう" 青木峰郎 著

本屋で立ち読みしていると、嵌ってしまった。こいつは、なんとなく凄い！なにしろ、ド素人の酔っ払いでさえも理解した気にさせてくれるのだから...ただし、これがふつうかどうかは知らん。
半分ほど読み終わったあたりであろうか、600ページ余りと重たいので腕が疲れてきた。ちょうどその時、カウンタから鋭い視線を感じる。お姉さんと目が合った。ドスの利いた声で「この本を頼む！」と声をかける。お姉さんは決まりきった営業台詞であっさりとかわす。どうやら照れ屋さんのようだ。

コンパイラの構造を眺めていると、昔のくだらない記憶が蘇る。実は、論文を書くのにドキュメントコンパイラなるものがあるといいなぁ、と思った時期がある。自分の文章を解析しながら、せめて誤字脱字チェッカだけでもできないものかと考えたりしたものだ。精神の泥酔者は嫌になるほどミスが多い。特許部から大量に添削された資料が戻ってくると、いつもうんざり！代理士と話をするのが憂鬱で仕方がなかった。周りには姑チェックの鬼が一人や二人はいるもので、いつも助けられる。
ところで、自分の書いた文章を解析するパーサを作るのは虚しいものがある。自己否定するような、自己嫌悪に陥っていまいそうな...自我の存在を少しでも認めたいがために、無暗に形容詞を混ぜたいという衝動は抑えられない。そして、自我は発散し、ついにはドキュメントコンパイラはcore(ゲロ)を吐くのであった。技術論文であれば、形容詞の扱いも制限できて、ある程度は形式化できそうな気がする。ボキャブラリが乏しいアル中ハイマーの文章ならば、効果的だろうと思った。しかし、形容詞には微妙なニュアンスの違いを吸収する緩衝材のような役割がある。いわば文章の華のような存在で、文章で癒されるのは形容詞の部分が大きい。
最近では、とても技術資料とは思えないような文章を書くようになった。それでも、ええんでないかい！精神の動きに身を委ねて！どうせ、まともな文章が書けるわけではない。元来、文章恐怖症な上に筆不精なところがあったが、精神の泥酔とともにそんな感覚も麻痺してしまった。脂ぎった欲望を捨て切った時、自然に精神が解放されるのだろうと信じて...

コンパイラは、ほとんど言語仕様で決まるようなものである。しかし、近年はダイナミックリンクも当り前となり、いまやOSを含めた実行環境に依存すると言ってもいいだろう。言語仕様にガベージコレクションのような強力な機能を搭載しているものや、実行環境に実行速度を上げるためのJIT(Just in time)のような機構を備えているものも珍しくない。スクリプト言語とはいえ、実行時に機械語に翻訳しながら動的にコンパイルするなどは普通に見られる。こうなると、従来のインタプリタの概念は、あまり意味がないのかもしれない。
言うまでもないが、コンパイラは作成者の意図を明確に指示しなければ正常に動作しない。まず、新たにプログラミング言語を使う時に注意することは、データ型の整合であろうか。個人的にはデータ型の定義が曖昧な言語はあまり好きになれない。いまだにbasicのイメージが残っているからであろうか？しかし、流行のスクリプト言語は、ほとんど曖昧な方向にあるようだ。確かに面倒な記述から解放されるのはありがたい。数年前から好んで使うRubyも全般的にデータ型の定義は緩やかである。だが、Rubyの場合は数値リテラルなど厳格に型チェックされる部分もあって、その按配が肌に合う。
曖昧さと言えば、構文解析で難しいイメージがあるのが、選択制御文である。C言語のif文の曖昧さは有名らしい。その感覚は酔っ払いだけではなかったか。elseがどのifにぶらさがっているのか、あるいは、ネストが深くなると選択肢の衝突が起こったりする。こうした問題は慣習的に回避しているところがある。ちなみに、回路設計ではハードウェア記述言語(HDL)を使うが、ここでも曖昧な記述はとんでもない回路を生成し、シミュレーションと実装がマッチしなかったりする。
こうした言語の曖昧さの按配というものは主観的な要素が大きい。どんな業界でも見られる暗黙というのが意外と紛らわしい。専門用語ですら、会社や組織によって微妙なニュアンスの違いを見せるのだから。したがって、言語の好みが分かれるのは自然であろう。そして、コンピュータ言語の多様化が進むのかもしれない。生産効率性という意味では矛盾するのかもしれないが、いや、人間社会の多様化には矛盾しないのか？いずれにせよ、製作者がユーザ意識とマッチするものを見出すことができれば、その業界で生きていく幸せが得られるのであろう。

本書は、一冊を通してC♭(シーフラット)という言語のコンパイラcbcを作成する。これは、ほぼC言語のサブセットで、ポインタ演算など主要部分を実装しているから、なんとなく凄そうなオモチャである。実行環境が、x86系で動作するLinuxをターゲットにしているのも手軽だ。ちなみに、C言語とJava言語を知っていることが前提だという。そういえば、むかーしJavaをちょろっとかじったことがあるが、その程度の知識でも十分についていける。そして、構文解析、抽象構文木、意味解析、中間表現から、アセンブラ、リンカ、ELFファイルの作成、更にx86アーキテクチャまで網羅され、プログラミングの実行環境を一冊で見通せる構成となっている。物理アドレスと仮想アドレスにおけるポインタイメージや、限られたレジスタでのスタック構造と関数呼び出しのイメージなどが少々くどく感じられるのは、初心者にも配慮しているからであろう。それにしても、これだけを一冊で網羅しようという試みには畏れ入る。
また、スキャナ(字句解析)やパーサ(構文解析)の実装にはJavaCCを利用し、アセンブラやリンカにはgnu環境を利用している。コンピュータの歴史で、字句解析や構文解析のノウハウが蓄積されているので、こうした定石を使うのが手っ取り早い。業界スタンダードから逸脱したツールは相手にされないということだろうか。考えてみれば、クロス環境がgnu環境で揃うのも凄い時代である。アル中ハイマー世代でお馴染みのアセンブラといえば、masmであろうか。なにしろ、組込み系では、C言語のような高級言語のコンパイラでは性能が出せないために、必然的にアセンブラで書いていた時代である。20年ぐらい前かぁ。
ところで、C言語って今でも高級言語なの？？？

1. cbcの実装イメージ
C♭には、プリプロセッサがない。したがって、#defineや#includeの代わりにJavaに似せてimport宣言を導入している。データ型には浮動小数点の機能がない。他にも構造体や共用体にも制限がある模様。インポートファイルの構文は、関数宣言、変数宣言、定数宣言、構造体や共用体の定義、typedefのみ。これだけあれば十分に実用レベルと言えよう。ちなみに、パッケージ構造はJavaの標準的なディレクトリ構造に従っているという。
mainメソッドの実装は、単純な構造をしている。コマンドライン引数をOptionクラスのparseメソッドで解析し、SourceFileオブジェクトのリストを得る。SorcsFileオブジェクトは、ソースコードを一つ指定して、buildメソッドに丸投げする。buildメソッドは、foreach文でSourceFileオブジェクトを一つずつ取り出し、Compileメソッドでコンパイルする。Compileメソッドは、ParseFileメソッドでソースコードをパースする。その結果、得られるASTオブジェクト(抽象構文木)に対して、semanticAnalyzeメソッドで意味解析を行う。更に、IRGeneratorクラスのgenerateメソッドでIRオブジェクト(中間表現)を生成する。
ここまでがフロントエンドのコード...
続いて、generateAssemblyメソッドでアセンブラコードを生成し、writeFileメソッドでファイルを書く。最後にlinkメソッドを呼び出して、オブジェクトとライブラリをリンクするといった感じ...

2. JavaCC
JavaCCは、スキャナとパーサを兼ねていて、両方を1つのファイルで同時に記述できるという。パーサジェネレータは、LLやらLALRやらLRといった扱える文法の広さによって区別されるようだ。ちなみに、LRが最も広い文法が扱える。どんなパーサも万能であるはずがない。処理速度など用途に合わせて使い分けるのであろう。
JavaCCは、LLパーサジェネレータで、専用ライブラリを必要としないという。人によっては、パーサジェネレータをコンパイラコンパイラと呼ぶらしい。つまり、コンパイラを生成するコンパイラという意味。JavaCCのCCもコンパイラコンパイラの略。ちなみに、JavaCC4.0では、エンコーディングを指定して日本語文字列のパーサ処理ができるという。このあたりにうまいこと規則を埋め込めば、ドキュメントコンパイラなるものも作成できるのかもしれない。
本書は、字句解析にJavaCCの持つ正規表現を利用している。JavaCCには、抽象構文木を作るための「アクション」という機能があるという。本書は、自力でアクションとノードクラスを書いて構文木を構築しているが、実は半自動生成できるツールにJJTreeというものがあるらしい。JJTreeは、ノードのメンバを配列で持つ設計になっているという。あまり配列に抵抗を感じないが、著者の好みには合わないらしい。

3. パーサの流れ
パーサと言えばyaccの時代が続いていた。yaccはLALRパーサジェネレータの代表格だそうな。
最近は、Packratパーサというものが登場したという。無限に先読みできて、スキャナとパーサを区別せずに書けて、メモリ消費量はソースコード長に比例するという特徴を持っているという。しかも、文法が曖昧にならず、ぶらさがりelseのような問題が発生しないのだそうな。
他にも、プログラミング言語をそのまま使って文法を記述する手法で、パーサコンビネータという技術があるという。JavaCCがJavaとは違った文法を記述するのに対して、そのままの言語でパーサが記述できるので、パーサジェネレータ自体がライブラリとなって、JavaCCのような別のツールを必要としないらしい。プログラミング言語を同じ言語で解析するとなると、自己矛盾に陥りそうな気もするが...

4. プログラムの実行イメージ
プロセスのメモリ展開には、mmapシステムコールを使う。そして、ELFセグメントとメモリ領域の対応や、スタックやヒープの関係など、プログラムの起動から終了までの過程が説明される。
また、GOT(Global Offset Table)とPLT(Procedure Linkage Table)のアドレス取得イメージから、実行可能ファイルであるPIE(Position Independent Executable)の生成といった実行イメージが解説される。ちなみに、GOTはプログラムを位置独立にする柔軟な仕掛けであるが、セキュリティ上は問題があるという。任意のアドレスへ飛ばすようなGOT上書き攻撃があるから。