Chomsky normal formをBackus–Naur Formに変換するソフトウェアがあれば教えてください。文脈自由文法変換
文脈自由文法変換
答えて
まあ、チョムスキーノーマルフォームとバッカス - ナウアフォームは、まったく同じ種類のコンセプトではないので、私は本当にそうは思わない。しかし、あなたがこのソフトウェアを必要としていることを教えてくれたら、私たちは手伝ってくれるかもしれません。
あなたが尋ねたところから、私はあなたがChomsky Normal FormにBNF文法を正規化するためのある種のコードを必要としていると仮定しています。私が知る限り、そのようなソフトウェアは存在しませんが、計算上実現可能なタスクであると仮定して、存在する可能性があります。
しかし、実際に必要なことについてさらに具体的に説明できる場合は、そのタスクに関する有用なアドバイスを提供することができます。
EDIT:私の本で少し掘り下げた後、任意のCFGをChomsky Normal Formに変換するアルゴリズムを定式化することが可能であることが判明しました。私は実際のアルゴリズムやその複雑さを持っていません。
あなたの補正書(編集)とウィキペディアのリンクで読んだことは、CNFはBNFの制限的なケースだと思います。すべてのCNF文法はBNFにあります。 BNF内の任意のCFGをCNFに変換することは、おそらく完全に自明ではない(導入された多くの非終端端末)が、実行可能であると思われる。 –
並べ替えCNFはCFGの制限ですが、BNFはCFGをエンコードする方法です(NはNormalではなくNaurです)。しかし、CFGをコード化する他の方法があります。たとえば、Wikipediaの記事の矢印表記です。 BNF(およびその子孫)は、コンピューティングで最も一般的な方法です。 – arnsholt
http://qntm.org/chomskyはCFGからCNFへの変換(PHPで)を実装しているようです。 –
- 1. NLTK文脈自由文法
- 2. 文脈自由文法の解析
- 3. 文脈自由文法のアルゴリズム
- 4. 文脈自由文法 - 計算理論
- 5. 文脈自由文法と逆転
- 6. NLTK文脈自由文法の制作
- 7. 正規表現を記述する文脈自由文法?
- 8. Cのための文脈自由文法
- 9. 音声認識用文脈自由文法を作成する
- 10. ネストと不等式を持つ文脈自由文法
- 11. 文脈自由文法の一部大きな謎
- 12. 文脈自由文法の左回帰規則
- 13. Chomsky Normal Formで文脈自由文法を構築する
- 14. 文脈自由言語の連合
- 15. 文脈自由文法を残す方法を教えてください。
- 16. 文脈自由へのプッシュダウンオートマトン:それを行う方法?
- 17. 文脈自由文法と対応するPDAを取得するには?
- 18. 次の言語のための文脈自由文法を書く
- 19. 文脈依存文法
- 20. PHPは完全に文脈自由言語ですか、文脈依存部分を持っていますか?
- 21. 文脈自由パーサー文法を作成するための対話型ユーティリティーを探してください
- 22. Pythonで内部DSLとして文脈自由な設計文法を表現するには?
- 23. 文脈自由文法を左と右の再帰的にすることができますか?
- 24. 任意の正規表現から文脈自由文法を生成するアルゴリズム
- 25. 文脈自由文法を書くにはどうすればいいですか?
- 26. OpenGL文脈紛失
- 27. 変換文法の問題
- 28. Railsアクティブレコード変換:自動大文字/小文字?
- 29. 文脈に応じたスペリングエンジン
- 30. Dojoチャートの文脈メニュー・アクション
申し訳ありませんが、間違っています。 BNFは一般的なCFGの表記ですので、「すべてのCFGはチョムスキー標準形になっています」と同じです。ここでの要点は、チョムスキー標準形式では、すべての非終端プロダクションがRHS上に2つの非終端記号しか持たないことです。 – arnsholt
私は訂正しました。私は次のように読んでいます。 "チョムスキー正規形のすべての文法は文脈自由であり、逆に、文脈自由文法はすべて、チョムスキー正規形の同等の文法に効率的に変換することができます。間違った結論に達しました。 –