簡単な言葉で、「Syntax Directed Translation」の意味を説明できる人はいますか? ドラゴンブックからトピックを読み始めましたが、理解できませんでした。Wikiの記事も役に立ちませんでした。
6177 次
2 に答える
19
簡単に言えば、「構文指示変換」とは、構文認識機能 (パーサー) を使用してコンパイル (変換) プロセス全体を駆動することを意味します。
概念的には、プログラムをコンパイルする (ソース コードからマシン コードに変換する) プロセスは、解析ツリーを生成するパーサーから始まり、次に一連のツリーまたはグラフ変換によってその解析ツリーを変換します。マシンコードを生成するためにトラバースされる最終的な単純化されたツリーまたはグラフが得られます。
このビューは理論的には優れていますが、直接実装しようとすると、ツリーまたはグラフ全体のコピーを少なくとも 2 つ保持するのに十分なメモリが必要になるという欠点があります。ドラゴンブックが書かれたとき（そしてこの理論の多くがハッシュ化されたとき）、コンピューターのメモリはキロバイト単位で測定され、64Kは大量でした. そのため、大きなプログラムをコンパイルするのは難しい場合があります。
Syntax Directed Translation を使用すると、パーサーが解析ツリーを認識する順序に基づいて、すべてのグラフ変換を編成できます。完全な解析ツリーを生成する代わりに、パーサーはその一部を構築し、それらのビットをコンパイラの後続のパスに供給して、最終的に小さなマシン コードを生成してから、解析プロセスを続行して次の解析を構築します。木。常に少量の解析ツリー (または後続のグラフ) しか存在しないため、必要なメモリははるかに少なくなります。構文レコグナイザーは、これらすべてを制御するマスター シーケンサーであるため (発生する順序を決定します)、これを構文指示変換と呼びます。
これはメモリ使用量を抑える非常に効果的な方法であるため、より簡単に実行できるように言語を再設計することさえありました。理想的なのは、構文解析からマシン コード生成までのプロセス全体を実際に実行できる「シングル パス」コンパイラを使用することです。シングルパスで。
現在、メモリはそれほど重要視されていないため、すべてを 1 回のパスに強制するというプレッシャーは少なくなっています。代わりに、通常、構文の解析、型チェックやその他のセマンティック チェックの実行、いくつかの単純な変換をすべてパーサーから行い、いくつかの内部形式 (3 つのアドレス コード、ツリー、または何らかの種類の DAG) を生成する、フロント エンドのためだけに構文直接変換を使用します）、独立した（したがって、構文指向ではない）個別の最適化パスとバックエンド パスがあります。この場合でも、これらの後のパスは少なくとも部分的に構文指向であると主張するかもしれません.次の入力。
yacc のようなツールは、Syntax Directed Translation の考え方に基づいて設計されています。このツールは、生成物 (解析ツリーのフラグメント) が認識されるとコードのフラグメント (ツール用語では「アクション」) を直接実行する構文認識エンジンを生成します。実際の「木」。これらのアクションは、コンパイラで論理的に後のパスを直接呼び出してから、解析を続行するために戻ることができます。これらすべてを駆動する必須のメイン ループは、パーサーのトークン読み取りステート マシンです。
于 2013-04-13T06:21:10.397 に答える