python - Pyparsing packrat会降低性能

Question

我正在寻找一种改进使用pyparsing构建的解析器性能的方法。我阅读了关于packrat的解析，看来这确实可以帮助解析器提高性能。但是，当我启用packrat解析时，性能会变差！如果没有packrat，则解析20 MB文件大约需要2分钟。启用packrat后，它需要花费2-3倍的时间。我读到packrat的parseActions可能有问题，所以我从语法中删除了所有parseActions，以查看packrat能否提高其性能，但这也无济于事。我尝试了不同的缓存大小限制（无限制，范围在100-1000之间），但是当启用packrat时，所有这些方法反而会降低解析器的性能。

设置packrat的cache_size_limit是否有经验法则？是否有任何语法结构限制了packrat解析的使用或解释了为什么我的解析器的性能变得更差？

Answer 1

不管如何，一个20MB的文件都需要一些时间来进行pyparsing，但是有些构造可能会减慢您的速度。

当我们重新执行packrat解析以将OrderedDict用于缓存时，我对缓存大小进行了一些不同值的测试。结果表明，默认值128仅比无限制的缓存低1-2％，在内存和性能方面均取得了巨大的成功。因此，如果大于200或300的值在缓存搜索和内存管理方面付出代价的同时，对缓存有很大帮助，我会感到惊讶。

通过在输入字符串的相同位置重新访问相同的表达式来获得高速缓存命中时，Packrat解析最有效。重要的是，它是完全相同的表达式，而不仅仅是等效的表达式。例如，如果您有以下内容：

Literal("A") + Optional("," + Literal("B")) + Optional("," + Literal("C"))

分隔逗号的单独文字是不同的表达式，因此不会是缓存命中。相反，如果您定义并重用单个表达式进行公共标点，则packrat解析中更有机会从缓存中查找其解析结果，而不用重新解析：

COMMA = Literal(",")
Literal("A") + Optional(COMMA + Literal("B")) + Optional(COMMA + Literal("C"))

最近，我一直在使用expr()语法创建expr的副本，以便不会在全局范围内意外更改诸如解析操作，空格设置等修饰符。这将防止表达式重用，因此，如果您有许多不需要的expr()实例，则只需重用基本的expr。还要注意，带有结果名称的表达式会隐式复制，因此请确保不要过度使用结果名称。

当使用infixNotation时，Packrat解析是最好的，尤其是当操作符优先级为6或更高时。 infixNotation生成的表达式可重复使用子表达式，而不是定义新的子表达式，因此它可以获得更好的缓存性能。

当您可以使用'|'时，可能会在Or中过度使用'^'运算符MatchFirst的运算符。当用于递归表达式（使用Forward）时，这可能特别昂贵。比较这两个表达式：

arith_operand = integer_expr ^ float_expr ^ variable_name ^ Keyword("pi") ^ Keyword("e")

通过使用“ ^”，将对所有表达式求值，然后选择最长的匹配项。特别是，如果解析“ 3.1416”，则必须这样做，因为前导“ 3”将匹配integer，但是较长的“ 3.1416”将匹配float_expr。但是我们也尝试匹配一个变量名，以及关键字“ pi”和“ e”，以确保没有匹配项。 （我们对variable_name和“ pi”和“ e”有相同的表达式掩盖问题，因为它们可能会作为可能的变量名匹配。）但是，如果更改为使用“ |”，则解析器将短路在第一场比赛。我们只需要注意解析顺序即可：

arith_operand = float_expr | integer_expr | Keyword("pi") | Keyword("e") | variable_name

也就是说，我们必须确保在匹配整数之前检查浮点数是否匹配，因为浮点数的前导部分可能会误认为是整数。

如果您有容易互斥的替代方案（例如一系列可能的关键字，由于它们的关键字性质，它们永远不会相互掩盖），那么您也可以根据一些可能的频率对它们进行排序。例如：

bad_expr = Keyword("xylophone") | Keyword("the") | Keyword("a")

在大多数非音乐应用程序中，它可能会成为性能损失。

在pyparsing的早期，我没有Regex类，因此我必须使用Combine(Word(nums) + "." + Optional(Word(nums)))之类的东西为实数定义一个表达式。只需使用Regex(r"\d+\.\d*")即可进行pyparsing的大量工作。通常，实数表达式是在给定的解析运行中使用并测试了数千次的真正的低级表达式，因此转换为Regex确实会有所收获。或使用pyparsing_common中的数字表达式之一，例如pyparsing_common.real或pyparsing_common.number。但是，您不需要太费力-pyparsing内部使用正则表达式使用Word和oneOf匹配表达式。

您还可以直接检查ParserElement.packrat_cache和ParserElement.packrat_cache_stats缓存和缓存统计信息。缓存状态是一个由两个元素组成的列表，元素0是缓存命中数，元素1是未命中数。您可以为重复的表达式定义调试操作，该操作将打印出缓存状态。您也可以使用Counter：Counter(str(key[0]) for key in ParserElement.packrat_cache)查找重复的表达式。通过str-表达式，它将有助于识别重复项。因此，您可以查看不同大小的缓存大小的缓存效率。

编辑：我的错误，ParserElement.packrat_cache中的缓存键上的迭代不起作用，缓存OrderedDict本身被隐藏，无法进行外部访问。