Parser und Übersetzer

Modul Parser

 aufwärts

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 Element natürliche Zahlen0 }.

 

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

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 15.08.2012   Updated: 10.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik