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 s, поэтому сам синтаксический анализ не является сложным. Однако некоторые из моих входных файлов очень велики (довольно часто превышают 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% случаев.

Answer 2

Не изменяя свой код, вы можете попробовать использовать версию Python "PyPy" с компиляцией точно в срок - он может выполнять ваш код намного быстрее, чем обычный CPython.