Booleschen Term analysieren

[Denker]

Hallo,

ich überlege seit Wochen an einem Lösung zu dem Problem, wie ich boolesche Terme auflösen/analysieren kann.
Ich habe als Inputs in mein System zum Beispiel einen Term als String: "(x650 & x480) / (x420 & !x720)", der zweite Input ist eine Liste z.B. [x650, x480, x320].

Nun habe ich vor, dass der boolesche Term abgearbeitet wird und quasi an der Liste überprüft wird und zum Schluss ein True oder False herauskommt. In dem Beispielfall ein True, da "x650" und "x480" vorhanden sind.

Nun habe ich das Problem, dass der Term absolut verschiedene Komplexität haben kann, die Tiefe der Klammern und die Verknüpfungen von & (AND), / (OR), ! (NOT) und Klammern ist nicht bekannt und kann sehr variieren. Leider habe ich im Moment nur eine Idee von vielen Schleifen und If abfragen um die Logik bis zu einer gewissen Tiefe abzubilden, leider ist aber der Programmieraufwand sehr hoch. Ich hoffe aber, dass es vielleicht schon ein solches Tool gibt und ich nichts nachprogrammieren muss. Ich arbeite aktuell mit Python 2.5.1 und kann aufgrund meiner Arbeitsumgebung auch nicht umsteigen.

Vielen Dank,
Jens

[EyDu]

Dafür lässt sich doch leicht ein Parser schreiben. Bool'sche Ausdrücke sind da ein gerne genommenes Einstiegsbeispiel. Es heißt übrigens Term und nicht Therm.

[BlackJack]

@Denker: An sich ist das doch einfach. Eine Klasse für jeden Operator schreiben mit einer `eval()`-Methode, die den Teilausdruck auswertet (rekursiv) und einen Parser der eine Zeichenkette mit so einem Ausdruck in einen Objektbaum aus Operator-Klassen übersetzt.

Für den Parser kann man eine Bibliothek verwenden. Ich persönlich mag PyParsing ganz gerne für solche Aufgaben.

[Denker]

@EyDu: Danke ich habe den Rechtschreibfehler korrigiert

Ich habe auch schon an einen Parser gedacht, aber meine Python Kenntnisse sind ich denke extrem gering. Ich schreibe zwar auch schon längere Programme, aber das ist alles sehr primitiv.
Bisher habe ich es versucht keine zusätzlichen Bibliotheken einzubinden, damit die Programme stets portabel bleiben.
Mit Klassen habe ich überhaupt noch nicht programmiert, ich war bisher froh, dass ich schonmal kleinere Programmblöcke verwendet habe.
Hättet Ihr vielleicht Beispiele für mich?

VG, Jens

[pillmuncher]

Hallo.

Es sind Terme, nicht Therme. Eine Therme war ein öffentliches Badehaus in der antiken römischen Welt.

Du wirst auch nicht mit Schleifen und Abfragen allein zurechtkommen. Wenn du es alles selbst programierst, brauchst du zudem einen Stack oder Rekursion, und einen einfachen Unifikationsmechanismus. Sorry, dass es so technisch klingt, aber das liegt an der Natur der Sache. Zuerst würde ich einen Parser schreiben, der aus einem Term einen Abstrakten Syntax-Baum (AST) generiert. Wie BlackJack empfehle ich dazu pyparsing. Den AST kannst du dann anhand der Aussagenlogischen Regeln interpretieren, bzw. einen Interpreter schreiben, der das für dich übernimmt. Das Logic-Modul aus sympykönnte dabei helfen, ich hab es allerdings noch nicht verwendet.

Eine Anmerkung noch: Aussagenlogische Formeln in denen nur Variablen auftauchen, können nicht als wahr oder falsch ausgewertet werden, sodern nur als erfüllbar, unerfüllbar oder allgemeingültig. Deine Beispiel-Terme scheinen solche Formeln zu sein. Für den Fall der Erfüllbarkeit kann man zudem fragen, unter welchen Variablen-Belegungen eine Formel wahr oder falsch ist. Unerfüllbare Formeln sind unter keiner Belegung wahr, und allgemeingültige unter jeder.

Gruß,
Mick.

[webspider]

Hättet Ihr vielleicht Beispiele für mich?

Die Pyparsing-Seiten dürften genug Dokumentation und Beispielcode für dich auf Lager haben.

[Denker]

Hallo,

wie ich das pyparsing anwende habe ich in Ansätzen verstanden. Aber wozu ich meinen Code parsen muss ist mir noch schleierhaft. Die Schreibweise meines booleschen Terms kann ich einfach anpassen, bereits bevor er analysiert werden soll.
Ich habe aktuell nur keine Idee, wie ich einen booleschen Term, der mir als String vorliegt analysieren lasse.
Es tut mir leid, aber ich weiß mir im Moment nicht anders zu helfen, als hier zu fragen. Ich nutze leider Python erst seit einem Jahr.

Grüße, Jens

[EyDu]

Hallo,

du sollst nicht deinen Code parsen, sondern deine boolschen Terme.

Sebastian

[Denker]

Ja die booleschen Terme habe ich ja auch gemeint und in welcher Form benötige ich dann meinen Term? Wie verarbeite ich diesen dann weiter?

[EyDu]

Ich würde ja mit den Links von webspider anfangen ...

[darktrym]

Ansonsten der gute sma hat vor langer Zeit ein Videotutorial für einen Basic Interpreter erstellt, da kannst dir einiges abgucken, wie Terme verarbeitet und ausgewertet werden können.

[lunar]

Ein Blick auf die Wikipedia-Seiten zu den in dieser Diskussion erwähnten Fachbegriffen wie „Parser“, „AST“, „Grammatik“, usw. kann sicher nicht schaden.

[pillmuncher]

Weil ich eine neue parser lib entdeckt habe:

Code: Alles auswählen

from parcon import id_word, InfixExpr, Forward
from operator import not_ as negation, and_ as conjunction, or_ as disjunction


class Universe(set):

    def __init__(self, items):
        set.__init__(self, items)
        formula = Forward()
        term = id_word[self.__contains__] | '~' + formula[negation] | '(' + formula + ')'
        term = InfixExpr(term, [('&', conjunction)])
        term = InfixExpr(term, [('|', disjunction)])
        formula << term
        self.evaluate = formula.parse_string


solver = Universe(['x650', 'x480', 'x320'])

print solver.evaluate('(x650 & x480) | (x420 & ~x720)')
print solver.evaluate('(x650 & x480) | ((x420 | x320) & ~x720)')
print solver.evaluate('x720 | x123 | x480')
print solver.evaluate('x720')
solver.add('x720')
print solver.evaluate('x720')

Ergebnis:

Code: Alles auswählen

$ python propsolve.py
True
True
True
False
True

All Hail Parser Combinators.

Für die Disjunktion habe ich | statt / verwendet und für die Negation ~ statt ! und wie üblich soll es & statt & heißen. Ohne Klammern hat & höhere Priorität als |. ~ hat die höchste Priorität.

Parcon ist zwar noch nicht ganz ausgereift, hat aber ein paar sehr gute Ideen, wie etwa dass semantische Aktionen mittels Subskriptions-Syntax angegeben werden können. Zudem verfügt es über monadische Bind- und Return-Parser, so dass auch kontextsensitive Grammatiken sehr einfach geparst werden können.

[BlackJack]

Ich hatte das ”damals” mit einer altbekannten Parserbibliothek gemacht — allerdings auf einem Rechner an dem ich dann lange zeit nicht mehr gesessen habe, und deswegen habe ich es bis jetzt nicht geposted:

Code: Alles auswählen

#!/usr/bin/env python
from itertools import imap
from operator import and_, or_
import pyparsing as pp


class Variable(object):
    def __init__(self, identifier):
        self.name = identifier
    
    def __str__(self):
        return self.name
    
    def __call__(self, context):
        return self.name in context


class Not(object):
    SYMBOL = '!'
    
    def __init__(self, operand):
        self.expression = operand
    
    def __str__(self):
        return '%s%s' % (self.SYMBOL, self.expression)
    
    def __call__(self, context):
        return not self.expression(context)
    
    @classmethod
    def parse_action(cls, context):
        return cls(context[0][1])


class BinaryOperation(object):
    FUNC = None
    SYMBOL = None

    def __init__(self, terms):
        self.terms = terms
    
    def __str__(self):
        return '(%s)' % (' %s ' % self.SYMBOL).join(imap(str, self.terms))
    
    def __call__(self, context):
        return reduce(self.FUNC, (t(context) for t in self.terms))
    
    @classmethod
    def parse_action(cls, context):
        return cls(context[0][0::2])


class Or(BinaryOperation):
    FUNC = or_
    SYMBOL = '/'


class And(BinaryOperation):
    FUNC = and_
    SYMBOL = '&'


def create_grammar():
    variable = (
        pp.Word(pp.alphas, pp.nums).setParseAction(lambda t: Variable(t[0]))
    )
    expression = pp.operatorPrecedence(
        variable,
        [
            (Not.SYMBOL, 1, pp.opAssoc.RIGHT, Not.parse_action),
            (And.SYMBOL, 2, pp.opAssoc.LEFT, And.parse_action),
            (Or.SYMBOL, 2, pp.opAssoc.LEFT, Or.parse_action),
        ]
    )
    return expression


def main():
    grammar = create_grammar()
    source = 'x650 & (x480 / x420) & !x720'
    expression = grammar.parseString(source)[0]
    print expression
    context = ['x650', 'x480', 'x320']
    print expression(set(context))


if __name__ == '__main__':
    main()

Ist ein bisschen länger. Ausgabe:

Code: Alles auswählen

(x650 & (x480 / x420) & !x720)
True