2

目标：找到一种正式定义语法的方法，该语法以任意顺序识别集合中的元素 0 或 1 次。随后，我想解析它并生成一个 AST。

例如：假设我的语言中的有效字符串集是{A, B, C}. 我想定义一个语法来识别任意数量的这些元素的所有有效排列。

语法上有效的字符串包括：

  • （空字符串）
  • A,
  • B A， 和
  • C A B

语法上无效的字符串包括：

  • A A， 和
  • B A C B

需要明确的是，在 CFG 中明确定义所有可能的排列对于我的目的是不可接受的，因为无法维护更大的集合。

据我了解，这种语言无法满足上下文无关语言的引理，因此该解决方案将不是上下文无关的或常规的。

更新

我所追求的被称为“置换语言”，Benedek Nagy作为上下文无关语言的扩展做了一些理论工作。

关于解析器生成器，我只发现了关于使用置换阶段（链接）实现解析器的讨论。解析器显然对生成的 CFG 的大小有一个指数下限，而且我还没有找到任何支持它的解析器生成器。

这个问题的一种解决方案是用 ANTLR 编写的。它使用语义谓词来“围绕”问题进行编码。

4

1 回答 1

1

假设备用字符串的集合是固定的并且事先已知，例如大小为n，则可以提出大小为O(n!)的（非上下文无关的）语法。这并不比枚举所有排列渐近地小，所以我认为它不能被认为是一个好的解决方案。我相信这种语法可以重新表述为上下文相关的语法（尽管我在下面建议的形式不是）。

对于{a, b, c}问题中提到的示例，一种这样的语法如下。按照惯例，我对终端符号使用小写字母，对非终端使用大写字母。 S是初始的非终结符。

S ::= XabcY
XabcY ::= aXbcY | bXacY | cXabY
XabY  ::= ab | ba
XacY  ::= ac | ca
XbcY  ::= bc | cb

非终结符X并将Y子字符串包含在尚未最终确定的产生式中；X这个子字符串最终将被和之间给出的终端的排列替换Y（以某种任意顺序）。

于 2013-08-26T21:24:36.423 回答