問題タブ [language-theory]

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

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

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

言語の標準的な表現を持つと便利なことがよくあります (私の場合、それらは通常ドメイン固有の言語です)。ただし、関連する言語の表現力には厳密な制限があり、その言語の任意のプログラムに対して標準形式を決定および/または作成できるかどうかを決定するものだと思います。残念ながら、これについて読んだことを（漠然と）思い出した参考文献を見つけることができませんでした.

一方では、言語の正規表現を作成することは、多くのハード グラフの問題 (例: グラフ同形性) に匹敵する複雑さであると合理的に思われますが、他方では、iirc、gcc、yhc、および ghc などのコンパイラは中間表現を使用します。さまざまな形式（アセンブリ、JavaScriptなど）で出力を生成するため、これは少なくともいくつかの形式では解決済みの問題です。

特定の言語の正規形を決定/生成できるのはいつですか? (その言語はどの程度表現力があり、言語の表現力は正規形の有用性にどのように影響しますか?) 可能であれば、参照または証明を提供してください。

編集：たとえば、正規言語（例：正規表現の「純粋な」形式）は、チューリング完全言語が表現できるのと同じ多くのことを表現できません。つまり、通常の言語で Web サーバーを作成することはできませんが、ラムダ計算を使用すると作成できます)。私の質問は理論的な可能性に関するもので、複雑性理論に関連する具体的な答えがあります。別のシステムに送信する必要がある DSL がある場合、送信する前にそのコードの標準的な形式を生成すると、2 つの異なるシステムで使用される独立した表現が分離されるため、多くの場合有益です。 でも、それがP空間完全、またはチューリング完全言語を標準形式に変換するためのNP完全である場合、標準形式を構築しようとして時間を無駄にすべきではありません-それを行う別の方法を見つけるか、削減します多項式時間で正規化できる言語の複雑さ。

クラスでCだったときにC++を学びました。XML やガベージ コレクションなどの新しいテクノロジがますます嫌いになっていることに気付きました。その一方で、Lua や Python などのスクリプト言語を発見しました。そして、決定論的なメモリ制御、埋め込みスクリプト言語、ガベージ コレクションなどを備えた C++ のハイブリッド環境が好きであることがわかりました。

私の問題は、これらの言語を学ぼうとすると、ラムダ、クロージャーなど、よくわからない用語に直面することです。

高齢者が最新情報を入手するためのオンライン リソースには、どのようなものがありますか?

多重継承を C# または Java の次のバージョンに含める必要があるかどうかを常に尋ねる人を見かけます。幸運にもこの能力を持っている C++ の人々は、これは誰かに最終的に首を吊るすためのロープを与えるようなものだと言います。

多重継承の問題は何ですか？具体的なサンプルはありますか？

私のコンピューティング言語の理論のクラスでは、フロー制御用の while ステートメントのみを含む (if ステートメントを含まない) 言語でコードを実装するという宿題がありました。これは主に、while ループだけでチューリング完全な言語を記述できることを証明するためです。

言語の文法を理解できる人のために、言語のルールを次に示します。

これは私のクラス ノートからコピーしたものです。

実装するコードは次のとおりです。

いずれにせよ、先に進み、上記の言語規則を使用してそれを書きたい場合は、先に進んでください。それ以外の場合は、最も使いやすい言語で書いてください。ただし、いくつかの注意点があります。

• while ループ以外の if ステートメントやその他の種類のフロー制御はありません。
• チート禁止: 上記の文法には、break ステートメント、return ステートメント、または例外が含まれていません。それらを使用しないでください。

私はこれのためにコードを書きました (コードの投稿を見せてくれるものではないことを証明するために投稿します)。私はちょっと興味がありますが、他の誰かが思い付くことができます。

左辺値とは

このコードには、C# で動作しないという明確に定義された動作があります。

注：私はすでにその方法を知っているので、そのコードを修正する方法を尋ねていません

これの正当化は何ですか？C# では、静的メンバーへの最初のアクセスを検出するためのランタイム チェックが既に行われています。これをメンバーごとに拡張して、オンデマンドで実行したり、コンパイル時にコンパイラーに順序を理解させたりしないのはなぜですか?

ところで：同じ質問（またはほぼ同じ）が非静的メンバーにも当てはまると思います。

たとえば、オペレーティング システムを作成するときに、チューリング完全な言語では実現できない特定のことがありますか?

this/ self/meポインタを明示的に必須にする利点は何ですか?

OOP理論によると、メソッドは主に(のみ?)メンバー変数とメソッドの引数で動作するはずです。これに続いて、 (オブジェクトのビューの側から) 外部変数よりもメンバー変数を参照する方が簡単なはずです...明示的thisにすると、より冗長になり、外部変数よりもメンバー変数を参照するのが難しくなります。これは私には直感に反するようです。

私は PDA のテストのために勉強していて、次の言語を認識するプッシュダウン オートマトンを設計する方法を知りたいです。

n-mが より大きいかどうかを認識する遷移関数を設計するにはどうすればよい0ですか?

また、このレベルの演習問題が解決されたコース教材があれば、リンクを貼ってください。