Parser und Übersetzer

Modul Parser

Das Modul Parser enthält die grund­legenden 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 grund­legenden Funktionen zur Abarbeitung des Eingabe­wortes definiert.

 

# Grundlegende Funktionen eines Parsers bzw. Compilers

# Uebernimmt ein Eingabewort x und ruft das Startsymbol
# der Grammatik auf; erzeugt ggf. Fehlermeldung und bestimmt
# die Position des Fehlers im Eingabewort
def compile(x, startSymbol):
    global inputstring, originalinput, errormessage, errorposition
    inputstring=x
    originalinput=x
    errormessage="ok"
    r=None
    try:
        r=startSymbol()
        if not inputEmpty():
            raise Exception("Zuviele Zeichen: "+inputstring)
    except Exception as e:
        errormessage=str(e)
    errorposition=len(x)-len(inputstring)
    return r

# Entspricht compile ohne Rueckgabewert
def parse(x, startSymbol):
    compile(x, startSymbol)

# Liefert True, wenn das Eingabewort mit String x beginnt
def comes(x):
    global inputstring
    return inputstring.startswith(x)

# Liefert die ersten k Zeichen des Eingabewortes
def lookahead(k=1):
    global inputstring
    return inputstring[:k]

# Entfernt die ersten k Zeichen des Eingabewortes
def consume(k=1):
    global inputstring
    inputstring=inputstring[k:]

# Gibt die ersten k Zeichen des Eingabewortes zurueck
# und entfernt diese vom Anfang des Eingabewortes
def getSymbol(k=1):
    x=lookahead(k)
    consume(k)
    return x

# True, wenn das Eingabewort leer ist
def inputEmpty():
    global inputstring
    return inputstring==""

# Liefert True, wenn das Eingabewort mit irgendeinem
# Zeichen aus der Menge der Zeichen des Strings x beginnt
def comesAnyOf(x):
    return not inputEmpty() and lookahead() in x

# Wenn das Eingabewort mit String x beginnt, wird
# der String x am Anfang des Eingabewortes entfernt.
# Anderenfalls wird eine Exception ausgeloest.
def match(x):
    if comes(x):
        consume(len(x))
    else:
        raise Exception("Erwartet: "+x)

# Bei kurzen Eingabewoertern Position des Fehlers anzeigen
def showErrorPosition():
    global originalinput, errormessage, errorposition
    s=originalinput+"\n"
    s+=errorposition*"-"
    s+="^\n"
    s+=errormessage
    print s

Die Funktion compile erhält die Funktion startSymbol als Parameter. Diese Funktion ist im Modul Parser nicht implementiert, sie wird in einem eigenen Modul, das den konkreten Recursive-Descent-Parser enthält, implementiert.

Anwendung

Die Grammatik mit den Produktionen

Sgeht über nachaSb  |  ε

erzeugt die Sprache

L  =  { anbn  |  n ∈ ℕ0 }.

 

Ein Parser für diese Sprache L wird wie folgt implementiert. Das Modul AsbParser importiert zunächst das Modul Parser. Dann wird die Funktion s entsprechend der Produktion für die Variable S der Grammatik implementiert.

from Parser import *

def s():
    if comes("a"):   # Produktion S -> aSb anwenden
        match("a")
        s()
        match("b")
    else:            # Produktion S -> epsilon anwenden
        pass         # tue nichts

 

Im Haupt­programm wird der Parser dann folgender­maßen getestet, hierbei wird der Funktion parse das Eingabewort und der Name der Funktion, die dem Startsymbol der Grammatik entspricht, übergeben.

from AsbParser import *

parse("aabb", s)
showErrorPosition()

Im Fehlerfall, etwa bei Eingabe des Wortes aaba, wird die Fehler­position mit showErrorPosition ausgegeben:

aaba
---^
Erwartet: b

 

[up]

 

H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Created: 15.08.2012   Updated: 17.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden