問題タブ [compiler-theory]

好奇心から、C++ の構文解析に関する「理論上の」結果とは何かを知りたいと思っていました。

n をプロジェクトのサイズとします (たとえば、LOC では、big-O を扱うため、あまり重要ではありません)。

• C++ は O(n) で解析されますか? そうでない場合、複雑さは何ですか？
• C (または Java またはその文法の意味でより単純な言語) は O(n) で解析されますか?
• C++1x では、解析がさらに困難になる新機能が導入されますか?

参考になれば幸いです！

名前に空白を含めることを許可するプログラミング言語はありますか? (名前で、私は変数、メソッド、フィールドなどを意図しています)

明確化

クロス コンパイルについて言及するとき、ホスト プラットフォームからターゲット プラットフォームへではなく、ある言語から別の言語 (GWT を考えてください) へのコンパイルを意味します。

バックグラウンド

私は Java にクロスコンパイルしたアラビア語プログラミング言語を開発しています。これにより、プラットフォーム固有の手間が省けました。今、私はこれを保留にする必要があり、さまざまな理由でCへのクロス コンパイルに切り替えました。

コンパイル時に実行されているシステムの同等のライブラリに置き換えられる単一のライブラリを開発したいと考えています。

たとえば、プログラマーが GUI 描画関数をアラビア語プログラミング言語で記述してコンパイルすると、Windows でコンパイルされた場合は win32 コードにクロス コンパイルされ、Gnome で GTK+、KDE ​​で Qt などにコンパイルされます。ライブラリも。

質問

コンパイルされた実行可能ファイルで終わるために、このすべての問題を経験する価値がありますか、それとも仮想マシンのアプローチを使用したほうがよいでしょうか? どちらかを選択することの長所と短所 (言語を使用するプログラマーではなく、言語開発者の観点から)? 他に考慮しなければならない要因はありますか？

さらに読むための参照リンクは大歓迎です:)

大学ではコンパイラ理論と文法を専攻していたので、この分野のバックグラウンドは十分にあり (かなり前のことですが)、少なくとも C++ などの言語の場合、コンパイラの作成は非常に重要な作業であることを知っています。

そのため、会社で働く大勢の人々ではなく、個人によって作成されたように見えるプログラミング言語の数が多いことについて、私は混乱しています。たとえば Ruby は、ウィキペディアによると 1 人の人物によって作成されたものです。その言語はおそらく信じられないほど単純なのでわかりませんが、自分で作成した言語がたくさんあるということです。

では、自分の言語 (単純すぎて役に立たないほどではない) を個人として作成し、そのために一生を費やすのではなく、どのようにすればよいのでしょうか?

このテーマに関する優れた本はありますか (コンパイラや一般的な仕様に関するものではありません)。

私は問題を抱えていて、頭を抱えているようには見えないので、ここの誰かが私を助けてくれることを願っていました.

私は miniGLSL 用のコンパイラを書いていますが、今のところうまくいっています。ARB フラグメント プログラムに出力する必要があるところですが、問題は、ターゲットにする必要がある ARB が分岐をサポートしていないことです。(サポートされている手順の完全なリストは、http://petewarden.com/notes/archives/2005/05/fragment_progra_2.htmlにあります)。

if/else をシミュレートするために、次のように CMP プログラムを使用しています (0 以上 = true、そうでない場合は false と仮定します。// は # としてコメントを表し、ここで不適切な書式設定が発生します)。

ARB フラグメントに:

これは、コードが本当に醜くなり始めることに気付く前に、私が到達する場所についてです。if/else の各レベルでは継続的にスタッキング比較が導入され、さらに最後の else では cond2 を再評価するか、別のレジスタを使用する必要があります。私はおそらくここで何か間違ったことをしていることを知っていますが、何がわからないのですか。カウンターを使用してみたり、if/else ブロックの前の段階の結果を追加したり、anding、oring などを試したりしましたが、if/else ブロックを ARB フラグメント アセンブリに変換する方法の適切な解決策が見つかりません。実際には、ますます大きくなる CMP ステートメントのスタック上にあります。私のコンパイラがこれをプログラムで出力できるように、これをより簡単にする方法を知っている人はいますか? 現時点では、最適化についてあまり心配していません。ただ機能させたいだけです。

ありがとう

アルゴリズムをインライン化する論文の議論を知っている人はいますか? そして密接に関連しているのが、親子グラフとコールグラフの関係です。

背景:主にこれと他のいくつかの最適化の結果として、関数を積極的にインライン化するコンパイラーを作成しましたOcaml。これは、多くの状況で他のほとんどのプログラミング言語よりも高速なコードを生成します ( C.

問題 #1:アルゴリズムに再帰の問題があります。このため、私のルールは、無限再帰を防ぐために、子を親にインライン化することだけですが、これにより、兄弟関数が相互にインライン化されることはなくなります。

問題 #2:インライン操作を最適化する簡単な方法を知りません。私のアルゴリズムは、関数本体の可変表現を使用することが不可欠です。効率的な関数型インライン化アルゴリズムを作成することは、リモートでさえ可能ではないように思われるからです。呼び出しグラフがツリーの場合、ボトムアップのインライン化が最適であることは明らかです。

技術情報:インライン化は、いくつかのインライン化ステップで構成されます。問題は、ステップの順序です。

各ステップは次のように機能します。

• 型パラメーターと値パラメーターの両方を引数に置き換えることにより、関数のコピーをインライン化してベータ削減します。
• 次に、return ステートメントを新しい変数への代入に置き換え、その後に関数本体の末尾にジャンプします。
• 関数への元の呼び出しは、この本体に置き換えられます。
• しかし、まだ終わっていません。また、関数のすべての子を複製し、それらもベータ削減し、複製を呼び出し元の関数に再親化する必要があります。

複製操作により、再帰関数をインライン化することが非常に困難になります。すでに進行中のもののリストを保持し、この呼び出しを既に処理しているかどうかを確認するだけの通常のトリックは、単純な形式では機能しません。関数、および再帰ターゲットが複製された子に変更された可能性があります。ただし、その子は、親を呼び出す際に、その子を呼び出す元の親を呼び出しているため、再帰の展開は停止しません。前述のように、子への再帰呼び出しのインライン化のみを許可し、兄弟の再帰がインライン化されないようにすることで、この回帰を打破しました。

インライン化のコストは、garbage collect未使用の関数が必要になるため、さらに複雑になります。インライン化は潜在的に指数関数的であるため、これは不可欠です。関数へのすべての呼び出しがインライン化されている場合、関数がまだインライン化されていない場合は削除する必要があります。そうしないと、使用されなくなった関数にインライン化する時間が無駄になります。誰が何を呼び出しているかを実際に追跡することは非常に困難です。なぜなら、インライン化するとき、実際の関数表現ではなく、「解明されていない」表現で作業しているためです。たとえば、命令のリストが順次処理され、新しいリストが構築されます。また、一貫した命令リストが存在しない可能性もあります。

彼の ML コンパイラで、Steven Weeks は繰り返し適用される多数の小さな最適化を使用することを選択しました。これにより、最適化が記述しやすく、制御しやすくなりましたが、残念ながら、これは再帰アルゴリズムと比較して多くの最適化の機会を逃しています。

問題 #3:関数呼び出しをインライン化しても安全なのはいつですか?

この問題を一般的に説明すると、遅延関数型言語では、引数がクロージャでラップされ、アプリケーションをインライン化できます。これは Haskell の標準モデルです。ただし、なぜHaskellこんなに遅いのかについても説明しています。引数が既知の場合、クロージャーは必要ありません。その場合、パラメーターは、発生する引数で直接置き換えることができます (これは通常の順序beta-reductionです)。

ただし、引数の評価が終了しないことがわかっている場合は、代わりに熱心な評価を使用できます。パラメーターには式の値が一度割り当てられ、その後再利用されます。これら 2 つの手法のハイブリッドは、クロージャーを使用するが、結果をクロージャー オブジェクト内にキャッシュすることです。それでも、GHC は非常に効率的なコードを生成することに成功していません。特に、個別にコンパイルする場合は、明らかに非常に困難です。

Felix では、逆のアプローチを取りました。正確さを要求し、最適化がセマンティクスを保持していることを証明することによって徐々に効率を改善する代わりに、最適化がセマンティクスを定義することを義務付けます。これにより、特定のコードがどのように動作するかについての不確実性を犠牲にして、オプティマイザーの正しい動作が保証されます。この考え方は、デフォルトの最適化戦略が積極的すぎる場合に、オプティマイザーを意図したセマンティクスに強制的に準拠させる方法をプログラマーに提供することです。

たとえば、デフォルトのパラメーター受け渡しモードでは、コンパイラーは引数をクロージャーでラップするか、パラメーターを引数で置き換えるか、または引数をパラメーターに割り当てるかを選択できます。プログラマーがクロージャーを強制したい場合は、クロージャーを渡すだけです。プログラマーが熱心な評価を強制したい場合は、パラメーターをマークしますvar。

ここでの複雑さは、関数型プログラミング言語よりもはるかに大きくなります。Felix は、変数とポインターを使用する手続き型言語です。Haskell スタイルの型クラスもあります。これにより、インライン化ルーチンが非常に複雑になります。たとえば、型クラスのインスタンスは、可能な限り抽象関数を置き換えます (ポリモーフィック関数を呼び出すときの型の特殊化により、インライン化中にインスタンスを見つけることができる場合があるため、新しい関数があります。インライン化できます)。

明確にするために、さらにメモを追加する必要があります。

インライン化と、ユーザー定義の用語削減、型クラスのインスタンス化、変数削除のための線形データ フロー チェック、テール レコードの最適化などの他のいくつかの最適化が、指定された関数に対して一度に実行されます。

順序付けの問題は、さまざまな最適化を適用する順序ではなく、関数を順序付けすることです。

脳死アルゴリズムを使用して再帰を検出します。各関数によって直接使用されるすべてのリストを作成し、クロージャーを見つけて、関数が結果に含まれているかどうかを確認します。使用セットは最適化中に何度も構築されることに注意してください。これは深刻なボトルネックです。

関数が再帰的であるかどうかは、残念ながら変わる可能性があります。tail rec の最適化後、再帰関数が非再帰になる可能性があります。しかし、もっと難しいケースがあります: 型クラスの「仮想」関数をインスタンス化すると、再帰的でないように見えたものを再帰的にすることができます。

兄弟呼び出しに関しては、問題は、f が g を呼び出し、g が f を呼び出す f と g を指定すると、実際には f を g に、g を f .. に 1 回インライン化したいことです。私の無限回帰停止規則は、f が g の子である場合に相互に再帰的である場合にのみ、f の g へのインライン展開を許可することです。これにより、兄弟のインライン展開は除外されます。

基本的に、すべてのコードを「可能な限り」「平坦化」したいと考えています。

既知の分離された数のテキストブロックを含む入力セットを提供します。

入力セット内のすべてのテキストブロックに一致する1つ以上の正規表現を自動的に生成するプログラムを作成したいと思います。

ブルートフォース検索を実装するための比較的簡単な方法がいくつかあります。しかし、私はコンパイラ理論の専門家ではありません。それが私が興味を持っている理由です：

1）この問題は解決可能ですか？または、そのようなアルゴリズムを作成するためのいくつかの原則的な不可能性がありますか？

2）このアルゴリズムの多項式の複雑さを達成し、ブルートフォースを回避することは可能ですか？

次のような文法があるとします。

S→A

A→ E「＝」E

この例では、シーケンス ( "=" ) をS 導出します。しかし、これの反対は何ですか？つまり、空欄に入る適切な単語は次のとおりです。EE

「シーケンス ( E"=" E) __ _ __ S . "

対義語を微積分から借りるとすれば、 ( E"=" E)は積分 Sする と言えますが、それは正しくないようです。

一意の決定論的な名前を持つさまざまなデータ型をC++で生成したいと思います。例えば：

現在、私のコンパイラはカウンタを使用して名前を合成します。つまり、同じデータ型を個別の変換単位でコンパイルする場合、名前は一致しません。

動作しないものは次のとおりです。

1. ABIMangled_name関数を使用します。すでに一意の名前を持つ構造体に依存しているためです。構造体が匿名であるふりをすることにより、C ++ 11準拠のABIで機能する可能性がありますか？

2. テンプレートは再帰型では機能しないため、struct2などのテンプレート。

3. 完全なマングリング。あまりにも長い名前を付けるからです（数百文字！）

グローバルレジストリ（YUK！）とは別に、私が考えることができる唯一のことは、最初に一意の長いマングル名を作成し、次にダイジェストまたはハッシュ関数を使用してそれを短縮することです（衝突がないことを願っています）。

実際の問題：タプル、合計型、関数型など、型が匿名の場合に呼び出すことができるライブラリを生成する。

他のアイデアはありますか？

編集：再帰型問題の追加の説明。次のようなリンクリストを定義することを検討してください。

これが実際に必要なことです。これは2つの理由で機能しません。1つは、typedefをテンプレート化できないことです。[いいえ、typedefを含むテンプレートクラスは使用できません。機能しません]次に、list *はまだ定義されていないため、引数として渡すことはできません。ポリモーフィズムのないCでは、次のことができます。

いくつかの回避策があります。この特定の問題については、Barton-Nackmanトリックの変形を使用できますが、一般化されていません。

一般的な回避策があります。最初にGabrielledesRoisによって示され、オープン再帰のテンプレートを使用し、次に部分的に特殊化してそれを閉じます。しかし、これを生成することは非常に困難であり、私がそれを行う方法を理解できたとしても、おそらく読めないでしょう。

バリアントを適切に実行することにも別の問題がありますが、それは直接関係していません（構築可能な型で結合を宣言することに対する愚かな制限のため、さらに悪いことになります）。

したがって、私のコンパイラは単に通常のC型を使用します。とにかくポリモーフィズムを処理する必要があります。それを作成する理由の1つは、テンプレートを含むC++型システムの問題を回避することでした。これにより、名前の問題が発生します。

カスタムマークアップ言語用のコンパイラを作成したいのですが、最適なパフォーマンスを実現したいのですが、優れたスケーラブルなデザインも必要です。

マルチパラダイムプログラミング言語（C ++）は、最新のデザインパターンを実装するのに適していますが、パフォーマンスが少し低下し（たとえば、RTTIを考えてください）、多かれ少なかれCがより適切な選択になると思います。

誰かが（ソフトウェアとしての最新のソフトウェアエンジニアリングの原則に準拠するという意味で）高速で効率的で適切に設計された最新のコンパイラを作成したい場合、最高の言語（C、C ++、またはObjective C）は何でしょうか。