Systematische Programmentwicklung
Modul Parser
Das Modul Parser enthält die grundlegenden Funktionen für einen Recursive-Descent-Parser.
Modul Parser
Im Modul Parser sind die globalen Variablen inputstring, originalinput, errormessage und errorposition sowie eine minimale Menge von grundlegenden Funktionen zur Abarbeitung des Eingabewortes definiert.
# uebernimmt einen Eingabestring x und ruft das Startsymbol der
# Grammatik auf; erzeugt ggf. Fehlermeldung und bestimmt
# die Position des Fehlers im Eingabestring
def parse(x, startSymbol):
global inputstring, originalinput, errormessage, errorposition
inputstring=originalinput=x
errormessage="ok"
try:
startSymbol() # arbeitet Eingabestring ab
if inputstring!="":
raise Exception("Zu viele Zeichen: "+inputstring)
except Exception as e:
errormessage=str(e)
errorposition=len(originalinput)-len(inputstring)
# wenn das Eingabewort mit String x beginnt,
# dann wird der String x vom Anfang des Eingabewortes
# entfernt. Anderenfalls wird eine Exception ausgeloest
def match(x):
if comes(x):
# entsprechend viele Zeichen vom Eingabewort abarbeiten
consume(len(x))
else:
raise Exception("Erwartet: "+x)
# liefert true, wenn das Eingabewort mit x anfaengt
def comes(x):
return inputstring.startswith(x)
# entfernt die ersten k Zeichen vom Eingabewort
def consume(k=1):
global inputstring
inputstring=inputstring[k:]
def showErrorPosition():
s=originalinput+"\n"
s+=errorposition*"-"
s+="^\n" # Zeiger nach oben: Position des Fehlers zeigen
s+=errormessage
print(s)
Die Funktion parse erhält die Funktion startSymbol als Parameter. Diese Funktion implementieren Sie in einem eigenen Modul, das den konkreten Recursive-Descent-Parser enthält.
Anwendung
Die Grammatik mit den Produktionen
S
aSb | ε
erzeugt die Sprache
L = { anbn | n ∈ ℕ0 }.
Einen Parser für diese Sprache L implementieren Sie wie folgt in einem Modul AsbParser. Dort importieren Sie zunächst das Modul Parser. Dann implementieren Sie die Funktion s entsprechend der Produktion für die Variable S der Grammatik.
def s():
if comes("a"): # Produktion S -> aSb anwenden
match("a")
s()
match("b")
else: # Produktion S -> epsilon anwenden
pass # tue nichts
Im Hauptprogramm testen Sie den Parser dann folgendermaßen. Hierbei übergeben Sie der Funktion parse das Eingabewort und den Namen der Funktion, die dem Startsymbol der Grammatik entspricht.
parse("aabb", s)
showErrorPosition()
Im Fehlerfall, etwa bei Eingabe des Wortes aaba, wird die Fehlerposition mit showErrorPosition ausgegeben:
---^
Erwartet: b
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 23.11.2025 Updated: 24.11.2025
Diese Webseiten sind größtenteils während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden