Automatisierte Programmanalyse

Ein Analyseprogramm für Ungeduldige

Zur Lösung des Halteproblems soll eine Python-Funktion istHaltend entwickelt werden, mit derenn Hilfe man Endlosschleifen bei beliebigen Python-Programmen feststellen kann.

Black Box

Wenn eine geeignete Funktionsdefinition für die Funktion istHaltend entwickelt ist, dann kann man mit dieser Funktion künftig Endlosschleifen verhindern.

While-Analyse

Wann treten Endlosschleifen auf? Sicher nicht, wenn das Programm keine Wiederholungsanweisungen und keine Rekursion enthält. Kritisch kann es demnach nur werden, wenn bestimmte Programmkonstrukte im Programm vorkommen.

Wir untersuchen im Folgenden, ob ein Python-Programm eine while-Anweisung enthält. Python-Programme sollen dabei immer in Form von Funktionsdefinitionen gegeben sein.

Black Box

Beispiel:

Black Box

Eine Vereinfachung

Zur Vereinfachung der Programmanalyse betrachten wir nur solche Programme, die sich ganz einfach in ihre Bestandteile (man sagt hier auch Token) zerlegen lassen. Mit Hilfe von Leerzeichen (und Zeilenumbrüchen) sollen hier alle Programmeinheiten jeweils getrennt werden. Man kann auf diese Vereinfachung verzichten, muss dann aber viel mehr Analysearbeit leisten (vgl. Fachkonzept - Scanner).

Statt der kompakteren Darstellung

def primzahl(n):
    if n == 1:
        prim = False
    else:
        prim = True
        i = 2
        while i < n:
            if n % i == 0:
                prim = False
    return prim

benutzen wir also die etwas strukturiertere Darstellung:

def primzahl ( n ) :
    if n == 1 :
        prim = False
    else:
        prim = True
        i = 2
        while i < n :
            if n % i == 0 :
                prim = False
    return prim

Der folgende Python-Dialog zeigt, welchen Vorteil das hier hat.

>>> quelltext1 = """
def primzahl(n):
    if n == 1:
        prim = False
    else:
        prim = True
        i = 2
        while i < n:
            if n % i == 0:
                prim = False
    return prim
"""

>>> quelltext1.split()
['def', 'primzahl(n):', 'if', 'n', '==', '1:', 'prim', '=', 'False', 
'else:', 'prim', '=', 'True', 'i', '=', '2', 'while', 'i', '<', 'n:', 'if', 'n', '%', 'i', 
'==', '0:', 'prim', '=', 'False', 'return', 'prim']
>>>
>>> quelltext2 = """
def primzahl ( n ) :
    if n == 1 :
        prim = False
    else :
        prim = True
        i = 2
        while i < n :
            if n % i == 0 :
                prim = False
    return prim
"""

>>> quelltext2.split()
['def', 'primzahl', '(', 'n', ')', ':', 'if', 'n', '==', '1', ':', 'prim', 
'=', 'False', 'else', ':', 'prim', '=', 'True', 'i', '=', '2', 'while', 'i', '<', 'n', ':', 'if', 
'n', '%', 'i', '==', '0', ':', 'prim', '=', 'False', 'return', 'prim']

Mit der split-Funktion kann man die Bestandteile des vorgegebenen Quelltextes direkt auflisten.

Beachte, dass es aber auch Fälle gibt, bei denen die beschriebene Vorgehensweise nicht zum gewünschten Ergebnis führt. Wir ignorieren diese Fälle hier.

>>> quelltext3 = """
def test ( ) :
    s = ' while '
    return s
"""

>>> quelltext3.split()
['def', 'test', '(', ')', ':', 's', '=', "'", 'while', "'", 'return', 's']
>>> 

Ein Analyseprogramm

Mit dieser Vorbereitung kann die Analyse mit dem folgenden Programm erfolgen:

def enthaeltWhile ( quelltext ) :   
    tokenliste = quelltext . split ( )
    gefunden = False
    for token in tokenliste :
        if token == 'while' :
            gefunden = True 
    return gefunden

# Test

quelltextPrimzahl = """
def primzahl(n):
    if n == 1:
        prim = False
    else:
        prim = True
        i = 2
        while i < n:
            if n % i == 0:
                prim = False
    return prim
"""

print(enthaeltWhile(quelltextPrimzahl))

Aufgabe 1

(a) Teste die Funktion enthaeltWhile mit verschiedenen Python-Quelltexten und kontrolliere die Ergebnisse.

(b) Die Funktion enthaeltWhile kann auch ihren eigenen Quelltext analysieren. Probiere das aus.

def enthaeltWhile ( quelltext ) :   
    tokenliste = quelltext . split ( )
    gefunden = False
    for token in tokenliste :
        if token == 'while' :
            gefunden = True 
    return gefunden

# Test

quelltextEnthaeltWhile = """
def enthaeltWhile ( quelltext ) :   
    tokenliste = quelltext . split ( )
    gefunden = False
    for token in tokenliste :
        if token == 'while' :
            gefunden = True 
    return gefunden
"""

print(enthaeltWhile(quelltextEnthaeltWhile))

Aufgabe 2

Versuche, eine Funktion enthaeltRekursion zu entwickeln, die überprüft, ob der Funktionsname in der weiteren Funktionsdefinition noch einmal vorkommt.

Beachte: Mit diesem Test werden nur direkte rekursive Aufrufe einer Funktion erfasst. Denkbar sind auch rekursive Aufrufe über weitere zwischengeschaltete Funktionen. Dieser Fall soll hier aber nicht weiter verfolgt werden.

Aufgabe 3

Beurteile den eingeschlagenen Weg, die Existenz von Endlosschleifen über Eigenschaften des Quelltextes herauszufinden. Wie vielversprechend ist dieser Weg?

Für deine Argumentation kannst du die folgenden Beispielprogramme verwenden: Programm 1 hält bei jeder Eingabe, bei Programm 2 weiß man nicht, ob es für jede Eingabe hält und Programm 3 hält nicht, wenn die Eingabe n größer als 3 ist.

Die Programme (in Form von Funktionsdefinitionen) benutzen alle die Hilfsfunktion primzahl.

def primzahl(n):
    if n == 1:
        prim = False
    else:
        prim = True
        i = 2
        while i <= n-1:
            if n % i == 0:
                prim = False
            i = i+1
    return prim

Programm 1: nächste Primzahl

def naechstePrimzahl(n):
    gefunden = False
    while not gefunden:
        if primzahl(n):
            gefunden = True
        else:
            n = n+1
    return n

Programm 2: nächstes Primzahlzwillingspaar

def naechstesPrimzahlzwillingspaar(n):
    gefunden = False
    while not gefunden:
        if primzahl(n) and primzahl(n+2):
            gefunden = True
        else:
            n = n+1
    return (n, n+2)

Programm 3: nächste nicht zu einer 6er Zahl benachbarte Primzahl

def naechsteNichtZu6erZahlBenachbartePrimzahl(n):
    gefunden = False
    while not gefunden:
        if primzahl(n) and ((n+1)%6 > 0) and ((n-1)%6 > 0):
            gefunden = True
        else:
            n = n+1
    return n
X

Fehler melden

X

Suche