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

insertar arbol binario de busqueda

Question

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;

<left_expr> <logical_operator> <right_expr>

Otro ejemplo seria

input_string = x > 7 AND x < 8 AND x = 4
parsed_expr  = [[[''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 << expr
print complex_expr.parseString("x > 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

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

Answer 1

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 utiliza con los operadores: no es necesario incluir su complexExpr entre paréntesis: operatorPrecedence lo hará por usted. Ya 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 anidados, 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 en el á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 precedencia 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 .

Answer 2

Permítanme sugerir este enfoque de análisis, que proviene directamente de la clase de Peter Norvig en el diseño de programas de computadora en la 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'']]]]], '''')