EBNF を使用して Context Free Grammar を表現できることは理解していますが、この 2 つに違いはありますか?
EBNF を CFG に変換するように求める質問があるので質問していますが、私の現在の理解では、それらは同じように見えます。したがって、この変換の背後にある意図は何ですか?
2779 次
3 に答える
3
概要: EBNF は CFG 形式と直接同等ではありませんが、多くの EBNF 文法は機械的に変換できます。
文脈自由文法は、次の 4 つのタプルです。
非終端記号のセット
Vから切り離された端子 Σ の集合
Vフォームのプロダクションのセット
v → ω
wherevは の要素でVあり、ωは(つまり、端末と非端末の空の文字列の可能性がある) の要素です。(V ⋃ Σ)*
Sの要素である開始記号V。
(ウィキペディアの記事とその参考文献を参照してください。非終端記号のセットとと の結合でVあるアルファベットを使用する別の同等の形式があります。)AVΣ
AlgolCFG の初期の具体的な構文は、プログラミング言語を記述するために、1959 年に John Backus によって提案されました。この形式主義は一般に と呼ばれBackus-Naur Form、Algol レポートの共著者である Peter Naur の貢献を認めて、Donald Knuth によって提案された名前です。BNF と上記の CFG 形式との主な違いは、共通の左辺を持つプロダクションが|記号を使用して省略されることです。
v → ω1 | ω2
⇒<br/>
v → ω1
v → ω2
ただし、実際には、通常の演算子、特に Kleene Star のような繰り返し演算子を使用すると、記述と理解がはるかに簡単になることが証明されています。BNF への多くの拡張が提案され、さまざまな文法で、特に Niklaus Wirth によって使用されました。特に、RFC (IETF インターネット標準) とさまざまな ISO 標準の両方の標準プロトコル ドキュメントで拡張 BNF の形式を使用することが一般的になりました。これらの形式は最終的に、拡張 BNF、ISO/IEC 14977およびやや類似した拡張 BNF、RFC-5234として「標準化」されました。
EBNF を CFG 形式に変換するためには、反復 (有限反復を含む)、代替およびオプション演算子のすべての使用をプリミティブ形式に拡張する必要があります。これには、新しい非終端記号の導入が必要です。また、EBNF と ABNF の両方とも、英語で書かれた制限を含め、CFG に変換できない可能性がある仕様を許可します。( Ebnfに対する私の回答の最初のメモを参照してください– Is this an LL(1) grammar? )
于 2014-02-02T17:23:19.580 に答える