Automatisierte Programmanalyse
Ein Analyseprogramm für Ungeduldige
Zur Lösung des Halteproblems soll eine Python-Funktion istHaltend
entwickelt werden,
mit deren Hilfe man Endlosschleifen bei beliebigen Python-Programmen feststellen kann.
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.
Beispiel:
Ein erstes Analyseprogramm
Hier ein erster Versuch zur Realisierung der Funktion enthaeltWhile
.
def enthaeltWhile(quelltext):
if 'while' in quelltext:
gefunden = True
else:
gefunden = False
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) Welches Problem ergibt sich hier? Wie könnte man das Problem lösen?
def enthaeltWhile(quelltext) :
if 'while' in quelltext:
gefunden = True
else:
gefunden = False
return gefunden
# Test
quelltextTest = """
def test( ):
print('while')
"""
print(enthaeltWhile(quelltextTest))
Ein verbessertes Analyseprogramm
Hier ein Vorschlag für ein verbessertes Analyseprogramm:
def enthaeltWhile(quelltext):
gefunden = False
while len(quelltext) > 0:
pos = quelltext.find("'")
quelltextVorHochkomma = quelltext[:pos]
quelltext = quelltext[pos:]
if 'while' in quelltextVorHochkomma:
gefunden = True
quelltext = quelltext[1:]
pos = quelltext.find("'")
quelltext = quelltext[(pos+1):]
return gefunden
# Test
quelltextTest = """
def test( ):
print('while')
"""
print(enthaeltWhile(quelltextTest))
Aufgabe 2
(a) Welche Logik nutzt diese Funktionsdefinition? Teste die Funktion mit verschiedenen Beispielquelltexten.
(b) Teste auch den Fall, dass die Funktion enthaeltWhile
den eigenen Quelltext analysiert.
def enthaeltWhile(quelltext):
gefunden = False
while len(quelltext) > 0:
pos = quelltext.find("'")
quelltextVorHochkomma = quelltext[:pos]
quelltext = quelltext[pos:]
if 'while' in quelltextVorHochkomma:
gefunden = True
quelltext = quelltext[1:]
pos = quelltext.find("'")
quelltext = quelltext[(pos+1):]
return gefunden
# Test
quelltextEnthaeltWhile = """
def enthaeltWhile(quelltext):
gefunden = False
while len(quelltext) > 0:
pos = quelltext.find("'")
quelltextVorHochkomma = quelltext[:pos]
quelltext = quelltext[pos:]
if 'while' in quelltextVorHochkomma:
gefunden = True
quelltext = quelltext[1:]
pos = quelltext.find("'")
quelltext = quelltext[(pos+1):]
return gefunden
"""
print(enthaeltWhile(quelltextEnthaeltWhile))
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