análisis de una expresión lógica compleja en pyparsing en forma de árbol binario

Estoy tratando de analizar expresiones lógicas complejas como la de abajo;

x > 7 AND x < 8 OR x = 4 

y obtener la cadena analizada como un árbol binario. Para la expresión anterior, la expresión analizada esperada debe verse como

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

El operador lógico ‘OR’ tiene mayor prioridad que el operador ‘AND’. Los paréntesis pueden anular la prioridad predeterminada. Para ser más general, la expresión analizada debe tener el aspecto;

    

Otro ejemplo seria

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

Hasta ahora se me ocurrió esta solución simple que, lamentablemente, no puede generar expresiones analizadas en forma de árbol binario. Operador La precedencia no parece ayudarme aquí donde hay el mismo operador lógico consecutivamente como en el ejemplo anterior.

 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 < 7 AND x < 8 AND x = 4") 

Cualquier sugerencia u orientación es bien apreciada.

BNF para la expresión (sin paréntesis) podría ser

  ->  |     ->     ->  |   -> '> |  | ='> | <' |  

Intenta cambiar:

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

a:

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

El primer argumento de operatorPrecedence es el operando primitivo que se utilizará con los operadores: no es necesario incluir su complexExpr entre paréntesis: operatorPrecedence lo hará por usted. Dado que su operando es en realidad otra comparación más profunda, podría considerar cambiar:

 condition = (expr + operator + expr) 

a:

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

de modo que la salida del operador La precedencia es más fácil de procesar. Con estos cambios, el análisis x > 7 AND x < 8 OR x = 4 da:

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

que reconoce la precedencia superior de OR y la agrupa primero. (¿Está seguro de que desea este orden de prioridad AND y OR? Creo que el orden tradicional es el inverso, como se muestra en esta entrada de wikipedia ).

Creo que también se está preguntando por qué pyparsing y operatorPrecedence no devuelven los resultados en pares binarios nesteds, es decir, espera que el análisis "A y B y C" devuelva:

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

pero lo que obtienes es:

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

Esto se debe a que operatorPrecedence analiza las operaciones repetidas en el mismo nivel de precedencia utilizando la repetición, no la recursión. Vea esta pregunta que es muy similar a la suya, y cuya respuesta incluye una acción de análisis para convertir su árbol de análisis repetitivo al árbol de análisis binario más tradicional. También puede encontrar un analizador de expresiones booleanas de ejemplo implementado usando operatorPrecedence en la página wiki de pyparsing.

EDITAR : Para aclarar, esto es lo que recomiendo que reduzca su analizador a:

 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") 

Si el soporte para NOT también podría ser algo que quieras agregar, entonces esto se vería así:

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

En algún momento, es posible que desee ampliar la definición de comparison_term con una expresión aritmética más completa, definida con su propia definición de precedente de operatorPrecedence . Sugeriría hacerlo de esta manera, en lugar de crear una definición de opPrec monstruo, ya que ya ha aludido a algunas de las desventajas de rendimiento de opPrec . Si aún tiene problemas de rendimiento, consulte ParserElement.enablePackrat .

Permítanme sugerir este enfoque de análisis, que proviene directamente de la clase de Peter Norvig en el diseño de progtwigs de computadora en udacity (y ajustado para sus necesidades).

 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") 

Salidas:

 (['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']]]]], '')