UNIXとコンパイラー・コンパイラーの世界

FrontPage

2010/08/17からのアクセス回数 6403

大型コンピュータの世界 †

私は、1983年に科学技術計算を得意とする独立系ソフトハウスに入社し、UNIX周りの ツール作成や研究開発の支援を主な仕事としていました。

まだ、SunからLight weight processが発表される前に同等のライブラリを開発したり、 同時に複数の人が絵を描くツールとか新しいものを作ったことが思い出に残ります。

私の入社した当時 †

私の入社した当時は、PCはありましたが実務では大型コンピュータを使っていました。 数少ない端末を共有しながらの仕事では、プログラミングも端末から直接入力するのでは なく、コーディング用紙と呼ばれる紙にプログラムを書き、それをパンチャーと呼ばれる 入力専門の人に依頼して入力していました。大型コンピュータの世界では人ではなく コンピュータの利用効率を高めることが第1の目標となっているため、プログラムの作成 環境は2の次でした。ですからUNIXの産みの親であるトンプソン氏とリッチー氏 が自由に使えるコンピュータ環境が欲しいと思いUNIXを作ったのも分かります。

既にあるものは2度作らない †

勉強したアルゴリズムを自分でプログラムしてみたいと思うのはプログラマーの常ですが、 先輩からは既にあるプログラムと同じものは作ってはいけないと指導されました。 当時は、IMSLという科学計算ライブラリを使っており、計算精度と信頼性という点では IMSLを使うことは当然のことでした。

今で言うと新しくプログラムを作る前に、同じものがオープンソースで提供されていないか 調べてみるのと似てますね。

「ソフトウェア作法」 †

カーニハン氏、ブローガー氏の「ソフトウェア作法」（木村泉氏訳）1981年に発売されて 以来30年も読み継がれている名著です。

UNIXコマンドの作り方 †

「ソフトウェア作法」では、Ratforという言語を使ってUNIXの基本コマンド （cp, wc,　種々のフィルター、 sort, ed, roff, m4等）の簡易版を作りながら、 トップダウンの構造化プログラミング手法を分かりやすく説明しています。

もう一つ「ソフトウェア作法」ではRatforの中に日常語を混在させた擬似コードを使い、プログラムの 構造を分かりやすく組み立てています。

例）標準入力を標準出力にコピーする例(P13から引用)

while (getc(c)が入力の終わりでない)
     call putc(c)
stop

トップダウンの問題点 †

とても有益なトップダウンの構造化プログラミングにも弱点があります。 それは一番下位のルーチンに設計のしわ寄せが来て、処理が複雑になることです。

それでもトップダウンで設計することで得るプログラムの読みやすさ、変更のしやすさ を考慮すると十分価値があると言えるのです。

ratforコンパイラー・コンパイラー †

巻末には、RatforからFortranへの翻訳プログラムも収録され、読者がRatforプログラミング を体験できるように工夫されていました。当時は今のようにC言語も普及してなく、Fortranしか 一般には普及していませんでした。

私もCP/MのFortranコンパイラーでRatforの翻訳プログラムを実際に動かして、Ratforプログラミン を楽しみました。これが私が構文解析に興味をもった最初の出来事でした。

英語は苦手 †

現在もオープンソースのドキュメントは、ほとんどが英語で書かれています。 私は英語が苦手なので、他の人のようにさくさくドキュメントを読むことができません。 しかしソフトウェアのドキュメントの場合、ソースコードなどの補助情報があるので 中身を類推しながら、読み進めることで返ってそのプログラムを理解できるような気がします。

UNIXの情報源は、ほとんどが英語 †

UNIXに関わった時には、日本語の解説書などはまったくありませんでした。 情報のほとんどがmanと英語の解説書という状況では、英語のドキュメントと向き合うしか 選択肢がありません。

「The UNIX System」はすごい †

「The UNIX System」は、shの開発者であるボーン氏が書いたUNIXのハンドブックです。 これ一冊あれば、シェルスクリプトからUNIXコマンド、システムコールの使い方等 一通りのことが分かる優れものです。私は「The UNIX System」を読んだことでそれまでの 英語は苦手という意識から何とか英語との本とも付き合える自信ができました。 特にコンピュータ関連のドキュメントは、記述パターンが多くないので1冊読みこなすと他の 本も読めるようになると思います。

「Lions' Commentary on UNIX」 †

UNIXカーネルについて書かれた書籍はたくさんありますが、「Lions' Commentary on UNIX」は 本物のUNIXソースとその解説から構成されている点が大きな特徴です。 元々この本は、著者のJ. Lions氏がニューサウスウェールズ大学の講師だった頃に学生のために書いた 「UNIXオペレーティングシステムコメンタリー」と呼ばれるノートが原点となっている、ちょっと変わった 経歴の本です。UNIXのカーネルがどのようにできたのかを知る貴重な資料です。

simhでUNIXのソースを読む †

「The Computer History Simulation Project」http://simh.trailing-edge.com/　では、 simhというシミュレータを使って過去の貴重なコンピュータを再現しています。

「Lions' Commentary on UNIX」で紹介されているPDP-11のsimhも提供されており、UNIXのソース と共にディスクイメージが提供されているので、UNIXコマンドとカーネルの勉強には最適です。 私の印象に残ったは、UNIXコマンドのソースが簡潔で美しいこととsimhの起動が本当に本で紹介されて いるイニシャルブートのシーケンス通りに動いていることでした。

yaccの勉強 †

UNIXのすごいところは、OSの他に多くのコマンドとコンパイラーやyacc, lexといった開発用ツールを 提供していることです。なかでもコンパイラーを作るためのツール（コンパイラー・コンパイラー）の yaccは、使いこなしてみたいツールの一つでした。

「Introduction to Compiler Constrction with UNIX」は、yacc, lexの使い方をsample Cと呼ばれる Cのサブセットを例に字句解析、構文解析、インタプリタ、コンパイラーの作り方を説明した本です。 この本の例題を動かすことでコンパイラー・コンパイラーの使い方が習得できるという点で非常に優れた 著書の一つです。

特にyaccで文法を記述しエラーが出たときの対応や、構文解析のエラー処理について丁寧に解説されて いるので、初心者にも安心してyaccが使えるようになっています。

バイナリファイルの構文解析もできる †

yaccは、字句解析を自前で作成することによってバイナリファイルの構文解析にも使うことができます。 私は、CADのバイナリファイルの変換プログラムでyaccを使いました。yaccを使うと可視化（テキスト表示） プログラムも簡単にできるので、デバッグやテストで重宝しました。

逆転の発想（Light Speed Cの世界） †

一般に構文解析のエラーリカバリ処理は難しく、大変な部分です。それならば、エラーリカバリの代わりにエラー 箇所をエディタで表示し、すぐに修正できるようにし、コンパイル時間の短縮することで、開発効率 高めたのが、MacintoshのコンパイラーLight Speed Cでした。この逆転の発想によってコンパイルという 時間のかかる処理が驚くほど改善されたのを今でも覚えています。

「Javaによるパーサ構築技法」 †

手続き型の言語の場合yaccで十分ですが、Prologのような論理型言語に対してはどのように対応したら よいのでしょうか。その答えが、「Javaによるパーサ構築技法」に紹介されています。

前半の構文解析も分かりやすく、簡潔に説明されており、後半の論理型言語パーサーでは推論エンジン による論理構造の表現方法と単一化がポイントです。この推論エンジンの解説とソースコードを見ていると 論理型言語パーサーの作り方を習得できたと感じるとても不思議な本です。

Antlr †

最後に紹介するAntlrは、ちょっと変わったコンパイラー・コンパイラーです。

yaccとは違い、LL(k)と呼ばれるトップダウンの構文解析を使っているため、処理の流れがイメージし易く ANTLRWorksというワークベンチを提供しており、ユーザの作った言語のチェックやテスト、デバッグがとても 簡単にできます。

言語の定義は、拡張BNFに似た形式となっていますので、はじめての人も記述しやすくなっています。 また、サポートしている言語が、C、C++、Java、Python、C#、ActionScript、JavaScriptと多いのも嬉しいです。

ANTLRを解説した日本語の本はありませんが、私は「The Definitive ANTLR Reference」を参考にしました。

ANTLRWorksを使う †

次の図が、ANTLRWorksを使ってユーザの作った文法（E1）に1+2*3を入力したときの解析結果を表示しています。 このように文法を記述するだけで、テストが行え、文法のチェックができるという夢のようなツールです。

構文木のサポート †

ANTLRの大きな特徴に、構文木をサポートしていることが挙げられます。 構文木を使うことによって、構文解析後の変数テーブル、関数テーブルの処理を再利用することができます。

構文木を使うには、文法の最初にoptionsとtokensを追加します。

options{
	output = AST;
	ASTLabelType = CommonTree;
}
tokens{
	ASSIGN; ALU_ADD; ALU_SUB; ALU_MUL; ALU_DIV;
}

構文木の生成には、部分木を生成する^オペレータとノードを生成しない!オペレータが用意されています。

次のstatementを例に簡単にオペレータの使い方を説明します。

statement
	: expression NEWLINE!
	| IDENTIFIER '=' expression NEWLINE
		-> ^(ASSIGN IDENTIFIER expression)
	| NEWLINE!
	;

NEWLINE!は、改行をノードに追加しません。

		-> ^(ASSIGN IDENTIFIER expression)

は、ASSIGNノードの下に、IDENTIFIERとexpressionからなる部分木を生成します。

Debuggerで動作を確認 †

ANTLRWorksのデバッガを使って、以下の入力をしたときの構文木を見てみましょう。

a=1
a+2*3

ASSIGNの下にa, 1がぶら下がる代入部分とALU_ADDの下にaとALU_MULの部分木が作成される計算部分が確認できます。

構文木は解析したプログラムを別の言語に変換するトランスレータを作成する場合にも便利で、ANTLRはトランスレータを作成する場合のテンプレート機能も提供しています。

自分だけの言語を作ってオリジナルのマシンを動かしてみる †

もう過去の技術だと思われていたコンパイラー・コンパイラーですが、Googleの提供するGWTでjavaからjava scriptへのトランスレータがプログラミングの壁を取り除く大きな要因になったことを顧みると、新しいものを作るために今後もコンパイラー・コンパイラー技術は使われていくのだと感じました。

最後に、学研の「大人の科学」Vol.24の付録の4ビットマイコンボード（GMC-4）用の簡易言語をAntlrを使って作成したときの様子をご紹介して私のつぶやきを締めくくります。

例）１５秒カウンタプログラム

int     a;
a = 15;
while (a > 0) {
     out(a);
     shts();
     a = a - 1;
     timer(10);
}

生成されたアセンブラは、以下のようになります。

TIA	f
TIY	0
AM
L1: TIY	0
TIA	0
AIA	1
M-
JUMP	L2
TIY	0
MA
AO
CAL SHTS
TIY	0
TIA	1
M-
TIY	0
AM
TIA	a
CAL TIMR
JUMP	L1
L2: CAL ENDS
L3: JUMP	L3

アセンブラ †

アセンブラから命令コードへの変換には、 http://www.musashinodenpa.com/misc/GMC4/ のアセンブラを使わせてもらいました。

シミュレータ †

GMC-4の元になった「FX-マイコン」のシミュレータが以下のURLに公開されています。

http://homepage2.nifty.com/kocha_web/fxms/fxms.html

シミュレータを使うことによって、コンパイラーのバグ等問題点が早期に見つかり、 とても助かりました。

実機での実行 †

生成された命令セットをGMC-4で動作しているときの画像です。