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. 在 Pair 产生中施加限制性规则，或；
  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： http ://www.w3.org/TR/REC-xml/#sec-starttags将元素定义为以 STags 开头并以 ETags 结尾很容易：

element ::= EmptyElemTag | STag content ETag

但是至于保持它们相同，我认为您需要在词法分析策略中定义的超前思考。xml 模式的相关 SO 帖子bnf/ebnf表明最好放弃 CFG 的目标并在代码中采用更基本的方法。说了这么多，我不知道有多少 XML 解析器实际上是在做这件事。

于 2012-09-13T00:51:04.003 回答