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

Question

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

x > 7 AND x < 8 OR x = 4 

y obtenga la cadena analizada como un árbol binario. Para la expresión anterior analizado la expresión esperada debe ser similar

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

'O' operador lógico tiene mayor precedencia que la 'Y' operador. El paréntesis puede anular la precedencia predeterminada. Para ser más general, la expresión analizada debería ser similar;

<left_expr> <logical_operator> <right_expr> 

Otro ejemplo sería

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

Hasta el momento se me ocurrió con esta sencilla solución, que por desgracia no puede generar la expresión analizada en forma de árbol binario. operatorPrecedence no parece haberme ayudado aquí donde hay el mismo operador lógico consecutivamente que 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 << expr 
print complex_expr.parseString("x > 7 AND x < 8 AND x = 4") 

Cualquier sugerencia u orientación es muy apreciada.

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

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

Answer 1

pruebe a 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 de la primitiva de utilizarse con los operadores; no es necesario incluir suExpr compleja en paréntesis: operatorPrecedence lo hará por usted. Debido a que su operando es en realidad otra comparación más profunda, puede considerar el cambio:

condition = (expr + operator + expr) 

a:

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

modo que la salida de operatorPrecedence 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 mayor precedencia y grupos de TI de OR primero. (¿Estás seguro de que quieres este orden de AND y OR precedencia? Creo que el orden tradicional es el inverso, como se muestra en this wikipedia entry.)

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

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

pero lo que se obtiene es:

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

eso se debe a que operatorPrecedence trata analiza las operaciones repite en la misma precedencia nivel usando re petición, no recursión.Vea this question que es muy similar al suyo, 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 a sample boolean expression parser implemented using operatorPrecedence en la página wiki de pyparsing.

EDITAR: Para aclarar, esto es lo que yo recomiendo a reducir el analizador para:

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 apoyo a NO también podría ser algo que desea agregar, entonces este sería el resultado:

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 operatorPrecedence. Sugeriría hacerlo de esta manera, en lugar de crear una definición de monstruo opPrec, ya que ya ha mencionado algunas de las desventajas de rendimiento a opPrec. Si aún tiene problemas de rendimiento, consulte ParserElement.enablePackrat.

Answer 2

Permítanme sugerir este enfoque de análisis, procedente directamente de la clase de Peter Norvig en el diseño de programas informáticos 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 => [a-z]+ 
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']]]]], '')