PLY：快速解析长列表项？

Question

我正在使用一个相对简单的解析器，叫做 PLY，其中有一个规则是这样的：

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

输入文件通常是简单的 thing 列表，所以解析过程并不复杂。不过，有些输入文件非常大（经常超过100,000行，极端情况下甚至超过1,000,000行）。通过性能分析（使用 cProfile 和 pstats），我发现大部分运行时间都花在了重复调用 p_things 上——可以推测每个 things 列表中的每个项目都要调用一次。

有没有办法来减少这个时间，或者更有效地构建这个规则？我看到的大多数答案（以及我找到的权威编译器信息）都把这种方法列为构建可解析项目列表的普遍接受方式，无论列表有多长。

Answer 1

总结一下：

• 性能问题其实和解析器本身没关系，而是和使用 += 有关。
• 为了让 LALR(1) 解析器更好用，尽量让右侧的表达式不模糊。
• 如果可以的话，最好把规则拆开，避免在规则中使用不必要的选择语句（比如 if 语句）。

为了更好地理解 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]

Answer 2

如果不想改动你的代码，可以试试使用“PyPy”这个版本的Python。它有一种叫做即时编译的技术，可能会让你的代码运行得比普通的CPython快很多。

Answer 3

看来我忘记了一些基本的编译器理论。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%的原来时间。