メタII

META II は、コンパイラを作成するためのドメイン固有のプログラミング言語です。1963 年から 1964 年にかけて、 UCLAの Dewey Val Schorre によって作成されました。META II は、Schorre が構文方程式と呼んだものを使用します。その動作は次のように簡単に説明できます。

各構文方程式は再帰サブルーチンに変換され、入力文字列に特定のフレーズ構造があるかどうかがテストされ、見つかった場合は削除されます。^[1]

Meta IIプログラムは、インタープリタ型バイトコード言語にコンパイルされます。その機能を示すVALGOLおよびSMALGOLコンパイラはMETA II言語で記述されました。 ^[1]^[2] VALGOLはMETA IIを説明する目的で設計された単純な代数言語です。SMALGOLはALGOL 60のかなり大きなサブセットでした。

表記

META IIは最初META I ^[3]で書かれました。これはMETA IIを手動でコンパイルしたバージョンです。META IがMETA IIの完全な実装であったのか、それとも完全なMETA IIコンパイラをコンパイルするために必要なMETA II言語の必須のサブセットであったのかは歴史がはっきりしていません。

META II のドキュメントでは、BNFに似ていると説明されています。 BNF は現在では生成文法として説明されています。 META II は分析文法です。TREE-METAドキュメントでは、これらの言語は簡約文法として説明されていました。

たとえば、BNF では算術式は次のように定義されます。

<式>  := <項> | <式>  <加法>  <項>

BNF ルールは、今日では、構成要素を組み立てて有効な言語構造のみを形成する方法を記述する生成ルールです。パーサーは、言語構造を分解する逆の処理を行います。META II は、出力ディレクティブを含むスタックベースの機能パーサープログラミング言語です。META II では、テストの順序は式で指定されます。META II は、他のプログラミング言語と同様に、左再帰を試みるとスタックがオーバーフローします。META II は、$ (0 個以上) シーケンス演算子を使用します。META II で記述された expr 解析式は、左から右に評価される条件式です。

expr =  term 
       $ (  '+'  term . OUT (' ADD ') 
        /  '-'  term . OUT (' SUB '));

上記の expr 方程式は、'=' の右側の式によって定義されます。'=' から左から右に評価すると、term が最初にテストされる必要があります。term が失敗を返す場合、expr は失敗します。成功した場合、用語が認識され、次に不定 $ ゼロ以上のループに入ります。ここで最初に '+' をテストし、それが失敗した場合は代替の '-' が試行され、最後に '-' が認識されなかった場合、ループは終了し、expr は 1 つの用語を認識して成功を返します。'+' または '-' が成功した場合は、term が呼び出されます。成功した場合は、ループが繰り返されます。expr 方程式は、ネストされたグループ化を使用して次のように表現することもできます。

式= 用語$ (( '+'  /  '-' ) 用語);

コード生成要素は、例を簡略化するために省略されています。初期のコンピュータの文字セットは限られていたため、文字は/代替の or 演算子として使用されていました。$ループ演算子は、0 個以上の何かに一致するために使用されます。

expr =  term $ (   '+'  term . OUT (' ADD ') 
              /  '-'  term . OUT (' SUB ')  
             );

上記は英語で次のように表現できます。expr は、0 個以上の (プラス項またはマイナス項) が続く項です。Schorre はこれを効率化の助けとなると説明していますが、単純な再帰降下コンパイラとは異なり、算術演算の結合性が正しいことも保証します。

expr =  term $ ( '+'  term . OUT (' ADD ')  
             /  '-'  term . OUT (' SUB ') 
             ); 
term =  factor $ (  '*'  factor . OUT (' MPY ') 
               /  '/'  factor . OUT (' DIV ') 
               ); 
factor =  (  . ID 
         /  . NUMBER 
         /  '('  expr ')') 
         (  '^'  factor . OUT (' EXP ') 
         /  . EMPTY );

ループまたは右（「末尾」）再帰を使用してシーケンスを表現できるため、評価の順序を制御できます。

構文規則は宣言的に見えますが、実際には意味仕様によって命令的になります。

手術

META II はスタックマシンのアセンブリコードを出力します。これを評価するのはRPN計算機を使用するようなものです。

expr =  term 
       $ ( '+'  term . OUT (' ADD ') 
        /'-'  term . OUT (' SUB ')); 
term =  factor 
       $ ( '*'  factor . OUT (' MPY ') 
       /  '/'  factor . OUT (' DIV ')); 
factor =  ( . ID . OUT (' LD   '  *)  
         /  . NUM . OUT (' LDL '  *) 
         /  '('  expr ')')  
         (  '^'  factor . OUT (' XPN '/. EMPTY );

上記の .ID と .NUM は組み込みのトークン認識子です。.OUT コード生成の * は、最後に認識されたトークンを参照します。.NUM で数値を認識すると、.OUT('LDL' *) は数値に続くロードリテラル命令を出力します。式:

(3*a^2+5)/b

生成されます:

      LDL 3 LD a LDL 2 XPN MPY LDL 5 ADD LD b DIV

META IIは、仮想マシンの最も初期のインスタンスの1つであるマシンコードにコンパイルされるため、メタコンパイラの最初の文書化されたバージョンです^{[注 1]}。

この論文自体は素晴らしい逸品で、Meta II 自体のブートストラップを含む数多くの優れた例が含まれています (これはすべて 8K (6 ビットバイト) の 1401 で実行されました!)。」—Alan Kay

オリジナルの論文は無料では入手できませんが、Doctor Dobb's Journal (1980 年 4 月) に再掲載されました。転写されたソースコードは、さまざまな時期に公開されています (おそらく CP/M ユーザーグループによる)。論文には Meta II の説明のリストが含まれていましたが、これを手動で処理して、仮想マシンオペコードで解釈可能なプログラムを生成することは原理的に可能です。これを実行して同一の出力が生成されれば、実装は正しいことになります。

META II は基本的に概念実証であり、作業の基盤となるものです。

META IIは標準言語としてではなく、ユーザーが独自のMETA「言語」を開発するための出発点として提示されています。^[1]

その後、多くの META「言語」が生まれました。Schorre はSystem Development Corporationに就職し、そこで Compiler for Writing and Implementing Compilers (CWIC) プロジェクトのメンバーになりました。CWIC の SYNTAX 言語は META II をベースに構築され、バックトラック代替演算子、正と負の先読み演算子、プログラムされたトークン方程式が追加されました。.OUTおよび.LABEL操作は削除され、スタック変換操作:<node>と追加されました。LISP 2!<number> に基づく GENERATOR 言語は、SYNTAX 構文解析言語によって生成されたツリーを処理しました。コードを生成するために、ジェネレータ関数への呼び出しが SYNTAX 方程式に配置されました。これらの言語は、構文指向コンパイラに関する LA ACM SIGPLAN サブグループのメンバーによって開発されました。Schorre が META II 言語をどのように考えていたかは注目に値します。

大文字のMETAを含むMETA「言語」という用語は、このようにして開発されたコンパイラ記述言語を表すために使用されます。^[1]

Schorre 氏は、META II を他の META「言語」を開発するための基盤として説明しています。

参照

注記

^ META II ドキュメントで簡単に言及されているだけの META I は無視します。

参考文献

^ abcd META II 構文指向コンパイラ記述言語 (Dewey Val Schorre UCLA コンピューティング施設 1964)
^ Dewey, Val Schorre (1963)。「1401 用の構文指向 SMALGOL」。ACM Natl. Conf.、コロラド州デンバー。
^ Dewey, Val Schorre (1963). META II: 構文指向コンパイラ記述言語(PDF) . UCLA: UCLA コンピューティング施設.

外部リンク

ACM - META II に関する論文
チュートリアル: メタコンパイラパート 1
Meta II メタコンパイラ

[META1-4] META II ドキュメントで簡単に言及されているだけの META I は無視します。

[METAII-1] META II 構文指向コンパイラ記述言語 (Dewey Val Schorre UCLA コンピューティング施設 1964)

[SMALGOL-2] Dewey, Val Schorre (1963)。「1401 用の構文指向 SMALGOL」。ACM Natl. Conf.、コロラド州デンバー。

[Schorre-3] Dewey, Val Schorre (1963). META II: 構文指向コンパイラ記述言語(PDF) . UCLA: UCLA コンピューティング施設.