разбор сложного логического выражения в pyparsing в двоичном древе

Я пытаюсь проанализировать сложное логическое выражение, подобное приведенному ниже;

x > 7 AND x < 8 OR x = 4 

и получить разобранную строку как двоичное дерево. Для вышеуказанного выражения ожидаемое синтаксическое выражение должно выглядеть так:

  • Как разобрать отступы и разделители с помощью pyparsing?
  • Что это означает, что значение << означает в Python
  •  [['x', '>', 7], 'AND', [['x', '<', 8], 'OR', ['x', '=', 4]]] 

    Логический оператор «ИЛИ» имеет более высокий приоритет, чем оператор «И». Скобки могут отменять приоритет по умолчанию. Чтобы быть более общим, выражение parsed должно выглядеть так:

     <left_expr> <logical_operator> <right_expr> 

    Другим примером может служить

     input_string = x > 7 AND x < 8 AND x = 4 parsed_expr = [[['x', '>', 7], 'AND', ['x', ',', 8]], 'AND', ['x', '=', 4]] 

    До сих пор я придумал это простое решение, которое, к сожалению, не может генерировать анализируемое выражение в двоичном древовидном стиле. operatorPrecedence, похоже, не помогает мне здесь, где есть тот же логический оператор, что и в предыдущем примере.

     import pyparsing as pp complex_expr = pp.Forward() operator = pp.Regex(">=|<=|!=|>|<|=").setName("operator") logical = (pp.Keyword("AND") | pp.Keyword("OR")).setName("logical") vars = pp.Word(pp.alphas, pp.alphanums + "_") | pp.Regex(r"[+-]?\d+(:?\.\d*)?(:?[eE][+-]?\d+)?") condition = (vars + operator + vars) clause = pp.Group(condition ^ (pp.Suppress("(") + complex_expr + pp.Suppress(")") )) expr = pp.operatorPrecedence(clause,[ ("OR", 2, pp.opAssoc.LEFT, ), ("AND", 2, pp.opAssoc.LEFT, ),]) complex_expr << expr print complex_expr.parseString("x > 7 AND x < 8 AND x = 4") 

    Любые предложения или рекомендации хорошо оценены.

    BNF для выражения (без скобок) может быть

     <expr> -> <expr> | <expr> <logical> <expr> <expr> -> <opnd> <relational> <opnd> <opnd> -> <variable> | <numeric> <relational> -> <'>'> | <'='> | <'>='> | <'<='> | <'!='> 

  • Создайте файл данных Pandas для облачного хранилища Google или BigQuery
  • установить python Google Cloud Client на Ubuntu 14.04
  • Реверсирование порядка слов предложения кусками
  • Selenium webdriver не может найти элементы в chrome: // загружает
  • CORS - использование AJAX для публикации на веб-службе Python (webapp2)
  • как создать случайный массив из списка, каждое значение в массиве не дублируется в python
  • 2 Solutions collect form web for “разбор сложного логического выражения в pyparsing в двоичном древе”

    Попробуйте изменить:

     expr = pp.operatorPrecedence(clause,[ ("OR", 2, pp.opAssoc.LEFT, ), ("AND", 2, pp.opAssoc.LEFT, ),]) 

    чтобы:

     expr = pp.operatorPrecedence(condition,[ ("OR", 2, pp.opAssoc.LEFT, ), ("AND", 2, pp.opAssoc.LEFT, ),]) 

    Первым аргументом для operatorPrecedence является примитивный операнд, который будет использоваться с операторами – нет необходимости включать ваш complexExpr в круглые скобки – operatorPrecedence сделает это за вас. Поскольку ваш операнд на самом деле является еще одним более глубоким сравнением, вы можете подумать об изменении:

     condition = (expr + operator + expr) 

    чтобы:

     condition = pp.Group(expr + operator + expr) 

    так что выход operatorPrecedence легче обрабатывать. При этих изменениях синтаксический анализ x > 7 AND x < 8 OR x = 4 дает:

     [[['x', '>', '7'], 'AND', [['x', '<', '8'], 'OR', ['x', '=', '4']]]] 

    который распознает более высокий приоритет OR и группирует его в первую очередь. (Вы уверены, что хотите этот порядок приоритетов AND и OR? Я думаю, что традиционное упорядочение – это обратное, как показано в этой записи в Википедии .)

    Я думаю, вы также спрашиваете, почему pyparsing и operatorPrecedence не возвращают результаты в вложенных двоичных парах, то есть вы ожидаете, что разбор «A и B и C» вернется:

     [['A', 'and', 'B'] 'and', 'C'] 

    но вы получаете:

     ['A', 'and', 'B', 'and', 'C'] 

    Это связано с тем, что operatorPrecedence анализирует повторяющиеся операции с одинаковым уровнем приоритета, используя повторение, а не рекурсию. См. Этот вопрос, который очень похож на ваш, и чей ответ включает в себя действие синтаксического анализа для преобразования вашего повторяющегося дерева разбора в более традиционное дерево разбора двоичных данных. Вы также можете найти образец логического синтаксического выражения, реализованный с использованием operatorPrecedence на странице вики-пирамизации.

    EDIT : Чтобы уточнить, я рекомендую вам уменьшить ваш парсер до:

     import pyparsing as pp operator = pp.Regex(">=|<=|!=|>|<|=").setName("operator") number = pp.Regex(r"[+-]?\d+(:?\.\d*)?(:?[eE][+-]?\d+)?") identifier = pp.Word(pp.alphas, pp.alphanums + "_") comparison_term = identifier | number condition = pp.Group(comparison_term + operator + comparison_term) expr = pp.operatorPrecedence(condition,[ ("AND", 2, pp.opAssoc.LEFT, ), ("OR", 2, pp.opAssoc.LEFT, ), ]) print expr.parseString("x > 7 AND x < 8 OR x = 4") 

    Если поддержка NOT может также быть чем-то, что вы хотите добавить, это будет выглядеть так:

     expr = pp.operatorPrecedence(condition,[ ("NOT", 1, pp.opAssoc.RIGHT, ), ("AND", 2, pp.opAssoc.LEFT, ), ("OR", 2, pp.opAssoc.LEFT, ), ]) 

    В какой-то момент вам может понадобиться расширить определение comparison_term с более полным арифметическим выражением, определенным с его собственным определением operatorPrecedence . Я предлагаю сделать это таким образом, а не создавать одно определение opPrec монстра, поскольку вы уже упоминали некоторые из недостатков производительности для opPrec . Если у вас все еще ParserElement.enablePackrat проблемы с производительностью, загляните в ParserElement.enablePackrat .

    Позвольте мне предложить этот подход синтаксического анализа, исходящий непосредственно из класса Питера Норвига в разработке компьютерных программ по udacity (и подстроенный для ваших нужд).

     from functools import update_wrapper from string import split import re def grammar(description, whitespace=r'\s*'): """Convert a description to a grammar. Each line is a rule for a non-terminal symbol; it looks like this: Symbol => A1 A2 ... | B1 B2 ... | C1 C2 ... where the right-hand side is one or more alternatives, separated by the '|' sign. Each alternative is a sequence of atoms, separated by spaces. An atom is either a symbol on some left-hand side, or it is a regular expression that will be passed to re.match to match a token. Notation for *, +, or ? not allowed in a rule alternative (but ok within a token). Use '\' to continue long lines. You must include spaces or tabs around '=>' and '|'. That's within the grammar description itself. The grammar that gets defined allows whitespace between tokens by default; specify '' as the second argument to grammar() to disallow this (or supply any regular expression to describe allowable whitespace between tokens).""" G = {' ': whitespace} description = description.replace('\t', ' ') # no tabs! for line in split(description, '\n'): lhs, rhs = split(line, ' => ', 1) alternatives = split(rhs, ' | ') G[lhs] = tuple(map(split, alternatives)) return G def decorator(d): def _d(fn): return update_wrapper(d(fn), fn) update_wrapper(_d, d) return _d @decorator def memo(f): cache = {} def _f(*args): try: return cache[args] except KeyError: cache[args] = result = f(*args) return result except TypeError: # some element of args can't be a dict key return f(args) return _f def parse(start_symbol, text, grammar): """Example call: parse('Exp', '3*x + b', G). Returns a (tree, remainder) pair. If remainder is '', it parsed the whole string. Failure iff remainder is None. This is a deterministic PEG parser, so rule order (left-to-right) matters. Do 'E => T op E | T', putting the longest parse first; don't do 'E => T | T op E' Also, no left recursion allowed: don't do 'E => E op T'""" tokenizer = grammar[' '] + '(%s)' def parse_sequence(sequence, text): result = [] for atom in sequence: tree, text = parse_atom(atom, text) if text is None: return Fail result.append(tree) return result, text @memo def parse_atom(atom, text): if atom in grammar: # Non-Terminal: tuple of alternatives for alternative in grammar[atom]: tree, rem = parse_sequence(alternative, text) if rem is not None: return [atom]+tree, rem return Fail else: # Terminal: match characters against start of text m = re.match(tokenizer % atom, text) return Fail if (not m) else (m.group(1), text[m.end():]) # Body of parse: return parse_atom(start_symbol, text) Fail = (None, None) MyLang = grammar("""expression => block logicalop expression | block block => variable operator number variable => [az]+ operator => <=|>=|>|<|= number => [-+]?[0-9]+ logicalop => AND|OR""", whitespace='\s*') def parse_it(text): return parse('expression', text, MyLang) print parse_it("x > 7 AND x < 8 AND x = 4") 

    Выходы:

     (['expression', ['block', ['variable', 'x'], ['operator', '>'], ['number', '7']], ['logicalop', 'AND'], ['expression', ['block', ['variable', 'x'], ['operator', '<'], ['number', '8']], ['logicalop', 'AND'], ['expression', ['block', ['variable', 'x'], ['operator', '='], ['number', '4']]]]], '') 
    Python - лучший язык программирования в мире.