問題タブ [chomsky-hierarchy]

プログラミング言語を解析したい。形式言語、チョムスキー階層、ANTLR についてよく読んでいます。しかし、言語 ANTLR v3 を LL(*) 再帰降下パーサーが受け入れるようにチョムスキー階層に関連付ける方法に関する情報を見つけることができませんでした。

チョムスキー型はどのように LL(*) と混ざりますか? あらゆる情報 (オンライン、本、論文) は大歓迎です。

編集:構文/意味述語とANTLRのバックトラッキングはこれにどのようにマップされますか?

私は現在、チョムスキーのヒエラルキーと、ヒエラルキーの各レベルを認識するオートマトンのタイプを学習する離散数学テストの勉強をしています。ほとんどのコンピューター言語は階層の「レベル 2 と 1」に分類されると教えられていますが、正確にはそうではありません。

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

1. 各レベルに属する機能は?

2. これは理論的根拠にすぎませんか？Dennis Ritchie や James Gosling のような言語設計者は、C や Java を設計する際にこの点を考慮する必要があったのではないかと思います。彼らは？誰かがこれをどのように適用しますか?

3. チューリング マシンは階層のレベル 0 を認識していると言われています。もしそうなら、レベル0に属する言語機能はありますか? これはもしかしたら自然言語処理なのかもしれませんね。

標準は公式の C++ 文法を指定していますか?

探しましたが、どこにもありませんでした。

また、どのカテゴリの文法に該当するかなど、C++ の文法について詳しく読みたいと思います。正しい方向に私を指すリンクは役に立ちます。

カテゴリ別に言うと

ここ から撮影。

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

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

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

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

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

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

チョムスキー階層を読んでいます... ... 正規表現がタイプ 2 文法 (文脈自由文法) を解析できないことは知っています。また、タイプ 1 とタイプ 0 も解析できません。正規表現はすべてのタイプ 3 文法 (正規文法)を解析/キャッチできますか?

入力文字列が特定の言語仕様に対して有効かどうかをチェックする関数を作成する必要があります。これは標準のCFG->チョムスキー標準形、次にCYK解析になると思いましたが、言語の規則の1つは、これが起こらないようにすることです。

いくつかのルールは単純です。端末を定義する{a,b,c,d,e,f,P,Q,R,S}と、有効な文字列は次のようになります。

1）分離された小文字の端子のいずれか
2）'x'が有効な文字列である場合、Sxも有効です。

しかし、3番目のルールは

3）XとYが有効な入力文字列である場合、PXY、QXY、RXYも有効です。

ここで{P,Q,R}、は残りの大文字の終端記号であり、XとYは非終端記号です。

このための制作ルールはどのようになりますか？こんな感じになると思いました

しかし、これには2つの問題があります。1つ目は、これはCFG規則ではないということです。つまり、この言語は代わりにCSGを定義するということですか？

そして2つ目は、これが機能しないことです。

XY-> PXY-> PPXY

すべての場合に有効なメッセージではありません。

私は4つの異なるチョムスキー言語タイプを理解しようとしていますが、私が見つけた定義は私にとって実際には何の意味もありません。タイプ0は自由文法、タイプ1は文脈依存、タイプ2は文脈自由、タイプ3は通常です。それで、誰かがこれを説明して、それを文脈に入れてくれませんか、ありがとう。

チョムスキー タイプ 2 (文脈自由言語) とチョムスキー タイプ 3 (正規言語) の違いをうまく説明できません。

誰かが平易な英語で答えてくれませんか? 階層全体を理解するのに苦労しています。

フォーマル言語のチョムスキー分類では、Non-Linear, Unambiguous and also Non-DeterministicContext-Free-Language(N-CFL) の例が必要ですか?

1. 線形言語:線形文法が可能なもの ( ⊆ CFG) 例:
   L ₁ = {a ⁿ b ⁿ | n ≥ 0 }

2. Deterministic Context Free Language(D-CFG) : Deterministic Push-Down-Automata(D-PDA) が可能な言語 (例:
   L ₂ = {a ⁿ b ⁿ c ^m | n ≥ 0, m ≥ 0 }
   L ₂は明確です。

線形でないCF 文法は非線形です。
L _nl = {w: n _a (w) = n _b (w)} も非線形 CFGです。

-- 3. Non-Deterministic Context Free Language(N-CFG) :only Non-Deterministic Push-Down-Automata(N-PDA)可能な例
L ₃ = {ww ^R | w ∈ {a, b} ^* }
L ₃も Linear CFG です。

--4. あいまいな CFL : only ambiguous CFG is possible
L ₄ = { a ⁿ b ^{n cm} | n ≥ 0, m ≥ 0 } U { a ⁿ b ^{m cm} | n ≥ 0, m ≥ 0 }
L ₄は非線形かつ曖昧な CFG であり、すべての曖昧な CFL \subseteq N-CFL.

私の質問は次のとおりです:
すべての非線形、非決定論的 CFL は曖昧ですか? そうでない場合は、非線形で非決定論的な CFL であり、明確な例が必要ですか?

以下にベン図を示します。

ここでも質問