BNF 可以处理远期消费吗？

最近我发现了 python 模块pyparsing，一个通过编写来解析数据的绝佳工具grammar，而不是解析器。我对上下文无关语法的概念很陌生，所以请纠正这个问题中的任何错误假设。

Pyparsing 可以实现 BNF (巴科斯-诺尔范式 http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form) 上下文无关语法。这个文法可以是递归的，但是它能有前瞻功能吗？自从我偶然发现这个问题以来，我一直想知道这个问题的答案这个问题 https://stackoverflow.com/questions/9898984/parsing-xdot-draw-attributes-with-pyparsing。让我给你举一个具体的例子。考虑字符串：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

让语法看起来像这样：

<number> :: __<digit>__
<block>  :: <number>(x) (<number> <number> <number> .... x times)

即读取第一个数字令牌，将其另存为x然后消费下一个x数字并将它们分组在一起。解析后的行应如下所示：

 [[1, 2], [3, 4, 5, 6], [7, 8, 9, 10, 11, 12, 13, 14], [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]]

我写了一个简单的 python MWEnot使用 pyparsing 所以很清楚我想要做什么：

A = range(1,31)

B, sub_b = [], []
consume  = 0

for a in A:
    if consume: 
        sub_b.append(a)
        consume -= 1
    else:
        if sub_b: B.append(sub_b)
        sub_b = [a,]
        consume = a
B.append(sub_b)
print B

两个（相关的）问题：这可以用 BNF 上下文无关语法来完成吗？如果是/否我该怎么做pyparsing?

在上下文无关语法中，或者在常规语法中，不存在参数化大小这样的东西。像你这样的数字参数consume不是CFG模型的一部分，可以证明用不同的方式得到效果是不可能的。您可以为任何内容编写作品fixed但是，您可以为长度为 1、长度 2、长度 3 等的块编写产生式：

<block3> :: <number> <number> <number>

或者，类似地，将长度作为前缀甚至后缀进行匹配：

<block3a> :: 3 <number> <number> <number>
<block3b> :: <number> <number> <number> 3

因此，要做你想做的事，你只需要一个包含此类规则的语法，对于所有N你可能需要。

给定的 CFG 将仅包含有限数量的此类产品。从数学上来说，编写一个可以处理无限参数化大小的 CFG（以 BNF 或任何其他形式）是不可能的，无论是作为前缀还是作为后缀。在实践中，您也许可以根据需要使用新作品动态更新您的 CFG。例如，读取一个数字N并创建一个规则blockN对于您的语法（如果尚不存在）。但没有single可以捕获无界参数化大小的 CFG。

Edit,因为您还询问了上下文相关语法：那仍然不行。问题在于整数运算的使用，而不是语法的类。Any乔姆斯基层次结构上的形式语言是根据有限数量的符号（标记）来定义的，并且由于整数有无限多个，因此不能为它们分配不同的含义（请注意，您的解析过程依赖于整数算术）。

如果您要将长度预处理为包含尽可能多的星星的序列（* * * 4 7 10），CFG 解析器很简单：

<group> :: * <group> <number>
<group> :: * <number>

这就是所谓的a^n b^n语言。您还可以使用表示“十”等的符号。但是如果没有预处理，唯一的解决方案（以及您的程序或图灵机在实践中所做的）就是解释语法中的数字符号。例如，将“21”解析为十十一。我怀疑这可以在 CFG 中完成（问题是处理任意长的数字，而没有针对数百万、数十亿等的单独规则），但我不太确定。不管怎样，它只是作为一种学术练习才有趣，因为使用实整数要容易得多。我确信人们已经研究了带有整数的形式语言的属性，但我不能对此说什么。