8

我正在使用一个相当简单的解析器PLY，我的规则之一采用以下形式：

def p_things(p):
    '''
    things : thing things
    things : thing
    '''
    p[0] = [p[1]]
    if len(p) == 3:
        p[0] += p[2]

输入文件通常是简单的things 列表，因此解析本身并不复杂。然而，我的一些输入文件非常大（经常超过 100,000 行，在极端情况下超过 1,000,000）。在分析中（通过cProfile 和 pstats），运行时的大部分时间都被重复调用占用p_things——大概是对列表中每个项目的调用things。

有没有办法减少这个时间，或更有效的方式来构建这个规则？到目前为止，我看到的大多数答案（以及我发现的规范编译器信息）都将此方法列为构造可解析项列表的公认方法，无论长度如何。

4

3 回答 3

10

原来我忘记了一些基本的编译器理论。PLY 是一个 LALR(1) 解析器，因此最好将规则编写为：

def p_things(p):
    '''
    things : things thing
    things : thing
    '''
    if len(p) == 2:
        p[0] = [p[1]]
    else:
        p[0] = p[1]
        p[0].append(p[2])

尽管它可能看起来更冗长，但实际上有一个显着的改进 - 在 PLY 或 Python 的某个地方，解析器能够对左递归形式应用一些优化。我已经看到较大的输入文件的性能从指数下降到线性；一个样本，things列表中有超过一百万个项目，运行时间不到 20%。

于 2011-06-21T18:21:30.277 回答
0

在不更改代码的情况下，您可以尝试使用带有即时编译的“PyPy”版本的 python——它可能比普通的 CPython 更快地运行您的代码。

于 2011-06-20T20:39:46.700 回答
0

所以总结一下：

  • 性能问题与解析器本身无关（但使用+=）
  • 通过使 RHS 明确，使 LALR(1) 解析器的事情变得更容易。
  • 如果可能，最好通过拆分规则来避免在规则中不必要的选择语句 (ifs)。

为了更好地理解Ioannis Filippidis 的评论，实际可视化它更容易。这就是我认为的意思，也是我最终的结果。

def p_things_iter(p):
    '''
    things_iter : things thing
    '''
        p[0] = p[1]
        p[0].append(p[2])

def p_things_end(p):
    '''
    things_iter : thing
    '''
    p[0] = [p[1]]

def p_things(p):
    '''
    things : things_iter
    things : things_end
    '''
    p[0] = p[1]
于 2019-08-09T14:31:16.837 回答