コンパイラーコンパイラー

コンピュータサイエンスにおいて、コンパイラコンパイラまたはコンパイラジェネレーターは、プログラミング言語とマシンの何らかの形式の形式的な記述からパーサー、インタープリタ、またはコンパイラを作成するプログラミングツールです。

最も一般的なタイプのコンパイラはパーサージェネレーターと呼ばれます。^[1]これは構文解析のみを処理します。

言語の正式な記述は、通常、パーサージェネレーターへの入力として使用される文法です。多くの場合、バッカスナウア記法(BNF) や拡張バッカスナウア記法(EBNF) に似ているか、独自の構文を持っています。文法ファイルは、生成されたコンパイラーのターゲットプログラミング言語の構文と、その特定の構造に対して実行する必要があるアクションを記述します。

プログラミング言語のパーサーのソースコードが、パーサージェネレーターの出力として返されます。このソースコードは、スタンドアロンまたは埋め込み型のパーサーにコンパイルできます。コンパイルされたパーサーは、ターゲットプログラミング言語のソースコードを入力として受け入れ、アクションを実行するか、抽象構文ツリー(AST) を出力します。

パーサージェネレーターはASTのセマンティクスやターゲットマシンのマシンコードの生成を処理しません。 ^[2]

メタコンパイラは、主に他のプログラミング言語のコンパイラ、トランスレータ、およびインタープリタの構築に使用されるソフトウェア開発ツールです。 ^[3]メタコンパイラへの入力は、主にコンパイラの構築を目的として設計された特殊なプログラミングメタ言語で書かれたコンピュータプログラムです。 ^[3]^[4]生成されるコンパイラの言語はオブジェクト言語と呼ばれます。コンパイラを生成する最小の入力は、オブジェクト言語の文法と意味変換をオブジェクトプログラムに指定するメタプログラムです。^[4]^[5]

バリエーション

一般的なパーサージェネレーターは、パーサーによってルールが適用されたときに実行される文法の各ルールに実行可能コードを関連付けます。これらのコードは、パーサーによって分析される構文構造のセマンティクスを定義するため、セマンティックアクションルーチンと呼ばれることもあります。生成するパーサーの種類に応じて、これらのルーチンは解析ツリー(または抽象構文ツリー) を構築するか、実行可能コードを直接生成します。

最も初期（1964 年）の、驚くほど強力なコンパイラコンパイラのバージョンの 1 つがMETA IIです。これは、スタックマシンコードを生成する出力機能を備えた解析文法を受け入れ、独自のソースコードと他の言語をコンパイルできます。

ベル研究所で構築されていたオリジナルのUnixバージョンの最も初期のプログラムの中には、2 つの部分からなるlexとyaccシステムがありました。これは通常、 C プログラミング言語コードの出力に使用されていましたが、プログラミング言語からテキストファイルの変換まで、あらゆる用途に使用できる柔軟な出力システムを備えていました。現在のGNUバージョンは flexとbisonです。

いくつかの実験的なコンパイラは、通常は表示的意味論を使用して、プログラミング言語の意味論の正式な記述を入力として受け取ります。このアプローチは「意味論ベースのコンパイル」と呼ばれることが多く、 1978年にピーター・モーゼスのセマンティック実装システム（SIS）によって開拓されました。 ^[6]しかし、生成されたコンパイラとそれが生成したコードはどちらも時間と空間の点で非効率的でした。現在、この方法で構築された製品コンパイラはありませんが、研究は続けられています。

カーネギーメロン大学のProduction Quality Compiler-Compiler ( PQCC ) プロジェクトでは、セマンティクスは形式化されていませんが、マシン記述のための半形式的なフレームワークは備えています。

コンパイラコンパイラにはさまざまな種類があり、コード生成のために書き換え文法に従って構文ツリーを並べるために使用されるボトムアップの書き換えマシンジェネレータ (JBurg を参照) や、属性文法パーサージェネレータ (たとえば、ANTLR は解析段階で同時型チェック、定数伝播などに使用できます) などがあります。

メタコンパイラ

メタコンパイラは、オブジェクト言語に関係なく同じ側面を自動化することで、コンパイラの作成作業を軽減します。これにより、特定の問題の仕様に適したドメイン固有言語の設計が可能になります。メタコンパイラは、このようなドメイン固有のオブジェクト言語のトランスレータを作成するコストを削減し、問題の解決にドメイン固有言語の設計を含めることが経済的に実現可能になります。^[4]

メタコンパイラのメタ言語は通常、強力な文字列およびシンボル処理言語であるため、他のさまざまなソフトウェアエンジニアリングおよび分析ツールの生成を含む、汎用アプリケーションに強力に応用されることが多い。^[4]^[7]

メタコンパイラは、ドメイン固有言語の開発に役立つだけでなく、コンパイラ作成のドメイン向けに設計されたドメイン固有言語の代表的な例です。

メタコンパイラは、通常、独自のメタ言語または既存のコンピュータプログラミング言語で記述されたメタプログラムです。独自のメタ言語で記述されたメタコンパイラが自分自身をコンパイルするプロセスは、セルフホスティングコンパイラと同等です。今日記述される最も一般的なコンパイラは、セルフホスティングコンパイラです。セルフホスティングは、多くのメタコンパイラの強力なツールであり、独自のメタプログラミングメタ言語を簡単に拡張できます。メタコンパイラと他のコンパイラコンパイラを区別する機能は、コンパイラの動作のすべての側面を記述する特殊なメタプログラミング言語を入力として受け取ることです。メタコンパイラによって生成されるメタプログラムは、C++、BASIC、またはその他の一般的なプログラミング言語で記述されたプログラムと同じくらい完全なプログラムです。メタプログラミングメタ言語は、コンピュータプログラミング言語やその他のコンピュータツールの開発を容易にする強力な属性です。コマンドラインプロセッサ、テキスト文字列の変換と分析は、メタコンパイラのメタプログラミングメタ言語を使用して簡単にコーディングできます。

フル機能の開発パッケージには、リンカーとランタイムサポートライブラリが含まれています。通常、サポートライブラリを作成するには、 Cや C++などのマシン指向のシステムプログラミング言語が必要です。コンパイルプロセスに必要なサポート関数で構成されるライブラリにより、通常、完全なメタコンパイラパッケージが完成します。

メタコンパイラの意味

コンピュータサイエンスでは、接頭辞「メタ」は一般に「（自身のカテゴリ）について」という意味で使用されます。たとえば、メタデータは他のデータを説明するデータです。他の言語を説明するために使用される言語は「メタ言語」です。「メタ」は「より高い抽象レベル」を意味する場合もあります。メタ言語は、言語の特性を説明するために、より高い抽象レベルで動作します。バッカス・ナウア記法（BNF）は、もともとALGOL 60を定義するために使用された正式なメタ言語です。BNFは「弱いメタ言語」です。なぜなら、BNFは構文のみを説明し、セマンティクスや意味については何も述べないからです。メタプログラミングとは、プログラムをデータとして扱うことができるようにコンピュータプログラムを書くことです。メタコンパイラは、メタプログラミングの目的のために特別に設計された特殊なメタ言語（より高レベルの抽象化）で書かれたメタプログラムを入力として受け取ります。 ^[4]^[5]出力は実行可能なオブジェクトプログラムです。

類推することができます: C++コンパイラがC++プログラミング言語プログラムを入力として受け取るのと同様に、メタコンパイラはメタプログラミングメタ言語プログラムを入力として受け取ります。

Forthメタコンパイラ

Forth言語の支持者の多くは、Forth の新しい実装を作成するプロセスをメタコンパイルと呼び、メタコンパイラを構成すると考えています。Forth におけるメタコンパイラの定義は次のとおりです。

「メタコンパイラは、自身のソースコードを処理し、自身の実行可能バージョンを生成するコンパイラです。」

Forth におけるメタコンパイラという用語の使用は、主流のコンピュータサイエンスでは異論の的となっています。Forth (プログラミング言語)およびコンパイラ構築の歴史を参照してください。実際の Forth のコンパイルプロセス自体は、自己ホスティング型の拡張可能なプログラミング言語である Forth と、場合によってはクロスコンパイル(コンピュータサイエンスで長年定着している用語) を組み合わせたものです。メタコンパイラは、汎用のコンパイラ記述システムです。Forth メタコンパイラの概念は、自己ホスティング型で拡張可能な言語と区別がつかないことに加え、実際のプロセスはより低いレベルで動作し、追加の Forth ワードを定義するために使用できる Forthワードの最小サブセットを定義します。その後、基本セットから完全な Forth 実装を定義できます。これは、ブートストラッププロセスのように思えます。問題は、ほとんどすべての汎用言語コンパイラも Forth メタコンパイラの説明に当てはまることです。

(自己ホスティングコンパイラ) X が自身のソースコードを処理し、結果として自身の実行可能バージョンを生成する場合、X はメタコンパイラです。

X を C、C++、 Pascal、COBOL、Fortran、Ada、Modula-2などの一般的な言語に置き換えるだけです。すると、Forth のメタコンパイラの使用法によれば、X はメタコンパイラになります。メタコンパイラは、コンパイルするコンパイラよりも上の抽象レベルで動作します。メタコンパイラは、自身をコンパイルするときのみ、同じ (自己ホスティングコンパイラ) レベルで動作します。メタコンパイラのこの定義の問題点を理解する必要があります。これは、ほとんどすべての言語に適用できます。

しかし、Forth でのプログラミングの概念を調べてみると、辞書に新しい単語を追加して、このように言語を拡張することがメタプログラミングです。Forth のこのメタプログラミングによって、Forth はメタコンパイラになります。

Forth でのプログラミングは、言語に新しい単語を追加することです。このように言語を変更することをメタプログラミングといいます。Forth はメタプログラミング用に特別に設計された言語であるため、Forth はメタコンパイラです。Forth でのプログラミングは Forth を拡張することです。Forth 語彙に単語を追加すると、新しい Forth方言が作成されます。Forth は Forth 言語方言に特化したメタコンパイラです。

歴史

オリジナルのコンパイラの設計は、1959年にトニー・ブルッカーとデリック・モリスによって開始され、最初のテストは1962年3月に始まりました^。[8]ブルッカー・モリス・コンパイラ（BMCC）は、マンチェスター大学の新しいアトラスコンピュータ用のコンパイラを作成するために使用され、Mercury Autocode、Extended Mercury Autocode、Atlas Autocode、ALGOL 60、ASA Fortranなどの言語が使用されました。ほぼ同じ時期に、プリンストン大学のET （ネッド）アイアンズとアルダーマストンの原子兵器研究施設のアリック・グレンニーによって関連作業が行われていました。グレニーの「構文マシン」論文（1977年に機密解除）は、以下で説明するMETAシリーズの翻訳書記体系に影響を与えました。

メタコンパイラの初期の歴史は、SIG/PLAN のシンタックスドリブンコンパイラに関するワーキンググループ 1 の歴史と密接に結びついています。このグループは、主にロサンゼルス地域のハワードメトカーフの努力によって開始されました。^[9] 1962 年の秋、ハワードメトカーフは 2 つのコンパイラ記述インタープリタを設計しました。1 つは、レドリーとウィルソンによって説明された方法に基づくボトムツートップ分析手法を使用していました。^[10]もう 1 つは、グレンニーの研究に基づくトップツーボトムアプローチを使用して、文脈自由文法からランダムな英語の文を生成しました。^[11]

同時に、ヴァル・ショレは生成型と解析型の2つの「メタマシン」を説明した。生成型マシンは実装され、ランダムな代数式を生成した。最初のメタコンパイラであるMeta Iは、1963年1月にUCLAのIBM 1401でショレによって実装された。彼のオリジナルのインタープリタとメタマシンは、疑似機械語で直接記述されていた。しかし、 META IIは、疑似機械語へのコンパイルを記述できる高レベルのメタ言語で書かれていた。^[12]^[13]^[14]

ボルト、ベラネック、ニューマンのリー・シュミットは、1963年3月にタイムシェアリングPDP-lのCRTディスプレイを利用したメタコンパイラを作成した。^[15]このコンパイラは、解釈コードではなく実際のマシンコードを生成し、Meta Iから部分的にブートストラップされた。^[要出典]

Schorre は 1963 年の春に Meta I から Meta II をブートストラップしました。1964 年のフィラデルフィア ACM 会議で発表された改良されたメタコンパイラシステムに関する論文は、一般的な参考資料として利用できるメタコンパイラに関する最初の論文です。Schorre のシステムの構文と実装手法は、その後のほとんどのシステムの基礎となりました。このシステムは小型の 1401 に実装され、小型のALGOLのような言語を実装するために使用されました。^[要出典]

同様のシステムが多数すぐに登場した。^[要出典]

ACデルコのロジャー・ラットマンは、1964年1月にIBM 7090上で論理設計シミュレーション用の言語であるLOGIKを開発し実装した。 ^[16]このコンパイラは、ブール式の効率的なコードを生成するアルゴリズムを使用していた。^[要出典]

1964年のACMプロシーディングスの別の論文では、UCLAのシュナイダーとジョンソンがIBM 7090用に開発したMeta IIIについて説明しています。 ^[17] Meta IIIは、多くの言語に対して効率的なマシンコードを生成する試みです。Meta IIIは完全にアセンブリ言語で実装されました。2つのコンパイラがMeta IIIで書かれました。CODOLはコンパイラ作成のデモコンパイラで、PUREGOLはALGOL 60の方言です（ALGOLと呼ぶのはまったく厚かましいことでした）。

1964 年後半、Lee Schmidt は PDP-l から Beckman 420 までメタコンパイラ EQGEN をブートストラップしました。EQGEN は論理方程式を生成する言語でした。

1964年、System Development Corporationはメタコンパイラの開発に本格的に取り組み始めました。この取り組みには、Lispで書かれた強力なメタコンパイラ、Bookl、Book2が含まれており、これらは広範なツリー検索とバックアップ機能を備えています。SDCのQ-32システムの1つから生まれたのがMeta 5です。^[18] Meta 5システムには、入力ストリームのバックアップと、あらゆるコンテキスト依存言語を解析するのに十分なその他の機能が組み込まれています。このシステムは、多くのユーザーにリリースされ、コンパイル以外にも多くの文字列操作アプリケーションがありました。また、多くの精巧なプッシュダウンスタック、属性設定とテスト機能、および出力メカニズムを備えています。Meta 5がJOVIALプログラムをPL/Iプログラムに正常に変換できることは、そのパワーと柔軟性を証明しています。

テキサス・インスツルメンツのロバート・マクルーアは、TMGと呼ばれるコンパイラを発明した（1965年に発表）。TMGは、B、PL/I、ALTRANなどのプログラミング言語用の初期のコンパイラを作成するために使用された。ヴァル・ショアのメタコンパイラとともに、ドナルド・クヌースの「The Art of Computer Programming」の最後の章の初期のインスピレーションとなった。^[19]

LOTシステムは1966年にスタンフォード研究所で開発され、Meta IIを非常に忠実にモデル化しました。^[20] LOTシステムには、PL/Iのサブセットをコンパイルできるコンパイラを生成するための新しい特殊目的の構造がありました。このシステムには広範な統計収集機能があり、トップダウン分析の特性を研究するために使用されました。

SIMPLEはPL/I用プリプロセッサの作成を支援するために設計された特殊な翻訳システムであり、PL/Iで書かれており、実行部、構文解析部、意味構成部の3つのコンポーネントで構成されています。^[21]

TREE -METAコンパイラは、1968 年 4 月にカリフォルニア州メンロパークのスタンフォード研究所で開発されました。初期のメタコンパイラの歴史は、TREE META マニュアルに詳しく記載されています。TREE META は、SDC の開発の一部と並行していました。初期のメタコンパイラとは異なり、セマンティクス処理と構文処理を分離しました。構文規則には、認識された言語要素をツリーノードと組み合わせるツリー構築操作が含まれていました。入力のツリー構造表現は、単純な形式のアンパース規則によって処理されました。アンパース規則は、ノード認識と属性テストを使用し、一致した場合に関連付けられたアクションが実行されました。さらに、ツリー要素もアンパース規則でテストできました。アンパース規則は再帰言語でもあり、アンパース規則のアクションが実行される前にツリーの要素を渡してアンパース規則を呼び出すことができました。

Glennie が最初に提唱したメタマシンの概念は非常に単純なため、3 つのハードウェアバージョンが設計され、そのうち 1 つが実際に実装されました。後者はセントルイスのワシントン大学で実装されました。このマシンはマクロモジュラーコンポーネントから構築され、命令には Schorre が記述したコードが使用されています。

CWIC (Compiler for Writing and Implementing Compilers) は、最後の Schorre メタコンパイラです。Systems Development Corporation で Erwin Book、Dewey Val Schorre、Steven J. Sherman によって開発されました。リスト処理言語 (lisp 2) のフルパワーにより、コード生成前に構文で生成されたリストとツリーを最適化アルゴリズムで操作できます。CWIC には、言語に組み込まれたシンボルテーブルもあります。

ドメイン固有言語の復活と、使いやすく、理解しやすく、保守しやすいパーサージェネレーターの必要性により、メタコンパイラーは高度なソフトウェアエンジニアリングプロジェクトにとって貴重なツールになりつつあります。

yacc系のパーサージェネレーターの他の例としては、ANTLR、Coco/R、^[22] CUP、^[要出典] GNU Bison、Eli、^[23] FSL、^[要出典] SableCC、SID (Syntax Improving Device)、^[24]JavaCCなどがあります。純粋なパーサージェネレーターは便利ですが、コンパイラー構築の問題のうち、構文解析の部分のみに対処します。PQCC 、Coco/R、DMS Software Reengineering Toolkitなどのより広い範囲をカバーするツールは、意味解析、コード最適化、生成などのより困難な構文解析後のアクティビティに対してかなりのサポートを提供します。

Schorre メタ言語

最も初期の Schorre メタコンパイラである META I と META II は、UCLA の D. Val Schorre によって開発されました。その後、他の Schorre ベースのメタコンパイラも登場しました。それぞれ言語分析やコード生成に改良が加えられました。

プログラミングでは、プログラミング言語名をコンパイラとプログラミング言語の両方を指すのに使うのが一般的で、文脈によって意味が区別されます。C++ プログラムは C++ コンパイラを使用してコンパイルされます。これは、次の場合にも当てはまります。たとえば、META II はコンパイラと言語の両方です。

Schorre メタコンパイララインのメタ言語は、出力変換構造が埋め込まれた構文方程式を解析するトップダウン文法を使用する関数型プログラミング言語です。

構文方程式:

<名前> = <本文>;

は、成功または失敗を返すコンパイルされたテスト関数です。<name> は関数名です。<body> は、グループ化され、代替があり、生成物を出力するテストで構成される論理式の形式です。テストは他の言語のboolに似ており、成功はtrue、失敗はfalseです。

プログラミング言語をトップダウンで分析的に定義するのは自然なことです。たとえば、プログラムは次のように定義できます。

プログラム = $宣言;

プログラムを 0 個以上の宣言のシーケンスとして定義します。

Schorre META X言語には駆動ルールがあります。上記のプログラムルールは駆動ルールの例です。プログラムルールは、テストルールである宣言を呼び出すテスト関数で、成功または失敗を返します。$ ループ演算子は、失敗が返されるまで宣言を繰り返し呼び出します。$ 演算子は、宣言が 0 の場合でも常に成功します。上記のプログラムは常に成功を返します。(CWIC では、長い失敗は宣言をバイパスできます。長い失敗は CWIC のバックトラッキングシステムの一部です)

これらの初期のコンパイラの文字セットは限られていました。文字/ は交互 (または) 演算子に使用されました。「A または B」は A / B と記述されます。括弧 ( ) はグループ化に使用されます。

A (B / C)

Aの後にBまたはCが続く構造を記述します。ブール式としては、

Aおよび(BまたはC)

シーケンス XY には暗黙の XとY の意味があります。( ) はグループ化であり、/ はor演算子です。入力文字シーケンスはテストの順序によって指定されるため、評価の順序は常に左から右になります。

最初の文字が「.」である特殊な演算子語は、明確にするために使用されます。 .EMPTY は、前の代替が存在する必要がない場合に最後の代替として使用されます。

X (A / B / .空)

X の後にオプションで AまたはBが続くことを示します。これは、プログラミング言語であるこれらのメタ言語の固有の特性です。上記により、バックトラックは回避されます。他のコンパイラコンストラクターシステムでは、3 つの可能なシーケンスを宣言し、それをパーサーに判断させる場合があります。

上記のメタプログラミングメタ言語の特性は、すべての Schorre メタコンパイラとそれらから派生したメタコンパイラに共通です。

メタI

META I は、META II をコンパイルするために使用された、手動でコンパイルされたメタコンパイラです。META II の最初のコンパイルで、手動でコーディングされた META I コンパイラとほぼ同じコードが生成されたということ以外、META I についてはほとんどわかっていません。

メタII

各ルールは、オプションでテスト、演算子、および出力生成物で構成されます。ルールは、入力プログラムソース文字ストリームの一部を一致させようとし、成功または失敗を返します。成功した場合、入力は一致した文字に進みます。失敗した場合、入力は進みません。

出力生成物は、構文規則から直接アセンブリコードの形式を生成しました。

ツリーメタ

TREE-META では、ツリー構築演算子< node_name >および[ < number > ]が導入され、出力生成変換が未解析ルールに移動します。ツリー構築演算子は、入力を抽象構文木に直接変換する文法規則で使用されました。未解析ルールは、ツリーパターンに一致するテスト関数でもあります。未解析ルールは、抽象構文木を出力コードに変換するときに文法規則から呼び出されます。抽象構文木と未解析ルールの構築により、解析木を分析してローカル最適化を実行できるようになりました。

出力生成を非解析ルールに移動することで、文法解析とコード生成が明確に分離されました。これにより、プログラミングが読みやすく、理解しやすくなりました。

ＣＷＩＣ

1968年から1970年にかけて、アーウィン・ブック、デューイ・ヴァル・ショア、スティーブン・J・シャーマンは、システム開発会社チャールズ・バベッジ研究所情報技術史センター（ボックス12、フォルダ21）でCWIC（コンパイラの作成と実装のためのコンパイラ）[4 ^]を開発しました。

CWIC は、3 つの専用ドメイン固有言語で構成されるコンパイラ開発システムです。各言語は、翻訳の特定の側面をわかりやすく記述できるように設計されています。構文言語は、ソーステキストの認識と、そこから中間ツリー構造を構築することを記述するために使用されます。ジェネレータ言語は、ツリーを適切なオブジェクト言語に変換することを記述するために使用されます。

構文言語は、Dewey Val Schorre の以前のメタコンパイラのラインを踏襲しています。構文言語にツリー構築演算子を持つ TREE-META に最も似ています。TREE-META の解析解除ルールは、 LISP 2に基づくオブジェクトベースのジェネレータ言語で動作するように拡張されています。

CWIC には 3 つの言語が含まれます。

構文: 文法変換式を使用して、ソースプログラム入力をリスト構造に変換します。解析された式構造は、規則内にジェネレータ呼び出しを配置することでジェネレータに渡されます。ツリーは、最初の要素がノードオブジェクトであるリストで表されます。言語には、リストを作成するための演算子<および>があります。コロン:演算子は、ノードオブジェクトを作成するために使用されます。:ADD はADD ノードを作成します。感嘆符!演算子は、解析されたエントリの数とノードを組み合わせてツリーを作成します。構文規則によって作成されたツリーはジェネレータ関数に渡され、成功または失敗を返します。構文言語は TREE-META に非常に似ています。どちらもコロンを使用してノードを作成します。CWIC のツリー構築感嘆符 !<number> は、TREE-META の [<number>] と同じように機能します。
ジェネレータ: それぞれが解析されていないパターンマッチングルールとLISP 2のような言語で書かれた出力生成物からなる一連の変換ルールの名前付きシリーズ。変換はIBM 360バイナリマシンコードに行われました。ジェネレータ言語の他の機能は出力を一般化しました。^[4]
MOL-360 :1968 年に開発され、基盤となるサポートライブラリの作成に使用された、IBM System/360 ファミリーのコンピュータ用の独立した中間レベルの実装言語。

ジェネレータ言語

ジェネレータ言語はLispに似たセマンティクスを持っています。解析ツリーは再帰リストとして考えられています。ジェネレータ言語関数の一般的な形式は次のとおりです。

  関数名(first-unparse_rule) => first-production_code_generator
           (2 番目の unparse_rule) => 2 番目の production_code_generator
           (3 番目の未解析ルール) => 3 番目の製品コードジェネレーター
               ...

与えられたツリーを処理するコードには、汎用プログラミング言語の機能に加えて、出力ファイルに (stuff) を出力するフォーム <stuff> が含まれています。unparse_rule では、ジェネレータ呼び出しを使用できます。ジェネレータには、それが配置されている unparse_rule パターンの要素が渡され、その戻り値は () にリストされます。例:

  expr_gen(ADD[expr_gen(x),expr_gen(y)]) =>
                                <AR + (x*16)+y;>
                                releasereg(y);
                                x を返します。
               (SUB[expr_gen(x),expr_gen(y)])=>
                                <SR + (x*16)+y;>
                                releasereg(y);
                                x を返します。
               (MUL[expr_gen(x),expr_gen(y)])=>
                              。
                              。
                              。
               r1 を getreg() で置き換える。
                            ロード(r1, x);
                            r1 を返します。
...

つまり、解析ツリーが(ADD[<something1>,<something2>]) のように見える場合、expr_gen(x) は <something1> で呼び出され、x を返します。解析解除ルール内の変数は、production_code_generator で使用できるローカル変数です。expr_gen(y) は <something2> で呼び出され、y を返します。ここでは、解析解除ルール内のジェネレータ呼び出しに、その位置の要素が渡されます。上記の x と y は、戻り時にレジスタになるはずです。最後の変換は、アトミックをレジスタにロードして、レジスタを返すことを目的としています。最初のプロダクションは、汎用レジスタに適切な値を持つ 360 "AR" (Add Register) 命令を生成するために使用されます。上記の例は、ジェネレータの一部にすぎません。すべてのジェネレータ式は、さらに処理できる値に評価されます。最後の変換は、次のように記述することもできます。

               (x)=> getreg(), x をロードして返します。

この場合、load は最初のパラメータ、つまり getreg() によって返されたレジスタを返します。関数 load と getreg は他の CWIC ジェネレータです。

CWICが取り上げられるドメイン固有言語用語の前にドメイン固有言語存在した

CWIC の著者より:

「メタコンパイラは、コンパイラが翻訳する言語に関係なく同じである非創造的な側面を自動化することで、コンパイラ構築のタスクを支援します。これにより、特定の問題の仕様に適した言語の設計が可能になります。メタコンパイラは、そのような言語用のプロセッサを作成するコストを削減し、問題の解決を言語設計から始めることが経済的に実現可能になります。」^[4]

例

ANTLR
GNUバイソン
ココ/R、ココ-2 ^[22]
DMSソフトウェアリエンジニアリングツールキット、パーサージェネレータを備えたプログラム変換システム
イプシロン文法スタジオ
レモンパーサージェネレーター
LRSTAR: LR(*) パーサージェネレーター
メタII
parboiled、パーサーを構築するための Java ライブラリ。
パックラットパーサー
PQCC は、パーサージェネレーター以上の機能を備えたコンパイラーです。
構文改善装置 (SID)
SYNTAX は、コンパイラ構築用の統合ツールセットです。
ツリーメタ
ヤック
Xテキスト
エクセル
JavaCC

参照

参考文献と注記

^ コンパイラ：原理、テクニック、ツール。Alfred V. Aho、Monica S. Lam、Ravi Sethi、Jeffrey D. Ullman、Alfred V. Aho（第2版）。ボストン。2007年。287ページ。ISBN 978-0-321-48681-3. OCLC 70775643.{{cite book}}: CS1 メンテナンス: 場所が不明な発行元 (リンク) CS1 メンテナンス: その他 (リンク)
^ 「ALGOL 60 用の構文指向コンパイラ」Edgar T. Irons、Communications of the ACM Volume 4 Issue 1、1961 年 1 月。
^ ab メタコンパイラ: (コンピュータサイエンス) 主に他のプログラミング言語のコンパイラを構築するために使われるコンパイラ。「Sci-Tech Dictionary McGraw-Hill Dictionary of Scientific and Technical Terms, 6th edition」。McGraw-Hill Companies。2018年4月7日時点のオリジナルよりアーカイブ。 2018年4月7日閲覧。
^ abcdefgh Book、Erwin、Dewey Val Schorre、Steven J. Sherman (1970 年 6 月)。「CWIC/36O システム、コンパイラの作成と実装のためのコンパイラ」。ACM SIGPLAN Notices。5 ( 6): 11–29。doi :10.1145/954344.954345。S2CID 44675240 。
^ ab C. Stephen Carr、David A. Luther、Sherian Erdmann、「TREE-META コンパイラ - コンパイラシステム: Univac 1108 および General Electric 645 用のメタコンパイラシステム」、ユタ大学技術レポート RADC-TR-69-83。
^ Peter Mosses、「SIS: 表示的意味論を使用するコンパイラ生成システム」、レポート 78-4-3、デンマーク、オーフス大学コンピュータサイエンス学部、1978 年 6 月
^ Neighbors、JM コンポーネントを使用したソフトウェア構築 Archived 2018-03-18 at the Wayback Machine . 技術レポート 160、情報・コンピュータ科学部、カリフォルニア大学アーバイン校、1980 年。
^ Lavington, Simon (2016 年 4 月). 「Tony Brooker と Atlas Compiler Compiler」(PDF)。2023 年 3 月 26 日時点のオリジナルよりアーカイブ(PDF) 。2023 年 9 月 29 日閲覧。
^ ハワード・メトカーフ、「機械言語学に基づくパラメータ化コンパイラ」、Planning Research Corporation R-311、1963 年 3 月 1 日、また Annual Review in Automatic Programming、第 4 巻にも掲載
^ Robert Ledley および JB Wilson、「自動プログラミング、構文解析による言語翻訳」、Communications of the Association for Computing Machinery、第 5 巻、第 3 号、pp. 145–155、1962 年 3 月。
^ AE Glennie、「構文マシンと汎用コンピュータの構築について」、技術レポート第2号、AD 240–512、カーネギー工科大学計算センター、1960年。
^ Schorre, DV、「META II 構文指向コンパイラ記述言語」、1964 年第 19 回 ACM 全国会議の議事録、pp. 41.301-41.3011、1964 年
^ Dewey, Val Schorre (1963)。「1401 用の構文 - 指示された SMALGOL」。ACM全国会議、コロラド州デンバー。
^ Meta I については、1963 年の Colorado ACM カンファレンスで発表された論文で説明されています。SMALGOL を参照してください。
^ LO Schmidt、「The Status Bitt ACM SegPlan「プログラミング言語に関する特別興味グループ」ワーキンググループ 1 ニュースレター」、1964 年。
^ Roger Rutman、「LOGIK. コンピュータビット時間シミュレーション用の構文指向コンパイラ」、修士論文、UCLA、1964 年 8 月。
^ FW Schneider および (GD Johnson、「構文指向コンパイラ記述、効率的なコードを生成するコンパイラ」、第 19 回全国計算機学会会議議事録、1964 年
^ D. Oppenheim および D. Haggerty、「META 5: データ文字列を操作するツール」、第 21 回 National Conference of the Association for Computing Machinery の議事録、1966 年。
^ Knuth, Donald (1990). 「属性文法の起源」(PDF)。P. Deransart、M. Jourdan (編)。属性文法とその応用に関する国際会議の議事録 (パリ、フランス)。属性文法とその応用に関する国際会議。コンピュータサイエンスの講義ノート。第 461 巻。ニューヨーク: Springer-Verlag。 pp. 1–12。CiteSeerX 10.1.1.105.5365。doi :10.1007/3-540-53101-7_1。ISBN 978-3-540-53101-2. 2020年11月23日時点のオリジナルよりアーカイブ(PDF) 。2020年2月6日閲覧。
^ Charles R. Kirkley および Johns F. Rulifson、「The LOT System of Syntax Directed Compiling」、スタンフォード研究所内部レポート ISR 187531-139、1966 年。
^ George JE (1967a). 構文解析器、認識器、パーサーおよび意味解釈システム、スタンフォード線形加速器センター、1967 年 11 月 15 日。
^ ab Rechenberg、Peter [ドイツ語] ;メッセンベック、ハンスペーター[ドイツ語] (1985)。マイクロコンピュータ用コンパイラジェネレータ - グルンドラーゲン、アンウェンドゥンゲン、Modula-2 のプログラムミエルング(ドイツ語) (第 1 版)。ミュンヘン、ドイツ:カール・ハンザー・フェルラーク。ISBN 3-446-14495-1。(注: この本では、Modula-2での Coco の構築について説明しています。)
^ Gray, Robert W.; Levi, Steven P.; Heuring, Vincent P.; Sloane, Anthony M.; Waite, William M. (1992). 「Eli: 完全で柔軟なコンパイラ構築システム」Communications of the ACM . 35 (2): 121–130. doi : 10.1145/129630.129637 . S2CID 5121773.
^ Foster, JM (1968). 「構文改善プログラム」.コンピュータジャーナル. 11 : 31–34. doi : 10.1093/comjnl/11.1.31 .

さらに読む

Brooker, RA ; MacCallum, IR; Morris, D.; Rohl, JS (1963). 「コンパイラコンパイラ」(PDF) . Annual Review in Automatic Programming . 3 : 229–275. doi :10.1016/S0066-4138(63)80009-9.
Brooker, R .A. ; Morris, D.; Rohl , JS (1967 年 2 月)。「コンパイラコンパイラの経験」(PDF)。Computer Journal。9 : 350。doi : 10.1093/comjnl/9.4.350 。2021年 5 月 7 日に閲覧。
Napper, RB E (1965 年 12 月)。コンパイラ入門(PDF)。
MacCallum, IR (1963 年 1 月)。ATLAS 上のコンパイラコンパイラの実装のいくつかの側面(PDF) (論文)。
Johnson, Stephen C. (1975 年 7 月)。Yacc - もう一つのコンパイラ - コンパイラ。米国ニュージャージー州マレーヒル:ベル研究所。コンピュータサイエンス技術レポート 32。
McKeeman, William M.; Horning, James J .; Wortman, David B. (1970). A Compiler Generator . Englewood Cliffs, New Jersey, USA: Prentice-Hall . ISBN 978-0-13-155077-3. 2012年12月13日閲覧。

外部リンク

トニー・ブルッカーとアトラスコンパイラ
コンパイラの説明コンパイラリスト (1963)
コンパイラコンパイラのソースコード (PDF の 182 ページあたりから)
オリジナルコンパイラコンパイラフローチャート
Computer50.org、Brooker Autocodes
Catalog.compilertools.net 2011-08-13 にWayback Machineでアーカイブされました。コンパイラ構築ツールのカタログ
Labraj.uni-mb.si、リサ
Skenz.it、Jflex、Cup のリソース(イタリア語)

[1] コンパイラ：原理、テクニック、ツール。Alfred V. Aho、Monica S. Lam、Ravi Sethi、Jeffrey D. Ullman、Alfred V. Aho（第2版）。ボストン。2007年。287ページ。ISBN 978-0-321-48681-3. OCLC 70775643.{{cite book}}: CS1 メンテナンス: 場所が不明な発行元 (リンク) CS1 メンテナンス: その他 (リンク)

[name-2] 「ALGOL 60 用の構文指向コンパイラ」Edgar T. Irons、Communications of the ACM Volume 4 Issue 1、1961 年 1 月。

[McGraw-3] メタコンパイラ: (コンピュータサイエンス) 主に他のプログラミング言語のコンパイラを構築するために使われるコンパイラ。「Sci-Tech Dictionary McGraw-Hill Dictionary of Scientific and Technical Terms, 6th edition」。McGraw-Hill Companies。2018年4月7日時点のオリジナルよりアーカイブ。 2018年4月7日閲覧。

[CWIC-4] Book、Erwin、Dewey Val Schorre、Steven J. Sherman (1970 年 6 月)。「CWIC/36O システム、コンパイラの作成と実装のためのコンパイラ」。ACM SIGPLAN Notices。5 ( 6): 11–29。doi :10.1145/954344.954345。S2CID 44675240 。

[TMETA-5] C. Stephen Carr、David A. Luther、Sherian Erdmann、「TREE-META コンパイラ - コンパイラシステム: Univac 1108 および General Electric 645 用のメタコンパイラシステム」、ユタ大学技術レポート RADC-TR-69-83。

[6] Peter Mosses、「SIS: 表示的意味論を使用するコンパイラ生成システム」、レポート 78-4-3、デンマーク、オーフス大学コンピュータサイエンス学部、1978 年 6 月

[bayfront-7] Neighbors、JM コンポーネントを使用したソフトウェア構築 Archived 2018-03-18 at the Wayback Machine . 技術レポート 160、情報・コンピュータ科学部、カリフォルニア大学アーバイン校、1980 年。

[8] Lavington, Simon (2016 年 4 月). 「Tony Brooker と Atlas Compiler Compiler」(PDF)。2023 年 3 月 26 日時点のオリジナルよりアーカイブ(PDF) 。2023 年 9 月 29 日閲覧。

[Metcalfe1-9] ハワード・メトカーフ、「機械言語学に基づくパラメータ化コンパイラ」、Planning Research Corporation R-311、1963 年 3 月 1 日、また Annual Review in Automatic Programming、第 4 巻にも掲載

[Ledleyl-10] Robert Ledley および JB Wilson、「自動プログラミング、構文解析による言語翻訳」、Communications of the Association for Computing Machinery、第 5 巻、第 3 号、pp. 145–155、1962 年 3 月。

[Glenniel-11] AE Glennie、「構文マシンと汎用コンピュータの構築について」、技術レポート第2号、AD 240–512、カーネギー工科大学計算センター、1960年。

[METAII-12] Schorre, DV、「META II 構文指向コンパイラ記述言語」、1964 年第 19 回 ACM 全国会議の議事録、pp. 41.301-41.3011、1964 年

[SMALGOL-13] Dewey, Val Schorre (1963)。「1401 用の構文 - 指示された SMALGOL」。ACM全国会議、コロラド州デンバー。

[META1-14] Meta I については、1963 年の Colorado ACM カンファレンスで発表された論文で説明されています。SMALGOL を参照してください。

[Schmidt1-15] LO Schmidt、「The Status Bitt ACM SegPlan「プログラミング言語に関する特別興味グループ」ワーキンググループ 1 ニュースレター」、1964 年。

[Rutman1-16] Roger Rutman、「LOGIK. コンピュータビット時間シミュレーション用の構文指向コンパイラ」、修士論文、UCLA、1964 年 8 月。

[Schneiderl-17] FW Schneider および (GD Johnson、「構文指向コンパイラ記述、効率的なコードを生成するコンパイラ」、第 19 回全国計算機学会会議議事録、1964 年

[Oppenheim-18] D. Oppenheim および D. Haggerty、「META 5: データ文字列を操作するツール」、第 21 回 National Conference of the Association for Computing Machinery の議事録、1966 年。

[19] Knuth, Donald (1990). 「属性文法の起源」(PDF)。P. Deransart、M. Jourdan (編)。属性文法とその応用に関する国際会議の議事録 (パリ、フランス)。属性文法とその応用に関する国際会議。コンピュータサイエンスの講義ノート。第 461 巻。ニューヨーク: Springer-Verlag。 pp. 1–12。CiteSeerX 10.1.1.105.5365。doi :10.1007/3-540-53101-7_1。ISBN 978-3-540-53101-2. 2020年11月23日時点のオリジナルよりアーカイブ(PDF) 。2020年2月6日閲覧。

[Kirkleyl-20] Charles R. Kirkley および Johns F. Rulifson、「The LOT System of Syntax Directed Compiling」、スタンフォード研究所内部レポート ISR 187531-139、1966 年。

[George-21] George JE (1967a). 構文解析器、認識器、パーサーおよび意味解釈システム、スタンフォード線形加速器センター、1967 年 11 月 15 日。

[Rechenberg-Mössenböck_1985-22] Rechenberg、Peter [ドイツ語] ;メッセンベック、ハンスペーター[ドイツ語] (1985)。マイクロコンピュータ用コンパイラジェネレータ - グルンドラーゲン、アンウェンドゥンゲン、Modula-2 のプログラムミエルング(ドイツ語) (第 1 版)。ミュンヘン、ドイツ:カール・ハンザー・フェルラーク。ISBN 3-446-14495-1。(注: この本では、Modula-2での Coco の構築について説明しています。)

[23] Gray, Robert W.; Levi, Steven P.; Heuring, Vincent P.; Sloane, Anthony M.; Waite, William M. (1992). 「Eli: 完全で柔軟なコンパイラ構築システム」Communications of the ACM . 35 (2): 121–130. doi : 10.1145/129630.129637 . S2CID 5121773.

[24] Foster, JM (1968). 「構文改善プログラム」.コンピュータジャーナル. 11 : 31–34. doi : 10.1093/comjnl/11.1.31 .