問題タブ [compiler-theory]

私はしばらくの間（表面上は学習体験のために）自分の言語を書くことで遊んでみたいと思っていたので、パーサー、インタープリター、コンパイラーの構築に比較的基礎を置く必要があります。それで：

• パーサー、インタープリター、およびコンパイラーの構築に関する優れたリソースを知っている人はいますか？

編集：私はLex、Yacc、Bisonなどのコンパイラコンパイラ/パーサコンパイラを探していません...

Nikhil Kothari のScript#は、かなり長い間 JavaScript の分野で目にした中で最も驚くべき概念の 1 つです。この質問は JavaScript に関するものではなく、.NET ランタイムでの言語のコンパイルに関するものです。

私は、.NET プラットフォームを使用して、元のコンパイラが出力を生成できるようにしながら、元のコンパイラから別の出力を生成するコンパイラ (C# など) を既に持っている言語用のコンパイラを作成する方法にかなり興味を持っていました。他のコンパイラの出力も参照/使用している間、同じビルド操作中に同じソース。

正しい詳細を質問するのに十分なほどプロセスを理解しているかどうかは完全にはわかりませんが、Script# ドキュメントの図に従って、これが現在のプロセスの見方です。私は、このような概念を利用できる可能性のある複雑な言語設計とコンパイルを含む多くのことについて考えてきました。また、他の人がその概念についてどう考えているかに興味があります。

--

編集：これまでにコメントしていただきありがとうございます。あなたの情報は、それ自体が非常に興味深いものであり、もっと調査したいのですが、私の質問は、実際には、同じソースで同時に実行できる独自のコンパイラをどのように作成できるかについてですCLR を使用して、複数の異なるタイプの (潜在的に) 相互に依存する出力を生成します。Script# は、同じ C# ソースを使用して JavaScript とアセンブリを生成し、コンパイルされたアセンブリを JavaScript と連携させるため、例として役立ちます。この性質のものを設計する際に、さまざまなアプローチと理論的概念がどのようなものであるかに興味があります。

せっかちな人のための要約: 共通言語構造のコードを生成するための良い参考文献を探していますが、解析はしていません。

私はプログラミング言語に興味があり、できるだけ文献を読むようにしています。しかし、それらのほとんどは、機能的および理論的な観点からトピックをカバーしているため、アイデアを実装するどころか、理解するのが難しいと思います.

問題は次のとおりです。より命令的かつ実用的な方法でトピックをカバーするプログラミング言語の実装について、どのリソースを提案しますか?

たとえば、「Lua 5.0 の実装」という論文は非常に有益です。

解析やトークン化に関する記事を求めているわけではないことに注意してください。

何百万ものノードがあるグラフのドミネーター ツリーを計算するために、Lengauer および Tarjan アルゴリズムとパス圧縮を使用しています。アルゴリズムは非常に複雑であり、完全に理解するのに時間がかかっていないことを認めなければなりません。使用しているだけです。ここで、ルート ノードの直接の子のドミネーター ツリーを計算し、この操作を繰り返して特定の深さまでグラフを再帰する必要があります。つまり、ルート ノードの子のドミネーター ツリーを計算するときに、ルート ノードがグラフから削除されたふりをしたいのです。

私の質問は、ルート ノードの初期ドミネーター ツリーで既に計算されている即時ドミネーター情報を利用する効率的な解決策があるかどうかです。言い換えれば、プロセス全体が非常に時間がかかるため、子供たちのそれぞれについてゼロから始めたくありません。

単純に、グラフの奥深くには、idom が少し上にあり、グラフの上部の変更の影響を受けないノードがたくさんあるため、それは可能であると思われます。

ところで、ドミネーターツリーの主題がコンパイラーの人々によって「所有」されており、古典的なグラフ理論に関する本でそれについて言及されていないのは奇妙です。私が使用しているアプリケーション (私の FindRoots Java ヒープ アナライザー) は、コンパイラ理論とは関係ありません。

明確化: ここでは有向グラフについて話しています。私が参照する「ルート」は、実際には最大の到達可能性を持つノードです。「ツリー」への参照を「グラフ」に置き換えて、上記のテキストを更新しました。形が主に木のような。グラフは実際には Java ヒープ内のオブジェクトであり、ご想像のとおり、適度に階層化されています。OOM リーク分析を行う際にドミネーター ツリーが役立つことが分かりました。答えは最終的にそのドミネーターです。ドミネーター ツリーを使用すると、木ではなく木を<ahem>見ることができます。しかし、時にはたくさんのがらくたが木のてっぺんに浮かぶので、そのすぐ下に何千もの子を持つ根があります。このような場合、ルートの (元のグラフの) 直接の子のそれぞれにルートを持つドミネーター ツリーの計算を試してから、1 つ下のレベルに移動します。（当分の間、バックリンクの可能性について心配しないようにしています:)

私が理解しているように、pimpl イディオムが存在するのは、C++ がすべてのプライベート クラス メンバーをヘッダーに配置することを強制するためだけです。ヘッダーにパブリック インターフェイスのみが含まれている場合、理論的には、クラスの実装を変更しても、プログラムの残りの部分を再コンパイルする必要はありません。

私が知りたいのは、C++ がそのような利便性を考慮して設計されていない理由です。クラスの非公開部分をヘッダーに公然と表示する必要があるのはなぜですか (しゃれは意図されていません)。

LR1 パーサーがどのように機能するかを理解しようとしていますが、奇妙な問題が発生しました: 文法にイプシロンが含まれている場合はどうなりますか? 例：文法がある場合：

開始方法は明らかです。

... 等々

しかし、私はそのような文法のためにそれを行う方法がわかりません:

するのは正しいですか：

そして、DFA でこの状態を受け入れますか?

どんな助けでも本当に感謝します！

このhttp://steve-yegge.blogspot.com/2007/06/rich-programmer-food.html 記事によると、私は間違いなくそうすべきです。

引用 穏やかでありながらしつこい要旨: コンパイラーの仕組みを知らなければ、コンピューターの仕組みもわかりません。コンパイラがどのように機能するかを 100% 確信できない場合は、コンパイラがどのように機能するかを知りません。

非常に興味深い記事だと思いましたし、応用分野は非常に役に立ちます (自分で読んでみてください)。その点についてはアーキテクチャですが、次のリストの各項目の 1 つまたは 2 つを知っていました。

• プログラミング パラダイム (オブジェクト指向、関数型など)
• プログラミング言語 API (C#、Java..) と、少なくとも 2 つの非常に異なるものがあると言う人もいます。(ジャバ/ハスケル)
• プログラミング フレームワーク (Java、.NET)
• 生産性を高める IDE (Eclipse、VisualStudio、Emacs など)。
• プログラミングのベスト プラクティス (例として fxcop ルールを参照)
• プログラミングの原則 (DRY、高結束、低結合など)
• プログラミング方法論 ( TDD、 MDE )
• 設計パターン (構造、行動など)
• アーキテクチャの基本 (階層、レイヤー、プロセス モデル (ウォーターフォール、アジャイルなど)
• テスト ツール (単体テスト、モデル テストなど)
• GUI テクニック (WPF、Swing)
• 文書化ツール (Javadoc、Sandcastle..)
• モデリング言語 (およびおそらくツール) (UML、VisualParadigm、Rational)
• （間違いなくここで非常に重要なことを忘れています）

これらのツールのすべてが優れたプログラマーになるために必要なわけではありませんが (GUI が必要ない場合のように)、ほとんどのツールは必要です。コンパイラはどこに登場し、コンパイラは本当に重要なのですか? 前述したように、多くのプログラマはコンパイラを知らなくてもうまくやっているようで、特に優れたプログラマになることは、多くの知識領域を生涯の成果として見られるからです:- ) ですから、コンパイラが非常に重要だとしても、もっと重要なものが常にあるのではないでしょうか?

それとも、「The Unleashed Compilers Unlimited Bible (in 24H..)))」を今日注文する必要がありますか?

記事を読んで、すぐに勉強を始めたい方へ：

パーサー、インタープリター、およびコンパイラーに関する学習リソース

または、もう少し正確に言うと、どのプログラミング言語が文脈自由文法によって定義されているのでしょうか。

私が収集したものから、C ++は、マクロやテンプレートなどの理由で文脈自由ではありません。私の腸は、関数型言語は文脈自由かもしれないと言っていますが、それをバックアップするためのハードデータはありません。

簡潔な例のための追加の担当者:-)

新しいオープンソース言語を作成したいと思います。
コンパイラ理論を実際に扱っているプログラマーを見つけることは本当にまれなので、私はいくつかのアドバイスが必要です。
オープンソースプロジェクトに興味を持ってもらうにはどうすればよいですか？
どのようにして彼を貢献したい立場に連れて行くのですか？
それらのpepoleを見つけることができる特別な場所はありますか（sourceforge.netを除く）？

inline キーワードを使用したり、クラス宣言にメソッドを挿入したり、短い ctor または getter メソッドを使用したりできることは理解していますが、メソッドをいつインライン化するかについて最終的な決定を下すのはコンパイラですか?

例えば：

コードが非効率になるとコンパイラが判断した場合、コンパイラはインライン宣言を無視しますか?

副次的な問題として、次のようにクラス外で宣言された getter メソッドがある場合:

コンパイラはこれを裏でインライン化しますか?