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 回答