ツリーメタ
| ツリーメタ | |
|---|---|
| 原作者 | ドナルド・アンドリュース、 ジェフ・ルリフソン |
| 初回リリース | 1968年 |
| プラットフォーム | UNIVAC 1108、GE 645、SDS 940、ICL 1906A、PERQ、UCSD p-システム |
| タイプ | コンパイラ-コンパイラ |
TREE -META（またはTree Meta、TREEMETA）翻訳記述システムは、文脈自由言語用のコンパイラ・コンパイラシステムであり、1960年代に開発されました。メタ言語の構文解析文は、木構築指示が埋め込まれた拡張バッカス・ナウア記法に似ています。逆構文解析[1]規則には、広範な木スキャンとコード生成構造が含まれています。
歴史
TREE-METAはNLS（オンラインシステム）の開発に役立ち、 UNIVAC 1108、GE 645、SDS 940、ICL 1906A、PERQ、UCSD p-Systemなど多くのシステムに移植されました。[2] [3]
例
これは、ICL 1900 TREE-METAマニュアル[4]の付録6に掲載されている、より完全な例（宣言、条件文、ブロックを含む）から抜粋した（テストは行われていない）TREE-METAプログラムの完全な例です。このマニュアルの付録3には、TREE-METAの定義も記載されています。このプログラムは認識プログラムであるだけでなく、入力に対応するアセンブリ言語の出力も行います。TREE-METAの主要機能の一つであるツリーパターンマッチングを実証しています。これは、LHS（例えばGETとVAL）とRHS（ADDとSUB）の両方で使用されます。
% これは% で区切られたALGOLスタイルのコメントです
% ======================= 入力解析規則 ======================== %.メタプログラム % 運転ルールを定義するプログラムが必要です。 %% この PROG ルールは完全なプログラムのドライバーです。 %PROG = $STMT;% $ は 0 個以上の演算子です。 %% PROG (プログラム) は、0 個以上の STMT (ステートメント) として定義されます。 %STMT = .ID ':=' AEXP :STORE[2]*;% ソースからツリーへの代入ステートメントを解析します。 %% ':=' は文字列定数、:STORE は STORE ノードを作成します、%% [2]はこれを2つのブランチ、すなわちSTORE[ID,AEXP]を持つものとして定義しています。%% * はツリーの逆解析をトリガーします。最後に作成された % から始まります。% ツリー、つまり出力として発行されるSTORE[ID,AEXP]と%% がツリーから削除されました。%AEXP = FACTOR $('+' FACTOR :ADD[2] / '-' FACTOR :SUB[2]);% ここでは算術演算 '+' :ADD と '-' :SUB の認識器があります %% ツリー構築。ここでも [2] は2分岐の ADD または SUB ツリーを作成します。%% 文全体が解析されるまで、解析解除は延期されます。 %% ADD[FACTOR,FACTOR] または SUB[FACTOR,FACTOR] %係数 = '-' PRIME :MINUSS[1] / PRIME ;PRIME = .ID / .NUM / '(' AEXP ')' ?3? ;% ?3? はエラーメッセージのヒントです。 % % ====================== 出力未解析ルール ======================= %STORE[-,-] => GET[*2] 'STORE ' *1 ;% *1は左のツリーブランチです。 *2は右の%です。% GET[*2]は*2をロードするコードを生成します。 %% 'STORE'文字列が出力されます %% の後に左分岐 *1 記号 %% 何であれ*2、GET[*2]によってロードされます。%GET[.ID] => 'LOAD ' *1 / [.NUM] => 'LOADI' *1 / [MINUSS[.NUM]] => 'LOADN ' *1:*1 / [-] => *1 ;% ここでは.IDまたは.NUMが単純にロードされます。MINUSSノード%.NUMを含む%はこれを使用します。*1:*1という表記は%を意味します。% 最初の分岐 (MINUSS) の最初の分岐 (a .NUM)。 %% その他はノード認識のために渡されます %% 解析解除ルールはツリーを分解してコードを出力します。 %ADD[-,-] => SIMP[*2] GET[*1] 'ADD' VAL[*2] / SIMP[*1] GET[*2] 'ADD' VAL[*1] / GET[*1] 'STORE T+' < OUT[A] ; A<-A+1 > / GET[*2] 'ADD T+' < A<-A-1 ; OUT[A] > ;% シェブロン < > は算術演算を示します。例: %% ベースアドレス T を基準としたオフセット A を生成します。 %SUB[-,-] => SIMP[*2] GET[*1] 'SUB' VAL[*2] / SIMP[*1] GET[*2] 'NEGATE' % 'ADD' VAL[*1] / GET[*2] 'STORE T+' < OUT[A] ; A<-A+1 > / GET[*1] 'SUB T+' < A<-A-1 ; OUT[A] > ;% 解析対象外ルール内のパーセント文字は改行を示します。 %SIMP[.ID] => .空 / [.NUM] => .EMPTY / [MINUSS[.NUM]] => .EMPTY;VAL[.ID] => ' ' *1 / [.NUM] => '私' *1 / [MINUSS[.NUM]] => 'N ' *1:*1 ;MINUSS[-] => GET[*1] 'NEGATE' ;。終わり参照
参考文献
- ^ Donald I. Andrews, JF Rulifson (1967). Tree Meta (Working Draft): A Meta Compiler for the SDS 940, Stanford Research Institute, Menlo Park, CA. Engelbart Collection, Stanford University Archive, M 638, Box 16, Folder 3.
- ^ボウルズ、KL、1978年 。「マイクロコンピュータおよびミニコンピュータ向けの（ほぼ）マシン非依存ソフトウェアシステム」SIGMINI Newsl.、4(1)、3–7。doi :10.1145/1041256.1041257
- ^ Bowles, KL (1978年5月). 「UCSD Pascal: マイクロコンピュータおよびミニコンピュータ向けの（ほぼ）マシン非依存ソフトウェアシステム」. Byte . 第3巻第5号. pp. 46, 170– 173 – インターネットアーカイブ経由.
- ^ Hopgood, FRA 1974、「TREE-META マニュアル」、Atlas Computer Laboratory。
- C. Stephen Carr、David A. Luther、Sherian Erdmann、「TREE-META コンパイラ - コンパイラ システム: Univac 1108 および General Electric 645 用のメタ コンパイラ システム」、ユタ大学技術レポート RADC-TR-69-83。
- Englebart, D. C.; English, W. K.; Rulifson, J. F. (1968年4月). マルチディスプレイ・タイムシェアリングコンピュータ施設の開発とコンピュータ支援管理システム研究(PDF) . カリフォルニア州メンロパーク：スタンフォード研究所.ニューヨーク州ニューヨーク市グリフィス空軍基地、ローマ航空開発センター向けに作成。代替ウェブサイトも用意。オンラインシステムにおける、当時特殊用途言語（SPL）と呼ばれていた言語（現在はドメイン特化言語（DSL））でのTree Metaの使用に関するレポート。
- Donald I. Andrews, JF Rulifson (1967). Tree Meta (Working Draft): A Meta Compiler for the SDS 940, スタンフォード研究所, メンロパーク, カリフォルニア州. エンゲルバート・コレクション, スタンフォード大学アーカイブ, M 638, Box 16, Folder 3.
- アンドリュース、レートマン、WHP. 「Tree Meta - オーグメンテーション・リサーチ・センター向けメタコンパイラ」。草稿、1971年3月25日。
- アラン・C・ケイ、リアクティブエンジン博士論文、1969年ユタ大学。SRI（エンゲルバート）SDS-940上のTREE-METAでFLEXコンパイラを開発したアンリ・ゴーローの記述あり。
- アトラス コンピュータ ラボラトリーの四半期レポート (1975 年 11 月 21 日) では、FRA Hopgood が TREE-META を使用して FR80 アセンブラ出力を生成するコンパイラを作成する作業を文書化しています。
- Atlas Computer Laboratory 四半期レポート (1973 年 10 月 12 日)、CJ Pavelin 文書 (セクション 4.10) TREE-META が1906Aに移植されています。
- TREE-META: Interdata Model 4用メタコンパイラ、WM Newman著。ロンドン、クイーン・メアリー・カレッジ。1972年11月。
外部リンク
