8

私はプログラミングをしている限り（たった5年）コンパイラ/インタプリタの設計/実装に興味があり、それは常に誰も実際に話さない舞台裏の「魔法」のように見えました（少なくとも私は知っていますオペレーティングシステム開発のための2つのフォーラムですが、コンパイラ/インタプリタ/言語開発のためのコミュニティを知りません）。とにかく、最近、プログラミングの知識を全体として広げることを期待して、自分で作業を開始することにしました（そしてねえ、それはかなり楽しいです:)。それで、私が持っている限られた量の読み物とウィキペディアに基づいて、私はコンパイラー/インタープリターのためのコンポーネントのこの概念を開発しました：

ソースコード->字句解析->抽象構文木->構文解析->意味解析->コード生成->実行可能コード。

（コード生成と実行可能コードにはまだまだあることは知っていますが、まだそれほど理解していません:)

そして、その知識を基に、ソースファイルから入力を受け取り、トークンを別のファイルに出力するための非常に基本的なレクサー（Java）を作成しました。サンプルの入力/出力は次のようになります。

入力：

int a := 2
if(a = 3) then
    print "Yay!"
endif

出力（レクサーから）：

INTEGER
A
ASSIGN
2
IF
L_PAR
A
COMP
3
R_PAR
THEN
PRINT
YAY!
ENDIF

個人的には、そこから構文/意味解析、さらにはコード生成に進むのは本当に簡単だと思います。それは私に疑問を投げかけます。私のレクサーが同じようにうまく機能しているように見えるのに、なぜASTを使用するのですか？しかし、私がこのトピックを研究するために使用する私の情報源の100％はすべて、これがコンパイラー/インタープリターの必要な部分であることを断固として主張しているようです。ASTが実際に何であるか（プログラムの論理フローを示すツリー）のポイントを見逃していますか？

TL; DR：現在、コンパイラーの開発を進めており、字句解析機能を終了しました。出力によって、ASTを実行するのではなく、構文解析/意味解析が簡単になるようです。では、なぜそれを使用するのですか？私は1つのポイントを逃していますか？

ありがとう！

4

2 に答える 2

17

まず、コンポーネントのリストに関する1つのことは意味がありません。ASTの構築は（ほとんど）構文解析であるため、そこに含めるべきではないか、少なくともASTの前に置く必要があります。

そこにあるのはレクサーです。それがあなたに与えるのは、個々のトークンだけです。いずれにせよ、正規言語はプログラムするのが面白くないので、実際のパーサーが必要になります。式を（適切に）ネストすることさえできません。ちなみに、演算子の優先順位を処理することさえできません。トークンストリームはあなたに与えません：

  1. ステートメントと式が開始および終了するアイデア。
  2. ステートメントがどのようにブロックにグループ化されるかについてのアイデア。
  3. 式のどの部分がどの優先順位、結合性などを持っているかという考え。
  4. プログラムの実際の構造に関する明確で整頓されたビュー。
  5. すべてのパスが、内の条件が括弧で囲まれていることを認識し、それに対応するコードを持たずに、無数の変換を通過できる構造。if
  6. ...より一般的には、単一のトークンのレベルを超えるあらゆる種類の理解。

コンパイラに、特定の種類の演算子を最適化する2つのパスがあり、特定の引数に適用されるとします（たとえば、定数畳み込みとのような代数的単純化x - x -> 0）。式のトークンを渡すと、これらのパスは、パーツが最初に来るx - x * 1ことを理解するために散らかっています。x * 1そして、変換が正しくないことを知っておく必要があります（検討してください1 + 2 * 3）。

これらのことは、そのままではうまくいくのに十分トリッキーなので、問題の解析にも悩まされたくはありません。そのため、別の解析ステップで、最初に解析の問題を解決します。次に、たとえば、括弧を追加することを心配せずに、関数呼び出しをその定義に置き換えることができるため、意味は同じままです。時間を節約し、関心の分離を行い、繰り返しを避け、他の多くの場所でより単純なコードを有効にします。

パーサーはそれをすべて把握し、その結果すべての情報を保持するASTを構築します。ノードに関するそれ以上のデータがなければ、ASTの形状だけでは何も得られません。1、2、3、その他多数、無料。続くバジリオンパスのどれももうそれについて心配する必要はありません。

それはあなたが常にASTを持っている必要があるということではありません。十分に単純な言語の場合は、シングルパスコンパイラを実行できます。解析中にASTまたはその他の中間表現を生成する代わりに、コードを出力します。ただし、これは単純でない言語では難しくなり、多くのことを合理的に行うことはできません（たとえば、すべての最適化と診断の70％-そしてはい、私はその数を増やしました）。一般的に、これを行うことはお勧めしません。シングルパスコンパイラがほとんど死んでいるのには十分な理由があります。それらを許可する言語（Cなど）でさえ、現在、複数のパスとASTで実装されています。これは始めるのに簡単な方法ですが、後であなた（そしてあなたがそれをデザインするなら言語）を厳しく制限します。

于 2012-08-10T02:13:58.417 に答える
9

フローチャートの間違ったポイントにASTがあります。通常、レクサーの出力は一連のトークンであり（出力にあるように）、これらはASTを生成するパーサー/構文アナライザーに送られます。したがって、レクサーの出力は、コンパイルプロセスのさまざまな時点で使用され、さまざまな目的を果たすため、ASTとは異なります。

次の論理的な質問は次のとおりです。それでは、ASTとは何ですか？構文解析/構文解析の目的は、レクサーによって生成された一連のトークンをAST（または解析ツリー）に変換することです。ASTは、プログラムで操作しやすい方法で構文要素間の関係をキャプチャする中間表現です。これについての考え方の1つは、テキストプログラムは1次元の構成であり、アイデアを要素のシーケンスとしてのみ表すことができますが、ASTはこの制約から解放され、2次元でこれらの要素間の基本的な関係を表すことができます（通常描かれているように）、またはそのように考えることを選択した場合は、より高次元の空間。

たとえば、二項演算子には2つのオペランドがあり、それらをAとBと呼びます。コードでは、これは「A * B」と綴ることができます（中置演算子を想定しています。ASTのもう1つの利点は、構文的に重要になる可能性のある区別を非表示にすることです。 、ただし意味的にはそうではありません）が、コンパイラがこの式を「理解」するには、5文字を順番に読み取る必要があり、小さな言語でも多くの可能性があるため、このロジックはすぐに面倒になる可能性があります。ただし、AST表現では、値が「*」である「二項演算子」ノードがあり、そのノードには値「A」と「B」の2つの子があります。

コンパイラプロジェクトが進むにつれて、この表現の利点がわかり始めると思います。

于 2012-08-10T02:30:19.440 に答える