問題タブ [compiler-theory]

Al Aho のコンパイラ クラスのコンパイラを作成しており、AST の生成用に次のコードを検討しています。ここにいくつかの背景があります。名前と ID のマッピングのスタックとしてスコープ ルールを実装し、宣言のノードを生成する前に一連のマッピングをスタックにプッシュします。

それでは、私の質問です。これはどのように作動しますか？このコードはいつ実行されますか? このプロダクションがパーサーによって削減されたときに実行されますか? いつどの部分が発生しますか？オフィスアワーに行って確認する必要がありますか？

私はコンパイラとツールのコースをやっています（今学期）。私は中間コード生成まで読み、最適性のためのDAG表現も見ました。コンパイラーで明らかなことの1つは、生成された中間コードが何であれ、プログラムを実行できるように、システムの命令セットにマップする必要があるということです。

特定のアーキテクチャ（たとえばA）用のコンパイラを作成しているとしましょう。2つの数値の加算はADD R1、R2、R3（Aの命令セットから）です。ここで、R1-は宛先、R2、R3は情報源。そして、私はこれらの命令でマッピングしました。つまり、中間コードで表される2つの数値（タイプに関係なく、簡単にするため）を追加したい場合は、ADDオペコードを実行します。

新しいアーキテクチャが市場に到着したと仮定します。このアーキテクチャでは、2つの数値を加算すると、AD R1、R2、R3などの異なる命令セットが使用されます。今、明らかに私のコンパイラは数字を追加しません！

さて、私の質問は、プログラミング言語用のコンパイラを作成するときに、すべてのアーキテクチャを命令セットとともに追加して、コンパイラが必要なことを正しく実行できるようにする必要があるということです。もしそうなら、この効果を最適化するためにそこにあるすべての方法は何ですか？すべての命令セットを追加すると、パフォーマンスがほぼ低下するためです。

私が間違っていたら正解です！

定義に到達する問題は、データ フロー分析における最も基本的な問題の 1 つです。変数の定義と用途を含む制御フロー グラフが与えられた場合、問題は、どの変数定義が特定の用途に達するかを計算することになります。

たとえば、フロー グラフを考えてみましょう。

ブロック 3 での変数 x の使用は、ブロック 1 またはブロック 2 のいずれかの定義から到達できます。

どの定義が用途に達するかを計算するアルゴリズムは、古典的なデータ フローの問題です。ドラゴン コンパイラの本 (新版) の表記法を使用すると、定義に到達するデータ フローの問題は次のようになります。

ドメイン : 定義のセット (例: {x <- .., ...})
方向 : 順方向
伝達関数 : fb(x) = gen(B) U (x - kill(B)) ここで、gen(B) はブロック B が生成する一連の定義と kill(B) ブロック B が削除する一連の定義
Boundary : OUT[ENTRY] = {} つまり、関数へのエントリのための定義フローはありません
演算子に適合します: U(union)、つまり定義ブロックへのフローは、先行ブロックからの定義の結合です。
式 : OUT[B] = fb(IN[B]), IN[B] = U(P in pred)OUT[P]
初期化: OUT[B] = {}

ただし、すべての定義が同じというわけではありません。たとえば、ブロック 1 の定義は、ブロック 2 の定義によって殺される可能性があるため、ブロック 3 の使用に決して到達しない可能性があります。一方、ブロック 2 の定義は、実行された場合、ブロックで使用されるまでその値を保持します。 3.

定義から使用法へのどのパスにも強制終了定義がない使用法の到達定義を見つけたいです。私の質問は、同様のデータフローの問題が存在するかどうかです（おそらく伝播など）。データフロー分析の観点からどのように解決できるか。

この問題に対する解決策は 1 つ考えられますが、解決策が既に存在する場合、車輪の再発明はしたくありません。

言語、文法、構文解析、コンパイラに関する試験の準備をしています。それは実際には私のお茶ではなく、私が見つけたほとんどのリソースは、数学の言語を使用して、交易条件のさまざまな用語を定義し、英語やフランス語に固執するのではなく、知る必要のあるさまざまな概念を説明しています。そのため、勉強を続ける動機を見つけることと、理論を理解することの両方に問題があります。だからここに私の質問があります：私がこれらすべてを学ぶ「楽しい」方法をどこで見つけることができるか知っている人はいますか？または、少なくとも、この主題を処理するためのより「具体的」で「数学的な」方法ではないかもしれません。

私は以下をカバーする必要があるので、これらの主題に関するものは何でも歓迎です！

• 構文解析（LR、LL、...）
• 文法（文脈自由、決定論的、...）
• 構文解析静的フロー分析
• ソフトウェアのメンテナンスとユーザーインターフェイスへの依存に関する影響分析
• 動的解析

ここに、私が探しているものを理解するためだけに、技術的な主題について学ぶための「楽しい」（引用符に重点を置いた）方法と見なすことができるいくつかのリソースがあります。

• Rubyの感動的なガイドはなぜですか
• MongoDBを試してください（Help + Enterと入力してください）

エラー生成は通常どのように追加されますか？エラー生成が浅すぎるという問題が発生しています。パーサーがステートメント内のエラーの状態をポップし始めると、パーサーが配置されているセクションのエラー生成に到達するまでポップし、無効なエラーを出力します。メッセージ。

すべての非終端記号に説明的なエラー生成を追加するのは良い考えですか？

私は、動的言語でメインの型として使用されるバリアント クラスを作成しました。これは、最終的に 256 の異なる型の値を許可します (ヘッダーは符号なしバイトで、実際に使用されるのは 20 のみです)。タイプ間のキャスト/変換を実装したいと思います。

私の最初の考えはルックアップ テーブルでしたが、必要となる大量のメモリを実装するのは現実的ではありませんでした。

代替手段は何ですか？現在、研究や他の人からの提案から、さらに 3 つの方法を検討しています。

1. 数値やコレクションなど、より大きなサブセットに型をグループ化します。
2. CanCast(from, to) メソッドと Cast(Variant) メソッドを持つ変換インターフェイスを作成し、そのインターフェイスを実装するクラスをリストに追加できるようにします。これにより、変換クラスのいずれかがキャストを実行できるかどうかを確認できます。
3. (1) と同様ですが、いくつかのマスター タイプを作成します。キャスティングは、元のタイプからマスター タイプへ、そして再び最終的なタイプへの 2 段階のプロセスです。

最適なシステムは何でしょうか?

編集：私はまだ最善のシステムがわからないので、賞金を追加しました.

現在、動的ディスパッチを実装するさまざまな方法を探しています。

私の知る限り、これを実装するには 2 つの「簡単な」方法があります。

• C++ のような仮想関数テーブル
• SmallTalk のようなメッセージ ディスパッチャー (メソッドを に属性として格納するという Python の考え方に多少似ています__dict__)

私が知る限り、VFT が選択された理由は、パフォーマンスが合理的で実装が簡単だった (また、C++ の個別のコンパイル モデルに適していた) ためであり、可能な限り最速の方法だったからではありません。

私はすでにいくつかの記事や出版物を読んだことがありますが、そのほとんどは「古い」ものであり (最後に読んだ(*) Pentium 200MHz を使用して言及されていました ... うーん)、それらが最新技術を表しているとは思えません。研究が停滞しない限り。

私は、に興味を持っています：

• ダイナミック ディスパッチ戦略は、複数の方法をサポートしている場合に適しています。
• さまざまな戦略のベンチマーク

私は特に最近の記事や非凡な戦略に興味があります (たとえそれらが効率的であるとは証明されなかったとしても)。

出版物は大歓迎です。自由に入手できればよりよいでしょう。それ以外の場合は、提示された技術の要約と結果が素晴らしいものになるでしょう。

実際のコンパイラの実装に関する技術記事も歓迎します。

(*) Eiffel に関するこの記事は、プログラム全体の分析が仮想呼び出しサイトの除去にどのように役立つかを示しています。

CFG (とりわけ) に 2 つの基本ブロック A と B があり、A から B へのエッジがあるとします。次の手順を実行する必要があります。

• そのエッジを横切るライブ値のセット S を取得します (これは過大評価である可能性があります。つまり、もうライブではない値が含まれている可能性があります)。
• それらのそれぞれを別の値にマップします (S->S')
• 置換 - B とその後継 - S の値のすべての使用をマップされた値 (S') に置き換える

LLVM は 1 番目と 3 番目のポイントを実行する簡単な方法を提供しますか? そうでない場合、それを行う方法について何か提案はありますか?

注: LLVM メーリング リストにクロスポストされました

私はこの質問を徹底的に読んだ後、IDE を構築するというアイデアが頭に浮かびました。

私は新卒で、IDE を構築する際の概念的な手順と実際の手順を知りたいと思っています。

この質問を投稿する前に宿題はありませんでしたが、ここで効率的な回答が得られると確信しています。