ツリーメタ

TREE -META（またはTree Meta、TREEMETA）翻訳記述システムは、1960年代に開発された文脈自由言語用のコンパイラ・コンパイラシステムです。メタ言語の構文解析ステートメントは、ツリー構築ディレクティブが埋め込まれた拡張バッカス・ナウア形式に似ています。構文解析解除^[1]ルールには、広範なツリースキャンとコード生成構造が含まれます。

TREE-METAはNLS （oN-Line System）の開発に役立ち、 UNIVAC 1108、GE 645、SDS 940、ICL 1906A、PERQ、UCSD p-Systemなど多くのシステムに移植されました。^{[2] [3]}

これは、ICL 1900 TREE-META マニュアルの付録 6 にある、より完全な例 (宣言、条件、ブロック) から抽出された (テストされていない) TREE-META プログラムの完全な例です。^[4]このドキュメントの付録 3 の TREE-META にも TREE-META の定義があります。このプログラムは単なる認識プログラムではなく、入力に対するアセンブリ言語を出力します。これは、TREE-META の重要な機能の 1 つであるツリー パターン マッチングを示しています。これは、LHS (たとえば、GET と VAL) と RHS (ADD と SUB) の両方で使用されます。

% これは%で区切られたALGOLスタイルのコメントです

% ======================= 入力解析ルール ======================== %

.メタプログラム
% 運転ルールを定義するプログラムが必要です。 %
% この PROG ルールは完全なプログラムのドライバーです。 %

PROG = $STMT;
% $ は 0 個以上の演算子です。 %
% PROG (プログラム) は、0 個以上の STMT (ステートメント) として定義されます。 %

STMT = .ID ':=' AEXP :STORE[2]*;
% ソースからツリーへの代入文を解析します。 %
% ':=' は文字列定数、:STORE は STORE ノードを作成します、%
% [2]では、これをSTORE[ID,AEXP]という2つのブランチを持つものとして定義しています。 %
% * はツリーの解析をトリガーします。最後に作成された % から始まります。
% ツリー、つまり出力として発行される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] => 'I ' *1 /
   [MINUSS[.NUM]] => 'N ' *1:*1 ;

MINUSS[-] => GET[*1] 'NEGATE' ;

。終わり

• NLS（コンピュータシステム）
• メタII

• C. Stephen Carr、David A. Luther、Sherian Erdmann、「TREE-META コンパイラ - コンパイラ システム: Univac 1108 および General Electric 645 用のメタ コンパイラ システム」^{[リンク切れ]}、ユタ大学技術レポート RADC-TR-69-83。
• [1] ^{[リンク切れ]}、また [2] 1968年のEnglebart、English、Rulifsonによる技術レポート。NLSにおける、現在ではドメイン固有言語(DSL)と呼ばれている特殊目的言語(SPL)でのTree Metaの使用に関するものです。
• Donald I. Andrews、JF Rulifson (1967)。Tree Meta (ワーキング ドラフト): SDS 940 のメタ コンパイラ、スタンフォード研究所、カリフォルニア州メンロ パーク。Engelbart コレクション、スタンフォード大学アーカイブ、M 638、ボックス 16、フォルダー 3。
• ANDREWS、LEHTMAN、W​​HP。「Tree Meta – Augmentation Research Center 用のメタコンパイラ」。予備草稿、1971 年 3 月 25 日。
• Alan C. Kay、The Reactive Engine、博士論文、1969年、ユタ大学。Henri Gouraud が SRI (Engelbart) SDS-940 上の TREE-META で FLEX コンパイラを作成したことを記しています。
• Atlas Computer Laboratory 四半期レポート (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 月。

• FRA Hopgood による TREE-META の ICL 1900 バージョンのマニュアル。
• TREE-METAに関する情報収集ホームページ
• TREE META ドラフト文書 1967 年 12 月、bitsavers.org にて
• TREE META リリース ドキュメント (1968 年 4 月)、bitsavers.org
• DC エンゲルバートによる人間の知能拡張技術の開発に関する研究
• C での TREE-META の実装 (ICL 1900 用の TREE-META バージョンに基づく) ^{[リンク切れ]}
• TREE-META コンパイラ コンパイラの復活。