Gehaxelts Blog

IT-Security & Hacking

LogicParser - Scanner/Parser/Evaluator für logische Ausdrücke

Ich habe gestern Abend ein kleines Python Script geschrieben, welches logische Ausdrücke auswerten kann.

Dieses mögchte ich vorstellen und ein wenig die Funktionsweise von Scanner/Parser & Compiler erklären.

Der Quelltext

Den (unschönen) Quelltext findet ihr in meinem entsprechenden GitHub-Repository. Diesen solltet ihr euch zunächst anschauen, damit ihr wisst wie dieser im Ganzen aussieht, auch wenn ich ihn hier Stück für Stück auseinander nehmen werde.

Was sind logische Ausdrücke

Ein logischer (boolscher) Ausdruck ist ein Term welcher aus boolschen Operatoren bzw. Operanden besteht und zu wahr (T) oder falsch (F) ausgewertet werden kann.

Dabei gibt es viele verschiedene Operationen. Die bekanntesten sind folgende: and, or, not; dessen Wahrheitstafel so aussehen:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

and:

a|b|y
-----
0|0|0
0|1|0
1|0|0
1|1|0

or:

a|b|y
-----
0|0|0
0|1|1
1|0|1
1|1|1

not:

a|y
---
0|1
1|0

Entsprechend kann man mit Kombinationen dieser Operatoren einen Ausdruck bilden:

1
2
3

T and not F == T
F or F and T == F
...

Dabei sollte man beachten, das der Operator “not” am stärksten bindet, gefolgt vom “and” und zuletzt vom “or”, bzw. den anderen Operatoren. Somit entfällt in den meisten Fällen die Klammerung, wie wir es von der *-+-Rechnung kennen.

Erklärung des Codes

Der Code macht eigentlich nichts anderes als die gegebene Grammatik auf die Eingabe anzuwenden. Die Eingabe wird zunächst gescannt, danach geparst und zuletzt evaluiert.

Die Grammatik

Die Grammatik lässt sich wie folgt beschreiben:

1
2
3

S        -> Operand | not S | ( S Operator S )
Operand  -> T | F
Operator -> or | and | -> | <-> | xor

S ist dabei die Starteingabe. Es gibt also 3 Möglichkeiten eine valide Eingabe zu machen:

  • S ist ein Operand, dann wird abgebrochen.

  • S ist “not”, danach folgt wieder S (rekursiv)

  • S ist “(“, dann muss S, ein Operator, wieder ein S und “)” folgen.

  • Operand ist “T” oder “F”

  • Operator ist “or”, “and”, “->”, ”<->” oder “xor”

Nach dieser Grammatik wird unser Programm die Eingabe auswerten. Mögliche Eingaben wären zum Beispiel:

1
2
3
4
5

T
F
not T
not (T or F)
(not T or (F xor T))

Folgende Eingaben wären hingegen nicht korrekt:

1
2
3

T or F
not T or
and or not T

Der Scanner

Die Aufgabe des Scanners ist es, die einzelnen Eingaben bzw. Token zu seperieren und in eine Liste zu überführen. Das erledigt für uns der folgende Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#Scan Tokens
def scan(inputstr):
    try:
        tokens = []
        token = ""
        for char in inputstr:
            if char == "(":
                tokens.append("(")
            elif char == ")":
                tokens.append(")")
            elif char == "T":
                tokens.append("T")
            elif char == "F":
                tokens.append("F")
            elif char == " ":
                if not token == "":
                    tokens.append(token)
                    token=""
                else:
                    pass
            else:
                token+=char
        return tokens
    except:
        return "Scanning error"

Wir haben ein Array “tokens”, in dem alle Tokens abgespeichert werden. Die Variable “token” nutzen wir, um mehrbuchstabige Tokens einzulesen (and,or,sad). Wichtig hierbei ist, dass auch nicht valide Zeichenketten, wie “andor” vorkommen können. Diese werden dann erst später beim Parser behandelt. Der Scanner nutzt als Trennzeichen hier das Leerzeichen ” “.

Für die folgende Eingabe sieht die zurückgegebene Liste so aus:

1
2

-> % ./logicparser.py "(T or (blubb and T))"
['(', 'T', 'or', '(', 'blubb', 'and', 'T', ')', ')']

Wie schon erwähnt, ist das keine Fehlfunktion des Scanners, wenn dort falsche Zeichenketten eingelesen werden. Diese werden im nächsten Schritt verarbeitet.

Der Parser

Der Parser wendet nun die Grammatik auf die übergebene Liste mit Tokens an. Dabei können Syntaxfehler erkannt werden, und das Parsing bricht ab. Es kann sinnvoll sein, den Parser eine möglichst gut evaluierbare Ausgabe erzeugen zu lassen.

Dazu nutze ich diesen Teil des Codes, wobei “parse” aufgerufen wird:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#Parses and, or,...
def parseOperator(tokens):
    token, tokens = getToken(tokens)
    if token == "and":
        return ["and",tokens]
    elif token == "or":
        return ["or",tokens]
    elif token == "->":
        return ["->",tokens]
    elif token == "<->":
        return ["<->",tokens]
    elif token == "xor":
        return ["xor",tokens]
    else:
        return ["error",tokens]

# Parses close
def parseClose(tokens):
    token, tokens = getToken(tokens)
    if token == ")":
        return ["",tokens]
    else:
        return ["error",tokens]

#Parses an expression
def parseExpr(tokens):
    token, tokens = getToken(tokens)
    if token == "T":
        return ["T",tokens]
    elif token == "F":
        return ["F",tokens]
    elif token == "not":
        exp1, rest1 = parseExpr(tokens)
        return [["not",exp1],rest1]
    elif token == "(":
        exp1, rest1     = parseExpr(tokens)
        operator, rest2 = parseOperator(rest1)
        exp2, rest3     = parseExpr(rest2)
        exp4,rest4      = parseClose(rest3)
        if exp4 == "error":
            return ["error_close",[]]
        return [[operator,exp1,exp2],rest4]
    else:
        ["error_end",[]]  

#Parse tokens
def parse(tokens):
    try: 
    
        expr, rest = parseExpr(tokens)

        if len(rest) > 0 or (expr == "error"):
            return "error"
        return expr
    except:
        return "Parsing error"

Wobei ich dafür noch eine Hilfsfunktion brauche, welche aus einer Liste mir das erste Element sowie die Restliste zurückgibt:

1
2
3
4
5
6
7
8

#Returns the first token and the rest list
def getToken(tokens):
    if len(tokens) > 0:
        token = tokens[0]
        del tokens[0]
        return [token,tokens]
    else:
        return ["error_end",[]]

Was passiert jetzt genau?

Wie schon gesagt, wird die Funktion “parse” mit der vom Scanner erzeugten Liste aufgerufen. Diese Funktion ruft dann die Funktion “parseExpr” auf, welche die eigentliche Arbeit übernimmt, und eine Token-Liste bzw. eine Restliste zurückgibt. Ist die Restliste nicht leer, oder ist die Expression ein Fehler, so wird ein “Parsing Error” ausgegeben. Hier würde man dann auch merken, wenn es eine falsche Zeichenkette in der Eingabe gab.

Was genau macht jetzt “parseExpr”?

Wenn man sich den Quellcode fix anschaut, dann erkennt man auf den ersten Blick zwei leichte Dinge: Falls das erste Token ein “T” oder “F” ist, so wird der boolsche Wert zurückgegeben. Damit hätten wir den Teil “Operand” der Grammatik abgedeckt. Die dritte Bedingung deckt den Fall “not S” ab, indem “parseExpr” rekursiv mit der Restliste (S) aufgerufen wird. Der Ergebnis wird dann in einer Unterliste zurückgegeben.

Kommen wir nun zum etwas interessanterem Teil:

1
2
3
4
5
6
7
8

elif token == "(":
    exp1, rest1     = parseExpr(tokens)
    operator, rest2 = parseOperator(rest1)
    exp2, rest3     = parseExpr(rest2)
    exp4,rest4      = parseClose(rest3)
    if exp4 == "error":
        return ["error_close",[]]
    return [[operator,exp1,exp2],rest4]

Damit möchten wir den dritten Fall der Grammatik abdecken, nämlich das erst eine öffnende Klammer, gefolgt von einem Operanden, einem Operator, dem rechten Operanden und einer schließenden Klammer in der Liste auftritt. Der Indikator ist die öffnende Klammer “(“.

Danach muss der linke Operand folgen, welcher selbst wieder ein Ausdruck sein kann. Das stellen wir mit “parseExpr” sicher. Den Operator stellen wir mit der zusätzlichen Funktion “parseOperator” fest, indem der Funktion die neue Restliste übergeben wird. Zurück bekommen wir einen Operator, sowie eine neue Restliste. Auf diesen muss dann wieder eine Expression und schließlich eine schließende Klammer folgen.

Schlägt eines der Parseschritte fehl, so kommt es zu einem Fehler. Ansonsten wird eine Liste mit einer Unterliste, sowie der Restliste zurück gegeben.

Damit wäre der schwierigste Schritt getan, und das ganze sieht dann so aus:

1
2

-> % ./logicparser.py "(T or (F and T))"
['or', 'T', ['and', 'F', 'T']]

Wie man sieht, nutze ich die polnische Notation zur Darstellung der Unterlisten. Das vereinfacht später die Evaluation, da der Operator vorne steht und der zweite Eintrag der linke bzw. der dritte Eintrag der rechte Operand ist.

Nachdem wir nun eine syntaktisch und semantisch korrekte Expression haben, müssen wir diese nur noch auswerten. Das erledigt die “logiceval” Funktion.

Der Evaluator

Zuletzt folgt der Evaluator, welcher den geparsten Ausdruck auswertet. Das geschieht mittels Rekursion:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

def logiceval(expr):
    try:
        token, tokens = getToken(expr)

        if token == "T":
            return True
        elif token == "F":
            return False
        elif token == "not":
            return not logiceval(getToken(tokens))
        elif token == "and":
            return logiceval(getToken(tokens)) and logiceval(getToken(getToken(tokens)))
        elif token == "or":
            return logiceval(getToken(tokens)) or logiceval(getToken(getToken(tokens)))
        elif token == "->":
            left = logiceval(getToken(tokens))
            if left:
                return False
            else:
                return True 
        elif token == "<->":
            left = logiceval(getToken(tokens))
            right = logiceval(getToken(getToken(tokens)))
            if (left and right) or (not left and not right):
                return True
            else:
                return False
        elif token == "xor":
            left = logiceval(getToken(tokens))
            right = logiceval(getToken(getToken(tokens)))
            if (left and not right) or (not left and right):
                return True
            else:
                return False
        else:
            return "error"
    except:
        return "Evaluation error"

Die Funktion schnappt sich aus der Tokenliste das erste Token und fängt dann an zu vergleichen. Wenn es ein Operand ist, dann muss nur noch der Wahrheitswert zurückgegeben werden.

Bei einer der möglichen Unterlisten muss zunächst geprüft werden, welcher Operator verwendet werden soll und entsprechend ein Schritt bzw. zwei Schritte von links der linke bzw. rechte Operand bestimmt werden. Dies passiert rekursiv, sodass bei den Operationen irgendwann nur noch die Wahrheitswerte links bzw. rechts stehen, welche dann miteinander verknüpft werden können. Bei der Implikation (->) reicht es das darauf folgende Token auszuwerten, denn es gibt bei der Implikation nur einen Fall, in der False zurückgegeben wird. Man kann nämlich nicht von etwas Wahrem auf etwas falsches schließen. Die anderen Operationen werden entsprechend berechnet.

Fazit

Wenn man eine bestimmte Grammatik gegeben hat, dann ist es ohne weiteres möglich ein Programm zu schreiben, welches die syntaktische Korrektheit einer Eingabe überprüft. Ich hoffe, ich konnte euch das Prinzip vom Scanner/Parser ein wenig näher bringen.

Gruß

gehaxelt