4

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

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

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？

4

3 回答 3

3

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

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

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

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

等等。所以要做你想做的事，你只需要一个包含那种规则的语法，N你可能需要的一切。

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

编辑，因为您还询问了上下文相关的语法：那仍然不会这样做。问题在于整数算术的使用，而不是语法的类。Chomsky 层次结构上的任何形式语言都是根据有限数量的符号（令牌）定义的，并且由于是无限多的整数，它们不能被赋予不同的含义（请注意，您的解析过程依赖于整数算术）。

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

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

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

于 2012-04-05T15:38:38.490 回答
3

Pyparsing 包括countedArray完全按照您的要求执行的助手。它接受一个参数expr，并将解析一个整数，后跟“n”个 expr 实例。对于您的输入字符串，您可以编写：

from pyparsing import *
from pprint import pprint

# make a long string of integers, starting at 0
source = ' '.join(map(str, range(50)))

# define an integer as a 'word' of numeric digits
integer = Word(nums)

# add a parse action to convert the parsed strings to integers, at parse time
integer.setParseAction(lambda t:int(t[0]))

# parse the source string into counted strings of integers, and print out
# with pprint
lists = OneOrMore(countedArray(integer)).parseString(source)
pprint(lists.asList())

打印出来：

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

  • 附加的解析操作integer将数字字符串转换回整数（列表中的数字没有引号）。

  • 注意开头的空列表，它是由源字符串的前导“0”创建的。

  • 即使源字符串包含超过 30 的更多数字，也不足以容纳另一个计数数组。

countedArray通过创建一个与前导整数匹配的表达式，后跟一个捕获的未定义正向表达式来实现此技巧。附加到前导整数的解析操作将expr*n表达式注入到强制转发中，然后解析以下“n”表达式。您可以轻松编写countedArray(Word(alphas))和解析"4 the quick brown fox"以获取['the', 'quick', 'brown', 'fox']. 正如@Aaron 在他的回答中指出的那样，没有必要保留前导计数器，因为您可以通过获取返回列表的 len 轻松获得它。

pyparsing 还支持使用 FollowedBy 和 NotAny 构造的更传统的前瞻（NotAny 可以通过使用'~'运算符来缩写）。在这个字符串“Four score and 7 years ago...”中，您可以使用 挑选出后面跟着以元音开头的单词的字符串Word(alphas) + FollowedBy(Word('aeiou',alphas))，这将匹配 'score' 和 'years'；或者后面没有使用句Word(alphas) + ~Literal('.')点的单词，这将匹配除“之前”之外的每个单词。在这种情况下，尝试通过输入字符串搜索匹配项，您可以使用searchStringorscanString代替parseString.

于 2012-04-06T03:03:17.953 回答
1

并不真地。

拥有语法的全部意义在于它允许以人类可以理解的方式定义数据。您的演示字符串是可读的，但为什么1除了3?

在您的情况下，正确的输入是：

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

语法看起来像这样：

<model> :: <term>
<list>  :: <term> | <term> <opt-whitespace> <list>
<term>  :: '[' <list> ']'

然后，您可以通过查看列表的长度来恢复丢失的计数元素。

于 2012-04-05T15:46:26.613 回答