Aritmética booleana parse incluyendo paréntesis con expresiones regulares?

Question

¿Hay una sola expresión regular que pueda analizar una cadena (en Python y/o Javascript, no necesita ser la misma expresión) que representa aritmética booleana simple? Por ejemplo, yo quiero analizar esta cadena:

a and (b and c) and d or e and (f or g) 

Suponiendo que:
* paréntesis no anidan
* los términos a, b, ..., z no son sub-expresiones

El Las capturas resultantes se deben agrupar primero entre paréntesis, que luego analizaré nuevamente con la misma expresión o una expresión regular más simple.

He tenido éxito escribiendo una expresión regular ingenua para analizar la aritmética booleana sin paréntesis.

¿Alguna idea?

Answer 1

Normalmente se usaría por ejemplo, un recursive descent parser para esta tarea, pero se puede agarrar todas las piezas (fichas) con una expresión regular:

x = 'a and (b and c) and d or e and (f or g)' 
import re 

matches = re.findall(r'\(.*?\)|\w+', x) 
print ','.join(matches) 

Los operadores suelen tener diferentes precedence. Los paréntesis se evaluarían primero, luego las expresiones and, y finalmente las expresiones or, con el orden de izquierda a derecha en caso de igual precedencia. Usted dice que primero quiere devolver las coincidencias de paréntesis, pero en realidad lo que normalmente haría es usar las partes para compilar un árbol de expresiones y evaluarlo recursivamente.

Answer 2

Suponiendo que no hay anidamiento lo simplifica a un nivel donde se puede usar regex. Una expresión regular para que coincida con eso sería (suponiendo y/o única, puede ser fácilmente extendido):

>>> expr = 'a and (b and c) and d or e and (f or g)' 
>>> regex = re.compile('\((\w+)\s+(and|or)\s+(\w)\)|(\w+)') 
>>> results = regex.findall(expr) 
>>> results = [i[:3] if i[0] else i[3] for i in results] 
>>> results 
['a', 'and', ('b', 'and', 'c'), 'and', 'd', 'or', 'e', 'and', ('f', 'or', 'g')] 

partes Ahora que ha paréntesis como tuplas de 3 cuerdas (operando-operador-operando) y el resto de la cadena como cadenas para cada token (operador o operando).

Puede recorrer la lista, evaluar cada expresión entre paréntesis y reemplazarla con el resultado. Una vez hecho esto, puede recorrerlo nuevamente y evaluarlo de izquierda a derecha o de acuerdo con algunas reglas de precedencia que establezca (por ejemplo, siga evaluando ANDs hasta que se quede sin AND, luego comience a evaluar las RUP).

Answer 3

El Examples page en el pyparsing wiki incluye una muestra de SimpleBool.py que analizar y evaluar expresiones tales como:

test = ["p and not q", 
     "not not p", 
     "not(p and q)", 
     "q or not p and r", 
     "q or not (p and r)", 
     "p or q or r", 
     "p or q or r and False", 
     ] 

(Hmmm, no hay ejemplos con parens anidados, pero estos son . apoyado también)

El analizador real se define en su totalidad mediante este código:

boolOperand = Word(alphas,max=1) | oneOf("True False") 
boolExpr = operatorPrecedence(boolOperand, 
    [ 
    ("not", 1, opAssoc.RIGHT, BoolNot), 
    ("and", 2, opAssoc.LEFT, BoolAnd), 
    ("or", 2, opAssoc.LEFT, BoolOr), 
    ]) 

El resto del ejemplo proporciona las implementaciones de BoolNot, BoolOr y BoolAnd. El constructo operatorPrecedence define la secuencia de operaciones, su arity y asociatividad, y opcionalmente una clase que se construirá con los elementos analizados. operatorPrecedence se encarga de definir la gramática, incluida la definición recursiva de boolExpr dentro de paréntesis anidados. La estructura resultante es similar a un AST anidado utilizando las clases BoolXxx dadas.Estas clases a su vez definen eval métodos para que las expresiones pueden analizarse y evaluarse utilizando este código:

p = True 
q = False 
r = True 
for t in test: 
    res = boolExpr.parseString(t)[0] 
    print t,'\n', res, '=', bool(res),'\n' 

pyparsing sí mismo es un módulo de algo bastante largo, pero es un solo fichero fuente por lo que su huella de instalación es bastante pequeña. La licencia de MIT permite el uso no comercial y comercial.