Разбор логического предложения очень медленный с помощью pyparsing

Я пытаюсь использовать pyparsing для анализа логических выражений, таких как эти

x FALSE NOT x (x + y <= 5) AND (y >= 10) OR NOT (z < 100 OR w) (A=True OR NOT (G < 8) => S = J) => ((P = A) AND not (P = 1) AND (B = O)) => (S = T) ((P = T) AND NOT (K =J) AND (B = F)) => (S = O) AND ((P = T) OR (k and b => (8 + z <= 10)) AND NOT (a + 9 <= F)) => (7 = a + z) 

Код, который я написал ниже, кажется, работает нормально – но он очень медленный (например, последний пример выше занимает несколько секунд). Я каким-то неэффективным образом структурировал грамматику? может быть рекурсия должна использоваться вместо operatorPrecedence? Есть ли способ ускорить его?

 identifier = Group(Word(alphas, alphanums + "_") + Optional("'")) num = Regex(r"[+-]?\d+(:?\.\d*)?(:?[eE][+-]?\d+)?") operator = Regex(">=|<=|!=|>|<|=") operand = identifier | num aexpr = operatorPrecedence(operand, [('*',2,opAssoc.LEFT,), ('+',2,opAssoc.LEFT,), (operator,2,opAssoc.LEFT,) ]) op_prec = [(CaselessLiteral('not'),1,opAssoc.RIGHT,), (CaselessLiteral('and'),2,opAssoc.LEFT ,), (CaselessLiteral('or'), 2,opAssoc.LEFT ,), ('=>', 2,opAssoc.LEFT ,), ] sentence = operatorPrecedence(aexpr,op_prec) return sentence 

У меня такая же проблема. Здесь найдено решение ( parserElement.enablePackrat() ): http://pyparsing.wikispaces.com/share/view/26068641?replyId=26084853

Следующий код теперь анализируется мгновенно (против 60 секунд до)

 ParserElement.enablePackrat() integer = Word(nums).setParseAction(lambda t:int(t[0]))('int') operand = integer | variable('var') # Left precedence eq = Literal("==")('eq') gt = Literal(">")('gt') gtEq = Literal(">=")('gtEq') lt = Literal("<")('lt') ltEq = Literal("<=")('ltEq') notEq = Literal("!=")('notEq') mult = oneOf('* /')('mult') plus = oneOf('+ -')('plus') _and = oneOf('&& and')('and') _or = oneOf('|| or')('or') # Right precedence sign = oneOf('+ -')('sign') negation = Literal('!')('negation') # Operator groups per presedence right_op = negation | sign # Highest precedence left_op_1 = mult left_op_2 = plus left_op_3 = gtEq | ltEq | lt | gt left_op_4 = eq | notEq left_op_5 = _and left_op_6 = _or # Lowest precedence condition = operatorPrecedence( operand, [ (right_op, 1, opAssoc.RIGHT), (left_op_1, 2, opAssoc.LEFT), (left_op_2, 2, opAssoc.LEFT), (left_op_3, 2, opAssoc.LEFT), (left_op_4, 2, opAssoc.LEFT), (left_op_5, 2, opAssoc.LEFT), (left_op_6, 2, opAssoc.LEFT) ] )('computation') 

Я помещаю ваш код в небольшую программу

 from sys import argv from pyparsing import * def parsit(aexpr): identifier = Group(Word(alphas, alphanums + "_") + Optional("'")) num = Regex(r"[+-]?\d+(:?\.\d*)?(:?[eE][+-]?\d+)?") operator = Regex(">=|<=|!=|>|<|=") operand = identifier | num aexpr = operatorPrecedence(operand, [('*',2,opAssoc.LEFT,), ('+',2,opAssoc.LEFT,), (operator,2,opAssoc.LEFT,) ]) op_prec = [(CaselessLiteral('not'),1,opAssoc.RIGHT,), (CaselessLiteral('and'),2,opAssoc.LEFT ,), (CaselessLiteral('or'), 2,opAssoc.LEFT ,), ('=>', 2,opAssoc.LEFT ,), ] sentence = operatorPrecedence(aexpr,op_prec) return sentence def demo02(arg): sent = parsit(arg) print arg, ":", sent.parseString(arg) def demo01(): for arg in ["x", "FALSE", "NOT x", "(x + y <= 5) AND (y >= 10) OR NOT (z < 100 OR w)", "(A=True OR NOT (G < 8) => S = J) => ((P = A) AND not (P = 1) AND (B = O)) => (S = T)", "((P = T) AND NOT (K =J) AND (B = F)) => (S = O) AND ((P = T) OR (k and b => (8 + z <= 10)) AND NOT (a + 9 <= F)) => (7 = a + z)" ]: demo02(arg) if len(argv) <= 1: demo01() else: for arg in argv[1:]: demo02(arg) 

и cProfile

 $ python -m cProfile pyparsetest.py 

Вы найдете много вызовов parseImpl , но в середине вывода есть

 2906500/8 26.374 0.000 72.667 9.083 pyparsing.py:913(_parseNoCache) 212752/300 1.045 0.000 72.608 0.242 pyparsing.py:985(tryParse) 

72.667 с суммарным временем от 72 очков.

Поэтому я бы рискнул предположить, что «кэширование» предложит хороший рычаг.

Просто разрешение http://pyparsing-public.wikispaces.com/FAQs не помогло, ты. Я добавил строки

 import pyparsing pyparsing.usePackrat = True 

и время выполнения было таким же.

Number-Regex также выглядит хорошо для меня – вполне стандартно, я думаю. Например, заменив его на

 #num = Regex(r"[+-]?\d+(:?\.\d*)?(:?[eE][+-]?\d+)?") num = Regex(r"8|1|10|100|5") 

также не помогло. В моем простом варианте нет «пустого совпадения», о котором я догадался, но это не так.

Последняя попытка – посмотреть на парсер результатов с:

 .... sentence = operatorPrecedence(aexpr,op_prec) print sentence return sentence .... 

И … пока … долго!

Ну, а не используя ваш первый operatorPrecedence Превращение происходит намного быстрее, но больше не работает для арифметики.

Таким образом, я бы рискнул предположить, что, да, попробуйте разделить два вида выражений (булевых и арифметических) больше. Возможно, это улучшит его. Я тоже загляну в нее, это меня интересует.