問題タブ [compiler-theory]

プログラミング言語で、入力プログラムからWin32プログラムを作成できるコンパイラのソースコードを探しています（どちらでも構いません、単純なほうがいいかもしれません）

それでも、自分に合ったものを見つけることができず、GCC のような巨大なコンパイラーには非常に多くの機能があり、どこから始めればよいかわからないため、非常に混乱します。

• 私が調べられるプログラミング言語用の OpenSource Win32 マイクロコンパイラはありますか?

コンパイラは、変換ユニット全体で重複する定義をどのように検出しますか。ヘッダーファイルにexternconst変数宣言があったとします。
このヘッダーファイルが複数の変換ユニット（それぞれが個別の定義を持つ）で使用された場合、各TUオブジェクトの作成は成功しますが、最終的な実行可能ファイルが作成されるとエラーがスローされます。

これらのTUのそれぞれをリンクしている間（実行可能ファイルの作成中）にこれらの重複を説明するために作成された参照テーブルはありますか？

このトピックに関するリンクは役に立ちます。

よろしくお願いします。

私はflex、byacc（字句および構文解析用）およびC ++を使用して言語のような小さなPythonを開発していますが、スコープ制御に関していくつか質問があります。

Pythonと同じように、インデントに空白（またはタブ）を使用しますが、それだけでなく、たとえば、別のwhileループ内にあるwhileループ内に「break2」と入力した場合のように、インデックスブレークを実装したいのですが、最後の1つですが、最初のループからも（したがって、ブレーク後の番号2）などです。

例：

しかし、スコープがいつ終了するかを確認するための「アンチ」タブ文字がないため（たとえば、Cのように「}」文字を使用するだけです）、この方法が最適かどうか疑問に思いました。

externを使用してlexファイルでアクセスするyaccファイルに「inttabIndex」のようなグローバル変数を定義します。次に、lexファイルでタブ文字を見つけるたびにその変数を1ずつインクリメントします。yaccファイルを解析するときに「break」キーワードを見つけた場合は、tabIndex変数からその後に入力した量だけデクリメントします。コンパイル後にEOFに到達し、tabIndex！= 0を取得すると、コンパイルエラーが出力されます。

問題は、インデントが減少したかどうかを確認するための最良の方法は何ですか？lexから\ b（バックスペース）文字を読み取ってから、tabIndex変数を減少させる必要があります（ユーザーがbreakを使用しない場合）？

これを達成する別の方法は？

また、もう1つの小さな質問ですが、すべての実行可能ファイルにstart（）という関数の開始点を持たせたいのですが、これをyaccファイルにハードコーディングする必要がありますか？

長い質問で申し訳ありませんが、どんな助けでも大歓迎です。また、誰かがpython用のyaccファイルを提供できる場合は、ガイドラインとして役立ちます（Googleで調べてみましたが、運がありませんでした）。

前もって感謝します。

Push、Pop、Jump、If の操作を伴うスタックベースのおもちゃの言語があるとします。

プログラムがあり、その入力はおもちゃの言語です。たとえば、シーケンスを取得します

その場合、最大スタックは 2 になります。より複雑な例では、ブランチが使用されます。

この場合、最大スタックは 3 になります。ただし、実際にはスタック アンダーフロー エラーが発生するため、この場合のように上から下に移動して最大スタックを取得することはできません。

CFG を使用すると、グラフを作成して、基本ブロックの可能なすべてのパスをたどることができます。ただし、パスの数は n 個の頂点で急速に増加する可能性があるため、(n-1) になります。可能なパス。

私の現在のアプローチは、グラフをできるだけ単純化し、可能なパスを少なくすることです。これは機能しますが、私はそれが醜いと思います。この問題を攻撃するためのより良い (読む: より速い) 方法はありますか? アルゴリズムが生成するスタック深度が最適でなくても問題ありません。正しいスタック サイズが m の場合、私の唯一の制約は、結果 n が n >= m であることです。ここで良い結果を生み出す貪欲なアルゴリズムが利用可能でしょうか?

更新:サイクルと、すべての制御フロー マージのスタック深度が同じであるという不変条件を認識しています。問題を説明するために、簡単なおもちゃのような言葉を書き留めようと思いました。基本的に、私は決定論的なスタックベースの言語 (JVM バイトコード) を使用しているため、各操作には既知のスタックデルタがあります。

私はこの問題に対して、良い結果 (単純化された cfg) を生成する実用的な解決策を持っていることに注意してください。

左再帰の削除で説明されているように、左再帰を削除するには 2 つの方法があります。

• いくつかの手順を使用して、元の文法を変更して左再帰を削除します
• 左再帰を持たないように文法を独自に書く

ANTLR で左再帰を削除する (持たない) ために、通常は何を使用しますか? パーサーに flex/bison を使用しましたが、ANTLR を使用する必要があります。ANTLR (または一般的な LL パーサー) の使用に関して私が懸念しているのは、左再帰の削除だけです。

• 実用的な意味で、ANTLR で左再帰を削除することはどれほど深刻ですか? これは ANTLR を使用する上での目玉ですか? それとも、ANTLR コミュニティでは誰も気にしていませんか?
• ANTLR の AST 生成のアイデアが気に入っています。AST をすばやく簡単に取得するという点で、(左再帰を削除する 2 つの方法のうち) どの方法が望ましいですか?

追加した

次の文法でいくつかの実験を行いました。

左再帰を削除した後、次のものが得られます

次の ANTLR 表現を思い付くことができました。比較的単純で簡単ですが、左再帰を持たない文法の方が適しているようです。

ANTLRでの左再帰の削除で質問と回答があったように、左再帰を削除できました

左再帰を削除すると、次のようになります

それでは、修正された文法でツリーを構築する方法は？入力1+2で、ツリーが欲しい

次のパターンが非常に頻繁に発生しています。

リテラル文字列が 2 回使用されていることに注意してください。抜粋は nginx ソースベースからのものです。

コンパイラは、コンパイル単位内でこれらのリテラルが検出されたときに、これらのリテラルをマージできる必要があります。

私の質問は次のとおりです。

1. 商用グレードのコンパイラ (VC++、GCC、LLVM/Clang) は、コンパイル ユニット内で発生したときにこの冗長性を取り除きますか?
2. (静的) リンカは、オブジェクト ファイルをリンクするときにそのような冗長性を取り除きますか?
3. 2 が適用される場合、動的リンク中にこの最適化が行われますか?
4. 1 と 2 が当てはまる場合、それらはすべてのリテラルに当てはまりますか。

これらの質問は、プログラマーが効率を失うことなく冗長にできるため、重要です。つまり、プログラムに組み込まれている膨大な静的データ モデル (たとえば、低レベルのシナリオで使用される意思決定支援システムのルール) について考えることができます。 .

編集

2 点 / 説明

1. 上記のコードは、認められた「マスター」プログラマーによって書かれています。男は片手でnginxを書きました。

2. リテラル ハードコーディングの可能なメカニズムのどれが優れているかは尋ねていません。したがって、話題を逸らさないでください。

編集 2

私の元の例は、非常に不自然で制限的でした。次のスニペットは、内部のハードコーディングされた知識に埋め込まれている文字列リテラルの使用法を示しています。最初のスニペットは、構成パーサーがどの文字列にどの列挙値を設定するかを伝えるためのものであり、2 番目のスニペットは、より一般的にプログラム内の文字列として使用されるためのものです。個人的には、コンパイラが文字列リテラルの 1 つのコピーを使用し、要素が静的であるため、グローバル シンボル テーブルに入らない限り、これで満足しています。

密接に続く:

話題にとどまった人たち、ブラボー！

コンパイラー理論のクラスでは、独自に設計したプログラミング言語用の単純なインタープリターを作成する任務を負っています。私はジェネレーターとして jflex と cup を使用していますが、字句エラーとは何かに少しこだわっています。また、jflex の状態機能を使用することをお勧めしますか? パーサーがその側面を処理するのにより適しているように見えるので、それは間違っているように感じます。また、言語を作成するための他のツールをお勧めしますか? せっかちで申し訳ありませんが、締め切りは火曜日です。

大学のプロジェクト用にコンパイラを書いています。抽象構文ツリーを制御フロー グラフ (CFG) に変換したいと考えています。

私は、CFGのノード ( V) は AST のノードであるべきだと考えています。私はエッジセット ( G=(V,E)) を構築する方法をアルゴリズム的に知っていますが、プロセスをもう少し形式的に書くのに苦労しています

この scala スタイルのパターン マッチング (疑似) を作成しました。

次のような AST 構造に一致する必要があります。

次のようなエッジセットを提供します。

ドットソース

これをスカラ「疑似コード」よりも少し形式的に行う方法についてのヒントはありますか?

私は次のような帰納的なことを考えています:

（ただし、上記はツリーのみを提供し、グラフは提供しません。たとえば、then-branch のエッジから次のステートメントへのエッジはありません）

編集：

私はkiama とscala のデータフローについて調べてきましたが、彼らが使用する「成功」と「フォロー」のアプローチが気に入っています。それにもかかわらず、私はそれをより正式な説明に煮詰めるのに苦労しています。これは主に、正式に指定しようとすると見苦しくなる詳細の一部を隠す気の利いchildAttrたのせいです。s.next

EDIT2：

私は Dragon Book と「Modern Compiler Implementation in ML」、およびLearning to write a compilerの他の資料のいくつかを読み、一部/ほとんどがデータ フローと制御フローについて言及していますが、作成方法についてはあまり触れていません。正式な方法でCFG。

EDIT3：

Kiamaの著者、准教授である Tony Sloane 博士から、検索するための追加の参考文献をいくつか受け取りました。

私が見ることができる限り、それらの本によると「それを行う方法」は、ASTよりもプログラムの「ステートメントごと」に基づいており、基本ブロックに基づいています。それにもかかわらず、素晴らしいインプット！

ドラゴンブックを読み始めたばかりですが、いくつかのステートメントを理解するのが難しいと感じています。

「字句解析プログラムは、ソースプログラムの各語彙素のトークンのシーケンスを生成します」と書かれています。上記の行を理解するのを手伝ってもらえますか？トークンと語彙素については知っていますが、語彙素ごとに複数のトークンを生成するとはどういう意味ですか....AFAIKLEXEME自体が単一のトークンを危険にさらします。

完全な見積もりは次のとおりです。

「コンパイラの最初のフェーズとして、字句解析プログラムの主なタスクは、ソースプログラムの入力文字を読み取り、それらを語彙素にグループ化し、ソースプログラムの各語彙素のトークンのシーケンスを出力として生成することです。」

上記の引用は、「字句解析器の役割」という見出しの下の第3章のセクション3.1からのものです。ページ番号は109です。