Powered by SmartDoc

Cコンパイラ設計(yacc・lexの応用)

竹本 浩
http://www.pwv.co.jp

近年、Linuxやcygwinの普及によってだれでもyacc/lexを使って新しい言語を作成し、その処理系を作成することができるようになってきた。

G・フリードマンの「Cコンパイラ設計」は、yacc/lexの使い方を丁寧に説明した名著であるが、英語の原本も日本語本も絶版で、amazonのオークションでも買えないため日本語訳本を借り、OCRから復刻することにした。

Linux、cygwinではbison, flexが使われているので若干本書と内容が異なる部分があるが、それも別枠で整理してみたいと考えている。

4章以降は、竹本 浩のページ(Wiki)に追加中2008/05/15

目次

Last modified: Sat May 17 08:58:02 JST 2008

翻訳者序文

コンピュータの発達とともに、これまでにCOBOL,FORTRAN、Pasca1,Lisp、C等、数多くのコンピュータ言語が作られてきました。一般には,新たなコンピュータ言語、あるいはそのコンパイラを作るなどということは、非常に困難かつ時間のかかる作業で、ソフトウェアの専門家やハッカーだけの特権であると考えている人が多いかと思います。しかし、決してそうではないことを本書が証明しています。もちろん、何の知識もなく、何のツールもなければ、それは非常に困難なことでしょう。本書はUNIX (1)に標準装備されているya?tとlexという強力なツールを利用して、sampleCというC言語のサブセットのためのコンパイラを設計・製作することを目的としています。つまり、sampleCコンパイラの製作を通じて、読者はyaccとleXというツールの使い方を修得し、コンピュータ言語の構造、認識、あるいは意味解析についての知識を学ぶことができます。

本書は机上の参考書として、言語をどのように定義するのか、あるいは言語はどのように認識されるのか、などを理解するために利用することも可能です。しかし、やはり、実際にUNIX上でyaccやlexを実行してみることが大切です。そして、sampleCコンパイラを作ってみることです。最終的には、読者自身の言語を設計し、言語仕様を定め、実際に自分自身の言語のためのコンパイラを作成することをお勧めします。さらに、yaCCや1eXに習熟すれば、作成するソフトウェアのユーザー・インタフェースの部分に利用することも可能となるでしょう。

最後に、本書の翻訳にあたり御協力いただいた海保氏、ならびに編集の労をとっていただいた吉崎氏に感謝いたします。

1987年9月28日

矢吹道郎

小暮博道

田中啓介

序文

現在普及しつつある多くのマイクロコンピュータにとっては、優れたユーザ・インタフェースとして良くできたコマンド言語が必要であるため、多くの言語が存在している。しかし、いい加減に作られた言語ではまったく使い物にならない。コンパイラを作ることは言語認識の一つの応用であり、また、ツールや基本的機能を拡張して大規模なプログラムをデザインし実装することである。簡単なコンパイラを理解することは,それ自体が目的となるばかりでなく、一般的なプログラミング・システムを理解し、より上手に利用するための助けとなる。

本書は、UNIXシステムに標準装備されており、十分強力で、かつ使いやすいツールであるyacc(パーサ・ジェネレータ)およびleX(標準表記に基づく意味解析ジェネレータ)の二つのジェネレータを利用して、コンパイラを作成するケース・スタディとなっている。

本書ではsampleCと呼ばれるC言語のサブセットを定義し、コンパイラの開発の例として取り上げる。ここではsampleCの作成それ自体が目的ではなく、いかに最適なオブジェクト・コードを作り出すかが目的となっている。章末問題はコードをさらに改善し、言語を拡張するための助けとなるでろう。

本書では、文法に関する詳細な解説や、ジェネレータの内部の働きなどの論理的な詳細にはあまり触れず、適当な本を読むよう示すに留め、ジェネレータを利用するための基本的な説明だけを行なうこととする。

ここで我々が目的とするのは、信頼性があり、容易に変更でき、かつシンプルなコンパイラを素早く作るために、いかにジェネレータを利用すれば良いかを解説することである。もう一つの目的は、コンパイラの構成要素とその一般的なインタフェースについての実際の知識を解説することである。、

本書は、コンパイラの構造の詳細なアルゴリズムに関して勉強する前に読むべき簡単な解説書、あるいはジェネレータを用いることによる多くの利点についての解説書となっている。つまり、本書はコンパイラ・デザインにおけるさまざまな問題点を広く取り扱う解説書ではないし、またジェネレータのすべての使い方を解説するものでもない。しかし、本書を一度読めば、参考文献として挙げている[Joh78コや[Les78b]などの、本来のジェネレータの解説書を読むことができるようになるはずである。コンパイラは非常に大きなプログラムであるので、後のデバッグ、拡張、保守に気を配りながら、どのように構成しデザインするかを本書は示している。

本書を読む場合には、エディタ、自分の使っているファイル・システム、そして、もちろんC言語(本書の例はすべてC言語で書かれている)に関する基礎知識が必要である。また、他の言語、たとえばPascal、FORTRAN、BASICに関する知識も有効である。C言語のような構造化言語とそのスコープに関する知識、あるいはスタックのようなデータ構造に関する知識も、第5章を読むために必要となる。第2章ではパターン・マッチング・エディタのある程度の経験も前提となっている.

用語法に関する知識はほとんど必要ない。我々は、変数、関数、ラベルや、他のプログラム要素の宣言とその要素の定義との差異を注意深く明らかにしていく。宣言とは単に、プログラム要素を持ち、それに変数の型、パラ・メータの型、あるいは関数の返し値などの性格を与える“文”である。また定義とは、変数に値を与えたり、関数の本体を記述したり、あるいはラベルの位置などを与えることによって、宣言されたプログラム要素にその内容を与えることである。

文法を考える場合に、我々は伝統的な用語法から多少離れる。プロダクション、右辺、左辺などの単語は使わないようにする。その代わりに,非終端記号のプロダクション(同様に右辺)すべてを意味する“規則”と、規則の右辺にあるものを表わす用語として“フォーミュレーショゾ”を用いる。

本書の例として挙げられているプログラムのソース・ファイルは,著者の一人であるH・G・FriedmanからARPANET,BITNET,CSNET,USENETを通じて手に入れることができる。

最後に、本書の構成に対していろいろな示唆を与えてくれた編集者に感謝する。また、部分的にNSFのMCS81-05896により助成されているUrbana-Champaignにあるmnois大学の計算機科学科のコンピュータの使用、ならびに本書の編集作業に助力してくれたUlm大学のSektion Informatikに感謝する。

ATS

HGF

Urbana,I11inois

  1. UNIXオペレーティング・システムは、ペル研究所が開発し,ATTがライセンスしています。