context-free-grammar - 在 Context Free Grammar 中，如何定义一对标签，例如 data？

Question

预期的语言是这样的:

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

我遇到的困难是如何指定以确保在一对标签中，开始标签和结束标签都具有相同的名称。
tag是长度小于 10 的 [a-zA-Z] 的组合。

<tag>data</tag>

Answer 1

tldr; BNF 和 EBNF 都不能以合理的方式表达这个 CFG。

考虑使用 EBNF 并明确 - 通过 EBNF 注释或外部上下文 - 要么:

在对生产中施加限制性规则，或；

介绍一种表示有限"template"非终结符集的方法。

根据使用情况，可能需要证明这些更改/限制仍然会产生 CFG。

(这个旧的前奏与非 CFG 相关，因为问题最初是这样写的。)

据我所知， <x>..</x>对于任意和未知的 x不是 CFL，因为 Context Free Grammar仅限于终端和非终端的有限集合。然而，根据上面的定义， 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 metasyntax forms可以用来正式描述这种语言，但不能用普通的 BNF/EBNF 来描述。