構文指向翻訳とは何を意味しますか？

Question

誰でも「構文指向翻訳」とは何かを簡単に説明できますか？私はドラゴンブックから話題を読み始めましたが、理解できませんでした。 Wiki articleも役に立たなかった。

Answer 1

「構文指向翻訳」は、構文認識プログラム（パーサー）を使用してコンパイル（翻訳）プロセス全体を駆動することを意味します。

概念的には、プログラムをコンパイルするプロセス（ソースコードからマシンコードに翻訳する）は、解析ツリーを生成するパーサで始まり、その解析ツリーを一連のツリー変換またはグラフ変換によって変換します。主に独立しているため、機械コードを生成するために横断される最終的な単純化されたツリーまたはグラフが得られる。

このビューは理にかなっていますが、それを直接実装しようとすると、ツリーまたはグラフ全体の少なくとも2つのコピーを保持するのに十分なメモリが必要になるという欠点があります。ドラゴンブックが書かれたとき（そしてこの理論の多くが解読されたとき）には、コンピュータの記憶はキロバイトで測定され、64Kは多くでした。だから大きなプログラムをコンパイルするのは難しいかもしれません。

構文変換を使用すると、パーサーが構文解析ツリーを認識する順序を中心に、すべてのグラフ変換が整理されます。パーサーは、完全な解析ツリーを生成するのではなく、小さなビットを作成し、コンパイラの次のパスにそれらのビットを送り、最終的に機械コードの小さな部分を生成してから、解析プロセスを続行して、木。パースツリー（または後続のグラフ）はいつでも少量しか存在しないため、メモリが大幅に少なくて済みます。シンタックスレコグナイザは、これをすべて制御する（シーケンシャルな順序を決める）マスターシーケンサであるため、シンタックスディレクテッドトランスレーションと呼ばれています。

メモリの使用を抑えるのに効果的な方法であるため、人々は簡単に行うために言語を再設計しました。理想的には、構文解析からプロセス全体を実行できる「シングルパス」コンパイラ1回のパスで機​​械コードの生成を行います。

今日、メモリはそれほどプレミアムではないため、すべてを強制的に1回にするというプレッシャーはありません。代わりに、一般的にフロントエンドだけで構文直接変換を使用し、構文解析、型チェックなどの意味チェック、パーサからの単純な変換、内部形式の生成（3つのアドレスコード、ツリー、または何らかの種類のダグ独立した個別の最適化とバックエンドパスを持つことができます。この場合であっても、これらの後のパスは少なくとも部分的に構文指示されていると主張するかもしれません。コンパイラは大量の入力（関数やモジュールなど）で動作し、次の入力。

yaccのようなツールは、構文指向翻訳のアイデアに基づいて設計されています - ツール（パーズツリーのフラグメント）が認識されるとコードのフラグメント（ツールの用語では「アクション」）実際のツリーを作成することはありません。これらのアクションは、コンパイラで論理的に後で渡されるものを直接呼び出すことができます。次に、解析を続行するために戻ります。このすべてを動かす必須のメインループは、パーサのトークン読み込み状態マシンです。

Answer 2

ドラゴンブックの前には、構文指向のコンパイラコンパイラがありました。 META II、TREE METAは1960年代に開発されました。メタ言語コンパイラ（メタコンパイラ）です。彼らは実際に失敗の成功を返す関数である解析ルールのセットを取っているトップダウンパーサーです。各ルールは論理的な解析式です。先頭のドライブルールは、ソースファイルの内容を定義しました。例えば、プログラミング言語は一連の宣言で構成されています。したがって、トップの走行ルールは次のようになります。

program = $declarations; 

$はゼロ以上を意味します。 $ declarationsは、コンパイルされるソースがいくつかの宣言で構成されることを指定します。宣言は宣言の型を定義します。外部リンケージ宣言、データ宣言、関数宣言または手続き宣言が必要な場合があります。

declarations = linkage_decl | data_decl | code_decl; 

宣言のタイプはそれぞれ別のルールです。この構文は、コード生成がいつ発生するかを制御します。メタコンパイラは構文規則からセマンティック処理を制御しました。最初はルールでそれは自己です。その後、ソースを木構造とリスト構造に変換し、出力を生成する意味規則にそれらを渡しました。たとえば、算術代入文を変換してセマンティック規則に渡すことができます。

asign = id '=' expr ';' :ASSIGN!2 arith_gen(*1); 
expr = term $(('+':ADD | '-':SUB) term !2); 
term = factor $(('*':MPY | '//' :REM | '/':DIV) factor!2); 
factor = id | number | '(' expr ')'; 

これらの言語はbnfのようでした。しかし、そうではありません。これらは分析トップダウン構文アナライザです。 arith_genは、組み込みツリーによって生成されたツリー構造を認識するようにコード化されます。 '：'と '！'演算子。使用されるツリー表記法はノードの後に​​ '['と ']'で囲まれ、 '、'で区切られたツリーブランチが続きます。上記の解析構文は、式の数学的階層を定義しています。乗算、除算および剰余が加算または減算の前に実行される。機能リスト表現に変換された算術代入式。構文は、入力の変換を機能表記に導いています。

x = a + (b - c)/d; 

機能表記ツリーを生成する： ASSIGN [X、ADD [、DIV [SUB [B、C]] D]

これら古いmetacompilersは正確に現在の用語と一致しません。

参照ウィキmetacompiler META IIとTREE METAトピックとそれがより多くの情報