python - 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 and pstats )，大部分运行时间被重复调用 p_things 占用 - 大概是对 things 列表中的每个项目调用一次。

有没有办法减少这个时间，或者有更有效的方法来构建这个规则？到目前为止我看到的大多数答案(以及我找到的规范编译器信息)都将此方法列为构建可解析项列表的普遍接受的方法，无论长度如何。

Answer 1

原来我忘记了一些基本的编译器理论。 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 列表中有超过 100 万个项目的样本在不到 20% 的时间内运行。