Parse arithmétique booléenne, y compris les parenthèses avec regex?

Question

Y a-t-il une seule expression régulière qui peut analyser une chaîne (en Python et/ou Javascript, n'a pas besoin d'être la même expression) qui représente l'arithmétique booléenne simple? Par exemple, je veux analyser cette chaîne:

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

En supposant que:
* entre parenthèses ne nichent pas
* les termes a, b, ..., z ne sont pas des sous-expressions

Le Les captures qui en résultent doivent d'abord être regroupées par parenthèses, que j'analyse à nouveau avec la même regex ou une expression plus simple.

J'ai réussi à écrire une expression rationnelle naïve pour analyser l'arithmétique booléenne sans parenthèses.

Des idées?

Answer 1

Normalement, vous utilisez par exemple un recursive descent parser pour cette tâche, mais vous pouvez saisir toutes les pièces (jetons) avec une expression régulière:

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) 

Les opérateurs ont généralement différents precedence. Les parenthèses seront évaluées d'abord, puis les expressions and et enfin les expressions or, avec un ordre de gauche à droite en cas de préséance égale. Vous dites que vous voulez retourner les parenthèses en premier, mais ce que vous feriez normalement, c'est d'utiliser les parties pour construire une arborescence d'expression et l'évaluer de manière récursive.

Answer 2

En supposant qu'aucune imbrication ne le simplifie à un niveau où regex peut être utilisé. Une expression rationnelle correspond ce serait (en supposant et/ou seulement, peut être facilement étendu):

>>> 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')] 

Maintenant, vous avez des pièces parenthesized comme tuples de 3 chaînes (opérande opérandes de l'opérateur) et le reste de la chaîne comme des chaînes pour chaque jeton (opérateur ou opérande).

Vous pouvez parcourir la liste, évaluer chaque expression entre parenthèses et la remplacer par le résultat. Une fois cela fait, vous pouvez le parcourir à nouveau et évaluer soit de gauche à droite ou selon certaines règles de préséance que vous avez définies (par exemple, continuer à évaluer les AND seulement jusqu'à épuisement des AND, puis commencer à évaluer les OR).

Answer 3

Le Examples page sur le wiki pyparsing comprend un SimpleBool.py exemple qui analyser et évaluer des expressions telles que:

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, il n'y a pas d'exemples avec parens imbriqués, mais ceux-ci sont . supporté aussi)

L'analyseur réel est défini dans son intégralité en utilisant le code suivant:

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), 
    ]) 

Le reste de l'exemple donne les implémentations de BoolNot, BoolOr et BoolAnd. La construction operatorPrecedence définit la séquence des opérations, leur arité et leur associativité, et éventuellement une classe à construire avec les éléments analysés. operatorPrecedence prend ensuite soin de définir la grammaire, y compris la définition récursive de boolExpr dans les parenthèses imbriquées. La structure résultante est similaire à une AST imbriquée utilisant les classes BoolXxx données.Ces classes définissent à leur tour eval méthodes afin que les expressions peuvent analysées et évaluées en utilisant ce code:

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

lui-même pyparsing est un module un peu longuet, mais il est un seul fichier source de sorte que son empreinte d'installation est assez petite. La licence MIT permet à la fois une utilisation non commerciale et commerciale.