python - BNF 可以处理远期消费吗？

Question

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

Pyparsing 可以实现 BNF ( Backus–Naur Form ) 上下文无关语法。这个文法可以递归，但是能不能有前瞻性呢？自从我偶然发现 this question 以来，我一直在想这个问题的答案。 .让我给你一个具体的例子。考虑字符串:

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]]

我已经使用 pyparsing 编写了一个简单的 python MWE 不，所以很清楚我想做什么:

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 来实现？

Answer 1

在上下文无关语法或常规语法中没有参数化大小这样的东西。像您的consume 这样的数值参数不是CFG 模型的一部分，可以证明以不同的方式获得效果是不可能的。不过，您可以为任何固定 长度编写产生式，因此您可以为长度为 1、长度为 2、长度为 3 等的 block 编写产生式:

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

或者，类似地，匹配长度作为前缀甚至作为后缀:

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

等因此，要执行您想要的操作，您只需要一个包含此类规则的语法，对于您可能需要的所有 N。

给定的 CFG 将仅包含有限数量的此类作品。在数学上不可能编写可以处理无限参数化大小的 CFG(以 BNF 或任何其他形式)，无论是作为前缀还是作为后缀。实际上，您可以根据需要使用新作品即时更新您的 CFG。例如，读取一个数字 N 并为您的语法创建一个规则 blockN(如果它不存在)。但是没有单个 CFG 可以捕获无限制的参数化大小。

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

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

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

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