请不要在这里回答，而是在 cstheory.stackexchange，我将这个问题复制到！
JSON 和 XML 都经常被称为上下文无关语言——它们都主要由 EBNF 中的形式语法指定。然而，这仅适用于RFC 4329 第 2.2 节中定义的 JSON，它不需要对象键的唯一性（许多人可能不知道，但 {"a":1,"a":2} 是有效的 JSON！）。但是，如果您需要 JSON 中的唯一键或XML 中的唯一属性名称，则无法通过上下文无关文法来表达。但是哪个是具有唯一键和格式良好的 XML 的 JSON 语言类（这意味着唯一的属性名称？）。
我在这个主题上找到的最好的论文之一（Murato et al, 2001: Taxonomy of XML Schema Languages using Formal Language Theory）明确排除了完整性约束，例如键/keyrefs 和要在附加层上检查的唯一性。除此之外，由 XML Schema 或 DTD 定义的 XML 子集是上下文无关的。但不是所有格式良好的 XML 文档的完整集。
我认为嵌套堆栈自动机（=索引语言）应该能够解析具有唯一键约束的 JSON。对于 XML 可以将问题简化为所有以逗号分隔的唯一整数列表的语言 S。有没有人知道更多，最好是引用？
PS：决定语言的简单算法（除了上下文无关部分）基于良好的排序算法。因此，在 O(n log n) 最坏情况下，它应该可以在“线性时间”中确定。我还没有发现复杂性类是例如“轻度上下文敏感”还是“索引”，但可能介于上下文无关和上下文敏感（？）之间。