Exprimer des expressions logiques avec Pyparsing

Question

Pour commencer, ce n'est pas des devoirs, j'essaie d'apprendre le pyparsing et je suis resté coincé ici.

Ma question est la suivante, je suis en train d'analyser des déclarations comme (abc or def) or def)

Mon programme va de la merde sur une expression infixe a or b, puisque les deux parties peuvent être eux-mêmes expressions, qui peuvent à nouveau être des expressions infixes, la l'analyseur récursive jusqu'à ce que la profondeur de récursivité soit atteinte et qu'aucun travail ne soit effectué.

code ci-dessous:

# infix operators are automatically created and dealt with 
infix_operators = ['and', '&', 'or', '|', 'implies', '->'] 

variable = Word(alphas) 
infix_op = oneOf(infix_operators, caseless=True) 

expr   = Forward() 
infix_expr = (expr + infix_op + expr) 
complex_expr = nestedExpr('(', ')', content=expr) 
expr  << (infix_expr | complex_expr | variable) 

print str(expr.parseString("(abc or def) or def)")[0]) 

Ma question est assez simple; comment irait-on éviter une boucle infinie dans ce genre de situations?

Answer 1

La solution canonique est quelque chose qui implémente cette BNF:

atom := variable | 'True' | 'False' | '(' expr ')' 
factor := [ 'not' ]... atom 
term := factor [ '&' factor ]... 
expr := term [ '|' term ]... 

Le problème gauche récursion est adressée parce que, même si expr récursif éventuellement par term ->factor ->atom, quand il arrive à expr, il doit d'abord analyser un chef de file « (» Ainsi, un expr ne doit d'abord analyser une profonde expr avant l'analyse d'autres éléments premier

Cette BNF se traduit presque directement à pyparsing que:..

and_ = Keyword('and') 
or_ = Keyword('or') 
not_ = Keyword('not') 
true_ = Keyword('true') 
false_ = Keyword('false') 

not_op = not_ | '~' 
and_op = and_ | '&' 
or_op = or_ | '|' 

expr = Forward() 

identifier = ~(and_ | or_ | not_ | true_ | false_) + Word(alphas) 
atom = identifier | Group('(' + expr + ')') 
factor = Group(ZeroOrMore(not_op) + atom) 
term = Group(factor + ZeroOrMore(and_op + factor)) 
expr <<= Group(term + ZeroOrMore(or_op + term)) 

Ou vous pouvez utiliser aide de pyparsing infixNotation:

expr = infixNotation(true_ | false_ | identifier, 
    [ 
    (not_op, 1, opAssoc.RIGHT), 
    (and_op, 2, opAssoc.LEFT), 
    (or_op, 2, opAssoc.LEFT), 
    ]) 

infixNotation est construit avec un opérande de base (dans ce cas, que ce soit un nom alpha variable ou une des booléennes true ou false), suivi d'une liste de tuples (operator, arity, associativity), donnés dans l'ordre de priorité des opérateurs. infixNotation prend en charge toutes les définitions de récursion, l'analyse des opérateurs associatifs à droite et à gauche, ainsi que certains opérateurs pour éviter l'imbrication supplémentaire des opérations pour un niveau de priorité donné s'il n'y a pas d'opérateurs.

Vous pouvez tester cette expression en utilisant la méthode runTests de pyparsing:

expr.runTests(""" 
    p and not q 
    not p or p 
    r and (p or q) 
    r and p or q 
    not q 
    q 
    """, fullDump=False) 

Giving:

p and not q 
[['p', 'and', ['not', 'q']]] 

not p or p 
[[['not', 'p'], 'or', 'p']] 

r and (p or q) 
[['r', 'and', ['p', 'or', 'q']]] 

r and p or q 
[[['r', 'and', 'p'], 'or', 'q']] 

not q 
[['not', 'q']] 

q 
['q']