4

予想される言語は次のようになります。

<hat>Nike</hat><car>Toyota</car>...

難しいのは、タグのペア内で、開始タグと終了タグの両方が同じ名前になるように指定する方法です。

はtag、長さが 10 未満の [a-zA-Z] の組み合わせです。

<tag>data</tag>
4

2 に答える 2

1

tldr; BNFもEBNFも、このCFGを合理的な方法で表現することはできません。

EBNFを使用し、明示的に（EBNFコメントを介して、またはコンテキスト外で）次のいずれかを使用することを検討してください。

  1. 対生成に制限ルールを課す、または;
  2. 「テンプレート」非終端記号の有限集合を表す方法を紹介します。

使用法によっては、これらの変更/制限によってCFGが生成されるというプーフが必要になる場合があります。

（この古い前奏曲は、質問が最初に書かれたように、非CFGに関連しています。）

私の知る限り、文脈自由文法は終端記号と非終端記号の両方の有限集合に制限されている<x>..</x>ため、任意の未知数 xはCFLではありません。ただし、上記の定義により、そのセットに含まれることが保証されているわけではありません。x

ただし、少し余裕があれば、 EBNF表記に非公式の制限を追加できます。もちろん、これらはEBNF構文自体の外にあります。

Pair = "<" Tag^1 ">" Content "</" Tag^2 ">"  (* Where Tag^1 equals Tag^2 *)
Tag = .. (* If a finite set, this could still be converted to
            formal EBNF by rewriting the above Pair as all possible alterations
            as shown in the next section.
            Only small values of "finite" are reasonable to express. *)
Content = ..

ECMAScriptのような仕様には、CFGの外部、つまりEBNFの外部に存在する可能性のあるいくつかの制限が含まれています。

ただし、この言語がCFLの場合は、次のようなCFGで表すことができます。

Pair = HatTagPair | CarTagPair | .. (* All possible non-terminal Pairs *)
HatTagPair = "<hat>" Content "</hat>"
CarTagPair = .. (* And so on.
                   While it's technically possible to have non-terminals
                   A, B .. AA, AB .. and so on, this quickly
                   becomes very impractical in EBNF. *)

BNFもEBNFも、そのような繰り返しを正式に表す「速記」の方法はありません。「タグは、長さが10未満の[a-zA-Z]の組み合わせです」は、妥当な有限の端末セットではありませんが、有限であり、したがってCFGの領域内にあります。

そのような言語を正式に記述するために使用できる他の CFGメタ構文形式があるかもしれませんが、単純なBNF/EBNFではありません。

于 2012-09-13T01:05:04.250 に答える
0

XML の EBNF は次の とおりです。

element ::= EmptyElemTag | STag content ETag

しかし、それらを同じに保つためには、字句解析戦略で定義されたかなり先のことを考える必要があると思います。関連する SO 投稿bnf/ebnf for xml schemaは、CFG の目標をやめて、コードでより基本的なアプローチを取る方がよいことを示唆しています。とは言っても、世の中にある多くの XML パーサーが実際にどのように機能しているかはわかりません。

于 2012-09-13T00:51:04.003 に答える