PLY:快速解析长项列表？

Question

我在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列表中的每个项目进行一次调用.

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

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列表中有超过一百万个项目,在不到20%的时间内运行.