問題タブ [formal-languages]

私はパーサーとパーサージェネレーターについて読んでいて、ウィキペディアのLR解析ページでこのステートメントを見つけました：

多くのプログラミング言語は、LRパーサーのバリエーションを使用して解析できます。注目すべき例外の1つはC++です。

なんでそうなの？C ++のどの特定のプロパティにより、LRパーサーで解析できなくなりますか？

グーグルを使用して、私はCがLR（1）で完全に解析できることを発見しただけですが、C ++はLR（∞）を必要とします。

Perl 正規表現エンジンの機能の一部が正規ではないことを知っています。しかし、それは何のクラスですか？文脈にとらわれないかもしれませんが、CS 理論は私の最強のテーマではありませんでした。

再帰集合と再帰関数の違いは何ですか？

正規表現間のある種の距離を計算できますか？

アイデアは、2つの正規表現がどのように類似しているかを測定することです。

次の言語を決定するための文法またはオートマトンを見つけるのを手伝ってください。

a ⁿ b ⁿ c ⁿここで、n≥1

プログラムのコール スタックを見て、各リターン ポインターをトークンとして扱う場合、プログラムの有効な状態の認識機能を構築するには、どのような種類のオートマトンが必要ですか?

当然のことながら、特定のバグ状態の認識機能を構築するには、どのようなオートマトンが必要ですか?

(注:この関数から取得できる情報のみを見ています。)

私の考えでは、これらが通常の言語を形成する場合、それを中心にいくつかの興味深いツールが構築される可能性があります。たとえば、一連のクラッシュ/障害ダンプが与えられた場合、それらを自動的にグループ化し、既知のバグの新しいインスタンスを識別するためのレコグナイザーを生成します。

注: これは診断ツールとしてではなく、大量のクラッシュ レポートをより便利なものに変えるためのデータ管理ツールとして提案しています。

• 「これらの 54 回のクラッシュは、42 回のクラッシュと同様に関連しているようです。」
• 「これらの新しいクラッシュは、日付 X 以前のものとは何の関係もないようです。」
• 等

私が何を達成しようと考えているのかが明確ではないように思われるので、以下に例を示します。

3 つのバグがあるプログラムがあるとします。

• 無効な引数が 1 つの関数に渡され、同じサニティ チェックをトリップさせる 2 つのバグ。
• (有効な) コーナーケースが与えられた場合、無限再帰に入る関数。

また、プログラムがクラッシュすると (アサートの失敗、キャッチされない例外、seg-V、スタック オーバーフローなど)、スタック トレースを取得し、その上の呼び出しサイトを抽出して、QA レポート サーバーに送信します。(1.プロジェクトごとに1回の費用で簡単に取得できること、2.プログラムに関する特別な知識がなくても使用できる単純で明確な意味があるため、その情報のみが抽出されると仮定しています)

私が提案しているのは、着信レポートを既知のバグの 1 つに関連するものとして (または新しいバグとして) 分類しようとするツールです。

最も単純なことは、1 つの障害サイトが 1 つのバグであると仮定することですが、最初の例では、2 つのバグが同じ場所で検出されます。次に簡単なのは、スタック全体が一致するように要求することですが、2 番目の例のように、同じバグを引き起こす可能性のある (有効な) 有効なコードが複数ある場合、これは機能しません。

shift-reduce 解析について学習しようとしています。ANSI C Yacc grammarに触発された、操作の順序を強制する再帰規則を使用する次の文法があるとします。

そして、shift-reduce 解析を使用して 1+2 を解析したいと考えています。まず、1 が NUMBER としてシフトされます。私の質問は、P、次に M、次に A、最後に S に還元されるのかということです。どこで停止するかをどのように知るのですか？

それが S までずっと還元され、それから '+' をシフトするとします。これで、以下を含むスタックができました。

「2」をシフトすると、リダクションは次のようになります。

ここで、最後の行のどちらかの側で、S は P、M、A、または NUMBER である可能性があり、任意の組み合わせがテキストの正しい表現であるという意味で有効です。パーサーはどのようにしてそれを「知る」のですか

式全体を A、次に S に還元できるようにするには? 言い換えれば、次のトークンをシフトする前に削減を停止することをどのように知るのでしょうか? これは LR パーサー生成における重要な問題ですか?

編集：質問への追加は次のとおりです。

を解析するとします1+2*3。一部のシフト/リデュース操作は次のとおりです。

これは正しいですか (確かに、まだ完全には解析されていません)? さらに、1 シンボルによる先読みは、 を読み取った後に避けられない構文エラーが発生するため、に還元A+Mしないことも教えてくれますか?A*3

プログラミング言語が正式なプログラミング言語であるとはどういう意味ですか? また、どの言語が正式なプログラミング言語ですか? また、非公式のプログラミング言語はどれですか?

私はまだ良い説明を見つけていません。

プログラミング言語に関連するチョムスキー階層のいくつかの側面を学ぼうとしていますが、まだドラゴンブックを読まなければなりません。

ほとんどのプログラミング言語は文脈自由文法 (CFG) として解析できると読みました。計算能力に関しては、プッシュダウン型の非決定性オートマトンに匹敵します。私は正しいですか？

それが本当なら、チューリングが完了している無制限文法 (UG) を CFG がどのように保持できるのでしょうか? プログラミング言語がCFGで記述されていても、実際にはチューリングマシンを記述するために使用されているため、UGを介して質問しています。

それは、少なくとも 2 つの異なるレベルのコンピューティングによるものだと思います。1 つ目は CFG の解析であり、言語の構造 (表現?) に関連する構文に焦点を当て、もう 1 つはセマンティック (意味、解釈) に焦点を当てています。チューリングが完了しているプログラミング言語の機能に関連しています。繰り返しますが、これらの仮定は正しいですか?

チョムスキーのヒエラルキーでは、再帰言語のセットは定義されていません。再帰言語は再帰的に列挙可能な言語のサブセットであり、すべての再帰言語は決定可能であることを知っています。

私が興味を持っているのは、再帰言語が文脈依存言語とどのように比較されるかということです。文脈依存言語は再帰言語の厳密なサブセットであり、したがってすべての文脈依存言語は決定可能であると仮定できますか?